/image%2F0571076%2F201306%2Fob_2f888877baf0962fa4d29e980b5a5bd2_4.png)
Programmation du jeu d'abalone
Avertissement : l'article ci-dessous a été, à quelques modifications près, éhontément copié sur un site que je ne nommerai pas, puisque ledit site ne dit mot sur MiGs, et a toujours refusé de donner le lien vers MiGs.
Programmation du jeu d’Abalone
Créer un programme qui joue à Abalone présente un certain nombre de difficultés :
- il n’existe quasiment aucune information théorique sur le jeu ;
- les joueurs forts sont rares ;
- le nombre de coups possibles, dans une position donnée, peut atteindre 148, c’est supérieur au nombre de coups possibles aux échecs. Sans atteindre la complexité combinatoire du jeu de go ou du jeu d’échecs, le nombre de coups possibles est suffisamment élevé pour mettre à mal les algorithmes de force brute habituels.
- le fait que le but du jeu soit progressif (éjection boule après boule) rend difficile la définition d’une fonction d’évaluation continue dans la mise en œuvre de l’algorithme alpha-beta, les programmes pouvant hésiter entre l’éjection d’une bille et un avantage positionnel, ou avoir tendance, comme les débutants, à éjecter des boules le plus tôt possible dans la partie.
-
Concepts mis en oeuvre par les programmes :
Les premiers programmes jouant à Abalone utilisaient essentiellement dans leur évaluation des positions les concepts suivants :
- connectivité (cohésion des groupes de billes) ;
- nombre de billes de chaque joueur ;
- une valeur théorique de la position des billes (les bords sont désavantageux, le centre est crucial).
Les programmes les plus récents qui jouent à Abalone mettent en œuvre un ou plusieurs des concepts suivants dans l’évaluation d’une position :
- nombre de sumitos possible, et type de sumitos comme leur influence sur le centre ou pas, la poussée vers le bord (l’idée nouvelle de MLA dans ce domaine) ;
- nombre de menaces d’éjections de billes ;
- évaluation géométrique de la position (l’idée nouvelle d’Aba-Pro dans ce domaine, l’utilisation du centre de masse respectif des groupes de billes de chaque joueur) ;
- la phase du jeu en cours et le type de position (ouverture, milieu de jeu, fin de partie, position type standard, gros avantage positionnel pour l’un des camps, etc.) ;
- nombre de groupes de billes, nombre de billes par groupe (utilisé, notamment, par Nacre).
-
- My Lovely Abalone (MLA), conçu par David Malek (France) : son développement a débuté fin 2003, MLA n’est parvenu à battre Aba-Pro que fin 2005. MLA, au début de son développement intégrait une évaluation de la position très similaire à Aba-Pro. MLA a battu Aba-Pro en réfutant l’évaluation de dangerosité de la position de Aba-Pro, en intégrant le dynamisme d’une position au travers de l’utilisation du nombre de sumitos comme critère complémentaire. La disponibilité d’Aba-Pro pour tester MLA a été cruciale, les programmeurs de MLA ont pu ainsi utiliser certaines des faiblesses d’Aba-Pro pour le vaincre.
- Aba-Pro, conçu par Tino Werner (Autriche) : sans conteste la première avancée significative dans le domaine. Redoutable programme, meilleur du monde de 2002 à 2005. Aba-Pro est remarquable par sa maîtrise de la combinatoire (le programme choisit ou non d’explorer les coups suivants en fonction d’une évaluation de la dangerosité de la position) et sa fonction d’évaluation (par utilisation d’une combinaison des centres de masse des groupes de billes des adversaires). Aba-Pro intègre également la prise en compte des phases de jeu (ouverture, milieu de jeu, fin de partie). Aba-Pro repose sur la maîtrise de la théorie des graphes, et d’heuristiques spécifiques au jeu d’Abalone. Aba-Pro était le sujet de thèse de ses auteurs à l’Institut de génie logiciel de l’Université Technologique de Graz (Autriche).
- Nacre, conçu par Peer Sommerlund (Danemark) : un programme fort, opposant malheureux d’Aba-Pro en 2003. Nacre utilisait, en 2003, un réseau de neurones, domaine de connaissance où Nacre a au moins égalé l’état de l’art.
Ce classement est établi selon la blitz ladder list officielle des programmeurs d’Abalone publiée sur le groupe Yahoo de programmation du jeu d’Abalone (la ladder list consiste à estimer la valeur de moteurs en leur donnant une seconde par coup).
Aba-Pro et Nacre se sont, de plus, rencontrés plusieurs fois et Aba-Pro a triomphé. MLA a été reconnu meilleur par l’auteur d’Aba-Pro qui disposait d’une copie de MLA pour valider la défaite d’Aba-Pro.
Le code source de ces trois programmes n’est pas libre et n’est pas distribué. Seul Aba-Pro est disponible en téléchargement.
En 2011 est apparu un sérieux concurrent à ces trois programmes : ULA (Uncle Lolo's Abalone), conçu par Laurent Pagli (France). Toutefois, aucune rencontre officielle n'a eu lieu entre ce challenger et ses trois rivaux.
Il existe d’autres programmes d’Abalone, qui ne résistent pas aux trois anciens cités plus haut, notamment :
- Abbalone 3D, Macintosh
- Jens Thiele Abalone, interface de jeu par courrier électronique
- Olivier Thill : Abalot
- Peter Tax Abalone, Macintosh
- Random Software : Abalone 1.2
Les codes sources de Abalot et Peter Tax Abalone sont disponibles sur Internet.
Les meilleurs joueurs d’Abalone parviennent à triompher de l’ensemble de ces programmes, les trois meilleurs cités plus haut compris.
Depuis l’apparition d’Aba-Pro, la connaissance du jeu a progressé. Plusieurs catégories de positions ont été isolées notamment la position de witch ring (cas où les billes d’un des deux adversaires se trouvent entourées par les billes adverses).
Nacre participe activement depuis 2005, à l’analyse des positions de fin de partie, notamment la constitution de prisons (cas où une bille se trouve isolée au bord du tablier de jeu, sans possibilité de reconnexion rapide avec ses camarades de la même couleur) ou encore à la comparaison entre l’avantage matériel (le nombre de billes de supériorité) et la position.
MLA a mis en évidence une pratique des plus forts joueurs : l’avantage positionnel est parfois aussi important que l’avantage matériel. MLA peut ainsi abandonner une ou plusieurs billes en début de partie pour obtenir un avantage positionnel déterminant.
En combinant Nacre, MLA et l’expérience de l’un des plus forts joueurs, les travaux menés en 2006 sur ces sujets ont isolé des positions où l’avantage positionnel ne parvient pas à compenser un trop gros déficit matériel (le nombre de billes est insuffisant pour parvenir à gagner). Ci-dessous, un exemple de position de witch ring où l’avantage positionnel ne permet pas de compenser le désavantage numérique.
Globalement, les programmes contribuent à améliorer sensiblement le niveau de jeu, en proposant un adversaire toujours disponible et capable de battre un joueur fort. Leur capacité de calcul tactique (prévision des coups à l’avance) entraînent également les joueurs aux aspects combinatoires du jeu.
/idata%2F4529924%2FProblemes%2Ftout-et-nimp%2Fpic589809_md.jpg)
/idata%2F4529924%2FAbalone-plongee_big.png)
/idata%2F4529924%2Fscouts3.jpg)
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)
