Countdown

October 30, 2009 1:31 PM

Is there an enumeration of complete chess games?

Has anyone made an accurate (ideally, "closed form") count of possible chess games?

I found an older article via Google that does a very rough guess-timate of how many complete chess games are possible.

I'm curious if anyone has since tried to count all possible games, given standard FIDE rules, played to completion. Presumably, for example, it is not exponential because some moves will result in an end state ("checkmate" or "stalemate") faster than other moves.

• Please do not offer speculation about the answer
• Please do not link to Google search results (unless you have found something that answers the question as specifically framed)
• Thanks!

posted by Blazecock Pileon to science & nature (10 comments total)

According to this page (from when scientists "solved" checkers), chess has approximately 10^40-50 positions, and cannot be "solved" using currently available technology. So I'd say no, no one has done what you're seeking.
posted by Admiral Haddock at 1:38 PM on October 30

MathWorld says "Hardy (1999, p. 17) estimated the number of possible games of chess as 10¹⁰⁵⁰.

The number of possible games of 40 moves or less P(40) is approximately 10^40 (Beeler et al. 1972), a number arrived at by estimating the number of pawn positions (in the no-captures situation, this is 15^8), multiplying by the possible positions for all pieces, then dividing by two for each of the (rook, knight) pairs that are interchangeable, and dividing by two for each pair of bishops (since half the positions will have the bishops on the same color squares). (However, note that there are more positions with one or two captures, since the pawns can then switch columns; Schroeppel 1996.) Shannon (1950) gave the estimate P(40) ≈ (64!)/(32!(8!)^2(2!)^6) ≈ 10^43."

You may also be interested in the Shannon number.
posted by jedicus at 1:39 PM on October 30 [2 favorites has favorites]

It's empirical rather than a closed-form solution, but François Labelle and Paul Byrne have worked out the exact number of games as far as 12 plies. At 12 plies the number of possible games is 62,854,969,236,701,747. Labelle estimates the number of possible games at 20 plies to be 8.350 * 10^28.
posted by jedicus at 1:59 PM on October 30

Sorry! I misread the question to be aimed at compiling all of the possible games, not calculating the number of possible games. Jedicus' informative links seem to have the answer you're looking for.
posted by Admiral Haddock at 2:16 PM on October 30

Chess endgames can go on indefinitely (theoretically), so that the number of possible games in infinite. I suppose you could make an assumption that a player will claim a draw under the fifty-move rule, but that seems a little arbitrary. As pointed out in the wiki article, some endgames could be winnable but require more than fifty moves, so that under the rules the player who would otherwise lose could force a draw.
posted by exogenous at 2:26 PM on October 30

A couple points:
1) Since resignation is a valid move at any point in the game, the number of complete games is equal to the sum over all positions of the number of ways of arriving at that position.

2) Speaking as a combinatorialist, chess is complicated enough that I seriously doubt that there exists a human-readable closed-form expression for the number of possible games. As I think of it, 'closed form' often refers to formulas for sizes of sets in a sequence. One such sequence describing the number of chess games is the sequence of number of possible chess games consisting of exactly $n$ moves.

3) An empirical enumeration with sufficient time to process the data would create a 'solution' to the game, which would certainly be a Big Deal. See Wikipedia on Solving Chess.
posted by kaibutsu at 2:27 PM on October 30 [1 favorite has favorites]

An empirical, brute-force search of all complete games would work, definitely. I was wondering if anyone had worked towards a clever formula to do the same thing. Thanks to all for your answers!
posted by Blazecock Pileon at 4:52 PM on October 30

Since resignation is a valid move at any point in the game, the number of complete games is equal to the sum over all positions of the number of ways of arriving at that position.

I don't understand the second clause and as a consequence of the first it makes even less sense.
posted by DU at 2:30 AM on October 31

I don't understand the second clause and as a consequence of the first it makes even less sense.

I think what he means is that a player may legally resign the game at any point, regardless of whether the game state is at an endpoint. It seems like a resignation would be a trivial case and I should have clarified my conditions, such that a "complete" game would be played to completion: i.e., checkmate or stalemate. I'm not sure if the estimations linked above consider resignation-at-any-point. I suppose those are legal end-states, but not very interesting ones?
posted by Blazecock Pileon at 12:06 PM on October 31

Yes, as exogenous points out, threefold repitition of position, or fifty moves without a capture or pawn move, only gives either player the right to claim a draw. (FIDE Laws of Chess, articles 9.2 and 9.3) If neither player chooses to exercise that right, the game can continue indefinitely.

The answer to the question as framed is "infinitely many." Any alleged answer that gives a finite number of possible games is most likely assuming that one player will claim a draw if both players have the opportunity to do so, but that is not "standard FIDE rules."
posted by DevilsAdvocate at 8:18 AM on November 2