Quelle est la limite inférieure connue la plus élevée pour le partenaire dans N à partir de la position de départ?

Edit : Il semble que ma question n'était pas assez claire. Permettez-moi de reformuler: quel est le plus grand N pour lequel nous pouvons sciemment dire "les échecs, à partir de la position de départ, ne sont pas forcés en N coups"?

Les échecs ne sont pas résolus, c'est-à-dire qu'on ne sait pas quel résultat de la position de départ est donné un jeu parfait.

Cependant, si la position de départ est gagnante pour l'un ou l'autre joueur, c'est un compagnon en N pour certains N. Aussi par exemple, si nous savons avec certitude que la position de départ n'est pas gagnable en 5 coups (pour l'un ou l'autre joueur), 5 est un borne inférieure pour N.

Dans quelle mesure est-il possible de rechercher de manière exhaustive à partir de la position de départ dans la pratique? Quelle est la limite supérieure connue pour N?

Il s'agit essentiellement de savoir quelle est la complexité du jeu d'échecs. Notez que par finitude, nous savons que les échecs sont déterminés, mais nous ne savons pas si la position de départ est une victoire pour les blancs, une victoire pour les noirs ou un match nul. La complexité du jeu d'échecs est à peu près le nombre minimum de positions que nous devons vérifier dans l'arbre de jeu pour déterminer l'état de la position initiale. C'est ce qu'on appelle le nombre de Shannon . Dans le document influent Programmer un ordinateur pour jouer aux échecs , Shannon a estimé que le nombre de Shannon était d'au moins 10 ^ {120). Notez que le nombre de particules dans l'Univers est estimé à 10 ^ (80). Pour répondre à la question, nous voulons en fait connaître la hauteurde l'arbre de jeu lorsque la position initiale est déterminée. Nous devons également diviser cette hauteur par 2, car un mouvement aux échecs est généralement considéré comme un mouvement blanc et noir. Le facteur de ramification de l'arbre est estimé à environ 30. Ainsi, nous pouvons prendre le plus grand N tel que 30 ^ (2N) <10 ^ (120).

Répondre. Au dos de l'enveloppe, N = 40 œuvres. Par coïncidence, cela se trouve être la durée d'une partie moyenne entre les grands-maîtres (bien qu'ils démissionnent souvent et ne jouent pas réellement le jeu jusqu'à la fin).

Éditer. La morale de l'histoire est que j'essayais d'estimer une borne supérieure pour votre borne inférieure. La première partie du raisonnement de Shannon n'est pas circulaire; il dit qu'il y a environ 30 coups légaux de chaque position, et ce nombre est raisonnablement constant pour la première partie d'une partie.

Ainsi, nous pouvons estimer que la valeur connue actuelle de N (qui est vraiment ce que vous demandez, appelons cela N ') pour être au plus log_30 (C) où C est égal à la quantité de puissance de calcul qui a existé dans l'histoire de l'humanité. Même avec des estimations prudentes pour C, nous obtenons quelque chose comme N 'au plus 20. En pratique, je ne pense pas que quiconque ait effectué ce calcul très haut dans l'arbre, car a priori nous savons que le calcul devient irréalisable après un très petite hauteur et il n'est pas nécessaire de rechercher exhaustivement l'arbre pour écrire de bons programmes d'échecs.

Notez cependant que vous posez une question légèrement plus faible, car il est possible que l'état initial du jeu soit un match nul avec un jeu optimal. Ainsi, on pourrait obtenir des limites pour N en écrivant un programme dont le but était de ne pas perdre le plus longtemps possible. Nous pourrions alors jouer ce programme contre les meilleurs programmes ou joueurs humains du monde et voir quelle est la durée d'une partie la plus courte. Encore une fois, cela ne répond pas correctement à la question, car nous ne pouvons pas supposer que nos adversaires jouent de manière optimale . Un vrai jeu optimal nécessite une connaissance complète de l'arbre de jeu, mais nous avons vu que cela est impossible à calculer. Ainsi, le mieux que nous puissions faire actuellement est d'approcher un adversaire jouant de manière optimale avec un Kasparov ou un très bon programme d'échecs.

Il n'est pas vrai que la position de départ ne soit pas gagnable en 5 coups ou moins en utilisant la définition canonique d'un coup complet aux échecs. Cela peut être fait en 2 mouvements via Fool's Mate .

Pour répondre à votre question, la force d'un moteur d'échecs dépend du logiciel et du matériel. En 1997, Deep Blue était une preuve de concept matériel, un supercalculateur massivement parallèle capable d'évaluer 200 millions de mouvements par seconde avec une profondeur moyenne de 7 à 8 mouvements. Cependant, en 2006, Deep Fritz fonctionnant sur un ordinateur personnel dual-core avait des résultats équivalents tout en n'évaluant que 8 millions de mouvements par seconde.

Aujourd'hui, le supercalculateur le plus puissant qui a été appliqué aux échecs est Blue Gene . À l'aide de 131 000 processeurs, Blue Gene peut calculer 280 billions d'opérations par seconde . Bien qu'il n'y ait pas de données pour confirmer la profondeur à laquelle Blue Gene peut calculer, je suppose que ce serait assez profond. Bien sûr, cela dépend de la durée de fonctionnement de l'ordinateur.

Cependant, nous ne pouvons pas dans ce cas utiliser le terme «exhaustif» lors de la «résolution» et de l'ouverture. Un moteur d'échecs n'a pas besoin d'aller jusqu'au bout de la ligne lorsqu'il est certain que le résultat final est déterminant. Dans ce cas, le programme se terminerait lorsqu'il deviendrait clair que l'évaluation était clairement en faveur d'un côté. C'est ce que l'on appelle en informatique théorique l' élagage Alpha-Beta .

Si je devais faire une estimation approximative, je dirais que Blue Gene serait capable de calculer entre 15 et 20 mouvements par seconde. Bien que son matériel et ses logiciels soient extrêmement impressionnants, nous devons nous rappeler que la complexité des échecs évolue de façon exponentielle. Selon des estimations récentes , la complexité de l'arbre de jeu des échecs est d'au moins 10 ^ 123 et le nombre de positions potentielles à 10 ^ 46,7.

En supposant qu'il y a une continuation gagnante à partir d'une position donnée et en supposant que le jeu parfait, implique Nest fixe et non limité (sinon son jeu n'est pas parfait!).

Dans ce cas, il faut vraiment travailler en arrière - ce qui est accompli par Endgame Tablebase

Les bases de tous les jeux avec jusqu'à six pièces sont disponibles en téléchargement gratuit et peuvent également être interrogées à l'aide des interfaces Web (voir les liens externes ci-dessous). La base de table Nalimov nécessite plus d'un téraoctet d'espace de stockage

Vous pouvez regarder ici pour une discussion. Bien sûr, vous ne devez pas utiliser la règle des 50 coups, mais selon ce forum, le record est maintenu jusqu'à présent par cette position (noir pour se déplacer):

517 se déplace vers une position gagnante et 525 pour s'accoupler (meilleur jeu des deux côtés). Voir ici , entrée 316. Il s'agit donc d'une position gagnante sans victoire en moins de 525 coups.

Permettez-moi également de reproduire les commentaires de Bourzutschky: "Des terminaisons encore plus profondes à 7 peuvent exister, mais j'en doute. Une telle profondeur est toujours possible avec autant de puissance de feu sur la carte suggère que des terminaisons encore plus profondes peuvent survenir avec 8 pièces, peut-être dans krnnkbbn. Cette fin pourrait être générée avec 64 Go de RAM en quelques mois sur une seule machine à processeur rapide et environ 5 téraoctets de stockage. Des preneurs? "

Edit: Désolé, on dirait que j'ai mal lu la question. Je suppose que tout N raisonnable est bien en dehors de l'horizon d'un ordinateur. Si nous configurons un ordinateur très puissant pour calucléer la position de départ qui est probablement le seul X confiant que nous puissions montrer, disons qu'il pourrait atteindre 10 millions de nœuds par seconde après 10 jours, nous pourrions calculer 10 * 86400 * 10 ^ 8 nœuds = 8,64 * 10 ^ 13 nœuds. Si nous supposons que la position moyenne dans les 20 premiers mouvements a environ 15 mouvements légaux (plus bas parce que le début a beaucoup moins et probablement même légèrement plus bas en raison de l'élagage alpha-bêta), ce qui n'est que d'environ 12 mouvements après 10 jours (position uniquement après le mouvement 6 ) vous voyez donc pourquoi ce problème est moche. Cependant, je pense que le jeu pratique suggère probablement une valeur beaucoup, beaucoup, beaucoup plus élevée. JE'

Ignorons que les échecs sont très probablement un match nul. Nous devons considérer les règles selon lesquelles les échecs sont joués dans la pratique. Dans presque toutes les situations de tournoi, il y a une règle de 50 coups en vigueur qui stipule que le jeu est un match nul si "les 50 derniers coups consécutifs ont été effectués par chaque joueur sans le mouvement d'un pion et sans la capture d'une pièce."

Cela signifie donc que nous pouvons avoir 49,5 coups par capture ou mouvement de pion. Chaque pion peut se déplacer jusqu'à 6 fois et il y a 15 pièces qui peuvent être capturées pour chaque côté (bien qu'une pièce doit rester pour livrer échec et mat) afin que nous puissions mettre une limite supérieure sur le nombre de mouvements.

Cela équivaut à 49,5 * (8 * 2 * 6 (mouvements de pion) + 29) = 6187,5 Cela signifie donc que si les échecs sont une victoire forcée pour les blancs en adhérant à la règle des 50 mouvements, alors il y a au plus 6188 mouvements pour les blancs . Je pourrais probablement réduire cela un tout petit peu sans trop en dire en disant que tous les partenaires K + V qui sont forcés (Rook at Queen uniquement) sont réalisables en moins de 50 coups (je pense à environ 16 jouer avec Nalimov pour quelques cas "difficiles". Je pense donc que nous pouvons probablement soustraire 34 coups de ce total en toute confiance pour 6134!

Par conséquent: si les échecs sont une victoire forcée pour les blancs avec le respect de la règle des 50 coups, alors ils sont au maximum de 6134 coups.