14

We all know the shortest possible checkmate is 4 ply:

  1. f3 e5

  2. g4 Qh5#

This isn't the only possible move order. In fact, there are 8, depending on whether white moves the f or g pawn first, whether he moves the f pawn to f3 or f4, and whether black plays e6 or e5. Of course, this makes up only a tiny fraction of the possible 4-ply sequences of moves, but these are the only ones that end the game.

What I'm looking for is, for small numbers of ply, how many sequences of moves end in checkmate vs not ending in checkmate. Ideally what I'd like is something along the lines of

  • 4 ply: X non-checkmate sequences, 8 4-ply checkmates
  • 5 ply: Y non-checkmate sequences, 8 4-ply checkmates, N 5-ply checkmates
  • 6 ply: Z non-checkmate sequences, 8 4-ply checkmates, N 5-ply checkmates, M 6-ply checkmates

and so on for as deep as this is reasonable to do.

This is inspired by a Math.SE question about the probability of two players making random moves resulting in the same chess game. I suspect the short games heavily dominate this probability, which should make the probability easy to approximate, but it'd be nice to have the real numbers to work with.

  • 1
    Related (but not identical) question which you may find of interest: chess.stackexchange.com/questions/24359/… – itub Aug 9 at 20:48
  • 2
    Based on the context of your question, you also may be interested to know that a game can end in a draw due to repetition at about 8 ply. – D M Aug 9 at 20:53
  • 1
    I don't think the data you're asking for here is enough to provide accurate bounds for the probabilities in the Math.SE question. You need more information about the structure of the game tree. (For an illustrative counterexample, consider a game where there are two possible choices for the first move: A and B. If the first move is A, there are 1 million distinct possible choices for the second move, whereas if it's B, the only possible second move is C. Now the game has 1,000,001 possible two move sequences, but the probability of a random player ending up playing the sequence B,C is 50%.) – Ilmari Karonen Aug 11 at 8:27
  • @IlmariKaronen That's true and I thought of that since I posted the question. However, I don't think the spread on the branching ratio of the game tree increases that quickly, with the exception of lines that contain a check. If the total contribution to the probability drops off quickly with ply, the approximation should still work reasonably well. – eyeballfrog Aug 12 at 13:23
25

There are no checkmates from 0-3 ply.

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" is the number of checkmating moves made on the final ply. So for 5 ply, there are 347 checkmating sequences of exactly length 5.

These values are from: https://www.chessprogramming.org/Perft_Results

Currently there is no checkmate data for 10 ply and above, presumably due to the computational resources needed.

To obtain more specific data (e.g. the lines themselves), you would need to write your own perft program which saves lines ending in checkmate.

13

This sequence of integers is known as A079485 in the On-Line Encyclopedia of Integer Sequences (OEIS) and numbers up to and including 13 ply are known with various references available.

  • REFERENCES Homer Simpson, Chess Review, Jan-Feb 1982. Ok, I made part of that up, but it would be funny... – Michael Aug 11 at 22:05
  • OEIS really does have everything, doesn't it? – eyeballfrog Aug 13 at 4:41
8

Here's a simple Python program that answers the question but is slow, taking 40 minutes to run to 5 plies on my laptop (and increasing at least 30-fold per additional ply). A nice thing is that it prints out the games, if you need that. I could post the output here but didn't want to make a 347-line long answer... :-)

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')
  • For future reference you can throw stuff like that output on pastebin.com; pick never expires. – Jason C Aug 12 at 0:42
  • The comments above suggest that exploring the actual game tree may be necessary for this calculation, so this program may prove quite helpful. Thanks. – eyeballfrog Aug 12 at 13:25
7

The top person that I know for this kind of analysis is François Labelle, who has computed many numbers associated with chess (including an estimate of the maximum growth rate of the number of chess games as a function of ply) and in particular has computed the number of checkmates up to ply 13. For values up to ply 12, see the figure in http://wismuth.com/chess/chess.html.

Then at http://wismuth.com/chess/statistics-games.html, he gives specific figures up to ply 13, which has 346,742,245,764,219 checkmate games apparently.

For the total number of games, he quotes results from others who've gone up to ply 15(!) but I think they didn't track checkmates.

From plies 5-13 there's about 1 chance in 10,000 that a move delivers mate. But it seems to be significantly easier to mate as White compared to Black:

graph of ply versus mate chance

The growth rate of number of games is also greater for White moves over Black moves, but that's just about 1%, much weaker than the pattern identified here.

I enjoy random games of chess. Sometime it would be nice to link that with an online quantum random number generator, to have a program which is playing all games of chess, if the multiple worlds hypothesis holds.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.