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 les Échecs infinis. 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

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 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 échecs infinis.

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

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

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 nulleMagnus Carlsen contre Viswanathan Anand, Attaque est indienne : Double Fianchetto (A07), ½-½, 16 coups.). 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 Cependant, Bremermann n'a pas exclu la possibilité qu'un ordinateur puisse un jour résoudre les échecs. Il a écrit : .

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 .

Notes et références

Catégorie:Théorie des échecs Catégorie:Théorie des jeux