The Longest Possible Chess Game
- 59,217 Reads
- 48 Comments
Chess is a game of small advantages and large numbers. For example, according to the U.S. Census Bureau population clock (http://www.census.gov/ipc/www/popclockworld.html) there were 6,637,552,653 people living on the earth on December 14, 2007, as I write this.
Suppose that each of these persons was engaged in a game of chess with an alien from another world, and they played bullet chess with only one minute on each…um…being’s clock to finish each game, and each game took the maximum two minutes to complete. Further suppose that these beings played continuously without rest. Under these circumstances there would be a total of 4,779,037,910,160 games played per day. After one non-leap year they would have played 1,744,348,837,208,400 games, and after a billion years they would have played 1.74434883721 x 10^24 games.
That may sound like a large number of games, but even if we increased their playing speed to an entire game in only one second, the Chess Gods would laugh at the small number of games thus presented to them for analysis.
The number based on one second games is vanishingly small compared to the number of possible games in chess even if we limit those games to just 40 moves.
And games can last longer than 40 moves. I’ve played some games myself that approached 100 moves against my PDA. Recently, I’ve begun wondering just how long the longest possible chess game could be.
Within a single google I was able to find that the longest recorded game of chess in history was an epic played in Belgrade in 1989. The Belgrade Marathon was a contest between Ivan Nicolic and Goran Arsovic that lasted over 20 hours and ended in a draw after 269 moves due to the so-called “50 Move Rule”, which I will discuss in a moment.
Here is that amazing game.
That is a long game indeed, but it is far from the longest possible game, which is what we are trying to determine. Is it 1,000 moves? 10,000 moves?
The site chess-poster.com http://www.chess-poster.com/english/notes_and_facts/did_you_know.htm claims that the longest possible game consists of 5,949 moves, but did not offer any details regarding the computation. Since I have not seen this particular number documented elsewhere, I decided to compute it for myself to either verify or refute the claim.
The first question to ask is whether there are any limiting factors that prevent a game from continuing ad infinitum. For this, we turn to two authoritative bodies, Fédération Internationale des Échecs (FIDÉ) and the U.S. Chess Federation (USCF). According to the FIDÉ official handbook rules: http://www.fide.com/official/handbook.asp?level=EE101
“The game may be drawn if each player has made at least the last 50 consecutive moves without the movement of any pawn and without any capture. (See Article 9.3)
The game is drawn, upon a correct claim by the player having the move, if
a. he writes his move on his scoresheet, and declares to the arbiter his intention to make this move which shall result in the last 50 moves having been made by each player without the movement of any pawn and without any capture, or
b. the last 50 consecutive moves have been made by each player without the movement of any pawn and without any capture.”
This is the well-known 50 move rule in competition chess. Let us compare that definition against its counterpart at the USCF.
“50 Move Rule-
If no pawns or pieces have been traded for more than 50 moves, a game is determined to be a draw. This rule requires that the player who makes the claim write down his moves.”
These two definitions differ. In the USCF version there is no reference to the absence of a pawn move, so presumably the 50 moves could include a pawn move. And a careful reading of both versions reveals that the game is not required to be drawn, only that it may be at the discretion of the side to move. Let us be merciful on the poor players, however, and assume that any extremely long game would indeed result in a draw under the 50 move rule. Otherwise, we have nothing further to discuss here regarding the longest possible game.
With respect to the issue of a pawn move taking place within the 50 moves I have to rule against my own countrymen and side with the FIDÉ version of the rule, which is much more clearly written, and which prohibits pawn moves during the 50.
So here is our approach, roughly speaking. (We will see a modification to this below.) We need to compute 49.5 full moves, where a full move is a move by each side, followed by either a pawn move or a capture, and then repeat this process until it is no longer possible. The maximum number of pawn moves is 6, at which point it will promote to another piece. Since there are 16 pawns it appears that we could have 6x16 = 96 total pawn moves. However, before all 6 moves for a pawn can occur the opposing pawn in front of it must be dealt with, as the following diagram shows.
There are two ways to manage this obstacle. The first is for one pawn to capture another, allowing the victor and its companion behind it to advance to promotional nirvana. The pawn that previously opposed the victor on the original file is also now free to advance its full 6 moves. If we allow the vanquished pawn to advance to its 6th rank, that pawn would have its maximum number of moves before its sacrifice. For example if the e2 pawn moved forward 4 times to reach the e6 square, whereupon it was captured by its opponent on f7, then the remaining 3 pawns on the e and f files could continue their full 6-move journey. Thus, among these 4 pawns there would be a total of 22 pawn moves. If a similar set of circumstances occurred on the other 3 pairs of adjacent files, then 88 of the 96 theoretically possible pawn moves could take place.
However, the second way of dealing with the issue would allow all of those 96 moves to take place. This could happen if the capturing pawn took a piece, rather than an enemy pawn. Look at the simplified diagram below, which shows a position after fxe6.
You can see that the white pawn on the f file now has no enemy pawn in front, so it can advance unopposed. But what about the 3 pawns now on the e file? This can be handled in a similar fashion. We simply offer up a piece for the white pawn on the e file so it can capture onto the f file, and now both white pawns on the f file can advance and both black pawns on the e file can advance. Clearly we can resolve all of the opposing pawns in this same fashion, allowing all 96 pawn moves to take place.
We are now almost ready to proceed with our computation. The game will begin with knight moves, 49 by each side and ending with a 50th knight move by white. With black to move he must either capture or move a pawn to avoid the draw, so let us say that he plays any pawn forward one square, say e6. This frees his queen as well as his bishop and king to move onto e7, if they so desire. Remember, we’re only interested in moving as many times as possible, not in winning the game.
Both sides then move their pieces repeatedly until another 49.5 full moves have occurred, at which point black again either moves a pawn, or he could also capture to relieve the monotony.
But wait! This cannot proceed indefinitely or we will fail to achieve our goal. Notice that Black is doing all the work on his 50th move, and if this continues unchecked (sic.) we could end up with the position shown above in Diagram 2, and now a pawn must capture a pawn and we will lose some of our precious 96 pawn moves.
Clearly, we cannot always play the full 49.5 moves before a pawn advances or a capture occurs. In the latter case, we would end up with all of White’s pieces being taken, and he would have only pawns remaining on the board. In order for them to move at all, they clearly have to move sometime before Black takes his 50th move on these sets of 50.
And for both sides, some of the pawn moves need to involve piece capture rather than forward moves, as discussed previously.
So we must alter our original outline and we will say that the game begins with 49.5 knight moves, followed by a Black pawn move one square. This is then followed by 49 full moves, whereupon White moves a pawn one square on his 100th move. We then repeat this process, alternating between Black making a pawn move or capture on his 50th move and White doing so.
We can now begin to sketch our computational formula as follows:
(49.5 + b) + (49 + w) + (49.5 + w) + (49 + b) + … , where b stands for a move by Black that consists of a pawn move or a capture, and w represents a pawn move or capture by White. The ellipsis stands for continuing repetitions of exactly the same terms of the formula that are fully written out. Notice the pattern of 49.5 moves alternating with 49 moves on adjacent terms, and each of b and w occurring twice in a full cycle.
Now we need to determine how many times this cycle can repeat itself. As we said each b or w can be a pawn move or a capture, and we want some of the pawn moves to involve captures. To be precise, we want exactly one such pawn capture per file as outlined above in order for all pawns to be able to promote. Thus, it seems that we need 8 moves involving pawns capturing pieces. This can involve either the capture of original board pieces or pieces that were created from previously promoted pawns. It does not matter which side does the capturing, just so long as one per file happens. And since there are those 8 pieces captured by pawns, we know that after the 96 pawn moves, there will be 24 units remaining on the board.
And following those 96 pawn moves, the remaining occurrences of b and w necessarily involve pieces capturing other pieces. Since there are 22 pieces available for capture (omitting the Kings), we now have the necessary information to complete our formula.
There will be 96 terms of the form (N + m), where N is 49.5 in 48 of those terms, and 49 in the other 48 terms, and m will be b in 48 terms and w in 48 terms, equally distributed between the 49.5 and the 49 coefficient terms.
We can write this much out as:
24(49.5 + b) + 24(49.5 + w) + 24(49 + b) + 24(49 + w)
We then add to that formula the following additional terms needed for the remaining 22 captures:
(49.5 + b) + (49 + w) + (49.5 + w) + (49 + b) + … where each of b and w now represents a capture of an opposing piece by Black and White, respectively. There are four terms in this expression and since we need 22 captures, we will have 5 occurrences of each term listed plus an additional occurrence of the first two terms (49.5 + b) and (49 + w).
Thus, the formula for the final 22 captures can be written as:
6(49.5 + b) + 6(49 + w) + 5(49.5 + w) + 5(49 + b).
Combining this with the previous formula we arrive at:
24(49.5 + b) + 24(49.5 + w) + 24(49 + b) + 24(49 + w) + 6(49.5 + b) + 6(49 + w) + 5(49.5 + w) + 5(49 + b), which simplifies to
30(49.5 + b) + 30(49 + w) + 29(49.5 + w) + 29(49 + b)
Since each of b and w represents a single half-move, we can combine terms of the form (49.5 + m) and we can combine terms of the form (49 + m) arriving at
59(49.5 + 0.5) + 59(49 + 0.5) = 59(50) + 59(49.5) = 2,950 + 2,920.5 = 5,870.5
Thus, the math tells us that the longest possible game is 5,870 full moves plus an additional move by White, which would be that final capture, apparently by White’s King resulting in a necessary draw, since only the Kings would be left on the board.
My answer computed here differs from the 5,950 figure that appears on chess-poster.com, which is exactly 78.5 moves larger than my figure.
One or both of us has made an error in calculation. I am perfectly willing to believe that it is me, and I will issue a revised version of this blog along with appropriate credit given to the mathematician who corrects either myself or chess-poster.com or both.
Regardless of who is correct, the preceding discussion shows us that pawns are not only the soul of chess, but define it in a very mathematical sense as well. And for any of you who try to actually play out a longest possible game (there will be very many such games, not just one), remember to choose your move carefully, in chess as in life.