Comment faire jouer une machine aux échecs ?

Principe

Les simulateurs d'échecs copient le raisonnement humain, en compensant leur absence d'intuition par une puissance de calcul de plus en plus monstrueuse (de l'ordre de 10.000 coups par seconde pour Cheeky Chess, écrit en javascript).

Analysons le raisonnement humain : comment procède un joueur dans le choix de son coup ? Dans un premier temps l'homo sapiens va lister l'ensemble des coups à sa disposition, puis il validera son choix en fonction des répliques possibles de l’adversaire qui jouera à son tour son coup le plus nuisible. Si notre homo sapiens est un grand-maitre-qui-déchire-tout, il analysera les X coups suivants et choisira in fine le coup qui l'avantage le plus à l'arrivée.

Arbre de possibilités

Ce raisonnement peut être modélisé par un arbre de possibilités, en partant de la situation présente sur l’échiquier. Considérons l'exemple ci-dessous, où c'est aux blancs de jouer :






Analysons pourquoi le coup F1-A6 est nul : une fois joué, nous pouvons être sûr que notre adversaire prendra le fou en jouant B7-A6. Un coup est donc à éviter à partir du moment ou il existe une possibilité de réponse cinglante. Inversement, un coup est bon si la meilleure réponse de l'adversaire reste bancale. Mathématiquement, nous cherchons à maximiser la valeur de notre coup, sachant que notre adversaire cherchera ensuite à minimiser cette valeur.

A l’horizon d'un coup, le meilleur choix correspond à Max(Min(X)), X désignant la valeur de la situation après un coup.

A l’horizon de deux coups, le meilleur choix correspond à
Max(Min(Max(Min(X)))), X désignant la valeur de la situation après les deux coups. Etc, pour trois coups : Max(Min(Max(Min(Max(Min(X))))))

Le simulateur va donc coupler deux fonctions principales :
  - une fonction construisant l’arbre des possibilités
  - une fonction évaluant la position résultante sur l’échiquier (plutôt bonne ou mauvaise ?)

Les résultats des différentes hypothèses sont ensuite remontés à la racine de l'arbre en prenant le max du min du max du min... Ca s'appelle un algorithme minimax et cette modélisation fonctionne plutot bien.

Evaluation d'une position

La fonction d'évaluation de la position sert à déterminer si l'échiquier est avantageux. Une première estimation est la somme de la valeur des pièces : un pion se voit attribué la valeur 1, un fou ou un cheval 3, une tour 5, une dame 9. Tel Richard III offrant son royaume pour un cheval, cette approximation doit évidement être nuancée : un pion allant à dame vaut nettement plus, de même qu'une pièce bien ancrée au centre. En revanche, on ne donnera pas cher de pièces isolées dans un coin, clouées ou d'un roi s'enfuiant en caleçon avec la cavalerie aux trousses.

La valeur obtenue est symétrique pour les joueurs : une valeur de +5 pour le joueur 1 équivaut à une valeur de -5 pour le joueur 2.

Elagage

Dans le cas des échecs, le problème de la construction de l’arbre réside dans l'explosion exponentielle des possibilités. Pour la position de départ 20 coups sont possibles. Easy baby, mais...

Si l’on multiplie par le nombre de réponses du berger à la bergère, on obtient 20x20 = 400 possibilités après un coup (je joue, tu joues). On peut arrondir le nombre de possibilités après deux coups à 20x20x20x20 = 20 ^ 4 = 160.000 possibilités à évaluer. Trois coups ? plus de 64 millions de possibilités. OK tout le monde a compris, les puissances de 20 (voire 50 parfois) explosent très vite.

La solution consiste à « élaguer » notre arbre. Elaguer signifie que l’on n'ira pas voir se qui se passe après avoir joué un coup particulièrement foireux. Pourquoi ? Justement parce qu’on ne va pas jouer ce coup foireux ! Idem pour l’adversaire : inutile de considérer qu’il va offrir sa dame au prochain tour, à moins qu'il soit totalement con cela n’arrivera pas (bon ok ça m'est déja arrivé...)

Bref, ça s'appelle l'élagage alpha-bêta, et ça réduit considérablement le nombre de positions à analyser. Tout est expliqué là en détail. Ainsi, Cheeky Chess analyse moins de 0.1% des positions possibles.

Coups pourris

Notre algorithme commence à tenir la route mais il est nécessaire d'améliorer les performances. En étudiant les ramifications de notre arbre, on s'aperçoit que certains coups particulièrement mauvais sont explorés X fois avec à chaque fois le même verdict : POURRI ! En effet, dans la majorité des cas si j’ai la possibilité de jouer un mauvais coup le tour suivant mais que je ne le joue pas, il se représentera à nouveau à moi le coup d’après. Une fois déterminé que ce coup possible est pourri, est-il utile de l’explorer à nouveau plus loin dans notre arbre ? Non : ce coup est pourri, restera pourri le coup suivant, et si je suis intelligent je ne le jouerai pas (pareil pour le gars d’en face). Détecter ces coups afin de les délaisser par la suite dans le parcours de l'arbre permet d'améliorer grandement les performances.

Cependant… il existe des cas où le coup noir joué au tour N change radicalement l’intérêt au tour N+1 d'un coup qui était pourtant pourri au tour N, comme ci-dessous :



Dans cet exemple où c'est aux noirs de jouer, le mouvement du fou E5-G3 est nul car on se fait reprendre par le pion. Néanmoins dans les sous-arbres constitués par un mouvement ultérieur des blancs H2-H4, ce coup noir E5-G3 peut redevenir intéressant. Il devra donc être exploré dans ces sous-arbres, pas dans les autres.

Toute la subtilité est de définir algorithmiquement ce qu’est un coup pourri, et le degré de mimétisme à partir duquel on considère que ce coup n'a pas besoin d'être analysé pour les échiquiers similaires rencontrés plus loin dans notre arbre des possibilités.

Cheeky Chess considère qu’un coup pourri correspond à un coup moins bon de 1 point ou plus par rapport à un autre coup possible (1 correspondant à la valeur d’un pion). Une fois ce coup déterminé comme pourri, Cheeky Chess n’analysera plus ce coup dans l’arbre des possibilités si la pièce supposément jouée ensuite par l’adversaire se trouve au même endroit.

Priorité

L'ordre d'examen des coups est aussi primordial, car il influe sur l'élagage. Le fait d'analyser le meilleur coup en premier pour chacun des joueurs permet dans la majorité des cas de conclure plus rapidement : si le premier coup de la machine analysé est le meilleur, il servira d'étalon pour l'étude des coups suivants qui seront ainsi élagués plus rapidement.

Les pièces non défendues seront ainsi mangées en priorité. A l'inverse les coups à priori mauvais, comme manger avec sa dame un pion protégé, seront étudiés en dernier et souvent ne le seront jamais car l'arbre sera élagué avant.

Fourchettes en plomb

Certains coups vont pourtant poser problème : une fourchette ou une mise en échec déclenchent un enchainement de coups qu'il convient d'étudier en entier, ce qui est lourd et plombe les performances. Cheeky Chess étudie ces coups en dernier (à partir du rang 2 de l'arbre) même s'ils sont à priori les meilleurs en espérant que l'arbre sera élagué avant d'évaluer la fourchette. Statistiquement la démarche est gagnante, car on n'analysera cette fourchette que dans les configurations plausibles.

Autres optimisations

Il est également utile de moduler la profondeur de l’arbre en fonction de l’intérêt des coups : par défaut on ira voir X coups en avance, mais dans le cas d’un échange de dames il sera sage de creuser quelques coups supplémentaires histoire de voir si on s’en tire bien (« je te bouffe, tu me bouffes, je te bouffe, … »)

Bien sûr dans certains cas en élaguant sans vergogne on passera à coté de coups intéressants, mais le but est d’optimiser le rapport entre le temps d’exécution et la probabilité d'obtenir le meilleur coup jouable : si on double le temps de calcul pour n’obtenir un résultat que dans 5% de cas, mieux vaut explorer d'autres pistes.

Langage de programmation

Le simulateur est entièrement écrit en javascript, langage interprêté par le navigateur web. Les coups ne sont donc pas adressés à un serveur pour analyse, tout est exécuté coté client ce qui offre l'avantage de ne plus dépendre du réseau une fois la page téléchargée.

A ma surprise, 1500 lignes de code ont été suffisantes pour obtenir une première maquette jouable d'un niveau débutant. Notre raisonnement est somme toute facilement copiable par des machines...

Le code source est disponible pour étude, les rouages se trouvent dans les fichiers echiquier.js et main.js

Le plus délicat a été le design des mascottes, je suis nul en dessin !

Logiciels utilisés :
  - Notepad++ pour l'écriture du javascript
  - GIMP pour les graphiques

Graphismes

La mascotte Brutus est inspirée du site www.how-to-draw-funny-cartoons.com

A propos du programmeur

Site développé en 2011 par Frédéric Gaonac'h.

J'écris en divers langages : VB/C#/ASP.NET, SQL, Javascript, XSL...
Tout sauf du COBOL, beurk !

L'idée de ce site m'est venue d'un projet de deuxième année à Dauphine qui consistait à faire jouer une machine au Puissance4. La logique d'un simulateur d'échecs est similaire, à ceci près que l'arbre des possibilités doit réellement être optimisé sans quoi la machine implosera.

Je suis moi-même joueur d'échecs... assez médiocre ! :-)

Des questions, commentaires ?