How many different ways are there to checkmate in the early game?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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')

Answer 4

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:

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.