Le nombre d'échecs possibles est-il infini?

16

Cette question est quelque peu liée à Peut-on calculer le nombre total de victoires / tirages / pertes possibles? , mais légèrement différent.

Il y a un épisode récent d'une émission de télévision qui prétend qu'il y a "plus d'échecs possibles que d'atomes dans l'univers". Ils avancent que "chaque mouvement possible représente un jeu différent, un univers différent [..]"; "au deuxième coup il y a 72084 jeux possibles, au troisième - 9 millions, au quatrième --- 318 millions".

Le nombre total de parties d'échecs est-il donc infini, à toutes fins pratiques, compte tenu des limites humaines et technologiques? Et les chiffres ci-dessus résistent-ils réellement à l'examen? (c.-à-d. quels sont les jeux possibles estimés d'ici, disons, le 10e coup?)

Curieusement, Wikipedia semble impliquer que le nombre de jeux peut être estimé:

le nombre de parties possibles [en Go] est vaste (10 761 contre, par exemple, les 10 120 possibles aux échecs)

theory statistics game-complexity landroni
la source
3
Si vous définissez un "jeu" comme l'historique des mouvements, tout jeu qui permet la répétition a des jeux infinis possibles. Snakes and Ladders propose des "jeux" infinis. Si vous êtes intéressé par la complexité de la résolution d'un jeu, ignorez l'historique des mouvements et regardez le nombre d'états possibles dans
lesquels
3
Remarque: les informaticiens s'opposeraient immédiatement à «infini, à toutes fins pratiques». Il est remarquablement dangereux de «arrondir» à l'infini. D'une manière générale, lorsqu'ils font l'erreur de le faire, quelqu'un casse rapidement leur algorithme en montrant que ce n'était en fait pas un infini avec lequel ils avaient affaire. En cryptage, il n'est pas rare d'avoir des algorithmes qui semblaient "incassables jusqu'à la mort thermique de l'univers" qui ont été cassés en raison de quelques astuces qui ont diminué la taille du problème de 10 ^ 80 ou plus
Cort Ammon - Reinstate Monica
2
Si je ne me trompe pas, vous faites référence à la série télévisée Personne d'intérêt, non? Ce que cela signifie, c'est qu'en prévoyant les prochains mouvements possibles, vous devez créer un arbre de décision pour calculer toutes les possibilités. Quand Harold se réfère au `` deuxième mouvement '', cela signifie regarder deux mouvements en avant (le vôtre et l'adversaire; en informatique, il s'agit du 2e niveau de profondeur de l'arbre). Donc, sans faire les calculs, je pense que cela pourrait être correct. Au moins, ce doit être un nombre énorme.
CMPSoares
Vous pouvez trouver cette vidéo intéressante. youtu.be/Km024eldY1A
Jivan Scarano

Réponses:

17

Le nombre maximum de coups dans une partie d'échecs n'est pas infini, c'est 11797 plis = 5898 coups et demi. Cela est dû à la règle des cinquante coups.

Donc non, le nombre de parties d'échecs possibles n'est pas infini.

Le nombre maximum de coups autorisés dans une position est de 218. Donc, une limite supérieure brute pour le nombre de parties d'échecs possibles est 218 ^ 11797 = 10 ^ 27586

Attendez, en fait, après cinquante mouvements sans capture ni mouvement de pion, les joueurs peuvent également continuer à jouer sans réclamer le tirage ...

L'article 9.3 des lois de la FIDE sur les échecs stipule que:

9.3

Le jeu est tiré, sur une réclamation correcte par un joueur ayant le coup, si:

  • il écrit son coup, qui ne peut pas être changé, sur sa feuille de match et déclare à l'arbitre son intention de faire ce coup qui se traduira par les 50 derniers coups de chaque joueur ayant été faits sans mouvement de pion et sans capture, ou
  • les 50 derniers coups de chaque joueur ont été accomplis sans le mouvement d'aucun pion et sans aucune capture.

Je suppose donc que le nombre de parties d'échecs possibles pourrait être considéré comme infini alors ...

Mais si vous n'êtes pas intéressé par les chiffres théoriques précédents:
le nombre moyen de coups légaux dans une position est d'environ 35, et la durée moyenne d'une partie d'échecs est d'environ 40 coups = 80 plis, donc une estimation du nombre de " les jeux d'échecs rationnels sont de 35 ^ 80 = 10 ^ 123
Quant au nombre total de positions légales, il se situe entre 10 ^ 40 et 10 ^ 50.

Sort
la source
Le problème de la répétition peut être résolu en peaufinant la question non pas sur les mouvements mais sur les états. Combien de configurations différentes possibles d'un échiquier sont possibles? C'est la question intéressante du point de vue de la complexité. La répétition n'a pas d'importance, elle répète le même état. De nombreux États ne peuvent pas être atteints, car ils prendraient plus de 50 coups, ou ils sont impossibles en raison de restrictions sur le mouvement des pièces (en particulier les pions).
Schwern
3
@ Tony Ennis: J'ai édité. Mais en fait non, la règle des 50 coups ne garantit pas la fin du jeu, car les joueurs peuvent également choisir de ne pas réclamer le tirage.
Sort
2
Pourriez-vous s'il vous plaît modifier votre réponse afin qu'elle se lise comme une réponse, plutôt que comme une discussion avec vous-même? Vous commencez par affirmer incorrectement que le nombre de jeux est fini, puis corrigez-vous. Faites d'abord la réclamation correcte; si vous voulez alors dire "Mais si les joueurs tirent toujours au sort dès qu'ils y ont droit alors ..." c'est très bien.
David Richerby
11
En fait, en juillet de l'année dernière, une règle de 75 mouvements est obligatoire. Ainsi, la règle des 50 coups ne garantit pas la fin du jeu, mais la règle des 75 coups le fait, bien que la partie la plus longue passe à 17 697 plis. Étant donné un facteur de branchement moyen de 35, on pourrait estimer le nombre possible de jeux à 35 ^ 17697, soit environ 10 ^ 27000.
Deedlit
1
Même si nous ne respectons pas la règle des 50 et des 75 coups, si les joueurs jouent sans réclamer un match nul, à un moment donné, une triple répétition doit se produire. Je ne sais pas si un tirage au sort est nécessaire ici, mais je considérerais un nombre fini de jeux distincts avec des possibilités infinies de répéter un nombre fini de jeux possibles, aux fins de cette question.
11684
6

Q1: Oui. Le nombre total de parties d'échecs peut être considéré comme infini à toutes fins pratiques. Nous n'avons pas la technologie pour forcer brutalement les 13 premiers mouvements depuis la position initiale.

Q2: Les nombres réels jusqu'à la profondeur 13 sont connus. Le nombre exact de positions possibles pour les 10e coups est de 69 352 859 712 417. Lisez cet article Wikipedia pour plus de détails.

Il y a une tentative de profondeur 14 mais jusqu'à présent, le calcul après des mois et des mois est toujours en cours.

Bonjour le monde
la source
Oui, des chiffres impressionnants. Drôle, nous ne pouvons pas calculer plus de 14 coups ... Je me demande combien de coups peuvent être calculés pour Go ... Trois? :)
landroni
Il n'a pas besoin d'être "considéré comme infini à toutes fins pratiques" car il est en fait infini. Bien que les règles de 50 coups et de répétition triple permettent à chaque joueur de réclamer un match nul, elles ne mettent pas automatiquement fin à la partie.
David Richerby
1
@landroni Go est probablement plus facile à calculer que les échecs. Il y a 361 jeux à un coup, 361 * 360 jeux à deux coups et 361 * 360 * 359 jeux à trois coups. Le nombre de quatre parties de coup dépend si le suicide est autorisé. Si c'est le cas, alors il y aura 358 quatrièmes coups possibles, à moins que les deux premières pierres noires ne prennent la première pierre blanche dans le coin, auquel cas il y en a 359. Donc 361 * 360 * 359 * 358 + 8 jeux à quatre mouvements. Si le suicide n'est pas autorisé, il y a 361 * 360 * 359 * 358 - 8 * 358 parties à quatre coups. Vous pouvez continuer de cette façon, en séparant les cas - 14 mouvements sont probablement réalisables avec un effort informatique.
Deedlit
4
Notez qu'il s'agit de 13 demi- mouvements, ou plis - sept mouvements en blanc et six en noir.
RemcoGerlich
2
@DavidRicherby: la règle des 75 coups (nouvelle depuis juillet 2014) est cependant obligatoire.
RemcoGerlich
2

À un moment donné, vous manquerez de combinaisons. La réponse est donc fondamentalement non.

Nuach
la source
1

Un argument simple selon lequel le nombre de parties d'échecs est fini pourrait être le suivant.

En raison de la règle des 50 coups, toute sous-séquence de 50 coups d'une partie d'échecs donnée contiendra au moins une capture ou un coup de pion. Puisqu'il y a un nombre infini de pièces sur le plateau et que les pions ne peuvent se déplacer que de façon finie plusieurs fois pendant une partie, le nombre de coups dans une partie d'échecs a une limite finie. Comme à chaque coup, les possibilités sont infiniment nombreuses, le nombre de tous les jeux est fini.

Notez que cet argument est presque inutile si l'on veut obtenir une estimation du nombre de jeux possibles. Si pour rien d'autre, la seule chose que j'utilise ci-dessus est la règle des 50 mouvements et la façon dont les pièces se déplacent, donc les répétitions sont autorisées (max. 50 répétitions, bien sûr). Par conséquent, l'argument est juste théorique, pas pratique.

Zvonimir
la source
0

La règle des 50 coups comprend «sur une réclamation correcte»: aucune réclamation, aucune mise en œuvre de la règle. Il en va de même pour la répétition. Ergo, infini.

Sans un nombre maximum de mouvements obligatoires, bien sûr.

x1797n7917
la source
4
Plus maintenant. Les nouvelles lois d'échecs de la FIDE ont une règle de 75 coups avec un tirage automatique. Voir fide.com/fide/handbook.html?id=171&view=article 9,6 $.
Dag Oskar Madsen
0

Sur la compréhension des lois de la FIDE - Tout d'abord, elles doivent être utilisées avec les tournois - donc étant donné que les informations comprennent comment les lois de la FIDE ne concernent pas deux amis qui décident de jouer? Pour deux amis, qui se réduisent à deux rois seulement, ils peuvent se poursuivre autour du plateau une quantité infinie s'ils le souhaitent. (Plausible-pas vraiment, possible-oui)

Sur la loi FIDE 9.2 - 50 coups consécutifs doivent être effectués là où aucun pion n'a été déplacé et aucune capture n'a été effectuée. Ce ne serait évidemment pas un "jeu à 50 coups" (par exemple, 1.e4 signifierait encore 50 coups consécutifs sans qu'un pion ne soit déplacé ou capturé)

Sur la loi FIDE 9.6 - 75 coups consécutifs ... Même raisonnement que ce n'est pas un jeu à 75 coups.

L'une des premières preuves d'un match enregistré a été de 14 coups consécutifs (1. e4 b6 2. d4 Bb7 3. Bd3 f5 4. ef5 Bg2 5. Qh5 g6 6. fg6 Nf6 7. gh7 Nh5) Même si le 15 était échec et mat - si le vainqueur avait décidé de ne pas échouer, il aurait encore eu besoin de 75 coups supplémentaires pour déclarer le tirage au sort selon la loi 9.6 de la FIDE (avec 12 pions restants sur le tableau - je doute que cela se soit produit en 75 coups)

Respectueusement, CFC

Clayton Currier
la source
2
Eh bien, si deux amis qui ne se soucient pas des règles officielles aiment jouer à un jeu absurde et l'appeler échecs, ils peuvent! Mais devrions-nous appeler cela des échecs aux fins de ce site? Une position avec seulement deux rois est un tirage immédiat.
RemcoGerlich
0

Étant donné que d'autres réponses ici pointent vers la répétition ou similaire, je souhaite modifier votre question comme suit: "Le nombre de POSITIONS d'échecs possibles est-il infini. La réponse est" Non ". Le total est cependant très élevé et estimé entre 10 et 120. On pense que le nombre total d'atomes dans l'univers n'est que de 10 à la puissance 80. Wow!

Le nombre 10 à la 134e puissance donnée par un intervenant précédent peut être correct.

Le jeu chinois "Go" est encore plus varié que les échecs (mais ennuyeux en comparaison puisque les échecs ont des pièces avec des capacités différentes, alors que dans Go toutes les pièces sont les mêmes).

markbolles44
la source
0

Je regarde peut-être cela de manière trop simpliste, mais il me semble que le nombre doit être fini. Si nous regardons le plateau et les pièces plutôt que le jeu d'échecs et calculons le nombre de variations possibles, nous pouvons obtenir une réponse finie. Esprit ahurissant mais fini. Étant donné que toutes les combinaisons ne sont pas possibles dans un jeu d'échecs, le nombre de combinaisons dans un jeu d'échecs doit être inférieur à ce nombre fini et donc un nombre fini lui-même.

Justin
la source