Existe-t-il un algorithme parfait pour les échecs? [fermé]

109

J'étais récemment dans une discussion avec une personne non codeur sur les possibilités des ordinateurs d'échecs. Je ne connais pas bien la théorie, mais je pense en savoir suffisamment.

J'ai fait valoir qu'il ne pouvait pas exister une machine de Turing déterministe qui gagnait toujours ou se bloquait aux échecs. Je pense que, même si vous recherchez tout l'espace de toutes les combinaisons de coups de player1 / 2, le coup unique que l'ordinateur décide à chaque étape est basé sur une heuristique. Étant basé sur une heuristique, il ne bat pas nécessairement TOUS les mouvements que l'adversaire pourrait faire.

Mon ami pensait, au contraire, qu'un ordinateur gagnerait ou égalerait toujours s'il ne faisait jamais un mouvement «d'erreur» (comment définissez-vous cela?). Cependant, étant un programmeur qui a pris CS, je sais que même vos bons choix - étant donné un adversaire avisé - peuvent vous forcer à faire des "erreurs" à la fin. Même si vous savez tout, votre prochain coup est avide de faire correspondre une heuristique.

La plupart des ordinateurs d'échecs essaient de faire correspondre une éventuelle fin de partie à la partie en cours, qui est essentiellement une trace de programmation dynamique. Encore une fois, la fin de partie en question est évitable.

Edit: Hmm ... on dirait que j'ai ébouriffé des plumes ici. C'est bon.

En y repensant, il semble qu'il n'y a pas de problème théorique à résoudre un jeu fini comme les échecs. Je dirais que les échecs sont un peu plus compliqués que les dames en ce sens qu'une victoire n'est pas nécessairement due à l'épuisement numérique des pièces, mais par un partenaire. Mon affirmation originale est probablement fausse, mais là encore je pense avoir souligné quelque chose qui n'est pas encore prouvé de manière satisfaisante (formellement).

Je suppose que mon expérience de pensée était que chaque fois qu'une branche dans l'arbre est prise, alors l'algorithme (ou les chemins mémorisés) doit trouver un chemin vers un compagnon (sans être accouplé) pour toute branche possible sur les mouvements de l'adversaire. Après la discussion, j'achèterai que compte tenu de plus de mémoire que nous ne pouvons en rêver, tous ces chemins pourraient être trouvés.

Survolé
la source
1
+1: excellent sujet. Cependant, je pense que cela devrait être wiki comme le démontre la variété et le volume des réponses.
IAbstract
1
"pense que j'ai signalé quelque chose qui n'est pas encore prouvé de manière satisfaisante"? Qu'avez-vous souligné qui n'a pas été prouvé officiellement?
S.Lott
2
Ack! comment peut-il y avoir 20 réponses différentes à une question aussi noire et blanche! (sans jeu de mots).
Peter Recore le
5
Je suis moi aussi étonné du nombre de personnes qui publient leurs réponses spéculatives sans savoir que la réponse a en fait été déterminée mathématiquement - réponse dans le sens où il a été prouvé que les échecs ont une solution - il n'est tout simplement pas pratique de la calculer.
DJClayworth
3
Cela me rappelle la blague sur l'ordinateur parfait pour jouer aux échecs. Jouant au blanc, il pense et pense et pense et puis .... démissionne!

Réponses:

104

"J'ai fait valoir qu'il ne pouvait pas exister une machine de Turing déterministe qui gagnait toujours ou se bloquait aux échecs."

Tu n'as pas tout à fait raison. Il peut y avoir une telle machine. Le problème est l'immensité de l'espace d'états qu'il faudrait rechercher. C'est fini, c'est juste VRAIMENT gros.

C'est pourquoi les échecs retombent sur l'heuristique - l'espace d'états est trop grand (mais fini). Énumérer même - et encore moins rechercher chaque mouvement parfait le long de chaque parcours de chaque jeu possible - serait un très, très gros problème de recherche.

Les ouvertures sont programmées pour vous amener à un milieu de partie qui vous donne une position «forte». Pas un résultat connu. Même les parties de fin - lorsqu'il y a moins de pièces - sont difficiles à énumérer pour déterminer le meilleur coup suivant. Techniquement, ils sont finis. Mais le nombre d'alternatives est énorme. Même un roi 2 tours + a quelque chose comme 22 coups suivants possibles. Et s'il faut 6 coups pour s'accoupler, vous regardez 12 855 002 631 049 216 coups.

Faites le calcul sur les mouvements d'ouverture. Bien qu'il n'y ait qu'environ 20 coups d'ouverture, il y a environ 30 secondes, donc au troisième coup, nous examinons 360000 états de jeu alternatifs.

Mais les parties d'échecs sont (techniquement) finies. Énorme, mais fini. Il y a des informations parfaites. Il y a des états de début et de fin définis, il n'y a pas de tirage au sort ou de jet de dés.

S.Lott
la source
22
Toutes les finales de 6 pièces ou moins ont été énumérées et résolues. Voir tablebase et bitbase ici: en.wikipedia.org/wiki/Tablebase . Par exemple, il y a une fin de partie KQNKRBN où 517 coups sont nécessaires pour forcer un compagnon! Mais le nombre total de parties d'échecs est d'environ (10 ^ (10 ^ 50)).
HTTP 410
2
Script pour gagner est une chose. Énumérer de manière exhaustive est une chose différente. Dans tous les cas, l'information est parfaite - tout est connu - le jeu est déterministe par définition.
S.Lott
11
@RoadWarrior: pas d'accord. L'aléatoire s'applique à la météo. Dieu lance les dés. L'aléatoire ne s'applique pas aux échecs - par définition. Les échecs ont des informations complètes. La météo a des effets quantiques - elle ne peut pas être complète.
S.Lott
3
Ce qui rend le temps difficile à prévoir, ce sont les facteurs chaotiques non linéaires, et non les effets quantiques. Avec suffisamment de puissance de calcul et de connaissances, nous pourrions en théorie créer une prévision météorologique "correcte".
HTTP 410
3
@monojohnny: Les règles interdisent trois répétitions de la même position. Les échecs sont simplement finis. C'est grand mais fini.
S.Lott
72

Je ne sais presque rien de ce qui a été découvert sur les échecs. Mais en tant que mathématicien, voici mon raisonnement:

Premièrement, nous devons nous rappeler que Blanc doit commencer et peut-être que cela lui donne un avantage; peut-être que cela donne un avantage aux noirs.

Supposons maintenant qu'il n'y ait pas de stratégie parfaite pour Black qui lui permette de toujours gagner / bloquer. Cela implique que peu importe ce que fait les Noirs, il existe une stratégie que les Blancs peuvent suivre pour gagner. Attendez une minute - cela signifie qu'il y a une stratégie parfaite pour les Blancs!

Cela nous dit qu'au moins l' un des deux joueurs n'ont une stratégie parfaite qui permet à ce joueur toujours gagner ou dessiner.

Il n'y a donc que trois possibilités:

  • Blanc peut toujours gagner s'il joue parfaitement
  • Le noir peut toujours gagner s'il joue parfaitement
  • Un joueur peut gagner ou faire match nul s'il joue parfaitement (et si les deux joueurs jouent parfaitement, ils sont toujours dans l'impasse)

Mais lequel de ceux-ci est réellement correct, nous ne le saurons peut-être jamais.

La réponse à la question est oui : il doit y avoir un algorithme parfait pour les échecs, au moins pour l'un des deux joueurs.

Artelius
la source
2
+1, c'est une très bonne façon de l'expliquer. Je ne peux pas croire que je n'y ai jamais pensé!
Zifre
2
Pourquoi le noir n'ayant pas de stratégie parfaite implique-t-il que le blanc a une stratégie parfaite? Et les deux joueurs n'ayant pas de stratégie parfaite? Si votre implication était vraie, ne serait-elle pas vraie pour chaque partie à 2 joueurs, ce qui signifie que chaque partie a une stratégie parfaite?
John M Naglick
8
@john: Parce que les échecs ont des informations parfaites et pas d'éléments aléatoires (contrairement à beaucoup d'autres jeux à 2 joueurs), le seul moyen pour qu'aucune stratégie parfaite n'existe pour les noirs serait que les blancs puissent forcer une victoire malgré toute tentative de noir - en d'autres termes, s'il existe une stratégie parfaite pour le blanc.
Dave Sherohman
2
En fait, cette logique ne tient pas toujours , mais est-ce vrai dans ce cas.
BlueRaja - Danny Pflughoeft
4
@john "pourquoi tant de discussions ici" - parce que certaines personnes ne connaissent pas la réponse, mais postent quand même ici.
DJClayworth
30

Il a été prouvé pour le jeu de dames qu'un programme peut toujours gagner ou égaler la partie. Autrement dit, il n'y a pas de choix de mouvements qu'un joueur peut faire qui forcent l'autre joueur à perdre.

Les chercheurs ont passé près de deux décennies à parcourir les 500 milliards de milliards de positions de pions possibles, ce qui est encore une fraction infiniment petite du nombre de positions d'échecs, soit dit en passant. L'effort des contrôleurs incluait les meilleurs joueurs, qui ont aidé l'équipe de recherche à programmer les règles empiriques des contrôleurs dans un logiciel qui classait les mouvements comme réussis ou non. Ensuite, les chercheurs ont laissé le programme fonctionner, sur une moyenne de 50 ordinateurs par jour. Certains jours, le programme fonctionnait sur 200 machines. Tandis que les chercheurs surveillaient les progrès et peaufinaient le programme en conséquence. En fait, Chinook a battu les humains pour remporter le championnat du monde des dames en 1994.

Oui, vous pouvez résoudre les échecs, non, vous ne le ferez pas de si tôt.

BCS
la source
6
«[V] ous ne le sera pas bientôt» est un euphémisme. Outre la limite de la durée attendue de l'univers, vous avez un problème de stockage - le nombre d'états dans Chess dépasse de loin les 500 milliards de milliards de dames; en fait, il dépasse le nombre de particules dans l'univers.
Michael Dorfman
30
"[...] en fait, il dépasse le nombre de particules dans l'univers.". Tant qu'il ne dépasse pas le nombre d'états des particules dans l'univers, il y a encore de l'espoir ;-)
Carsten
1
que se passe-t-il quand le programme qui force toujours l'adversaire à perdre joue contre lui-même ????
John Demetriou
1
@BCS hmm, que se passe-t-il s'il y a une prédiction dans laquelle si je joue en tant que deuxième joueur et que l'autre utilise la même heuristique que moi, suivez cette heuristique pour gagner et si le premier joueur a une heuristique similaire ???? ?
John Demetriou
1
ce que je dis, c'est que s'il existe un algorithme parfait et que les deux joueurs l'ont, il y aura un nombre indéfini de probabilités que l'algorithme puisse changer pour qu'il soit parfait
John Demetriou
15

Ce n'est pas une question sur les ordinateurs mais uniquement sur le jeu d'échecs.

La question est: existe-t-il une stratégie de sécurité pour ne jamais perdre la partie? Si une telle stratégie existe, alors un ordinateur qui sait tout peut toujours l'utiliser et ce n'est plus une heuristique.

Par exemple, le jeu tic-tac-toe se joue normalement sur la base d'heuristiques. Mais, il existe une stratégie de sécurité intégrée. Quel que soit le mouvement de l'adversaire, vous trouvez toujours un moyen d'éviter de perdre la partie, si vous le faites dès le début.

Vous auriez donc besoin de prouver qu'une telle stratégie existe ou non pour les échecs également. C'est fondamentalement la même chose, juste l'espace des mouvements possibles est beaucoup plus grand.

ypnos
la source
Alors, qui a eu envie de voter contre ma réponse? Y a-t-il quelque chose qui ne va pas? Envie de vous mettre en avant?
ypnos
@ypnos, je n'ai pas du tout voté pour votre réponse. Je viens de dire de ne pas laisser les votants au hasard vous abattre. Vous avez gagné 30 répétitions et n'en avez perdu que 1. Aussi, +1;)
mmcdole
1
Plusieurs raisons de voter contre. 1) On sait qu'il existe un algorithme pour résoudre le jeu, c'est juste que l'algorithme n'est pas pratique à calculer en utilisant n'importe quelle technologie imaginable. 2) Résoudre le jeu n'implique PAS qu'il existe une stratégie de sécurité intégrée. Tic-tac-toe est résolu, mais il n'y a pas de stratégie pour le deuxième joueur qui évite une perte.
DJClayworth
2
"Ce n'est pas une question sur les ordinateurs mais seulement sur le jeu d'échecs." Eh bien, l'informatique ne concerne pas réellement les ordinateurs. Ils ne sont qu'un outil. L'informatique fonctionne sans ordinateur.
Janus Troelsen
1
C'est en fait une question sur les ordinateurs, car la question est de savoir si une machine de Turing (= ordinateur) pourrait exister, qui résout les échecs.
SDwarfs
14

J'arrive à ce fil très tard, et que vous avez déjà réalisé certains des problèmes. Mais en tant qu'ancien maître et ancien programmeur d'échecs professionnel, j'ai pensé que je pourrais ajouter quelques faits et chiffres utiles. Il existe plusieurs façons de mesurer la complexité des échecs :

  • Le nombre total de parties d'échecs est d'environ 10 ^ (10 ^ 50). Ce nombre est incroyablement élevé.
  • Le nombre de parties d'échecs de 40 coups ou moins est d'environ 10 ^ 40. C'est toujours un nombre incroyablement élevé.
  • Le nombre de positions d'échecs possibles est d'environ 10 ^ 46.
  • L'arbre de recherche d'échecs complet (numéro de Shannon) est d'environ 10 ^ 123, basé sur un facteur de ramification moyen de 35 et une durée de jeu moyenne de 80.
  • À titre de comparaison, le nombre d'atomes dans l'univers observable est généralement estimé à environ 10 ^ 80.
  • Toutes les finales de 6 pièces ou moins ont été rassemblées et résolues .

Ma conclusion: alors que les échecs sont théoriquement résolubles, nous n'aurons jamais l'argent, la motivation, la puissance de calcul ou le stockage pour le faire.

HTTP 410
la source
3
Allons y. Il faut penser le problème différemment. Ne pensez pas au nombre de jeux, car les transpositions et les algorithmes alpha-bêta et autres réduisent énormément cela. Pensez aux positions du plateau (10 ^ 60) ou aux combinaisons de pièces d'échecs (100 millions). Avec l'informatique quantique, c'est trivial.
lkessler
2
Alpha-beta dans ce contexte (résoudre les échecs) nécessiterait une fonction d'évaluation parfaite. Il en va de même pour les positions des planches et les combinaisons de pièces. Nous n'avons pas de fonction d'évaluation parfaite, donc l'informatique quantique ne nous aide pas.
HTTP 410
1
Chaque fois que je pense que quelque chose est "trivial", et je suis sûr que personne ne l'a déjà fait, je suis aussi sûr que je me suis trompé au moins une fois.
Dean J
2
@lkessler: Les positions du conseil ne racontent pas toute l'histoire. Au moins une certaine histoire du jeu est nécessaire pour le roque ou la capture en passant ou le tirage en raison du manque de capture ou de mouvement de pion, et toute l'histoire du tirage par répétition. De plus, comme il s'agissait d'un résultat de recherche notable récemment pour un ordinateur quantique au facteur 15, je dirais que rien n'est trivial avec l'informatique quantique pour le moment.
David Thornley
2
À titre de comparaison ici, si vous pouvez générer toutes les positions d'échecs possibles, vous pouvez de manière triviale forcer tout chiffrement avec une clé de 128 bits, puisque 10 ^ 46 équivaut à environ 2 ^ 152 ou 2 ^ 153. Il y a d'excellentes raisons de penser que cela est impossible avant la mort par la chaleur de l'Univers.
David Thornley
9

Certains jeux ont, en fait, été résolus. Tic-Tac-Toe est très facile pour construire une IA qui gagnera ou égalera toujours. Récemment, Connect 4 a également été résolu (et s'est avéré injuste pour le deuxième joueur, car un jeu parfait le fera perdre).

Les échecs, cependant, n'ont pas été résolus, et je ne pense pas qu'il y ait de preuve qu'il s'agit d'un jeu équitable (c'est-à-dire si le jeu parfait aboutit à un match nul). Parlant strictement d'un point de vue théorique cependant, Chess a un nombre fini de configurations de pièces possibles. Par conséquent, l'espace de recherche est fini (quoique incroyablement grand). Par conséquent, une machine de Turing déterministe qui pourrait jouer parfaitement existe. La question de savoir si une personne pourra jamais être construite est cependant une autre question.

Cybis
la source
8

Le bureau moyen de 1000 $ sera capable de résoudre les dames en seulement 5 secondes d'ici 2040 (calculs 5x10 ^ 20).

Même à cette vitesse, il faudrait encore à 100 de ces ordinateurs environ 6,34 x 10 ^ 19 ans pour résoudre les échecs. Pas encore faisable. Pas même proche.

Vers 2080, nos ordinateurs de bureau moyens auront environ 10 ^ 45 calculs par seconde. Un seul ordinateur aura la puissance de calcul pour résoudre les échecs en environ 27,7 heures. Cela sera certainement fait d'ici 2080 tant que la puissance de calcul continuera de croître comme elle l'a fait ces 30 dernières années.

D'ici 2090, il y aura suffisamment de puissance de calcul sur un bureau à 1000 $ pour résoudre les échecs en environ 1 seconde ... donc à cette date, ce sera complètement insignifiant.

Compte tenu de dames a été résolu en 2007, et la puissance de calcul pour le résoudre en 1 seconde d'environ accuseront un retard 33-35 ans, nous pouvons probablement à peu près estimer échecs seront résolus quelque part entre 2055 et 2057. Probablement plus tôt que lorsque plus de puissance de calcul sera disponible (ce qui sera le cas dans 45 ans), on pourra consacrer davantage à des projets comme celui-ci. Cependant, je dirais 2050 au plus tôt et 2060 au plus tard.

En 2060, il faudrait en moyenne à 100 ordinateurs de bureau 3,17 x 10 ^ 10 ans pour résoudre les échecs. Réalisez que j'utilise un ordinateur à 1000 $ comme référence, alors que des systèmes plus grands et des supercalculateurs seront probablement disponibles car leur rapport prix / performances s'améliore également. En outre, leur ordre de grandeur de la puissance de calcul augmente à un rythme plus rapide. Supposons qu'un supercalculateur puisse maintenant effectuer 2,33 x 10 ^ 15 calculs par seconde et un ordinateur à 1000 $ environ 2 x 10 ^ 9. Par comparaison, il y a 10 ans, la différence était de 10 ^ 5 au lieu de 10 ^ 6. D'ici 2060, la différence d'ordre de grandeur sera probablement de 10 ^ 12, et même cela pourrait augmenter plus rapidement que prévu.

Cela dépend en grande partie du fait que nous, en tant qu'êtres humains, avons la volonté de résoudre les échecs, mais la puissance de calcul le rendra réalisable à cette époque (tant que notre rythme continue).

Sur une autre note, le jeu de Tic-Tac-Toe, qui est beaucoup, beaucoup plus simple, a 2.653.002 calculs possibles (avec un tableau ouvert). La puissance de calcul pour résoudre Tic-Tac-Toe en environ 2,5 secondes (1 million de calculs par seconde) a été atteinte en 1990.

En reculant, en 1955, un ordinateur avait le pouvoir de résoudre Tic-Tac-Toe en environ 1 mois (1 calcul par seconde). Encore une fois, cela est basé sur ce que 1000 $ vous rapporteraient si vous pouviez le mettre dans un ordinateur (un bureau de 1000 $ n'existait évidemment pas en 1955), et cet ordinateur aurait été consacré à la résolution de Tic-Tac-Toe .... ce qui ce n'était tout simplement pas le cas en 1955. Le calcul était coûteux et n'aurait pas été utilisé à cette fin, même si je ne crois pas qu'il y ait une date où Tic-Tac-Toe a été jugé "résolu" par un ordinateur, mais je suis sûr qu'il est en retard sur la puissance de calcul réelle.

De plus, sachez que 1000 $ en 45 ans vont valoir environ 4 fois moins que maintenant, donc beaucoup plus d'argent peut être investi dans des projets comme celui-ci, tandis que la puissance de calcul continuera de devenir moins chère.

Franc
la source
9
"Saviez-vous que les ventes de disques disco ont augmenté de 400% pour l'année se terminant en 1976? Si ces tendances continuent ... AAY!" - Disco Stu
Jeremy Friesner
2
La loi de Moore - la puissance de calcul double tous les 18 mois - est susceptible d'échouer vers 2015. Ou la conception des processeurs informatiques devra être radicalement différente. Donc 2080 n'est pas un objectif réaliste.
Philip Smith
3
@Philip: Les vitesses d'horloge des processeurs des ordinateurs de bureau n'ont augmenté que légèrement depuis 2003, et les améliorations depuis lors ont principalement consisté en une augmentation du cache et des cœurs multiples. Étant donné qu'un processeur 3 GHz a un cycle d'horloge dans le temps qu'il faut à la lumière pour se déplacer de 4 pouces / 10 cm, on ne peut pas s'attendre à ce que la vitesse d'horloge augmente indéfiniment. De plus, le parallélisme est généralement difficile. La projection d'une augmentation exponentielle pendant cinquante ans lorsqu'elle a commencé à s'effondrer il y a sept ans ne semble pas être une valeur sûre.
David Thornley
1
@David - tout cela est vrai. Mais manque le point. Si vous faites la moitié de la taille des composants sur la puce, les électrons en font deux fois plus à la même vitesse d'horloge. C'est ce qui alimente la loi de Moore.
Philip Smith
3
@Philip: La réduction de moitié ne peut bien sûr pas durer éternellement. Un atome de silicium mesure environ un quart de nanomètre de diamètre et la fabrication de puces est déjà réduite à des dizaines de nanomètres. De plus, aux niveaux quantiques, les particules obéissent à des règles statistiques, pas à des règles absolues, il est donc nécessaire de déplacer suffisamment d'électrons à la fois pour invoquer la loi des grands nombres. Jusqu'à présent, la loi de Moore se situe quelque part entre une loi et une prophétie auto-réalisatrice, mais cela se termine assez tôt.
David Thornley
7

Il est en fait possible pour les deux joueurs d'avoir des stratégies gagnantes dans des jeux infinis sans un bon ordre; cependant, les échecs sont bien ordonnés. En fait, en raison de la règle des 50 coups, il y a une limite supérieure au nombre de coups qu'une partie peut avoir, et donc il n'y a qu'une infinité de parties d'échecs possibles (qui peuvent être énumérées pour résoudre exactement ... théoriquement, au moins :)

BlueRaja - Danny Pflughoeft
la source
4
Techniquement, la règle des cinquante coups, comme la répétition de trois coups (qui limite également les choses - il y a un nombre fini de positions possibles, donc multiplier ce nombre par trois nous donne une limite supérieure) ne provoque pas de match nul. Au contraire, cela donne à l'un ou l'autre des joueurs la possibilité de réclamer un match nul. Habituellement, le joueur perdant le fera, mais ce n'est pas obligatoire. Par conséquent, ce qui suit est un jeu entièrement légal: 1. Nc3 Nc6 2. Nb1 Nb8 3. Nc3 Nc6 4. Nb1 Nb8, répété à jamais. Et si je ne me trompe pas, il n'a pas été prouvé que ce n'est pas le résultat de deux algorithmes parfaits jouant en blanc et en noir.
Lenoxus
6

Votre fin de l'argument est étayée par la façon dont les programmes d'échecs modernes fonctionnent maintenant . Ils fonctionnent de cette façon parce qu'il est trop gourmand en ressources pour coder un programme d'échecs pour fonctionner de manière déterministe. Ils ne fonctionneront pas nécessairement toujours de cette façon. Il est possible que les échecs soient un jour résolus , et si cela se produit, il sera probablement résolu par un ordinateur.

Bill le lézard
la source
5

Pour mémoire, il existe des ordinateurs qui peuvent gagner ou égaler aux dames . Je ne sais pas si la même chose pourrait être faite pour les échecs. Le nombre de coups est beaucoup plus élevé. De plus, les choses changent parce que les pièces peuvent se déplacer dans n'importe quelle direction, pas seulement en avant et en arrière. Je pense, bien que je ne sois pas sûr, que les échecs sont déterministes, mais qu'il y a juste trop de coups possibles pour qu'un ordinateur puisse actuellement déterminer tous les coups dans un laps de temps raisonnable.

Kibbee
la source
1
Cela peut être fait, mais est-ce que cela peut être fait sur un ordinateur que nous verrons probablement jamais?
BCS
1
Probablement pas de notre vivant. Toutes les recherches vraiment intéressantes dans le domaine se font dans le jeu Go. :)
Bill the Lizard
La plupart des enfants de 6 ans de l'IIRC peuvent être n'importe quel ordinateur chez Go.
BCS
2
@BCS: Plus maintenant. Les meilleurs programmes Go battent maintenant les joueurs de niveau dan (professionnel).
Bill the Lizard
1
@BlueRaja: C'était en 2008. Je ne sais pas quel est le record actuel, mais MoGo a battu les pros avec 6 et 7 pierres sur un 19x19. ireport.cnn.com/docs/DOC-214010
Bill the Lizard
5

Je pense que tu es mort. Des machines comme Deep Blue et Deep Thought sont programmées avec un certain nombre de jeux prédéfinis et des algorithmes intelligents pour analyser les arbres jusqu'aux extrémités de ces jeux. Il s’agit, bien entendu, d’une simplification excessive. Il y a toujours une chance de «battre» l'ordinateur au cours d'une partie. J'entends par là faire un mouvement qui force l'ordinateur à faire un mouvement qui n'est pas optimal (quoi que ce soit). Si l'ordinateur ne peut pas trouver le meilleur chemin avant la limite de temps pour le déplacement, il pourrait très bien faire une erreur en choisissant l'un des chemins les moins désirables.

Il existe une autre classe de programmes d'échecs qui utilise un véritable apprentissage automatique, ou une programmation génétique / des algorithmes évolutifs. Certains programmes ont évolué et utilisent des réseaux de neurones, et al, pour prendre des décisions. Dans ce type de cas, j'imagine que l'ordinateur pourrait faire des "erreurs", mais finir par remporter une victoire.

Il existe un livre fascinant sur ce type de médecin généraliste appelé Blondie24 que vous pourriez lire. Il s'agit de dames, mais cela pourrait s'appliquer aux échecs.

Jason Jackson
la source
C'est ainsi que vous battez les ordinateurs d'aujourd'hui aux échecs. Demain sera mieux. Je suis cependant d'accord avec vous que Blondie24 est fascinant.
Bill the Lizard
Voté de nouveau. Ce message ne mérite pas une note négative.
Cybis
Malheureusement, le problème des jeux d'échecs est trop important pour que l'apprentissage automatique fonctionne. Ils ne pourraient jamais avoir un programme d’apprentissage d’échecs pour jouer même de façon novatrice sans erreurs. Les heuristiques sont meilleures. Mais Brute Force était encore mieux. Le domaine de l'apprentissage automatique n'a appris que de son échec aux échecs.
lkessler
Les programmes d'échecs ne font pas d'erreurs à court terme, et les meilleurs programmes jouent mieux que les champions du monde. Je pense que la dernière version de Rybka 64 bits est évaluée comme 3200 ELO
Alex
5

D'après la théorie des jeux, sur laquelle porte cette question, la réponse est oui, les échecs peuvent être parfaitement joués. L'espace de jeu est connu / prévisible et oui si vous aviez les ordinateurs quantiques de votre petit-enfant, vous pourriez probablement éliminer toutes les heuristiques.

Vous pouvez écrire une machine tic-tac-toe parfaite de nos jours dans n'importe quel langage de script et elle fonctionnerait parfaitement en temps réel.

Othello est un autre jeu auquel les ordinateurs actuels peuvent facilement jouer parfaitement, mais la mémoire et le processeur de la machine auront besoin d'un peu d'aide

Les échecs sont théoriquement possibles mais pas pratiquement possibles (en 2008)

i-Go est délicat, son espace de possibilités dépasse le nombre d'atomes dans l'univers, il nous faudra donc peut-être un certain temps pour créer une machine i-Go parfaite.

Robert Gould
la source
Ce n'est pas la théorie des jeux
BlueRaja - Danny Pflughoeft
4
Techniquement, c'est la théorie des jeux combinatoires.
Anaphory
5

Les échecs sont un exemple de jeu matriciel qui, par définition, a un résultat optimal (pensez à l'équilibre de Nash). Si les joueurs 1 et 2 effectuent chacun des mouvements optimaux, un certain résultat sera TOUJOURS atteint (s'il s'agit d'une victoire-égalité-perte est encore inconnue).

Jon Smock
la source
5

En tant que programmeur d'échecs des années 1970, j'ai définitivement une opinion à ce sujet. Ce que j'ai écrit il y a environ 10 ans est toujours fondamentalement vrai aujourd'hui:

"Travail inachevé et défis pour les programmeurs d'échecs"

À l'époque, je pensais que nous pourrions résoudre les échecs de manière conventionnelle, si cela est fait correctement.

Checkers a été résolu récemment (Yay, Université de l'Alberta, Canada !!!) mais cela a été effectivement fait Brute Force. Pour faire des échecs de manière conventionnelle, vous devrez être plus intelligent.

Sauf, bien sûr, l' informatique quantique devienne une réalité. Si c'est le cas, les échecs seront résolus aussi facilement que Tic-Tac-Toe.

Au début des années 1970, dans Scientific American, une courte parodie a retenu mon attention. C'était une annonce que le jeu d'échecs avait été résolu par un ordinateur d'échecs russe. Il avait déterminé qu'il y avait un coup parfait pour les blancs qui assurerait une victoire avec un jeu parfait des deux côtés, et ce coup est: 1. a4!

Lkessler
la source
3

Beaucoup de réponses ici font ressortir les points importants de la théorie des jeux:

  1. Les échecs sont un jeu fini et déterministe avec des informations complètes sur l'état du jeu
  2. Vous pouvez résoudre un jeu fini et identifier une stratégie parfaite
  3. Les échecs sont cependant assez gros pour que vous ne puissiez pas le résoudre complètement avec une méthode de force brute

Cependant ces observations passent à côté d'un point pratique important: il n'est pas nécessaire de résoudre parfaitement le jeu complet pour créer une machine imbattable .

Il est en fait fort probable que vous puissiez créer une machine d'échecs imbattable (c'est-à-dire qu'elle ne perdra jamais et forcera toujours une victoire ou un match nul) sans chercher ne serait-ce qu'une infime partie de l'espace d'états possible.

Les techniques suivantes par exemple réduisent toutes massivement l'espace de recherche requis:

  • Techniques d'élagage des arbres comme Alpha / Beta ou MTD-f réduisent déjà massivement l'espace de recherche
  • Position gagnante prouvée. De nombreuses fins entrent dans cette catégorie: vous n'avez pas besoin de rechercher KR vs K par exemple, c'est une victoire avérée. Avec un peu de travail, il est possible de prouver beaucoup plus de victoires garanties.
  • Des victoires presque certaines - pour un jeu «assez bon» sans aucune erreur stupide (disons à propos de ELO 2200+?) De nombreuses positions d'échecs sont des victoires presque certaines, par exemple un avantage matériel décent (par exemple un chevalier supplémentaire) sans avantage de position compensatoire. Si votre programme peut forcer une telle position et a une heuristique suffisamment bonne pour détecter un avantage de position, il peut supposer en toute sécurité qu'il gagnera ou au moins dessinera avec une probabilité de 100%.
  • Heuristique de recherche arborescente - avec une reconnaissance de formes suffisamment bonne, vous pouvez rapidement vous concentrer sur le sous-ensemble pertinent de mouvements «intéressants». C'est ainsi que jouent les grands maîtres humains, donc ce n'est clairement pas une mauvaise stratégie ..... et nos algorithmes de reconnaissance de formes s'améliorent constamment
  • Évaluation des risques - une meilleure conception du «risque» d'une position permettra une recherche beaucoup plus efficace en concentrant la puissance de calcul sur des situations où le résultat est plus incertain (il s'agit d'une extension naturelle de la recherche de quiescence )

Avec la bonne combinaison des techniques ci-dessus, je serais à l'aise d'affirmer qu'il est possible de créer une machine à jouer aux échecs "imbattable". Nous ne sommes probablement pas trop loin de la technologie actuelle.

Notez que c'est presque certainement plus difficile à prouver que cette machine ne peut pas être battue. Ce serait probablement quelque chose comme l'hypothèse de Reimann - nous serions presque sûrs qu'il joue parfaitement et aurait des résultats empiriques montrant qu'il n'a jamais perdu (y compris quelques milliards de tirages consécutifs contre lui-même), mais nous n'aurions pas la capacité de le faire. prouve le.

Note supplémentaire concernant la "perfection":

Je fais attention à ne pas décrire la machine comme "parfaite" au sens de la théorie des jeux car cela implique des conditions supplémentaires inhabituellement fortes, telles que:

  • Toujours gagner dans toutes les situations où il est possible de forcer une victoire, quelle que soit la complexité de la combinaison gagnante. Il y aura des situations à la limite entre victoire / nul où cela est extrêmement difficile à calculer parfaitement.
  • Exploiter toutes les informations disponibles sur les imperfections potentielles dans le jeu de votre adversaire, par exemple en déduisant que votre adversaire pourrait être trop gourmand et en jouant délibérément une ligne légèrement plus faible que d'habitude au motif qu'elle a un plus grand potentiel pour inciter votre adversaire à faire une erreur. Contre des adversaires imparfaits, il peut en fait être optimal de faire une défaite si vous estimez que votre adversaire ne remarquera probablement pas la victoire forcée et que cela vous donne une probabilité plus élevée de gagner vous-même.

La perfection (en particulier compte tenu des adversaires imparfaits et inconnus) est un problème beaucoup plus difficile que d'être simplement imbattable.

Mikera
la source
Avoir des adversaires imparfaits n'est pas un vrai problème. Cela permet simplement au joueur parfait de gagner / dessiner (quel que soit le résultat parfait) en moins de coups. Un mouvement optimal dans chaque position est toujours meilleur ou égal aux autres mouvements possibles (par définition). Ainsi, un coup sous-optimal permet à votre adversaire d'atteindre un état final optimal (victoire / nul) plus tôt ou permet même de forcer un meilleur résultat. Par exemple, si les noirs perdraient toujours si les blancs jouent parfaitement, il est possible que les noirs gagnent, si les blancs ne jouent qu'un seul coup sous-optimal. Mais oui, cela devrait augmenter un peu la complexité de l'analyse.
SDwarfs
@Stefan - les adversaires imparfaits sont un énorme problème si vous vous souciez du jeu optimal . En particulier, vous pouvez concevoir des situations où il est en fait préférable de jouer un coup perdant (c'est-à-dire un coup où un adversaire parfait vous battrait définitivement) si vous savez que la probabilité que votre adversaire fasse une erreur est suffisamment élevée.
mikera
à mon avis, le jeu optimal signifie obtenir le meilleur résultat possible sans risque. Votre adversaire est probablement «faible» mais lorsque vous jouez ce coup perdu, il / elle peut malheureusement jouer un bon coup par accident. Se soucier des adversaires sous-optimaux n'est pertinent que s'il y a seulement le choix entre des coups perdants où l'un d'eux a plus de chances d'une erreur de l'adversaire (jouant sous-optimal) conduisant réellement à un match nul ou à une victoire.
SDwarfs
1
Ce n'est pas la définition habituelle de l'optimal en théorie des jeux. Optimal signifie généralement maximiser le résultat attendu . Dans ce cas, un joueur optimal acceptera certains risques à condition qu'il obtienne un meilleur résultat en moyenne .
mikera
Dans ce cas, vous avez tout à fait raison!
SDwarfs
2

si vous recherchez tout l'espace de toutes les combinaisons de coups de joueur1 / 2, le coup unique que l'ordinateur décide à chaque étape est basé sur une heuristique.

Il y a là deux idées concurrentes. L'un est que vous recherchez tous les mouvements possibles, et l'autre est que vous décidez en fonction d'une heuristique. Une heuristique est un système permettant de faire une bonne estimation. Si vous recherchez tous les mouvements possibles, vous ne devinez plus.

Joel Coehoorn
la source
En fait, la citation est juste. Les programmes examinent tous les mouvements possibles des deux côtés dans la position actuelle et utilisent l'heuristique pour trouver un bon mouvement pour conduire le jeu dans la direction d'une position favorable pour l'ordinateur.
Bill the Lizard
1
Non, ils ne regardent pas tous les mouvements possibles. Ils utilisent une heuristique de déplacement nul pour élaguer l'arbre.
Alex
2

"Y a-t-il un algorithme parfait pour les échecs?"

Oui il y a. C'est peut-être pour White de toujours gagner. C'est peut-être pour Black de toujours gagner. C'est peut-être pour les deux de toujours se nouer au moins. Nous ne savons pas lequel, et nous ne le saurons jamais, mais cela existe certainement.

Voir également

lubrifiants polygènes
la source
1
Étant un joueur d'échecs assez décent et ayant étudié le problème de manière approfondie au fil des ans, je suis sûr à 99,9% que la stratégie du préfet aux échecs pour les deux joueurs aboutit à un match nul (comme cela a été prouvé avec les dames). Il existe également des preuves que, à mesure que la force du joueur augmente, le pourcentage de tirages augmente également.
mikera
2

J'ai trouvé cet article de John MacQuarrie qui fait référence au travail du "père de la théorie des jeux" Ernst Friedrich Ferdinand Zermelo . Il tire la conclusion suivante:

Aux échecs, soit les blancs peuvent forcer une victoire, soit les noirs peuvent forcer une victoire, ou les deux côtés peuvent forcer au moins un match nul.

La logique me semble saine.

Ben Gartner
la source
2

C'est parfaitement résoluble.

Il y a 10 ^ 50 positions impaires. Chaque position, à mon avis, nécessite un minimum de 64 octets ronds à stocker (chaque carré a: 2 bits d'affiliation, 3 bits de pièce). Une fois qu'elles sont rassemblées, les positions qui sont des coéquipiers peuvent être identifiées et les positions peuvent être comparées pour former une relation, montrant quelles positions mènent à d'autres positions dans un grand arbre de résultats.

Ensuite, le programme n'a besoin que de trouver les racines d'échec et mat les plus basses d'un seul côté, si une telle chose existe. En tout cas, Chess a été assez simplement résolu à la fin du premier paragraphe.

Salomon
la source
1

Je ne suis convaincu qu'à 99,9% par l'affirmation selon laquelle la taille de l'espace d'états rend impossible l'espoir d'une solution.

Bien sûr, 10 ^ 50 est un nombre incroyablement grand. Appelons la taille de l'espace d'états n.

Quelle est la limite du nombre de coups dans la partie la plus longue possible? Puisque tous les jeux se terminent par un nombre fini de coups, il existe une telle limite, appelez-la m.

À partir de l'état initial, ne pouvez-vous pas énumérer tous les n mouvements dans l'espace O (m)? Bien sûr, cela prend du temps O (n), mais les arguments de la taille de l'univers ne traitent pas directement de cela. L'espace O (m) pourrait même ne pas être beaucoup. Pour l'espace O (m), vous ne pouviez pas non plus suivre, au cours de cette traversée, si la poursuite d'un état le long du chemin que vous parcourez mène à EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin ou BlackMayWinOrForceDraw? (Il y a un treillis selon le tour de qui c'est, annotez chaque état de l'histoire de votre parcours avec le treillis se rencontrent.)

À moins que je ne manque quelque chose, c'est un algorithme d'espace O (n) temps / O (m) pour déterminer dans laquelle des catégories possibles les échecs appartiennent. Wikipedia cite une estimation de l'âge de l'univers à environ 10 ^ 60e fois Planck. Sans entrer dans un argument cosmologique, supposons qu'il reste à peu près autant de temps avant la chaleur / le froid / quelle que soit la mort de l'univers. Cela nous oblige à évaluer un mouvement toutes les 10 ^ 10 fois Planck, ou toutes les 10 ^ -34 secondes. C'est un temps incroyablement court (environ 16 ordres de grandeur plus courts que les temps les plus courts jamais observés). Disons avec optimisme qu'avec une implémentation super-duper-bonne fonctionnant au-dessus de la technologie présente-ou-prévue-non-quantique-P-est-un-sous-ensemble-de-NP, nous pourrions espérer évaluer (prenez un un pas en avant, catégoriser l'état résultant comme un état intermédiaire ou l'un des trois états finaux) à une fréquence de 100 MHz (une fois toutes les 10 ^ -8 secondes). Comme cet algorithme est très parallélisable, cela nous laisse besoin de 10 ^ 26 de ces ordinateurs, soit environ un pour chaque atome de mon corps, ainsi que de la capacité de collecter leurs résultats.

Je suppose qu'il y a toujours une lueur d'espoir pour une solution par force brute. Nous pourrions avoir de la chance et, en explorant un seul des mouvements d'ouverture possibles des blancs, en choisir un avec une répartition bien inférieure à la moyenne et un dans lequel les blancs gagnent ou gagnent ou tirent toujours.

Nous pourrions également espérer réduire quelque peu la définition des échecs et persuader tout le monde que c'est toujours moralement le même jeu. Avons-nous vraiment besoin d'exiger que les positions se répètent 3 fois avant un tirage au sort? Avons-nous vraiment besoin de faire en sorte que les fugitifs démontrent leur capacité à s'échapper pendant 50 coups? Est-ce que quelqu'un comprend même ce qu'est la règle en passant ? ;) Plus sérieusement, avons-nous vraiment besoin de forcer un joueur à bouger (par opposition à dessiner ou à perdre) quand son seul mouvement pour échapper à un échec ou une impasse est un en passant prise ? Pouvons-nous limiter le choix des pièces auxquelles un pion peut être promu si la promotion non-reine souhaitée ne conduit pas à un échec ou un échec immédiat?

Je ne sais pas non plus dans quelle mesure autoriser chaque ordinateur à accéder par hachage à une grande base de données d'états de fin de partie et leurs résultats éventuels (ce qui pourrait être relativement réalisable sur le matériel existant et avec les bases de données de fin de partie existantes) pourrait aider à élaguer la recherche plus tôt. De toute évidence, vous ne pouvez pas mémoriser la fonction entière sans stockage O (n), mais vous pouvez choisir un grand entier et mémoriser autant de fin de partie énumérant à l'envers à partir de chaque état final possible (ou même pas facilement prouvable impossible, je suppose).

Doug McClean
la source
1
Votre m = 5898. Les règles d'échecs de la FIDE définissent que vous devez déplacer un pion ou prendre une pièce (quelque chose qui change irréversiblement le jeu) au moins tous les 50 coups (appelée règle des 50 coups) ou l'un des joueurs peut réclamer un match nul. Il a été calculé que la partie la plus longue possible est de 5898 coups, si les deux joueurs coopèrent et réclament un match nul dès que possible. Cela n'a pas de sens de continuer à jouer si les deux joueurs peuvent réclamer un match nul. Si un joueur remarque qu'il perd, il peut réclamer le tirage au sort, donnant le même résultat. Voir: chess.com/blog/kurtgodden/the-longest-possible-chess-game
SDwarfs
1
Remarque: m = 5898 est le nombre de "coups". Le nombre maximum de demi-coups est (118-3) * 100 + 3 * 99 = 11797. Vous pouvez trouver la preuve ici (en allemand!): De.wikipedia.org/wiki/50-Z%C3%BCge-Regel# Schachmathematik
SDwarfs
1

Je sais que c'est un peu une bosse, mais je dois mettre mes 5 cents ici. Il est possible pour un ordinateur, ou une personne d'ailleurs, de mettre fin à chaque partie d'échecs à laquelle il / elle participe, soit dans une victoire, soit dans une impasse.

Pour y parvenir, cependant, vous devez connaître précisément tous les mouvements et réactions possibles et ainsi de suite, tout au long de chaque résultat possible du jeu, et pour visualiser cela, ou pour faire un moyen facile d'analyser cette information, pensez à c'est une carte mentale qui se ramifie constamment.

Le nœud central serait le début du jeu. Chaque branche de chaque nœud symboliserait un mouvement, chacun différent de ses mouvements frères. Le présenter dans ce manoir prendrait beaucoup de ressources, surtout si vous le faisiez sur papier. Sur un ordinateur, cela prendrait peut-être des centaines de Terrabytes de données, car vous auriez de très nombreux mouvements répétitifs, à moins que vous ne fassiez revenir les branches.

Cependant, mémoriser de telles données serait invraisemblable, voire impossible. Faire en sorte qu'un ordinateur reconnaisse le mouvement le plus optimal pour retirer des (au plus) 8 mouvements instantanément possibles, serait possible, mais pas plausible ... car cet ordinateur aurait besoin de pouvoir traiter toutes les branches après ce mouvement, jusqu'à une conclusion, comptez toutes les conclusions qui aboutissent à une victoire ou à une impasse, puis agissez sur ce nombre de conclusions gagnantes contre des conclusions perdantes, et cela nécessiterait une RAM capable de traiter des données dans les Terrabytes, ou plus! Et avec la technologie d'aujourd'hui, un tel ordinateur exigerait plus que le solde bancaire des 5 hommes et / ou femmes les plus riches du monde!

Donc, après toute cette considération, cela pouvait être fait, mais personne ne pouvait le faire. Une telle tâche nécessiterait 30 des esprits les plus brillants vivants aujourd'hui, non seulement aux échecs, mais en science et en informatique, et une telle tâche ne pourrait être accomplie que sur un (mettons-le entièrement dans une perspective de base) ... extrêmement finalement hyper hyper ordinateur super-duper ... qui ne pourrait pas exister pendant au moins un siècle. Ça sera fait! Mais pas dans cette vie.

MrDeeJayy
la source
1

Il y a deux erreurs dans votre expérience de pensée:

  1. Si votre machine de Turing n'est pas "limitée" (en mémoire, vitesse, ...) vous n'avez pas besoin d'utiliser des heuristiques mais vous pouvez calculer évaluer les états finaux (victoire, perte, tirage au sort). Pour trouver le jeu parfait, il vous suffirait alors d'utiliser l'algorithme Minimax (voir http://en.wikipedia.org/wiki/Minimax ) pour calculer les mouvements optimaux pour chaque joueur, ce qui conduirait à un ou plusieurs jeux optimaux.

  2. Il n'y a pas non plus de limite à la complexité de l'heuristique utilisée. Si vous pouvez calculer un jeu parfait, il existe également un moyen d'en calculer une heuristique parfaite. Si nécessaire, c'est juste une fonction qui cartographie les positions d'échecs de la manière "Si je suis dans cette situation S, mon meilleur coup est M".

Comme d'autres l'ont déjà souligné, cela se terminera par 3 résultats possibles: les blancs peuvent forcer une victoire, les noirs peuvent forcer une victoire, l'un d'eux peut forcer un match nul.

Le résultat d'un jeu de dames parfait a déjà été "calculé". Si l'humanité ne se détruit pas avant, il y aura aussi un calcul pour les échecs un jour, lorsque les ordinateurs auront suffisamment évolué pour avoir suffisamment de mémoire et de vitesse. Ou nous avons des ordinateurs quantiques ... Ou jusqu'à ce que quelqu'un (chercheur, experts en échecs, génie) trouve des algorithmes qui réduisent considérablement la complexité du jeu. Pour donner un exemple: quelle est la somme de tous les nombres entre 1 et 1000? Vous pouvez soit calculer 1 + 2 + 3 + 4 + 5 ... + 999 + 1000, ou simplement calculer: N * (N + 1) / 2 avec N = 1000; result = 500500. Maintenant, imaginez que vous ne connaissez pas cette formule, vous ne connaissez pas l'induction mathématique, vous ne savez même pas comment multiplier ou ajouter des nombres, ... Alors, il est possible qu'il y ait un algorithme actuellement inconnu qui réduit finalement la complexité de ce jeu et il faudrait juste 5 minutes pour calculer le meilleur coup avec un ordinateur actuel. Peut-être serait-il même possible de l'estimer comme un humain avec un stylo et du papier, ou même dans votre esprit, avec un peu plus de temps.

Donc, la réponse rapide est: si l'humanité survit assez longtemps, ce n'est qu'une question de temps!

SDwarfs
la source
0

Cela pourrait être résolu, mais quelque chose me dérange: même si l'arbre entier pouvait être traversé, il n'y a toujours aucun moyen de prédire le prochain coup de l'adversaire. Nous devons toujours baser notre prochain coup sur l'état de l'adversaire et rendre disponible le «meilleur» coup. Ensuite, en fonction de l'état suivant, nous recommençons. Ainsi, notre mouvement optimal pourrait être optimal si l'adversaire se déplace d'une certaine manière. Pour certains mouvements de l'adversaire, notre dernier coup aurait pu être sous-optimal.

Je ne vois tout simplement pas comment il pourrait y avoir un mouvement «parfait» à chaque étape.

Pour que cela soit le cas, il doit y avoir pour chaque état [dans le jeu en cours] un chemin dans l'arbre qui mène à la victoire, quel que soit le prochain coup de l'adversaire (comme dans tic-tac-toe), et j'ai un dur le temps de le comprendre.

E Dominique
la source
5
Le coup parfait est décidé par la stratégie «minmax»: c'est le coup qui maximise votre score minimum possible (étant donné tous les mouvements possibles que l'adversaire pourrait faire). Ou pour le dire autrement, cela suppose que l'adversaire joue également parfaitement.
Nick Johnson
C'est cependant un point intéressant. Une situation pourrait-elle se produire où une réponse au meilleur coup possible vous désavantagerait si votre adversaire ne prend pas le meilleur coup possible? Quelles implications cela a-t-il?
Nona Urbiz
Je ne suis ni mathématicien ni très bon joueur d'échecs; J'ai également supposé qu'en théorie (si tout l'arbre du jeu devait être connu), la réponse à cette question est «oui». Cependant, maintenant que vous mentionnez ce problème [le choix de l'autre joueur], cela signifie-t-il que le système est potentiellement imprévisible? Y a-t-il un point médian du jeu où l'autre joueur pourrait forcer un désavantage? Est-ce un peu comme le fait que le Perceptron (Neural Net) peut apprendre «OU» et «ET» mais ne peut jamais saisir «XOR»? Les échecs sont-ils un exemple de système «chaotique»? FWIW, IMHO Je pense que la réponse semble être «je ne sais pas» à ce stade.
monojohnny
@Nona Par définition, ce mouvement serait le meilleur coup. Il n'y a aucune hypothèse.
piccolbo
@piccolbo: Mieux, l'un des meilleurs coups. Il y a des positions aux échecs où plusieurs coups donnent le même résultat (victoire, match nul ou perte dans le même nombre de coups).
SDwarfs
0

Mathématiquement, les échecs ont été résolus par l' algorithme Minimax , qui remonte aux années 1920 (trouvé par Borel ou von Neumann). Ainsi, une machine à turing peut effectivement jouer aux échecs parfaits.

Cependant, la complexité informatique des échecs le rend pratiquement impossible. Les moteurs actuels utilisent plusieurs améliorations et heuristiques. Les meilleurs moteurs d'aujourd'hui ont surpassé les meilleurs humains en termes de force de jeu, mais en raison des heuristiques qu'ils utilisent, ils pourraient ne pas jouer parfaitement lorsqu'ils sont donnés un temps infini (par exemple, les collisions de hachage pourraient conduire à des résultats incorrects).

Les plus proches que nous ayons actuellement en termes de jeu parfait sont les tables de fin de partie . La technique typique pour les générer est appelée analyse rétrograde . Actuellement, toutes les positions avec jusqu'à six pièces ont été résolues.

Philipp Claßen
la source
-1

Oui , en mathématiques, les échecs sont classés comme un jeu déterminé, cela signifie qu'il a un algorithme parfait pour chaque premier joueur, cela s'est avéré être vrai même pour un échiquier infini, donc un jour, une IA quantique trouvera probablement la stratégie parfaite, et le jeu est parti

Plus d'informations à ce sujet dans cette vidéo: https://www.youtube.com/watch?v=PN-I6u-AxMg

Il y a aussi des échecs quantiques, où il n'y a pas de preuve mathématique qu'il s'agit d'un jeu déterminé http://store.steampowered.com/app/453870/Quantum_Chess/

et voilà une vidéo détaillée sur les échecs quantiques https://chess24.com/en/read/news/quantum-chess

Dhia Hassen
la source
-2

Bien sûr, il n'y a que 10 à la puissance de cinquante combinaisons de pièces possibles sur le plateau. Ayant cela à l'esprit, pour jouer à chaque compibation, vous auriez besoin de faire moins de 10 à la puissance de cinquante coups (y compris les répétitions, multipliez ce nombre par 3). Donc, il y a moins de dix à la puissance de cent coups aux échecs. Choisissez simplement ceux qui mènent à l'échec et vous êtes prêt à partir

Alex
la source
-3

Les maths 64 bits (= échiquier) et les opérateurs binaires (= prochains coups possibles) sont tout ce dont vous avez besoin. Si simplement. Brute Force trouvera généralement le meilleur moyen. Bien sûr, il n'y a pas d'algorithme universel pour toutes les positions. Dans la vraie vie, le calcul est également limité dans le temps, le timeout l'arrêtera. Un bon programme d'échecs signifie un code lourd (pions passés, doublés, etc.). Le petit code ne peut pas être très fort. Les bases de données d'ouverture et de fin de partie ne font que gagner du temps de traitement, une sorte de données prétraitées. L'appareil, je veux dire - le système d'exploitation, les possibilités de thread, l'environnement, le matériel définissent les exigences. Le langage de programmation est important. Quoi qu'il en soit, le processus de développement est intéressant.

Développeur IA
la source