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 3-fold repetition because it is a pain to take into account. Actually a draw by 3-fold 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, then I believe that it's ok to enumerate those games. Draw by 5-fold repetition (article 9.6a) is automatic and should affect the number of games. The rule is not very clear, but according to one interpretation, the earliest it can apply is at ply 22, which means that it would affect the count at ply 23. Draw by the 50-move rule (not automatic), draw by the 75-move rule (automatic), and draw by impossibility of checkmate (automatic) don't apply before even more moves. For the complete rules of chess see the FIDE Laws of Chess.
|without check nor checkmate||in check||in checkmate||total (perft)|
|ply 13||(*) 1981066775000396239|
|ply 14||(**) 61885021521585529237|
(*) Computed by Paul Byrne and confirmed by Steven Edwards, but not by me... yet!
(**) Computed by Peter Österlund and confirmed by Ankan Banerjee, but not by me... yet!
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.My definitions:
|direct check only||single discovered check only||direct and discovered check||double discovered check||total|
|direct checkmate only||single discovered checkmate only||direct and discovered checkmate||double discovered checkmate||total|
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!
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
Richard Bean wrote an article that has some of the earlier history (click on the cached version).
In 2007, I calculated fairly good estimates for perft 13 and higher by randomly pruning the game tree:
The behavior of the perft(n)/perft(n-1) ratio is more interesting:
Ignoring the 75-move rule, 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.
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).
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!)and not the correct (exact) value
perft(8) = 84,998,978,956.
As of March 30, 2015, the erroneous value is leading 1010 to 12 in a Google Fight. Anthony's perft(20) value appears on multiple trivia pages on the Web.
Here we consider games at ply p that lead to a position that is mate-in-n moves (assuming perfect play). We also consider games where the player on the move is losing under perfect play. Both of these are only possible if one of the players made a game-losing blunder in the opening. The goal is to obtain a depth-to-mate (DTM) analysis of chess openings similar to endgame tablebases. Numbers for "lose-in-0" are the same as the number of games ending in checkmate from the first table of this page.
The number of games ending in win-in-n at ply p is similar to the number of games ending in lose-in-(n-1) at ply p+1. For example, at ply 5 there are 10822 games leading to a win-in-1. Among them, 6 games (such as 1.f3 e6 2.g4 Bd6 3.h3) lead to a win-in-1 with two keys (two mating moves). This gives a total of 10828 games ending in lose-in-0 at ply 6. Click on a number in the table below to access a file with the games. I thank Serge Zhemeytsev for the idea of computing these numbers.
|win in (mate in)...||lose in (mated in)...|
|1 move||2 moves||3 moves||4 moves||5 moves||0 moves||1 move||2 moves||3 moves||4 moves|