Logique vs. Imagination


Albert Einstein en 1929

“La logique vous mènera d’un point A à un point B. L’imagination vous emmènera où vous voulez.”

Attribué abusivement à Albert Einstein (1879-1955)

Retrouvez toutes les citations dans le Dictionnaire de citations.

°°°°°°


A1B2 en notation Aba-Pro (A1D4 en notation Nacre)

Aller d’un point A à un point B n’est pas une mauvaise manière de commencer une partie d’abalone (^_-)—☆

FightClub

Publicités

Les systèmes de notation

Cet article est une réédition d’une page publiée sur ce blog le 3 mai 2013, et antérieurement sur OverBlog par Gramgroum.

FightClub


AVANT-PROPOS : Qu’est-ce qu’un système de notation ?

Un système de notation est un ensemble de conventions (convention = chose dont on convient arbitrairement, sur laquelle on se met d’accord) qui permet de décrire, à l’aide de signes (généralement alphanumériques) les mouvements qu’effectuent les pièces d’un jeu abstrait sur le tablier de jeu.

Ce type de notation est appelé « notation algébrique ». D’un point de vue pratique, c’est un véritable langage international qui permet par exemple d’échanger facilement de nombreuses parties avec un simple fichier texte. Et bien avant l’ère des nouvelles technologies de communication, les systèmes de notation  permettaient de diffuser des parties ou de jouer à distance, par simple courrier postal  (ainsi au jeu d’échecs, où la notation existe depuis le milieu du XVIIIème siècle).

Pour dire les choses plus simplement, un système de notation est un code fait de chiffres et de lettres qui permet de décrire les coups joués.

Tout le monde a déjà joué à la bataille navale, qui est fondée sur un système de notation orthogonale (lignes se coupant en angle droit) : chaque coup joué est décrit à l’aide de deux coordonnées (une lettre et un chiffre) qui indiquent la position d’une case. C’est un système de notation très simple, dans la mesure où il n’y a pas de mouvement effectué : chaque coup joué porte le nom d’une case (par exemple : A7, C4, D8 etc.).

La notation se complique un peu quand il s’agit de décrire un déplacement. Aux échecs par exemple, la notation reste relativement simple : pour chaque coup, on indique la case de départ et la case d’arrivée d’une pièce ; aucune ambiguïté n’est possible. Ainsi, un coup noté e2-e4 signifie que la pièce qui se trouvait sur la case e2 a été déplacée sur la case e4 (Je parle de la notation des échecs complète, je n’entre pas dans les détails de la notation simplifiée, ce n’est pas l’objet ici.).

Cela se complique encore quand il s’agit de décrire les déplacements au jeu d’abalone, pour plusieurs raisons :

– les cases sont traversées par trois axes, on n’a donc pas d’orthogonalité (ce qui est déroutant, mais n’est pas gênant en soi ; nous verrons plus loin que les systèmes de notation ont en fait « réintégré » l’orthogonalité),

– le joueur peut déplacer une, deux ou trois pièces de même couleur en un même coup,

– le joueur peut pousser une ou deux billes adverses (ce n’est  pas indifférent, nous le verrons lorsque nous aborderons la question de la réversibilité).

LA NOTATION DU JEU D’ABALONE

Très tôt dans l’histoire d’abalone, différents systèmes de notations ont été mis en oeuvre. Certains ont disparu, en raison de leurs défauts (ambiguïté, lourdeur…). D’autres ont subsisté et cohabitent aujourd’hui. Parmi ceux-ci, deux systèmes assez proches l’un de l’autre se sont imposés et sont généralement utilisés : les systèmes Aba-Pro et Nacre (Aba-Pro et Nacre furent longtemps les deux plus fortes intelligences artificielles d’abalone ; voir l’article Des intelligences artificielles : les programmes existants). Notons que MiGs et MLA n’ont pas de système de notation qui leur soit propre, et laissent le choix entre ces deux systèmes.

Avant d’en venir à ces deux systèmes, disons quelques mots sur les autres tentatives, où Aba-Pro et Nacre plongent parfois leurs racines.

1) Les tentatives de Marc Ghigou

En 1989, la défunte Fédération Française d’Abalone proposait un système de notation dû à Marc Ghigou, fondé sur la notation du plateau suivante :

notation0

Il s’agit d’un article paru dans le magazine Jeux & Stratégies du mois de novembre 1989, qui explique ce système. Celui-ci était si compliqué et source de tant d’ambiguïtés qu’il n’a jamais été vraiment utilisé.

Dès le mois de mai 1990, la Fédération a adopté un nouveau système de notation, qui se présentait ainsi :

notation90

Il s’agit d’un article paru dans Jeux & Stratégies du mois de mai 1990, qui vous explique ce système (c’était, je crois, l’avant-dernier numéro de ce magazine avant sa disparition).

Plus pratique que le précédent, ce système présente néanmoins des inconvénients, notamment en ce qui concerne la notation des cases : si les lignes horizontales sont désignées par une lettre, les lignes transversales en revanche ne sont pas nommées, et chaque case se voit attribuer un chiffre dépendant de sa position sur la ligne horizontale ; de sorte que deux cases traversées par la même ligne transversale ne sont pas nécessairement désignées par le même chiffre (ainsi E2 et F1 sont sur la même ligne transversale). Remarquez  la conclusion un peu prophétique de l’article.

2) Les travaux de Michael Frank

A peu près à la même époque, c’est-à-dire au début des années 1990, de l’autre côté de l’Atlantique, on réfléchissait à la programmation d’abalone et par la même occasion aux systèmes de notation. Vous trouverez ici des échanges entre Michael Frank, du MIT (Massachusetts Institute of Technology), et d’autres chercheurs sur ce sujet.

Michael Frank s’est aperçu qu’il pouvait placer les cases du plateau d’abalone dans un système orthogonal, chaque case étant ainsi désignée selon l’abscisse (axe des x) et l’ordonnée (axe des y). Il n’est pas du tout nécessaire de faire intervenir le troisième axe qui traverse chaque case. Le schéma suivant, de Michael Frank, nous montre comment l’hexagone s’inscrit dans un carré :notation2

Plus joliment, cela nous donne :

plateau

Voilà qui était très arrangeant, au moins autant pour la construction de programmes informatiques que pour la notation elle-même. Il ne restait plus ensuite qu’à remplacer les chiffres en ordonnée par des lettres, pour éviter toute confusion. De fait, Michael Frank jetait là les bases des principaux systèmes de notations d’abalone existant encore aujourd’hui.

En ce qui concerne la notation des déplacements, je vous laisse suivre vous-mêmes les tâtonnements de Michael Frank (ici). Sachez qu’il n’est pas parvenu à une notation vraiment aboutie. Je relève au passage l’idée de départ assez intuitive de désigner les directions à l’aide des points cardinaux, idée qui sera toutefois abandonnée.

3) Autres systèmes de notation

D’autres systèmes ont existé (ou existent encore de manière marginale). J’en citerai deux qui n’utilisent pas de coordonnées pour nommer les cases, mais un simple système de numérotation.

– le système LMU (Loyola Marymount University – Los Angeles, 1994) qui numérote les cases de 0 à 60. J’ignore comment sont notés les déplacements dans ce système.

abalone

– le système OKUN, que vous pouvez découvrir en cliquant sur l’image ci-dessous, qui numérote les cases de 1 à 61.

notation3

(à suivre : les notations Nacre et Aba-Pro)

Gramgroum

Programmation du jeu d’Abalone

(Mise à jour du 13 septembre 2014)

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.


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).

Programmes qui jouent à Abalone :

Les trois meilleurs programmes d’Abalone étaient en 2006 : MLA, Aba-Pro et Nacre. Ces trois programmes sont issus des travaux de recherche fondamentale dans le domaine de la théorie des jeux effectués par leurs auteurs.
• 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. Au début de son développement MLA 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 d’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.

Programmes et connaissance du jeu :

Lorsqu’on débute à Abalone émerge rapidement la certitude que le centre du tablier est primordial. Il en est de même pour la connectivité des billes (elles doivent être regroupées et présenter une forte cohésion). Contrairement aux jeux les plus anciens comme le jeu d’échecs, les programmes d’Abalone ont été créés avant que le jeu ne soit véritablement analysé de manière approfondie.

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).

°

Abalone_witch_ring

witch ring, par François Haffner

°

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îne également les joueurs aux aspects combinatoires du jeu.

Gramgroum