Programmation des échecs et d'autres jeux

Une première version de cet article a été initialement publiée sur Interstices en 2012 puis mise à jour en juin 2023.

Dans les années 90, les ordinateurs sont devenus capables de jouer contre de grands joueurs d'échecs et de les mettre en difficulté. En 1997, Garry Kasparov, champion du monde, est battu par Deep Blue. En 2005, le programme Hydra (sur un ordinateur parallèle puissant) écrase Michael Adams, un des meilleurs joueurs du monde, sur le score de 5 ½ à ½. Désormais, des programmes commerciaux généralistes sur des machines usuelles sont devenus aussi forts que les meilleurs joueurs humains. Ils gagneront contre vous presque à coup sûr, même en vous donnant des avantages divers (par exemple un pion d'avance).

Selon quels principes les programmes qui ont permis ces exploits sont-ils conçus ? Les techniques présentées ici peuvent servir à programmer de nombreux jeux, et sont proches de techniques utilisables pour résoudre d'autres problèmes.

Le graphe de pile ou face

Les échecs étant bien compliqués, regardons comment programmer un jeu beaucoup plus simple : pile ou face. Commençons même par un exemple encore plus simple : imaginons que nous ayons une pièce truquée qui tombe toujours sur pile. Nous savons alors que pour gagner, il faut choisir « pile », et que si l'on choisit « face », on va perdre. Le graphe représentant ce problème est le suivant :

Nous avons donc représenté un jeu (certes très simple ici) par un graphe, c'est-à-dire des nœuds (les ronds) reliés par des arêtes (les flèches). Nous avons placé un \(1\) pour la situation finale conduisant à une victoire, et un \(0\) pour la situation finale conduisant à une défaite.

Généralisons à présent ce principe d'un graphe pour représenter un jeu, mais cette fois-ci avec deux joueurs : le premier choisit pile ou face, et le second, qui entend la décision du premier joueur, place la pièce selon son propre choix, sur pile ou sur face. Si le premier joueur a deviné ce qu'allait faire le second, il gagne ; sinon, le second joueur gagne. Ce jeu n'est pas beaucoup plus intéressant que le précédent, pourriez-vous objecter, car s'il joue bien, le second joueur peut toujours gagner ! Vous avez raison, mais ce qui est intéressant, c'est que cela peut être démontré grâce à la représentation par un graphe. Ce jeu se présente comme suit :

Il y a maintenant des nœuds bleus et des nœuds jaunes dans le graphe. Si on se place du point de vue du joueur 1, les nœuds jaunes correspondent aux situations où son adversaire prend une décision. En partant du haut de l'arbre, le joueur 1 choisit la branche descendante de son choix lorsque le nœud est bleu, et le joueur 2 choisit la branche de son choix lorsque le nœud est jaune. Là encore, les \(1\) marquent les victoires du joueur 1 et les \(0\) ses défaites.

Quoique le jeu ne soit pas bien compliqué, on n'a pas immédiatement accès à une stratégie pour le premier joueur. En regardant le nœud tout en haut, et même les nœuds juste en dessous, nous ne savons pas ce que le joueur 1 devrait jouer. Par contre, dans chacun des nœuds jaunes, nous voyons bien que le second joueur a une stratégie très simple pour gagner. Nous pouvons donc étiqueter les nœuds jaunes avec des \(0\) et des \(1\), tout comme les nœuds terminaux. Nous constatons que pour chacun de ces nœuds, le joueur 2 peut gagner (en choisissant face dans le cas où le joueur 1 a choisi pile, et en choisissant pile dans le cas où le joueur 1 a choisi face). Ces situations sont donc équivalentes à des défaites pour le joueur 1 ; par conséquent, nous les étiquetons \(0\). Nous obtenons alors le graphe suivant :

Nous constatons que quel que soit le choix du joueur 1, il se retrouve en situation \(0\) (perdante). On peut donc étiqueter aussi le nœud tout en haut d'un \(0\), montrant que la situation initiale est synonyme de défaite pour le joueur 1 :

La procédure à appliquer est donc la suivante :

• écrire le graphe représentant le jeu
• étiqueter les nÅ“uds avec des \(0\) et des \(1\) (éventuellement avec des ½ pour les cas d'égalité), en remontant depuis les nÅ“uds du bas de l'arbre, jusqu'à la racine. Un nÅ“ud a pour valeur le maximum des nÅ“uds fils, lorsque le nÅ“ud est bleu ; et le minimum des nÅ“uds fils lorsque le nÅ“ud est jaune.

Nous obtenons ainsi deux certitudes :

• nous savons que si les joueurs jouent « bien », le joueur 2 gagne ;
• nous savons que le joueur 2 doit jouer une arête menant à un \(0\) pour gagner.

Bien sûr, nous avons examiné un jeu très simple, mais fondamentalement cette approche permet, théoriquement, d'étudier des jeux compliqués, dans la mesure où la mémoire de l'ordinateur et le temps de calcul permettent de réaliser toutes les opérations requises. Cette approche pour résoudre un jeu s'appelle le Minimax. Son inconvénient est le très long temps de calcul qu'il nécessite, dès lors que le jeu s'approche d'un jeu réel.

Le cas du jeu d'échecs

Le nombre inscrit dans nos nœuds (0, 1 ou ½ dans les exemples ci-dessus) est appelé valeur du nœud (on parle aussi de la valeur de la situation). Pour résoudre un jeu avec l'outil présenté ci-dessus, il faut écrire une valeur dans chaque nœud. C'est faisable sur les jeux triviaux ci-dessus, ou sur des jeux comme tic-tac-toe, mais pas pour le jeu d'échecs, où une telle approche demanderait un temps déraisonnable.

Pour traiter le jeu d'échecs, Claude Shannon a proposé en 1950 une approximation de cet algorithme. Pour définir cette approximation, nous allons avoir besoin d'une définition : on définit la profondeur d'un nœud comme le nombre d'arêtes à parcourir avant de remonter à la racine. On décide alors d'une profondeur limite \(k\). Pour tous les nœuds à profondeur \(k\) ou les nœuds où le jeu est fini, la valeur sera :

• un nombre positif très élevé (par exemple 100 000) en cas de victoire dans cette situation ;
• un nombre très négatif (par exemple -100 000) en cas de défaite dans cette situation ;
• une valeur approchée, calculée à partir des éléments visibles sur le plateau, par exemple pour les échecs, comme suit :
  • 10 pour une dame (-10 pour la dame adverse) ;
  • 5 pour une tour (-5 pour une tour adverse) ;
  • 3 pour un cavalier ou un fou (-3 pour un cavalier ou fou adverse) ;
  • 1 pour un pion (-1 pour un pion adverse) ;

  en prenant en compte aussi des éléments de position, comme -½ pour chaque pion « doublé » (deux pions sur la même colonne).

Une telle approximation est appelée « fonction d'évaluation ». Il se trouve que des fonctions assez simples fournissent de très bons résultats, et qu'on arrive efficacement à améliorer ces fonctions en discutant avec des experts.