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

" j'ai fait valoir qu'il ne pouvait pas exister une machine de Turing déterministe qui a toujours gagné ou stalemated aux échecs."

vous n'avez pas tout à fait raison. Il peut y avoir une telle machine. Le problème est l'immensité de l'espace d'état qu'il aurait à chercher. C'est fini, c'est juste vraiment grand.

C'est pourquoi les échecs retombe sur l'heuristique -- l'espace d'état est trop énorme (mais fini). De même énumérer -- beaucoup moins de recherche pour chaque mouvement parfait le long de chaque cours de chaque jeu possible -- serait un très, très gros problème de recherche.

Ouvertures sont écrites pour vous amener à un milieu de jeu qui vous donne une "forte". Pas un résultat connu. Même les jeux de fin -- quand il y a moins de pièces -- sont difficiles à énumérer pour déterminer un meilleur prochain mouvement. Techniquement ils sont finis. Mais le nombre d'alternatives est énorme. Même un 2 rooks + king a quelque chose comme 22 mouvements possibles. Et si il faut 6 mouvements pour s'accoupler, 12 855 002 631 049 216 mouvements.

faites le calcul sur les mouvements d'ouverture. Alors qu'il n'y a qu'une vingtaine de mouvements d'ouverture, il y en a une trentaine de seconds mouvements, donc par le troisième mouvement nous sommes face à 360 000 états de jeu alternatifs.

, Mais les jeux d'échecs sont (techniquement) finis. Énorme, mais finie. Il y a une information parfaite. Il y a des états de début et de fin définis, il n'y a pas de pièce de monnaie ou des rouleaux de dé.

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

d'abord, il faut se rappeler que le blanc doit passer en premier et peut-être cela lui donne un avantage; peut-être cela donne-t-il un avantage au noir.

supposons maintenant qu'il y a pas de stratégie parfaite pour Black qui lui permet toujours de gagner/stalemate. Cela implique que peu importe ce que fait Black, il y a une stratégie Blanc peut suivre pour gagner. Attendez une minute - cela signifie qu'il est une stratégie parfaite pour les blancs!

cela nous indique qu'au moins un des deux joueurs fait ont une stratégie parfaite qui permet à ce joueur toujours gagner ou tirer.

il n'y a que trois possibilités, alors:

• le blanc peut toujours gagner s'il joue parfaitement
• Noir peut toujours gagner si il joue parfaitement
• un joueur peut gagner ou tirer 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.

il a été prouvé pour le jeu de dames qu'un programme peut toujours gagner ou égaliser le jeu. C'est-à-dire qu'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 en passant par les 500 milliards de milliards de possible pions positions, ce qui est encore une infime fraction du nombre de positions d'échecs, par façon. Les meilleurs joueurs ont participé à l'effort des vérificateurs, qui ont aidé l'équipe de recherche à établir les règles empiriques des vérificateurs dans un logiciel qui classait les mouvements comme réussis ou non. Puis les chercheurs ont laissé le programme fonctionner, sur une moyenne de 50 ordinateurs par jour. Certains jours, le programme fonctionnait sur 200 machines. Alors que les chercheurs ont suivi les progrès et modifié le programme en conséquence. En fait, Chinook a battu humans pour remporter le championnat du monde de dames en 1994.

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

il ne s'agit pas d'une question d'ordinateurs mais seulement du jeu d'Échecs.

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

par exemple, le jeu tic-tac-toe est normalement joué sur la base d'heuristiques. Mais il existe une stratégie de sécurité. Quel que soit le mouvement de l'adversaire, vous trouver un moyen pour éviter de perdre le jeu, si vous le faites dès le début sur.

donc vous devez prouver qu'une telle stratégie existe ou pas pour les échecs aussi bien. C'est fondamentalement la même, juste l'espace de coups possibles est beaucoup plus importante.

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

• Le nombre total de jeux d'échecs est d'environ 10^(10^50). Ce nombre est incroyablement élevé.
• Le nombre de jeux d'échecs de 40 mouvements ou moins est d'environ 10^40. C'est encore un nombre incroyablement élevé.
• le nombre de positions d'échecs possibles est d'environ 10^46.
• l'arbre complet de recherche d'Échecs (nombre de Shannon) est d'environ 10^123, basé sur un facteur de ramification moyenne de 35 et une longueur de jeu moyenne de 80.
• a titre de comparaison, le nombre d'atomes dans l'univers observable est généralement estimé à environ 10^80.
• tous les endgames de 6 pièces ou moins ont été rassemblées et résolues .

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

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

"151900920 d'Échecs", cependant, n'a pas été résolu, et je ne pense pas qu'il n'y a aucune preuve que c'est un bon jeu (c'est à dire, si le jeu parfait des résultats à un tirage au sort). En parlant strictement d'un point de vue théorique cependant, les échecs ont un nombre limité de configurations possibles. Par conséquent, l'espace de recherche est finie (quoique, incroyablement grand). Par conséquent, une machine de Turing déterministe qui pourrait jouer parfaitement existe. Mais la question de savoir si l'on pourra jamais en construire un est une autre.

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

même à cette vitesse, il faudrait encore 100 de ces ordinateurs environ 6,34 x 10^19 années pour résoudre Échecs. Toujours pas faisable. Même pas proche.

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

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

étant donné checkers a été résolu en 2007, et la puissance de calcul pour le résoudre en 1 seconde sera d'environ 33-35 ans, nous pouvons probablement à peu près estimation d'échecs sera résolu quelque part entre 2055-2057. Probablement plus tôt, car lorsque plus de puissance de calcul est disponible (ce qui sera le cas dans 45 ans), plus peut être consacré à des projets tels que 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 des échecs. Je me rends compte que j'utilise un ordinateur de 1000 $comme point de référence, alors que les systèmes plus grands et les supercalculateurs seront probablement disponibles car leur rapport prix/performance s'améliore également. De plus, leur puissance de calcul augmente plus rapidement. Considérons qu'un superordinateur peut maintenant effectuer 2.33 x 10^15 calculs par seconde, et un ordinateur $1000 environ 2 x 10^9. En comparaison, il y a 10 ans, la différence était de 10^5 au lieu de 10^6. En 2060, la différence d'ordre de grandeur sera probablement de 10^12, et même cette différence pourrait augmenter plus rapidement que prévu.

une grande partie de ceci dépend de si oui ou non nous en tant qu'êtres humains avons la volonté de résoudre des échecs, mais la puissance de calcul le rendra possible autour de ce temps (aussi longtemps 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 une planche ouverte). La puissance de calcul pour résoudre Tic-Tac-Toe en environ 2,5 (1 million de calculs par seconde) secondes a été atteinte en 1990.

se déplaçant à reculons, en 1955, un ordinateur avait le pouvoir de résoudre Tic-Tac-Toe en environ 1 mois (1 Calcul par seconde). Encore une fois, ceci est basé sur ce que 1000 $vous obtiendriez si vous pouviez l'empaqueter dans un ordinateur (un bureau de 1000 $évidemment n'existait pas en 1955), et cet ordinateur aurait été consacré à la résolution Tic-Tac-Toe....qui a été tout simplement pas le cas en 1955. Le calcul était coûteux et n'aurait pas été utilisé à cette fin, bien que je ne je crois qu'il y a une date où le 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.

aussi, prendre en compte 1000 $dans 45 ans vaudra environ 4 fois moins qu'il ne l'est actuellement, tellement plus d'argent peut aller dans des projets tels que celui-ci tandis que la puissance de calcul continuera à devenir moins cher.

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

Votre argument est soutenu par la façon moderne d'échecs des programmes de travail maintenant . Ils fonctionnent de cette façon parce que c'est trop axé sur les ressources pour coder un programme d'échecs pour fonctionner de façon déterministe. Ils ne seront pas nécessairement toujours travailler de cette façon. Il est possible que chess soit un jour résolu , et si cela se produit, il sera probablement résolu par un ordinateur.

pour information, il y a des ordinateurs qui peuvent gagner ou faire égalité à checkers . Je ne suis pas sûr que la même chose puisse être faite pour les échecs. Le nombre de mouvements est beaucoup plus élevé. Aussi, les choses changent parce que les morceaux peuvent se déplacer dans n'importe quelle direction, pas seulement en avant et en arrière. Je pense que même si Je ne suis pas sûr, que les échecs est déterministe, mais qu'il ya juste beaucoup trop de mouvements possibles pour un ordinateur pour déterminer actuellement tous les mouvements dans une quantité raisonnable de temps.

je pense que tu es mort. Les Machines comme Deep Blue et Deep Thought sont programmées avec un certain nombre de jeux prédéfinis, et des algorithmes intelligents pour séparer les arbres dans les extrémités de ces jeux. Il s'agit, bien sûr, d'une simplification excessive et dramatique. Il y a toujours une chance de "battre" l'ordinateur au cours d'un jeu. J'entends par là un mouvement qui oblige l'ordinateur à faire un mouvement qui n'est pas optimal (quel qu'il soit). Si l'ordinateur ne peut pas trouver le meilleur chemin avant la limite de temps pour le mouvement, il pourrait très bien faire une erreur en choisissant l'un des chemins moins souhaitables.

Il ya une autre classe de programmes d'échecs qui utilise l'apprentissage machine réelle, ou la programmation génétique / algorithmes évolutifs. Certains programmes ont évolué et l'utilisation des réseaux de neurones, et al, à prendre des décisions. Dans ce type de cas, j'imagine que l'ordinateur peut faire des "erreurs", mais quand même dans une victoire.

il y a un livre fascinant sur ce type de GP appelé Blondie24 que vous pourriez lire. Il s'agit de dames, mais il pourrait s'appliquer aux échecs.

de la théorie des jeux, ce qui est l'objet de cette question, la réponse est oui Échecs peut être joué parfaitement. 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 pourriez écrire une machine parfaite tic-tac-toe maintenant-a-days dans n'importe quel langage de script et il jouerait parfaitement en temps réel.

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

"151900920 d'Échecs" est théoriquement possible, mais pratiquement pas possible (en 2008)

i-Go est un peu délicate, c'est l'espace des possibles, tombe au-delà de la quantité d'atomes dans l'univers, de sorte qu'il pourrait nous prendre un certain temps pour faire un parfait j'-Aller de la machine.

échecs est un exemple d'un jeu de matrice, qui par définition a un résultat optimal (pensez équilibre Nash). Si le Joueur 1 et le Joueur 2 prennent chacun des mouvements optimaux, un certain résultat sera toujours atteint (que ce soit une victoire-égalité-perte est toujours inconnue).

en tant que programmeur d'échecs des années 1970, j'ai certainement une opinion là-dessus. Ce que j'ai écrit il y a environ 10 ans, est toujours 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 fait correctement.

Dames a été résolu récemment (Yay, Université de l'Alberta, au Canada!!!), mais qui a été effectivement fait La Force Brute. Pour jouer aux échecs, il faut être plus intelligent.

à moins, bien sûr, calcul quantique devient une réalité. Si c'est le cas, les échecs seront résolus aussi facilement que le Tic-Tac-Toe.

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

si vous recherchez l'espace entier de toutes les combinaisons de mouvements player1/2, le seul mouvement que l'ordinateur décide à chaque étape est basé sur une heuristique.

Il y a deux idées concurrentes. L'un est ce que vous cherchez tous les coups possibles, et l'autre est que vous décidez basé sur une heuristique. Une heuristique est un système pour faire une bonne estimation. Si vous cherchez dans tous les mouvements possibles, alors vous ne devinez plus.

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

Oui. C'est peut-être pour le Blanc toujours gagner. Peut-être que C'est pour les noirs de toujours gagner. Peut-être que c'est pour les deux de toujours attacher au moins. Nous ne savons pas lequel, et nous ne le saurons jamais, mais il existe certainement.

voir aussi

• algorithme de Dieu

j'ai trouvé cette l'article de John MacQuarrie qui fait référence à des travaux par le "père de la théorie des jeux" Ernst Friedrich Ferdinand Zermelo . Il tire la conclusion suivante:

aux échecs soit le blanc peut forcer une victoire, soit le noir peut forcer une victoire, ou les deux côtés peuvent forcer au moins un match nul.

la logique me semble saine.

Beaucoup de réponses ici de rendre le match important de la théorie des points:

1. les échecs sont un jeu limité, 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
"151930920 d'Échecs" est cependant assez grand pour que vous ne serez pas en mesure de le résoudre complètement avec une force brutale méthode

point pratique important: il n'est pas nécessaire de résoudre le jeu complet parfaitement afin de créer une machine imbattable .

il est en fait tout à fait probable que vous pourriez 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 fraction de l'espace d'état possible.

les techniques suivantes, par exemple, réduisent massivement l'espace de recherche requis:

• techniques D'élagage des arbres comme Alpha / Beta ou MTD-f déjà réduire massivement l'espace de recherche
• position gagnante prouvable. Beaucoup de fins tombent dans cette catégorie: vous n'avez pas besoin de rechercher KR vs K par exemple, c'est une victoire prouvée. Avec certains travaux il est possible de prouver beaucoup plus de victoires garanties.
• presque certaines victoires-pour" Assez bon " jouer sans aucune erreur stupide (dire à 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 compensation avantage de position. Si votre programme peut forcer une telle position et a assez de heuristiques pour détecter avantage de position, il peut en toute sécurité supposer qu'il gagnera ou au moins tirer avec 100% de probabilité.
• heuristique de recherche D'arbre - avec assez de reconnaissance de modèle, vous pouvez rapidement se concentrer sur le sous-ensemble pertinent de " intéressant" déplacer. C'est comme ça que les grands maîtres humains jouent donc ce n'est clairement pas une mauvaise stratégie..... et nos algorithmes de reconnaissance de formes s'améliorent constamment
• l'évaluation des Risques et une meilleure conception du "risque" d'un poste permettra beaucoup plus efficace de la recherche en concentrant la puissance de calcul sur les situations où l'issue est plus incertaine (c'est une extension naturelle de Quiescence de Recherche )

avec le 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 très loin de la technologie actuelle.

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

Note complémentaire concernant la "perfection":

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

• toujours gagnant dans toutes les situations où il est possible de forcer une victoire, peu importe la complexité de la combinaison gagnante peut être. Il y aura des situations sur la frontière entre win/draw où c'est extrêmement difficile à calculer parfaitement.
• exploiter toutes les informations disponibles sur l'imperfection potentielle dans le jeu de votre adversaire, par exemple inférer que votre adversaire pourrait être trop gourmand et jouer délibérément une ligne un peu plus faible que d'habitude au motif qu'il a un plus grand potentiel de tenter votre adversaire à faire un erreur. Contre les adversaires imparfaits, il peut en fait être optimal de faire un perdre si vous estimez que votre adversaire ne sera probablement pas repérer la victoire forcée et il vous donne une plus grande probabilité de gagner vous-même.

Perfection (en particulier pour les adversaires imparfaits et inconnus) est un beaucoup problème plus difficile que d'être tout simplement imbattable.

c'est parfaitement 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'ils sont compilés, les positions qui sont des cochées 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.

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

je ne suis qu'à 99,9% convaincu par l'affirmation que la taille de l'espace d'état rend impossible l'espoir d'une solution.

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

Quelle est la limite sur le nombre de coups dans le jeu le plus long possible? Puisque tous les jeux se terminent par un nombre fini de mouvements il existe un tel lié, appelez-le M.

à partir de l'état initial, ne pouvez-vous énumérer tous les n mouvements dans l'espace O(m)? Bien sûr, cela prend du temps, mais les arguments de la taille de l'univers ne traitent pas directement de cela. O (m) l'espace pourrait même ne pas être beaucoup. Pour O (m) space ne pouviez - vous pas aussi suivre, pendant cette traversée, si la suite d'un État le long du chemin que vous traversez mène à EitherMayWin, EitherMayForceDraw, WhiteMayWin, WhiteMayWinOrForceDraw, BlackMayWin, ou BlackMayWinOrForceDraw? (Il y a un réseau selon le tour de qui il est, annoter chaque état dans l'histoire de votre traversée avec le réseau se rencontrer.)

à moins que je ne manque quelque chose, c'est un algorithme d'espace O(n) time / O(m) pour déterminer dans laquelle des catégories possibles chess tombe. Wikipedia cite une estimation pour l'âge de l'univers à environ 10^60ème Planck times. Sans entrer dans une discussion de cosmologie, supposons qu'il reste à peu près autant de temps avant la chaleur/le froid/n'importe quelle mort de l'univers. Cela nous laisse avoir à évaluez un mouvement toutes les 10^10 Planck times, ou toutes les 10^-34 secondes. C'est un temps incroyablement court (environ 16 ordres de grandeur plus court que les temps les plus courts jamais observés). Disons de façon optimiste qu'avec une mise en œuvre super-duper-good en haut de la ligne present-or-forseen-non-quantum-P-is-a-proper-subset-of-NP technologie nous pourrions espérer évaluer (faire un seul pas en avant, catégoriser l'état résultant comme un état intermédiaire ou l'un des trois états finaux) États à une fréquence de 100 MHz (une fois toutes les 10^-8 secondes). Comme cet algorithme est très parallélisable, nous avons besoin de 10^26 ordinateurs de ce type ou environ un pour chaque atome de mon corps, ainsi que la capacité de recueillir leurs résultats.

je suppose qu'il y a toujours un peu d'espoir pour une solution brutale. Nous pourrions avoir de la chance et, en explorant seulement un des mouvements d'ouverture possibles de blanc, les deux choisissent un avec beaucoup plus bas que la moyenne fanout et un dans lequel blanc gagne toujours ou gagne ou gagne.

nous pourrions aussi espérer rétrécir un peu la définition des échecs et convaincre tout le monde que c'est encore moralement le même jeu. Faut - il vraiment que les positions soient répétées 3 fois avant un tirage au sort? Avons-nous vraiment besoin de faire la fête démontrer la capacité de s'échapper pour 50 coups? Est-ce que quelqu'un comprend ce qu'il se passe avec la règle en passant ? ;) Plus sérieusement, faut - il vraiment forcer un joueur à se déplacer (par opposition au dessin ou à la perte) lorsque son seul mouvement pour échapper contrôle ou une impasse est un en passant capture? Pourrions-nous limiter le choix des pièces sur lesquelles un pion peut être promu si la promotion non-queen souhaitée ne conduit pas à un échec immédiat ou échec et mat?

je suis également incertain sur combien permettre à chaque ordinateur basé sur le hash accès à une grande base de données des états de jeu en retard et leurs résultats possibles (qui pourraient être relativement faisable sur le matériel existant et avec les bases de données de fin de jeu existantes) pourrait aider à réduire la recherche plus tôt. Évidemment, vous ne pouvez pas memoize la fonction entière sans stockage O(n), mais vous pourriez choisir un grand entier et memoize que de nombreux endgames énumérant à l'envers de chaque état final possible (ou même pas facilement provably impossible, je suppose).

je sais que c'est un peu un choc, mais je dois mettre mes 5 cents ici. Il est possible pour un ordinateur, ou une personne, en la matière, à la fin de chaque jeu d'échecs qu'il/elle/il participe, dans une victoire ou d'une impasse.

pour y parvenir, cependant, vous devez connaître précisément tous les mouvements et les réactions possibles et ainsi de suite, tout au long de chaque résultat de jeu possible, et de visualiser ceci, ou de faire un moyen facile d'analyser cette information, pensez-y comme une carte de l'esprit qui se ramifie en permanence.

le noeud central serait le début du jeu. Chaque branche de chaque nœud symboliserait un déménagement, chacun différent de ses frères se déplace. La présenter dans ce manoir demanderait beaucoup de ressources, surtout si vous le faisiez sur papier. Sur un ordinateur, cela prendrait peut-être des centaines de Terrabytes de données, comme vous auriez beaucoup de mouvements repédatifs, à moins que vous n'ayez fait venir les branches arrière.

pour mémoriser de telles données, cependant, serait implacable, sinon impossible. Faire en sorte qu'un ordinateur reconnaisse le mouvement le plus optimal pour sortir des (au maximum) 8 mouvements instantanément possibles, serait possible, mais pas réalisable... comme cet ordinateur devrait être en mesure de traiter toutes les branches au-delà de ce mouvement, tout le chemin vers une conclusion, compter toutes les conclusions qui aboutissent à une victoire ou une impasse, puis agir sur ce nombre de conclusions de wining contre la perte de conclusions, et cela nécessiterait 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, il pourrait être fait, cependant, personne ne pouvait le faire. Une telle tâche exigerait 30 des esprits les plus brillants vivants aujourd'hui, non seulement aux échecs, mais dans la science et la technologie informatique, et une telle tâche ne pourrait être achevée sur a (mettons-le entièrement dans la perspective de base)... extrêmement finalement hyper super-duper ordinateur... qui ne pourrait exister avant au moins un siècle. Il sera fait! Tout simplement pas dans cette vie.

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

1. si votre machine de Turing n'est pas "limitée" (en mémoire, vitesse, ...) vous n'avez pas besoin d'utiliser l'heuristique mais vous pouvez calculer évaluer les états finaux (victoire, défaite, match nul). Pour trouver le jeu parfait, vous auriez alors juste besoin 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 également aucune limite à la complexité de l'heuristique utilisée. Si vous pouvez calculer un jeu parfait, il est aussi un moyen pour calculer une parfaite heuristique. Si nécessaire, c'est juste une fonction qui cartographie les positions d'Échecs de la façon "si je suis dans cette situation s mon meilleur mouvement est M".

comme d'autres l'ont déjà souligné, cela se terminera en 3 résultats possibles: blanc peut forcer une victoire, noir peut forcer une victoire, l'un d'eux peut forcer un tirage au sort.

le résultat d'un jeu de dames parfait a déjà été"calculé". Si l'humanité ne se détruira pas avant, il y aura aussi un calcul pour les échecs un jour, quand les ordinateurs auront évolué assez pour avoir assez 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 vous pouvez simplement calculer: N*(N+1)/2 avec N = 1000; résultat = 500500. Maintenant imaginez ne pas connaître cette formule, vous ne savez pas à propos de l'induction mathématique, vous ne savez même pas comment multiplier ou ajouter des nombres,... Donc, il est possible qu'il y ait un algorithme actuellement inconnu qui finalement réduit la complexité de ce jeu et il ne faudrait que 5 Minutes pour calculer le mieux se déplacer avec un ordinateur actuel. Peut-être qu'il serait même possible de l'estimer comme un humain avec un stylo et du papier, ou même dans votre esprit, étant donné un peu plus de temps.

ainsi, la réponse rapide est: si l'humanité survit assez longtemps, c'est juste une question de temps!

c'est peut-être soluble, 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 mouvement de l'adversaire. Nous devons toujours baser notre prochain mouvement sur l'état de l'adversaire, et rendre le "meilleur" mouvement disponible. Ensuite, en fonction de l'état suivant nous le faire à nouveau. Donc, notre mouvement optimal pourrait être optimal si l'adversaire bouge d'une certaine manière. Pour certains mouvements de l'adversaire de notre dernier déplacement pourrait avoir été sous-optimale.

I juste ne vois pas comment il pourrait y avoir un "parfait" dans toutes les étape.

pour que ce soit le cas, il doit y avoir pour chaque État [dans le jeu actuel] un chemin dans l'arbre qui mène à la victoire, indépendamment du prochain mouvement de l'adversaire (comme dans tic-tac-toe), et j'ai du mal à le comprendre.

mathématiquement, chess a été résolu par le algorithme Minimax , qui remonte aux années 1920 (soit trouvé par Borel ou von Neumann). Ainsi, une machine de turing peut effectivement jouer aux échecs parfaits.

cependant, la complexité computationnelle des échecs les rend pratiquement infaisables. Les moteurs actuels utilisent plusieurs améliorations et heuristiques. Les meilleurs moteurs ont aujourd'hui surpassé les meilleurs humains en termes de puissance de jeu, mais en raison de la heuristiques qu'ils utilisent, ils pourraient ne pas jouer parfait lorsque donné le temps infini (par exemple, collisions de hachage pourrait conduire à des résultats incorrects).

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

Oui , en mathématiques, les échecs est classé comme un jeu déterminé , ce qui signifie qu'il a un algorithme parfait pour chaque premier joueur , ce qui est prouvé pour être vrai même pour échiquier infinate, donc un jour probablement un quantom AI trouvera la stratégie parfaite, et le jeu est parti

pour en savoir plus sur cette vidéo: https://www.youtube.com/watch?v=PN-I6u-AxMg

il y a aussi Quantom chess, où il n'y a pas de preuve mathématique qu'il est déterminé jeu http://store.steampowered.com/app/453870/Quantum_Chess /

et voilà la vidéo détaillée sur quantom chess https://chess24.com/en/read/news/quantum-chess

bien sûr Il n'y a que 10 à la puissance de 50 combinaisons possibles de pièces sur le tableau. Ayant cela à l'esprit, pour jouer à chaque compibation, vous auriez besoin de faire moins de 10 à la puissance de cinquante mouvements (y compris les répétitions multiplier ce nombre par 3). Donc, il y en a moins de dix à la puissance de cent mouvements aux échecs. Il suffit de choisir ceux qui mènent à checkmate et vous êtes bon à aller

64bit math (=échiquier) et bitwise operators (=next possible moves) est tout ce dont vous avez besoin. Alors, tout simplement. La force Brute trouvera généralement le meilleur moyen. Bien sûr, il n'y a pas d'algorithme universel pour tous les postes. Dans la vie réelle, le calcul est également limité dans le temps, le temps mort l'arrêtera. Un bon programme d'Échecs signifie le code lourd (passé,double pions,etc). Le petit code ne peut pas être très fort. L'ouverture et la fin des bases de données ne font que gagner du temps de traitement, une sorte de données pré-traitées. Appareil, Je veux dire - le système D'exploitation,filetage poss., environnement, matériel définir les exigences. Le langage de programmation est important. De toute façon, le processus de développement est intéressant.