Combien de façons différentes existe-t-il pour échec et mat en début de partie?

15

Nous savons tous que le mat le plus court possible est de 4 plis:

  1. f3 e5

  2. g4 Qh5 #

Ce n'est pas le seul ordre de déplacement possible. En fait, il y en a 8, selon que le blanc déplace le pion f ou g en premier, qu'il déplace le pion f sur f3 ou f4, et que le noir joue e6 ou e5. Bien sûr, cela ne représente qu'une infime fraction des séquences de mouvements à 4 plis possibles, mais ce sont les seuls qui mettent fin au jeu.

Ce que je recherche, c'est, pour un petit nombre de plis, combien de séquences de mouvements se terminent par échec et non se terminant par échec. Idéalement, ce que j'aimerais, c'est quelque chose comme

  • 4 plis: X séquences sans échec et mat, 8 camarades à 4 plis
  • 5 plis: Y séquences sans échec et mat, 8 camarades à 4 plis, N camarades à 5 plis
  • 6 plis: Z séquences sans échec et mat, 8 compagnons à 4 plis, N à 5 plis, M à 6 plis

et ainsi de suite aussi profondément que cela est raisonnable à faire.

Ceci est inspiré d'une question Math.SE sur la probabilité que deux joueurs effectuent des mouvements aléatoires aboutissant au même jeu d'échecs. Je soupçonne que les jeux courts dominent fortement cette probabilité, ce qui devrait rendre la probabilité facile à approximer, mais ce serait bien d'avoir les vrais chiffres avec lesquels travailler.

globe oculaire
la source
1
Question connexe (mais pas identique) qui peut vous intéresser: chess.stackexchange.com/questions/24359/…
itub
2
En fonction du contexte de votre question, vous serez peut-être également intéressé de savoir qu'un jeu peut se terminer par un nul en raison de la répétition à environ 8 plis.
DM
1
Je ne pense pas que les données que vous demandez ici soient suffisantes pour fournir des limites précises pour les probabilités dans la question Math.SE. Vous avez besoin de plus d'informations sur la structure de l'arbre de jeu. (Pour un contre-exemple illustratif, considérons un jeu où il y a deux choix possibles pour le premier coup: A et B. Si le premier coup est A, il y a 1 million de choix possibles distincts pour le deuxième coup, alors que si c'est B, le seul le deuxième coup possible est C. Maintenant, le jeu a 1 000 001 séquences de deux coups possibles, mais la probabilité qu'un joueur aléatoire finisse par jouer la séquence B, C est de 50%.)
Ilmari Karonen
@IlmariKaronen C'est vrai et j'y ai pensé depuis que j'ai posté la question. Cependant, je ne pense pas que l'écart sur le taux de branchement de l'arbre de jeu augmente aussi rapidement, à l'exception des lignes qui contiennent un chèque. Si la contribution totale à la probabilité diminue rapidement avec le pli, l'approximation devrait quand même fonctionner raisonnablement bien.
eyeballfrog

Réponses:

26

Il n'y a pas de camarades de contrôle de 0-3 plis.

4 ply: 8 checkmates, 197,281 total nodes
5 ply: 347 checkmates, 4,865,609 total nodes
6 ply: 10,828 checkmates, 119,060,324 total nodes
7 ply: 435,767 checkmates, 3,195,901,860 total nodes
8 ply: 9,852,036 checkmates, 84,998,978,956 total nodes
9 ply: 400,191,963 checkmates, 2,439,530,234,167 total nodes

"checkmates" est le nombre de mouvements d'échec et mat effectués sur le pli final. Donc pour 5 plis, il y a 347 séquences de matrices de longueur exactement 5.

Ces valeurs proviennent de: https://www.chessprogramming.org/Perft_Results

Actuellement, il n'y a pas de données de matrices de contrôle pour 10 plis et plus, probablement en raison des ressources de calcul nécessaires.

Pour obtenir des données plus spécifiques (par exemple les lignes elles-mêmes), vous devez écrire votre propre programme perft qui enregistre les lignes se terminant par échec et mat.

konsolas
la source
13

Cette séquence de nombres entiers est connue sous le nom de A079485 dans l'Encyclopédie en ligne des séquences de nombres entiers (OEIS) et les nombres jusqu'à 13 plis inclus sont connus avec diverses références disponibles.

orlp
la source
REFERENCES Homer Simpson, Chess Review, Jan-Feb 1982. D'accord, j'en ai fait une partie, mais ce serait drôle ...
Michael
OEIS a vraiment tout, n'est-ce pas?
eyeballfrog
8

Voici un programme Python simple qui répond à la question mais est lent, prenant 40 minutes pour s'exécuter sur 5 plis sur mon ordinateur portable (et augmentant au moins 30 fois par pli supplémentaire). Une bonne chose est qu'il imprime les jeux, si vous en avez besoin. Je pourrais poster la sortie ici mais je ne voulais pas faire une longue réponse de 347 lignes ... :-)

import chess
from chess import pgn

def dfs(board, depth):
    global n
    result = board.result(claim_draw=True)
    if result != '*':
        game = pgn.Game.from_board(board)
        print(game.mainline())
    elif depth > 0:
        moves = list(board.legal_moves)
        for move in moves:
            n += 1
            board.push(move)
            dfs(board, depth-1)
            board.pop()

n = 0
try:
    board = chess.Board()
    dfs(board, 4)
except KeyboardInterrupt:
    pass
print(n, 'positions checked')
itub
la source
Pour référence future, vous pouvez lancer des trucs comme cette sortie sur pastebin.com; le choix n'expire jamais.
Jason C
Les commentaires ci-dessus suggèrent que l'exploration de l'arbre de jeu réel peut être nécessaire pour ce calcul, donc ce programme peut s'avérer très utile. Merci.
eyeballfrog
7

La principale personne que je connais pour ce type d'analyse est François Labelle, qui a calculé de nombreux nombres associés aux échecs (y compris une estimation du taux de croissance maximum du nombre de parties d'échecs en fonction du pli) et en particulier a calculé le nombre de compagnons de contrôle jusqu'à la couche 13. Pour les valeurs jusqu'à la couche 12, voir la figure dans http://wismuth.com/chess/chess.html .

Ensuite, à http://wismuth.com/chess/statistics-games.html , il donne des chiffres spécifiques jusqu'à la couche 13, qui a apparemment 346 742 245 244 764 219 jeux d'échec et de mat.

Pour le nombre total de matchs, il cite les résultats d'autres joueurs qui ont grimpé jusqu'à 15 (!) Mais je pense qu'ils n'ont pas suivi les camarades.

Des plis 5 à 13, il y a environ 1 chance sur 10 000 qu'un coup livre du maté. Mais il semble être beaucoup plus facile de s'accoupler en tant que blanc que noir:

graphique du pli par rapport à la chance du partenaire

Le taux de croissance du nombre de jeux est également plus élevé pour les coups blancs que pour les coups noirs, mais c'est à peu près 1%, beaucoup plus faible que le modèle identifié ici.

J'aime les parties d'échecs aléatoires. Parfois, ce serait bien de lier cela à un générateur de nombres aléatoires quantiques en ligne, d'avoir un programme qui joue à tous les jeux d'échecs, si l'hypothèse des mondes multiples tient.

Laska
la source