by François Labelle

Abstract

The longest possible chess game is 8848.5 moves long. The number of possible chess games is at least 1029241 according to a Monte Carlo simulation, and at most 1034082 according to a calculation.

Introduction

What is the length of the longest possible chess game? It used to be infinite because the 50-move rule and the draw by 3-fold repetition aren’t automatic—they must be claimed by one of the players. Some people answered the question assuming that a draw must be claimed if it is available, presumably to get a more interesting answer. We no longer need to assume anything: In 2014, FIDE introduced two new rules, the 75-move rule and the draw by 5-fold repetition, which are automatic. When introduced, the 5-fold repetition rule applied to consecutive repetition so it could be avoided by the players, but the 75-move rule cannot be avoided and makes the longest possible chess game finite, and the number of possible chess games finite. (In 2017, the 5-fold repetition rule has been modified to no longer require consecutive repetition, giving a second independent reason why chess is finite.)

Length calculation

Article 9.6b from the Laws of Chess of 2014 says that the game is drawn if "any consecutive series of 75 moves have been completed by each player without the movement of any pawn and without any capture. If the last move resulted in checkmate, that shall take precedence". So at a high-level, the plan will be to play 74.5 moves without the movement of any pawn and without any capture, then move a pawn or make a capture to avoid an immediate draw, and repeat. There are 16 × 6 = 96 pawn moves available, and 30 captures available, giving us 126 "delay plies" (half-moves that can be used to delay the draw). For the pawns to cross past each other, 8 of them will have to capture as they move, so we’re down to 118 delay plies. Another concern is that by waiting exactly 74.5 moves before playing a delay ply, Black gets to do all the delay plies, which won’t work because White has to play delay plies too. Each time we need to switch control we’ll have to play 74.0 moves between 2 delay plies instead of 74.5 moves. It’s not too hard to find a way to schedule all 118 delay plies by switching control 4 times, but it’s possible to be clever and switch control only 3 times. At the end we have a choice between capturing to get down to 2 kings and draw that way, or playing a non-capturing move and draw by the 75-move rule. Sometimes the second choice is the only option because the first choice may require switching control which costs 0.5 moves. Taking all of that into account, I believe that the length of the longest possible chess game is 118 × 75.0 − 3 × 0.5 = 8848.5 moves.

For comparison with other values on the Internet, the equivalent calculation when the players are forced to claim a draw by the 50-move rule gives 118 × 50.0 − 3 × 0.5 = 5898.5 moves. This is in agreement with a section of the German Wikipedia article on the 50-move rule. According to this Retros mailing list post, Karl Fabel obtained this number as early as 1947. The 50-move rule is different from the 75-move rule because it is not automatic, but also because Article 9.3a says that the ply triggering the 50-move rule will be written on the player’s scoresheet, and that the player intends to play it, but it doesn’t clearly state that the ply is played or that it is part of the game. To avoid losing 0.5 moves due to this, for a 50-move-rule record I suggest using a plan which ends with a capture on the last move (without switching control a 4th time).

A specific plan (Deedlit and Tatzelwurm)

Below is an explicit schedule for the 118 delay plies. It switches control 3 times using the idea discussed by Deedlit and Tatzelwurm in this chess.com forum thread.

In the diagrams below, the position of the pawns is important, but the position of the other pieces is not (just their number). The type of promotion can be changed.

After 0.0 moves

Initial position

After 975.0 moves

Phase 1:

• Black pushed 6 pawns (13 delay plies)

After 4124.5 moves

Phase 2:

• White promoted 7 pawns, making 7 captures to get around the black pawns (7×6=42 delay plies)

After 7724.0 moves

Phase 3:

• Black promoted 8 pawns, making 1 capture to get around the white e2 pawn (35 delay plies)
• Black captured every remaining white piece except the king and the e-pawn, making 13 capture (13 delay plies)

After 8848.5 moves

Phase 4:

• White promoted 1 pawn to rook or queen (6 delay plies)
• White captured the remaining 8 black pieces (8 delay plies)
• Black didn’t capture the last white piece because that would require switching control. Instead the players drew by the 75-move rule (1 delay ply)

An alternative plan (falconbrook)

Another way to switch control 3 times is described in the post by falconbrook (Jeff Falkenbach) in this other chess.com forum thread. This alternative plan can end with a capture, so it is suitable for a 50-move rule record. It appears to be the same plan as the one discussed on the German Wikipedia article mentioned above. Below I show the first phase.

After 300.0 moves

• Black captured 2 knights and pushed 2 pawns (4 delay plies)

A maximum-length chess game

The game-tree generated by a plan such as those above can be explored with a computer to find an explicit game that reaches the maximum number of moves. This can also give a lower bound on the number of games of maximum length (see the next section). To get the best possible lower bound, I chose the plan by Deedlit and Tatzelwurm and added the following constraints:

• In Phase 3, promote the 8 black pawns before capturing 13 white pieces. This gives White more possible moves because White keeps its pieces for longer.
• In Phase 4, promote the 1 white pawn before capturing the 8 black pieces. This gives Black more possible moves for the same reason.
• Always promote to queen. Forcing a specific promotion decreases the number of possibilities by 4, but this is paid back by the higher mobility of the queen in the rest of the game.

Below is a randomly generated game obeying these constraints. Alternatively here’s the PGN file, but be warned that many chess programs choke when importing a very long game. I chose a game ending in checkmate to make sure that Article 1.3 (draw by impossibility of checkmate) doesn’t trigger a few moves before the end.

(it takes a few seconds for the viewer to open).

Playing this game as slowly as possible while still obeying FIDE’s standard time control would take 2 × (90 + 30 + 0.5×8848.5) minutes = 6.31 days.

Number of maximum-length chess games

By randomly pruning the tree and keeping track of the amount of pruning done, it’s possible to estimate the total number of games that satisfy the plan. This is the same technique that I used for perft estimation in 2007 (for more details on perft estimation see this article by Daniel Shawul [pdf]). I explore the tree level by level, capping the number of positions at each ply using reservoir sampling. The larger the cap is, the more accurate the estimate is. Technically the estimate is unbiased, but in practice for the problem at hand it is a lower bound because the random moves that are played are unlikely to discover the very best way of maintaining a high fan-out. The likelihood increases with a large cap, so in practice a larger cap gives a tighter lower bound.

Using the notation from the integer sequence A048987, the number of games that are exactly 8848.5 moves long is called a(17697). The fact that this is the maximum length means that a(17698) = 0. To estimate a(17697) I ran a Monte Carlo simulation using a cap of 1 million positions and obtained a(17697) > 1026827. This implies an average growth factor of 32.8 per ply.

Number of possible chess games

The lower bound on a(17697) is also a lower bound on the total number of chess games, but a better lower bound can be obtained by following a slightly shorter plan. For example, by switching control during Phase 1 we would lose a few plies, but we would open the white pawn wall earlier, which would increase the fan-out early in the game.

In an attempt to get the highest possible fan-out, I used the following plan:

• White and Black capture 4 pieces each to cross pawns, and promote all 16 pawns to queens. They switch control 16 times. (96 delay plies)
• White and Black capture the remaining pieces, switching control 7 times. (22 delay plies)

A lot of these numbers are arbitrary and I do not claim that the plan is optimal, but it is extremely time-consuming to run a simulation each time I want to test an idea, so this will have to do for now. The result of the simulation (still using a cap of 1 million positions) is a significantly larger lower bound: a(17677) > 1029241, implying an average growth factor of 45.1 per ply.

Upper bound

The maximum number of available moves in a position seems to be 218. In that position, the number is much lower for Black, and 218 isn’t sustainable for White. On this page I briefly argue that the largest sustainable growth factor in chess is 84.3. This gives an upper bound of 84.317697 < 1034082.

Hardy’s estimate

Hardy estimated the number of possible chess games to be 101050, but he didn’t give his reasoning. Some people think that it is a misprint for the more reasonable estimate 10105. Other people think that his estimate assumes that players are forced to claim a draw by the 3-fold repetition rule, but not by the 50-move rule.

Graph

Below is a smoothed graph of the growth factor per ply obtained throughout the simulations. We see that the new plan (which attempts to maximize the number of games) isn’t as restrictive as the old plan, and leads to higher growth factors. It was nice to see the simulation discover through random search something close to the upper bound that I derived in 2007. Without a plan, the simulation discovers a way of increasing the growth factor early, but it doesn’t realize that doing so will force a draw much sooner.

---

page created: November 14, 2015 page updated: January 6, 2020 (mentioned the 5-fold repetition rule modification of 2017, fixed some broken links, made the iChess viewer work under https). page updated: October 17, 2020 (fixed a broken link). back to Chess Problems by Computer

the diagrams on this page were created using these chess piece images