Si on leur donne une puissance de traitement infinie, existe-t-il un algorithme qui jouerait parfaitement aux échecs?

Existe-t-il un tel algorithme où, si on lui donne une puissance de traitement infinie, un ordinateur pourrait parfaitement jouer aux échecs pour qu'il ne perde jamais?

Si oui, où puis-je trouver un pseudo-code pour cela?

Existe-t-il un algorithme? Oui. Selon le théorème de Zermelo , il y a trois possibilités pour une partie déterministe finie à deux informations parfaites comme les échecs: soit le premier joueur a une stratégie gagnante, soit le deuxième joueur a une stratégie gagnante, soit l'un ou l'autre joueur peut forcer un match nul. Nous ne savons pas (encore) de quoi il s'agit pour les échecs. (Les dames, en revanche, ont été résolues : chaque joueur peut forcer un match nul.)

Conceptuellement, l'algorithme est assez simple: construisez un arbre de jeu complet , analysez les nœuds terminaux (les positions de fin de jeu) et effectuez le mouvement initial gagnant, démissionnez ou offrez un match nul.

Le problème réside dans les détails: il y a environ 10 ⁴³ positions possibles, et un nombre encore plus grand de mouvements (la plupart des positions peuvent être atteintes de plusieurs manières). Vous avez vraiment besoin de votre ordinateur infiniment puissant pour en profiter, car un ordinateur qui peut tirer parti de cet algorithme ne peut pas entrer dans l'univers connu ou ne terminera le calcul que quelque temps après la fin de l'univers.

Voir https://en.wikipedia.org/wiki/Endgame_tablebase .

Avec une puissance informatique infinie, on pourrait construire une telle table pour la position de départ et résoudre les échecs .

Dans la pratique, seules les positions comptant jusqu'à sept "hommes" (pions et pièces, en comptant les rois) ont été résolues à l'aide des superordinateurs actuels, nous sommes donc très loin de résoudre les échecs. La complexité du problème augmente de façon exponentielle avec le nombre de pièces.

Si vous aviez vraiment une puissance de traitement infinie , un tel algorithme serait en fait trivial à écrire. Comme les échecs ont un nombre fini d'états possibles, vous pouvez en théorie simplement les parcourir tous jusqu'à ce que vous trouviez un chemin de jeu parfait. Ce serait horriblement inefficace, mais si vous avez une puissance de traitement infinie , cela n'aurait pas d'importance.

Pour répondre directement à la question: oui, il existe un tel algorithme. Cela s'appelle minimax. (Les bases de table de fin de partie sont générées en utilisant cet algorithme (à l'envers!), Mais l'ancien algorithme simple minimax simple est tout ce dont vous avez besoin). Cet algorithme peut parfaitement jouer à n'importe quel jeu à somme nulle pour deux joueurs. Trouvez le pseudocode ici:

https://en.wikipedia.org/wiki/Minimax

notez que des variantes de cet algorithme sont utilisées par les programmes d'échecs informatiques modernes.

Non seulement existe-t-il un algorithme pour jouer aux échecs parfaits, mais il est possible d'écrire un programme court qui (étant donné des ressources infinies) jouera parfaitement à n'importe quel jeu déterministe de connaissances parfaites à durée finie à deux joueurs .

Le moteur de jeu n'a même pas besoin de connaître les règles du jeu auquel il joue. Tout ce dont il a besoin est une représentation opaque d'un "état de jeu" et des fonctions qui (a) donnent n'importe quel état de jeu, fournissent une liste des prochains états de jeu légaux et (b) donnent un état de jeu, décident si c'est une victoire pour le joueur 1 , une victoire pour le joueur 2, un match nul, ou ce n'est pas un état final.

Étant donné ces fonctions, un simple algorithme récursif "résout" le jeu.

Ce fait a été évoqué dans les réponses précédentes par chessprogrammer (minimax) et par Acccumulation (qui fournit une version du programme en python).

J'ai écrit un tel programme il y a plus de 20 ans. Je l'ai testé en jouant aux noughts-and-crosses (tic-tac-toe si vous êtes américain). Effectivement, il a joué un jeu parfait.

Bien sûr, cela tombera rapidement sur n'importe quel ordinateur imaginable pour tout jeu sérieux. Parce qu'il est récursif, il construit efficacement la totalité de l'arborescence du jeu sur la pile, vous obtiendrez donc un "débordement de pile" (jeu de mots très voulu) avant de vous approcher de l'analyse des 10 ^ 123 états d'échecs mentionnés dans d'autres réponses. Mais c'est amusant de savoir qu'en principe ce petit programme ferait l'affaire.

Pour moi, cela dit aussi quelque chose d'intéressant à propos de l'IA: quelle que soit l'intelligence que vous pensez est exposée par Deep Blue, ou Go Zero, ou bien par un humain jouant aux échecs ou à Go, il y a un sens dans lequel ces jeux ont une trivialité, une calculabilité optimale optimale solutions. Le défi est de savoir comment obtenir une bonne solution, mais pas optimale, dans un délai raisonnable.

J'ignorerai les possibilités de tirages ou de séquences infinies de mouvements pour plus de simplicité. Une fois l'algorithme compris, il n'est pas particulièrement difficile de l'étendre à ces cas.

Tout d'abord, quelques définitions:

1. Tout coup qui gagne la partie pour le joueur qui fait ce coup est un coup gagnant.

2. Tout coup qui perd la partie pour le joueur qui fait ce coup est un coup perdant.

3. Tout coup qui laisse à l'autre joueur au moins un coup gagnant est également un coup perdu. (Puisque l'adversaire peut prendre ce mouvement et forcer une perte.)

4. Tout coup qui laisse l'autre joueur avec seulement des coups perdus est également un coup gagnant. (Peu importe le mouvement de votre adversaire, vous gagnerez.)

5. Une stratégie parfaite signifie toujours faire des coups gagnants s'il en reste et démissionner quand il ne reste plus que des coups perdants.

Maintenant, il est trivial d'écrire une stratégie parfaite. Explosez simplement toutes les séquences de mouvements possibles et identifiez les mouvements gagnants / perdants. Ignorant l'impasse, cela finira par identifier chaque coup comme un coup gagnant ou un coup perdant.

Maintenant, la stratégie est triviale. Regardez tous vos mouvements possibles. S'il reste des coups gagnants, prenez-en un et gagnez. S'il ne reste que des coups perdants, démissionnez, car votre adversaire peut vous forcer à perdre.

Il n'est pas difficile d'ajuster la stratégie pour inclure la possibilité d'une impasse.

Mise à jour : juste au cas où il n'est pas clair comment cela identifie chaque mouvement comme un gain gagnant ou un coup perdant, considérez:

1. Chaque coup qui donne lieu à une victoire est un coup gagnant.
2. Chaque coup qui entraîne une perte est un coup perdu.
3. Chaque coup qui fait que l'adversaire n'a que des coups gagnants ou perdants est un coup gagnant ou un coup perdu.
4. Appelez nle nombre de coups dans la partie d'échecs la plus longue possible. (Nous ignorons les séquences illimitées pour l'instant, bien que les inclure ne soit pas difficile.)
5. Il n'y a aucun mouvement avec ndes mouvements antérieurs que nous devons considérer.
6. Chaque coup avec n-1des coups précédents est soit un coup gagnant, soit un coup perdu puisque les ncoups mettent fin à la partie la plus longue.
7. Ainsi, chaque coup en profondeur n-2est suivi uniquement de coups gagnants ou de coups perdus et est donc lui-même un coup gagnant ou un coup perdu.
8. Et ainsi de suite jusqu'au premier coup.

Supposons que vous avez trois fonctions: win_state, get_playeret next_states. L'entrée pour win_stateest un état de jeu, et la sortie est -1 si le blanc est en échec et mat, 0 s'il s'agit d'un match nul, 1 si le noir est en échec et Noneautre. L'entrée pour get_playerest un état de jeu, et la sortie est -1 si c'est le tour du noir et 1 si c'est le tour du blanc. L'entrée pour next_statesest une liste des états possibles du prochain jeu qui peuvent résulter d'un mouvement légal. Ensuite, la fonction suivante, lorsqu'elle reçoit un état de jeu et un joueur, devrait vous dire dans quel état de jeu se déplacer pour que ce joueur gagne.

def best_state(game_state,player)
  def best_result(game_state):
     if win_state(game_state):
        return(win_state)
     else:
         player = get_player(game_state)
         return max([best_result(move)*player for move in next_states(game_state)])*player
  cur_best_move = next_states(games_state)[0]
  cur_best_outcome = -1
  for state in next_states(game_state):
     if best_result(state)*player > cur_best_outcome:
           cur_best_outcome = best_result(state)*player
           cur_best_move = state
return(best_move)

Utiliser une table de correspondance

Oui. C'est facile. Vous n'avez même pas besoin d'une puissance de traitement infinie. Tout ce dont vous avez besoin est une table de consultation qui contient, pour chaque position de plateau possible, le meilleur coup à jouer dans cette position. Voici le pseudo-code:

def play-move(my-color, board-position):
    return table-of-best-moves[my-color, board-position]

La prise

Le seul hic, c'est que cette table de correspondance devrait être très, très grande - peut-être plus grande que la galaxie de la Voie lactée - et il faudrait beaucoup de temps pour la construire - peut-être plus longtemps que l'âge actuel de l'univers, à moins qu'il n'y ait une régularité inconnue dans les échecs qui le rend beaucoup plus simple que ce que nous pouvons voir en ce moment. Mais si vous aviez cette table de recherche, le sous-programme pour choisir un mouvement parfait à chaque fois pourrait être implémenté en aussi peu qu'une instruction CPU.

De plus, étant donné nos connaissances actuelles sur les échecs, il n'y a aucun moyen d'être sûr qu'un jeu parfait garantit que vous ne perdrez pas. Par exemple, si un jeu parfait garantit une victoire pour les Blancs, alors les Noirs perdraient même si les Noirs jouent parfaitement.