Présentation

Depuis début mai 2006 j'ai programmé le "moteur" de Dariush 3D. Celui-ci a obtenu quelques résultats intéressants au jeu d'atari-go :

Règle : La règle est très simple. Les coups se jouent comme au go sur des gobans de taille variable. Le 1er qui prend au moins un pion a gagné.

Evaluation :

Pour évaluer la vitesse de mon algorithme, je mesure 2 grandeurs :

Le temps qui dépend de l 'algorithme mais aussi de la vitesse du micro-processeur.

Le nombre d 'appel de ma procédure "coupjoue". Cela correspond au nombre de coups que l'algorithme a du jouer pour résoudre le problème. Ce nombre est indépendant de la vitesse du micro-processeur. Nous l'appellerons XCOUPS.

Résultats :

-Mon algorithme résout atari-go sur un goban 6*6 avec comme figure de départ un cross-cut. Il résout ce problème en 0,141 seconde avec XCOUPS =52806. (problème résolu pour la première fois par M Tristan Cazenave Professeur université Paris 8 en 2002)

- Mon algorithme résout atari-go sur un goban 6*6 vide. C'est à dire qu'il trouve 2 coups gagnants pour noir en début de partie. Il trouve le premier coup gagnant 1 heure 12 minutes avec XCOUPS = 1331351943.

- Mon algorithme résout atari-go sur un goban 7*7 en démarrant la partie avec un cross-cut. Je distingue 2 sortes de cross-cut en 7*7 le haut et le bas (voir logiciel). Le cross-cut haut est résolu en 0,109 secondes pour XCOUPS =28635. Le cross-cut bas est résolu en 0,297 secondes pour XCOUPS = 80938.

A ma connaissance, mon algorithme est le premier à résoudre ce problème pour un goban 6*6 vide et pour un goban 7*7 avec un cross-cut (en mai 2006). Sauf erreur de ma part :)

Télecharger Résultats Fichier PDF 8Ko

Présentation de mon algorithme :

L'algorithme que j'utilise est un alpha-bêta classique qui recherche uniquement les (ou la) solution gagnante si elle existe. Nous l'appellerons "l'alpha-bêta principal". Pour simplifier, La couleur pour laquelle nous chercherons une solution gagnante sera appelée couleurordi et l'autre couleurjoueur. L'algorithme doit répondre à la question suivante : "existe t-il un coup gagnant pour couleur ordi et si oui lequel ?"

Les optimisations que j'utilise sont dans l'ordre suivant :

1) utilisation d'une table de transposition. Je m'en sers uniquement pour ne pas ré étudier les plateaux déjà étudiés précédemment.

2) Ensuite je trie les coups possibles. Je privilégie les mises à un degré de liberté des chaînes adverses, puis les mises à 2 degrés, puis à 3 etc etc. Ensuite pour chaque sorte de coups (mise à 1, mise à 2 etc), je trie à nouveau pour que ces coups soient le plus proche possible d'une chaîne de la même couleur. L'idée est que globalement pour prendre un pion adverse, il faudra diminuer les degrés de liberté de l'adversaire tout en jouant des coups suffisamment fort pour ne pas se faire prendre sois-même.

3) J'utilise ensuite un autre algorithme alpha-bêta. Nous l'appellerons "l'alpha-bêta secondaire". Son rôle est de déterminer si on peut prendre un pion adverse en x coups. Il est beaucoup plus rapide que le précédent car on est pas obligé d 'étudier tous les coups d'attaque. Si par exemple on le lance pour x=3 cela impose de n'étudier que les mises à 1 degré des chaînes adverses. En effet une mise à 1 degré au 1er noeud de cet alpha-bêta entraîne au mieux une prise au 3ème noeud. Si je le lance pour x=5, on ne doit étudier que les coups de mise à 1 degré et de mise à 2 degré etc etc. Par contre pour qu'il y ait une certitude sur le résultat d'une prise, on étudie tous les coups possibles de défense. Cet alpha-bêta secondaire est la cause principale de la vitesse de mon algorithme. Je le lance donc pour chaque coup sélectionné au point numéro 2. En cas de réponse positive, j'obtiens un élagage.
C e nombre x varie en fonction de la profondeur de l alpha-bêta principal.
P lus je le lance a une profondeur grande dans l alpha-bêta principal, plus je
diminue x. J'ai du faire une multitude de tests pour optimiser le rapport (temps gagné grâce à cet alpha-bêta dans l'algorithme principal / durée de cet alpha-bêta secondaire). Il est évident qu'une valeur de x trop grande à une profondeur très grande va prendre énormément de temps. Et bien que le nombre d'élagages de l'alpha-bêta principal soit plus grand, le temps global d'étude augmente considérablement.

4)A ce niveau on entre dans l'étude des coups. Je les étudie dans l'ordre obtenu au 2) mais je fais un petit test avant. Je regarde l'impact de chaque coups au cas ou l'adversaire ne répondrait pas. Pour cela j'utilise à nouveau mon alpha-bêta secondaire. J' ai alors la réponse à la question suivante : "est ce que ce coup prendrait un pion adverse en x coups si il pouvait jouer 2 fois ?". Si la réponse est oui, j'étudie ce coup dans l'algorithme principal et je passe au noeud suivant. Si c'est non, je met de côté ce coup et je l'étudierai si besoin après ceux dont la réponse est oui. Cette partie permet elle aussi de gagner énormément de vitesse.

5)Dans l'algorithme principal, je met en mémoire les coups qui ont donné un élagage. Si à une profondeur n l'algorithme n'obtient pas d'élagage, il regarde le coup mémorisé adverse qui a donné un élagage à la profondeur n+1. Si ce coup n' a pas encore été étudié à la profondeur n, et bien je change le tri du 2) pour l'étudier en priorité. Ce tri est donc modifié en permanence. Je pars du principe qu'un bon coup "de réponse" pour l'adversaire a des fortes chances d 'être aussi un bon coup "d'attaque" pour la couleur étudiée (ce qui n'est malheureusement pas toujours vrai...).

6)On peut aussi appliquer la méthode 5 a la profondeur elle même. C'est à dire qu'un coup qui a déjà donné un élagage à une certaine profondeur a des chances d'en donner à nouveau. L'expérience m'a montré que cette supposition peut vraiment varier suivant la situation. De manière générale j'en ai tiré les conclusions suivantes :

- Si le plateau étudié à une profondeur donnée est susceptible d'avoir beaucoup de coups forcés (mise à 1 degré, coup qui tue etc etc) cette supposition est bonne. C'est par exemple le cas pour une étude qui commence avec un cross-cut. Cette figure de départ favorise énormément les coups forcés. Dans ce cas mon algorithme va étudier en priorité ces fameux coups qui ont déjà donné un élagage.

- Par contre si la configuration du jeu n'admet pas de coups forcés à courte échéance, il peut y avoir explosion combinatoire des coups et donc une explosion combinatoire des "situations". Dans ce cas, un coup qui a déjà donné un élagage à cette profondeur n'a peut être plus aucun rapport avec l'étude de la situation présente. Dans ce cas, étudier ce coup en priorité est une mauvaise option et il vaut mieux se contenter du tri obtenu au 2). C'est par exemple le cas d'une recherche de solution gagnante sur un plateau vide.

Ces deux méthodes 5) et 6) sont la partie la moins maîtrisée de mon algorithme. Quelquefois elles permettent de gagner du temps, quelquefois elles en font perdre....On remarquera en analysant les tableaux des résultats, que plus la profondeur maximum de l alha-bêta est grande, plus ces méthodes donnent des résultats contradictoires. Ces deux méthodes sont donc d'autant moins fiables que la profondeur est grande.

7) Mon "second" tri du 5) fais que globalement si il existe une solution gagnante pour une couleur, il y a de fortes chances que cette solution soit étudiée dans les premiers coups. Et statistiquement cela ce vérifie à chaque étage de mon alpha-bêta. Partant de ce principe, je limite le nombre de coups de couleurordi à n. Ce nombre n dépendra essentiellement du goban de départ. Par exemple, pour un goban vide en 6*6, si n=7 le rendement est optimisé. Avec un cross-cut l'optimisation est maximum pour 3.

Dans mon alpha-bêta principal si couleurordi n' a trouvé aucune solution gagnante au bout de n coups, l'algorithme élague. Pour que mon résultat final soit obtenu sans aucune incertitude, cette limite "n" est uniquement pour les coups de couleurordi, dans tous les cas couleurjoueur étudie tous ses coups. L'incertitude n'est donc que pour les résultats positifs. Si mon algorithme ne trouve pas de solution gagnante cela ne veut pas dire qu'il n'y en a pas. Par contre si il trouve une solution gagnante, celle-ci est sans aucune incertitude.

Télechargez Pseudo-code Atari-Dariush Fichier PDF 17Ko

Observation

Dans mon logiciel j'ai mis les résultats des études décrites précédemment dans une base de donnée. Si Dariush3D joue avec les noirs au niveau le plus élevé ("bon joueur"), il jouera donc forcement Le coup gagnant pour un goban de taille inférieure à 6 et pour un goban 7*7 avec un cross-cut au départ. Je vous invite à tester cette base. Dans la version de démonstration, on ne peut jouer qu'en 6*6. Si vous êtes programmeur et si vous voulez tester en 7*7, envoyez moi un courrier (fr.boissac@free.fr).

Boissac Frédéric le 17 juin 2006

Mon ordinateur :AMD Athlon(tm) 64 processor 3000+ 1,79Ghz 1Go de RAM

Téléchargez et Testez Dariush 3D version de démonstration (5,4Mo).