Peut-il y avoir un algorithme d'échecs parfait?

Les algorithmes d'échecs actuels vont d'environ 1 ou peut-être 2 niveaux dans un arbre de chemins possibles en fonction des mouvements du joueur et de l'adversaire. Disons que nous avons la puissance de calcul pour développer un algorithme qui prédit tous les mouvements possibles de l'adversaire dans une partie d'échecs. Un algorithme qui a tous les chemins possibles que l'adversaire peut emprunter à tout moment en fonction des mouvements des joueurs. Peut-il jamais y avoir un algorithme d'échecs parfait qui ne perdra jamais? Ou peut-être un algorithme qui gagnera toujours? Je veux dire en théorie que quelqu'un qui peut prédire tous les mouvements possibles doit être capable de trouver un moyen de vaincre chacun d'entre eux ou simplement de choisir un chemin différent si un certain le mènera efficacement à la défaite .....

edit-- Quelle est vraiment ma question. Disons que nous avons la puissance de calcul pour un algorithme parfait qui peut jouer de manière optimale. Que se passe-t-il lorsque l'adversaire joue avec le même algorithme optimal? Cela s'appliquera également dans tous les jeux à 2 joueurs avec un nombre fini (très grand ou non) de coups. Peut-il jamais y avoir un algorithme optimal qui gagne toujours?

Définition personnelle: un algorithme optimal est un algorithme parfait qui gagne toujours ... (pas un qui ne perd jamais, mais un qui gagne toujours

Votre question s'apparente au vieux châtaignier: "Que se passe-t-il lorsqu'une force irrésistible rencontre un objet inamovible?" Le problème est dans la question elle-même: les deux entités décrites ne peuvent exister dans le même univers logiquement cohérent. Votre algorithme optimal, un algorithme qui gagne toujours, ne peut pas être joué par les deux camps dans une partie où un camp doit gagner et l'autre par définition perdre. Ainsi, votre algorithme optimal tel que défini ne peut pas exister.

Tout d'abord, je crois que les algorithmes d'échecs semblent plus de 2 plis, bien qu'ils ne considèrent pas toutes les possibilités différentes; l'élagage de l'arbre de recherche est très important pour éviter l'explosion combinatoire du nombre de mouvements possibles.

Pour un jeu comme les échecs, il y a trois possibilités quant à l'identité du vainqueur: soit le joueur 1 a une stratégie gagnante, soit le joueur 2 a une stratégie gagnante, soit les deux joueurs tirent sous un jeu optimal. On ne sait pas ce qui est le cas pour le jeu d'échecs. Cependant, comme les échecs sont un jeu fini, il existe un algorithme informatique, composé d'une très grande table, qui joue aux échecs de manière optimale.

Bien sûr, un tel algorithme ne serait pas pratique. Mais pour certains jeux plus simples, la "valeur" du jeu (quel joueur gagne, le cas échéant) a été déterminée, et un algorithme optimal a été conçu. Un tel jeu est connu comme un jeu résolu .

Le sujet mathématique qui traite (ce qu'on appelle) les jeux combinatoires est la théorie des jeux combinatoires . Les mathématiciens ont développé une méthode récursive pour déterminer la valeur d'un jeu étant donné le graphique du jeu, qui inclut toutes les positions et mouvements autorisés. Vous devriez pouvoir trouver une description de cet algorithme dans l'entrée Wikipédia ou dans toutes les notes de cours sur le sujet.

Tout d'abord, les bons algorithmes d'échecs vont au-delà de 1 ou 2 niveaux. Plutôt que d'utiliser une recherche d'arbre naïve, ils effectuent un élagage alpha-bêta pour réduire le nombre d'options à considérer. Notez que pour les ouvertures et les jeux de fin, une grande base de données de mouvements est utilisée car elle a de meilleures performances que la recherche dans les arbres, qui est utilisée au milieu du jeu.

A la question: ce que vous demandez, je crois, c'est "Les échecs sont-ils résolubles ?". En théorie, c'est le cas, bien que les opinions divergent sur la question de savoir si ce résultat sera réalisable de sitôt. Checkers a été résolu en 2007 par exemple, mais a beaucoup moins de positions (autour de la racine carrée du nombre d'échecs). Voir l'article Wikipedia pour plus d'informations.

Soit dit en passant, les meilleures IA d'échecs actuelles battent ou tirent presque toujours avec des champions du monde; donc bien qu'ils ne soient pas actuellement parfaits, les algorithmes sont au moins assez bons!

En principe, les échecs peuvent être résolus comme n'importe quel autre jeu. Cependant, comme les autres réponses l'ont souligné, cela ne devrait pas se produire de sitôt.

Edit: il a été souligné dans les commentaires que [1] est un canular donc sautez le reste de cette réponse.

Cela dit, il y a eu récemment des développements dans cette direction. [1] prétend avoir montré que l'ouverture d'échecs appelée King's Gambit est résolue : il n'y a qu'un seul coup qui tire pour les Blancs, tandis que tous les autres coups d'ouverture mènent à une victoire pour les Noirs. Notez que [1] n'a pas exploré l'arborescence du jeu en profondeur, mais prétend que ces résultats sont valables avec une forte probabilité.

[1] http://chessbase.com/newsdetail.asp?newsid=8047

Qu'il soit possible de toujours gagner une partie d'échecs ou non dépend des règles du jeu. Cependant, il existe une technique / algorithme nommé Minimax (pour plus de détails, consultez https://en.wikipedia.org/wiki/Minimax ). L'algorithme consiste à essayer de prédire quel joueur a le dessus dans différents scénarios avec une fonction récursive. Voici une explication claire de la façon dont cela fonctionne avec un jeu plus simple: Tic-tac-toe https://www.neverstopbuilding.com/blog/2013/12/13/tic-tac-toe-understanding-the-minimax-algorithm13 .

ajoutera une autre réponse qui met l'accent sur l'espace d'état massif, pas vraiment conceptualisé dans la question ou souligné dans d'autres réponses. doit être en désaccord avec votre prémisse:

Disons que nous avons la puissance de calcul pour développer un algorithme qui prédit tous les mouvements possibles de l'adversaire dans une partie d'échecs.

voir info sur le shannons 1950 paper, "Programming a Computer for Playing Chess" qui a introduit le domaine du jeu d'échecs / algorithmes sur ordinateur et dont son analyse est fondamentalement inchangée et toujours solide (même par la révolution informatique et la loi de Moores qui ont suivi ). il estime le nombre de coups. son absolument astronomique. dans la gamme de "matériel jamais envisageable même avec des avancées révolutionnaires imprévues".

c'est un fait psychologique documenté [3], probablement l'un des nombreux biais psychologiques [2], que les humains ont du mal à comprendre des nombres de cette ampleur. voir aussi la pensée contrefactuelle . [4] tandis que les supercalculateurs calculent des problèmes massifs, ce n'est incontestablement pas à la portée de tout supercalculateur qui est actuellement construit ou pourrait jamais être construit. (et de nombreux amateurs d'échecs diraient que cette "explosion combinatoire" dans les possibilités de mouvement / position est un aspect intrinsèque de la "saveur" des jeux qui semble être intentionnellement conçue dans le jeu millénaire).

par conséquent, les échecs sont fondamentalement différents de certains jeux qui ont des espaces d'état "résolubles" plus petits [dont il existe des études en informatique et en théorie des jeux, etc.] et, à certains égards, ne peuvent pas être évalués dans ce cadre.

$10^{123}$$4×10^{79}$$10^{81}$

maintenant, cela dit, il est concevable (mais peu probable) qu'il puisse y avoir des informations théoriques sur le jeu qui pourraient être utilisées pour tailler l'espace de recherche de manière substantielle. cela s'est produit depuis 1950, mais pas vraiment d'une manière fondamentalement révolutionnaire.

voir également

[1] quelle est la complexité de calcul pour résoudre les échecs, tcs.se

[2] Les préjugés humains dans le jugement et la prise de décision

[3] Les étudiants en psychologie publient des recherches sur la conceptualisation des nombres

[4] pensée contrefactuelle