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 repetition of position" rule because it is a pain to take into account. Actually a draw by repetition of position 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 because of a dead position (automatic) don't apply before way more moves than I can analyze. For the complete rules of chess see the FIDE Laws of Chess.

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!

Estimation for higher plies

The number of chess games at ply n is often called perft(n). The name "perft" comes from a command in the chess playing program Crafty. The exact value is known up to ply 12 (see the right-most column of the first table of this page). By randomly pruning the game tree I can get fairly good estimates for higher perft values:

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

The following figure is widespread and apparently appears in Isaac Asimov's Book of Facts:

perft(8) = 318,979,564,000

Well it is wrong. The correct (exact) value is:

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

How can someone claim nine (or twelve?) significant digits for a number that is off by a factor of 3.75? On February 27, 2005, the erroneous value was leading 1350 to 10 in a Google Fight. Two years later (February 11, 2007) the erroneous value is still leading 647 to 110.

Another value comes up on trivia pages on the Web:

perft(20) = 169,518,829,100,544,000,000,000,000,000

This value (1.69518829100544e+29) falls in the same ballpark as my estimate 8.350e+28, but again suffers from the excessive-significant-digits syndrome (while I believe all the digits of 8.350e+28 are significant).

I'd be interested to know the original source of these numbers and/or how they were derived. The perft(20) value for instance appears to be an ad-hoc product of twenty integers around 30.

Here are the factorizations:

318979564000 = 2^5 * 5^3 * 79 * 113 * 8933
169518829100544000000000000000 = 2^24 * 3^14 * 5^15 * 7 * 11 * 29 * 31

back to Chess Problems by Computer