Statistics on chess games

My numbers agree with numbers independently computed by other people, which is a good sign that my program is bug-free. Some column headings link to the corresponding integer sequence from The On-Line Encyclopedia of Integer Sequences.

I am ignoring the draw by threefold repetition because it is a pain to take into account. Actually a draw by threefold repetition isn't automatic: one of the players must make a correct claim for the draw to occur. So if it's legal to ignore the repetition of position, I believe that it's ok to enumerate those games. Draw by the fifty-move rule (not automatic) and draw by impossibility of checkmate (automatic) don't apply before way more moves than I can analyze. For the complete rules of chess see the FIDE Laws of Chess.

(*) Computed by Paul Byrne and confirmed by Steven Edwards, but not by me... yet!

Discovered check, double check, etc.

It's hard to find definitions of "discovered check" and "double check" written by someone who understands the fine details. Here are typical errors:

"a discovered check is a check given by one piece when another friendly piece moves out of the way". This excludes cases where the check happens because an enemy pawn gets captured en passant.

"a double check is a discovered check where the moving piece also gives check". This definition excludes cases where a king is under two discovered attacks. Also in general the expression "the moving piece" sounds awkward, because two pieces move during castling.

• direct check: When a piece which moved gives check.
• discovered check: When a piece which didn't move gives check.
• double check: When two pieces give check. Split into two categories: "direct and discovered check" and "double discovered check".

Thanks to Joost de Heer for computing ply 11 with my program on his computer, although he did it for the chess problems, not the statistics!

Perft

The number of chess games at ply n is often called perft(n) and is probably the most interesting chess sequence (see the right-most column of the first table of this page). The name "perft" comes from a command in the chess playing program Crafty. As far as I can tell, the first computations were

• perft(10) in 2003 by Richard Bean,
• perft(11) in 2003 by a distributed project led by Albert Bertilsson,
• perft(12) in 2006 by Paul Byrne,
• perft(13) in 2011 by Paul Byrne.

Richard Bean wrote an article that has some of the earlier history (click on the cached version).

Perft estimation for higher plies

In 2007, I calculated fairly good estimates for perft 13 and higher by randomly pruning the game tree:

Perft ratios

The behavior of the perft(n)/perft(n-1) ratio is more interesting:

I expect the ratio to converge to some value, the "maximum sustainable fan-out", probably somewhere around 84.3. Below is a position which appears to sustain such an expansion factor indefinitely if we make non-capturing moves only.

Games leading to this type of position are very rare at first, but they must eventually dominate the perft count because the fan-out is much bigger than in "normal" games.

Thanks to Andrew Buchanan for pointing out that 18 queens are impossible with only 6 captures, and for giving some ideas on how to optimize the example.

Other people's estimates

perft(8) = 20*20*28*29*30*31*33*32 = 318,979,584,000 ± 20%

and suggested multiplying by 30 for each additional ply. The correct value is now known to be perft(8) = 84,998,978,956, so his estimate was off by 275%.

An updated version of the article appears in James Mason's book The Principles of Chess in Theory and Practice, 4th edition (1902), p322-324 (and also in the 2nd (1896) edition and on, according to Mario Richter). The updated article adds the explicit estimate

perft(20) = [above]*30*30*30*30*30*30*30*30*30*30*30*30 = 169,518,829,100,544,000,000,000,000,000.

Those estimates shouldn't be considered accurate since the article itself states that the goal was only to get "something of an approximation". Still, the factors that were multiplied together are quite off compared to the modern perft ratios, and the errors quickly accumulate. In fact, the ratios are not very good even for 1896 because, according to MathWorld, an almost-correct value of perft(4) was known in 1889, so the product should have started 20*20*22.255*22.163 and not 20*20*28*29.

Mario Richter tells me that Karl Fabel wrote a critical article in Die Schwalbe about Anthony's estimation and gave his own estimation as perft(20) = 0.976437504 * 10^29, which is fairly close to mine (8.350e+28).

Perft disinformation

Unfortunately, Edwin Anthony's approximations above gained the status of "fact", possibly because the non-significant digits were not rounded off in the article, so readers assumed they were all significant. As an example, the Isaac Asimov's Book of Facts reports

perft(8) = 318,979,564,000 (Anthony's value with a typo!)

perft(8) = 84,998,978,956.

As of January 19, 2012, the erroneous value is leading 1720 to 19 in a Google Fight. Anthony's perft(20) value appears on multiple trivia pages on the Web.