Résolution du jeu d'échecs

La résolution du jeu d'échecs consiste à avoir trouvé une stratégie optimale pour le jeu d'échecs, c'est-à-dire une stratégie par laquelle l'un des joueurs (Blancs ou Noirs) peut toujours forcer une victoire, ou l'un ou l'autre peut forcer un match nul (voir jeu résolu). Cela signifie aussi plus généralement résoudre des jeux "comme les échecs" (c'est-à-dire des jeux combinatoires à l'information parfaite), tels que les échecs Capablanca et infinite chess (en). Selon le théorème de Zermelo, une stratégie optimale déterminable doit exister pour les échecs et les jeux de type échecs.

Dans un sens plus faible, « résoudre les échecs » peut faire référence à déterminer lequel des trois résultats possibles (les Blancs gagnent ; les Noirs gagnent ; match nul) est le résultat pour deux adversaires jouant parfaitement, sans nécessairement indiquer la stratégie optimale elle-même (voir raisonnement par l'absurde).

Aucune solution complète pour les échecs dans l'un ou l'autre des deux sens n'est connue, et on ne s'attend pas non plus à ce que les échecs soient résolus dans un proche avenir. Il y a désaccord sur la question de savoir si la croissance exponentielle actuelle de la puissance de calcul se poursuivra assez longtemps pour permettre un jour de la résoudre par recherche exhaustive, c'est-à-dire en vérifiant toutes les possibilités.

Les progrès à ce jour sont extrêmement limités ; il existe des tables de finale qui permettent d'exécuter parfaitement les fins de partie mettant en jeu un petit nombre de pièces, et plusieurs variantes sur des échiquiers de tailles plus réduites ont été résolues au moins dans le sens faible du terme. Il y a des estimations chiffrées de la complexité de l'arbre de jeu et de la complexité de l'espace des phases des échecs qui fournissent une vue d'ensemble de l'effort de calcul qui pourrait être nécessaire pour résoudre le jeu.

Résultats partiels

Tables de finale

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Un mat en 546 coups (trait aux Blancs) trouvé par la table de finales Lomonosov.

Les tables de finale sont des bases de données informatisées qui contiennent toutes les positions calculées par analyse rétrograde ressortant d'une analyse exhaustive avec un petit nombre de pièces restant sur l'échiquier. Les tables de finale ont résolu les échecs à un degré limité, déterminant le jeu parfait dans un certain nombre de finales, y compris toutes les finales non triviales avec au plus sept pièces ou pions (y compris les deux rois). Certaines finales trouvées par ces tables dépassent la règle des 50 coups avec un jeu parfait.

Une variante décrite pour la première fois par Shannon fournit un argument sur la valeur théorique des jeux d'échecs : il propose de permettre le coup de « passe ». Dans cette variante, on peut prouver ainsi avec une argumentation de confiscation de stratégie (en) que le premier joueur a au moins une nulle dans la position de départ : si le premier joueur a un coup gagnant, laissez-le jouer, sinon passez. Le deuxième joueur est maintenant confronté à la même situation en raison de la symétrie de l'échiquier : si le premier joueur n'avait aucun coup gagnant en premier lieu, le deuxième joueur n'en a plus maintenant. Par conséquent, le deuxième joueur peut au mieux annuler, et le premier joueur peut au moins annuler, donc un jeu parfait fait que le premier joueur gagne ou fait match nul.

Variantes des échecs

Certaines variantes d'échecs qui sont plus simples que les échecs ont été résolues. Une stratégie gagnante pour les noirs dans le maharajah et les cipayes peut être facilement mémorisée. Les mini-échecs sur un échiquier 5x5 ont été faiblement résolus comme un match nul. Bien que les échecs à qui perd gagne sont joués sur un échiquier 8x8, leur règle de capture forcée limite considérablement leur complexité et une analyse informatique a réussi à résoudre faiblement cette variante comme une victoire pour les blancs.

La perspective de résoudre des jeux spécifiques similaires aux échecs devient plus difficile à mesure que la taille de l'échiquier augmente, comme dans les variantes d'échecs avec un grand échiquier et infinite chess (en).

La complexité du jeu d'échecs

En 1950, le théoricien de l'information Claude Shannon décrit une procédure théorique pour jouer parfaitement (c'est-à-dire résoudre les échecs) :

« Avec les échecs, il est possible comme suit, en principe, de jouer parfaitement ou de construire une machine pour le faire : on considère dans une position donnée tous les coups possibles, puis tous les coups possibles de l'adversaire, etc., jusqu'à la fin de la partie (dans chaque variante). La partie doit obligatoirement avoir une fin, selon les règles du jeu, après un nombre fini de coups (en se souvenant de la règle des 50 coups). Chacune de ces variantes se termine par une victoire, une défaite ou une égalité. En calculant à rebours à partir de la fin, on peut déterminer s'il y a une victoire forcée, si la position de départ est une égalité ou est perdue avec un jeu parfait. »

Shannon a ensuite estimé que résoudre les échecs selon cette procédure nécessiterait de comparer quelque 10¹²⁰ variantes de jeu possibles, ou d'avoir un "dictionnaire" indiquant un coup optimal pour chacune des quelques 10⁴³ positions possibles sur l'échiquier (actuellement connues pour être d'environ 5 x 10⁴⁴.

Le nombre d'opérations mathématiques nécessaires pour résoudre les échecs, cependant, peut être significativement différent du nombre d'opérations nécessaires pour produire l'ensemble de l'arbre de jeu des échecs. En particulier, si les Blancs peuvent forcer la victoire, seul un sous-ensemble de l'arbre de jeu nécessiterait une évaluation pour confirmer qu'une victoire forcée existe (c'est-à-dire sans réfutation par les Noirs). De plus, le calcul de Shannon pour la complexité des échecs suppose une durée de jeu moyenne de 40 coups, mais il n'y a aucune base mathématique pour dire qu'une partie parfaitement jouée de chaque côté aurait un rapport avec cette durée de jeu. En effet, certaines parties jouées de manière experte (jeu de niveau Grand maître international) ont été aussi courtes que 16 coups (partie nulle). Pour ces raisons, les mathématiciens et les théoriciens des jeux ont été réticents à affirmer catégoriquement que la résolution des échecs est un problème insoluble.

Hans Joachim Bremermann, professeur de mathématiques et de biophysique à l'Université de Californie à Berkeley, a en outre soutenu dans un article de 1965 que « la vitesse, la mémoire et la puissance de traitement de tout futur équipement informatique éventuel sont limitées par des barrières physiques spécifiques : la barrière de la vitesse de la lumière, la barrière quantique et la barrière thermodynamique. Ces limitations impliquent, par exemple, qu'aucun ordinateur, quelle que soit sa configuration, ne pourra examiner l'arbre entier des séquences de coups possibles dans le jeu d'échecs. » Cependant, Bremermann n'a pas exclu la possibilité qu'un ordinateur puisse un jour résoudre les échecs. Il a écrit : « pour qu'un ordinateur puisse jouer parfaitement ou presque parfaitement, il sera nécessaire d'analyser le jeu complètement... ou d'analyser le jeu de manière approximative et de combiner cela avec une quantité limitée de recherches dans les arbres. ... Cependant, une compréhension théorique de ces heuristiques de programmation fait toujours défaut ».

Les progrès scientifiques récents n'ont pas sensiblement modifié ces évaluations. Le jeu de Dames a été (faiblement) résolu en 2007, mais il a approximativement la racine carrée du nombre de positions aux échecs. Jonathan Schaeffer, le scientifique qui a dirigé les travaux, a déclaré qu'une avancée comme l'informatique quantique serait nécessaire avant que l'on puisse tenter de résoudre les échecs, mais il n'exclut pas la possibilité, disant que la seule chose qu'il a apprise de ses 16 ans d'efforts pour résoudre les Dames « est de ne jamais sous-estimer les progrès technologiques ».