Est-il un parfait algorithme pour le jeu d'échecs?

Question

J'étais récemment dans une discussion avec un non-programmeur personne sur les possibilités d'échecs des ordinateurs. Je ne suis pas bien versé dans la théorie, mais je pense que je connais assez.

J'ai fait valoir qu'il ne pouvait exister qu'une machine de Turing déterministe qui a toujours gagné ou stalemated au jeu d'échecs. Je pense que, même si vous rechercher l'ensemble de l'espace de toutes les combinaisons de joueur1/2 se déplace, le seul mouvement que l'ordinateur décide à chaque étape est basée sur une heuristique. Étant basée sur une heuristique, il n'est pas nécessairement battre TOUS les coups de l'adversaire pourrait faire.

Mon ami a pensé, au contraire, qu'un ordinateur serait toujours la victoire ou la cravate si elle n'a jamais fait une "erreur" déplacer (mais en est-il?). Cependant, d'être un programmeur qui a pris la CS, je sais que même votre bon choix donné par une sage adversaire peut vous forcer à faire de "l'erreur" se déplace à la fin. Même si vous savez tout, votre prochaine étape est gourmand en contrepartie d'une heuristique.

La plupart des échecs des ordinateurs essayer de correspondre à une possible fin du jeu pour le jeu en cours, qui est essentiellement une programmation dynamique de retraçage. Encore une fois, la fin de la partie en question est évitable.

Edit: Hmm... on dirait que je ébouriffé quelques plumes ici. Ce qui est bon.

Y penser encore, il semble qu'il n'y a pas de problème théorique à la résolution d'un jeu fini comme les échecs. Je dirais que le jeu d'échecs est un peu plus compliqué que des pions dans ce une victoire n'est pas nécessairement par ordre numérique de l'épuisement des morceaux, mais par une contrainte. Mon affirmation est probablement faux, mais là encore je pense que j'ai remarquer quelque chose qui n'est pas encore prouvé de manière satisfaisante (officiellement).

Je suppose que mon expérience a été que quand une branche dans l'arbre, l'algorithme (ou mémorisé chemins d'accès) doit trouver un chemin d'accès à un compagnon (sans faire saillie) pour toute branche sur l'adversaire se déplace. Après la discussion, je vais acheter celui donné plus de mémoire que nous ne pouvons le rêve de tous ces chemins peut être trouvé.

Answer 1

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

Vous n'êtes pas tout à fait droit. 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 parfait se déplacer le long de tous les cours de toutes les règles du jeu -- serait un très, très gros problème de recherche.

Les ouvertures sont écrites pour vous amener à un milieu de jeu qui vous donne une "forte". Pas un résultat connu. Même la fin des jeux -- quand il y a moins de pièces -- sont difficiles à énumérer pour déterminer un meilleur mouvement suivant. Techniquement ils sont finis. Mais le nombre de solutions de rechange est énorme. Même à 2 tours + le roi a quelque chose comme 22 possible prochains mouvements. Et si elle prend 6 se déplace vers les mecs, vous êtes à la recherche à 12,855,002,631,049,216 se déplace.

Faire le calcul sur les coups de l'ouverture. Alors qu'il n'y a qu'environ 20 coups de l'ouverture, il y a quelque chose comme 30 ou de sorte que la deuxième se déplace, de sorte que par le troisième mouvement, nous sommes à la recherche à de 360 000 alternative jeu d'états.

Mais les jeux d'échecs sont (techniquement) finis. Énorme, mais finie. Il y a une information parfaite. Il existe de début et de fin définies-unis, Il n'y a pas de pièce de monnaie-lance ou des lancers de dés.

Answer 2

Je sais rien à propos de ce qui a été effectivement découvert à propos des échecs. Mais en tant que mathématicien, voici mon raisonnement:

D'abord nous devons nous rappeler que le Blanc arrive à passer en premier et peut-être ce qui lui donne un avantage; peut-être qu'il donne du Noir un avantage.

Maintenant, supposons qu'il n'existe pas de stratégie parfaite pour le Noir qui lui permet de toujours gagner/impasse. Cela implique que n'importe quel Noir n'est, il est une stratégie de Blanc peut suivre pour gagner. Attendez une minute - ce qui signifie qu'il y est une stratégie parfaite pour le Blanc!

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

Il n'existe 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 impasse si il joue à la perfection (et si les deux joueurs jouent parfaitement alors qu'ils ont toujours l'impasse)

Mais laquelle de ces est correcte, nous ne saurons jamais.

La réponse à la question est oui: il doit y avoir une parfaite algorithme pour le jeu d'échecs, au moins pour un des deux joueurs.

Answer 3

Il a été prouvé pour le jeu de dames qu'un programme peut toujours gagner ou de lier le jeu. Qui est, il n'y a pas le choix de coups qu'un joueur peut faire ce qui force le 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 la manière. Les pions de l'effort inclus des joueurs de haut niveau, qui a permis à l'équipe de recherche du programme de pions règles de base en logiciel classé se déplace comme un succès ou un échec. Puis les chercheurs ont laisser fonctionner le programme, sur une moyenne de 50 ordinateurs tous les jours. Certains jours, le programme est exécuté sur 200 machines. Alors que les chercheurs ont surveillé les progrès et modifié le programme en conséquence. En fait, Chinook battre l'homme de gagner les pions du championnat du monde en 1994.

Oui, vous pouvez résoudre les échecs, non, vous n'aurez pas de sitôt.

Answer 4

Ce n'est pas une question à propos des ordinateurs, mais seulement sur le jeu d'échecs.

La question est, existe-t-il un "fail-safe" stratégie pour ne jamais perdre le jeu? 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é basé sur des heuristiques. Mais, il existe un fail-safe de la stratégie. Quel que soit l'adversaire se déplace, vous trouverez toujours un moyen pour éviter de perdre le jeu, si vous le faites dès le début sur.

De sorte que vous devez à la preuve qu'une telle stratégie existe ou pas pour le jeu d'échecs. C'est fondamentalement la même, juste l'espace de coups possibles est beaucoup plus importante.

Answer 5

Je suis venue à ce fil très fin, et que vous avez déjà réalisé certaines de ces questions. Mais comme un ex-maître et un ex-professionnel d'échecs programmeur, j'ai pensé que je pourrais ajouter quelques faits et chiffres. Il y a plusieurs façons de mesurer la complexité du jeu d'échecs:

• Le nombre total de jeux d'échecs est d'environ 10^(10^50). Ce nombre est très grand.
• Le nombre de jeux d'échecs de 40 déplacements ou moins autour de 10^40. C'est encore un nombre incroyablement élevé.
• Le nombre de positions d'échecs est autour de 10^46.
• L'complet d'échecs, un arbre de recherche (Shannon nombre) est de l'ordre de 10^123, basé sur un facteur de branchement moyen de 35 et un jeu moyen longueur de 80.
• Pour comparaison, le nombre d'atomes dans l'univers observable est communément estimée à environ 10^80.
• Toutes les finales de 6 pièces ou moins ont été rassemblées et résolu.

Ma conclusion: bien que le jeu d'échecs est théoriquement possible, nous n'aurons jamais de l'argent, la motivation, la puissance de calcul ou de stockage à jamais.