the number of unique positions reached after N moves. This corresponds with
http://oeis.org/A133047 where Jonathan Schaeffer provides numbers for the first
15 ply. I thought I'd add a few more:
Code: Select all
Depth Uniq Ratio UniqUniq %
0 1 --- 1 100.00%
1 7 7.00 7 100.00%
2 49 7.00 49 100.00%
3 216 4.41 130 60.19%
4 805 3.73 323 40.12%
5 2,733 3.40 735 26.89%
6 9,105 3.33 1,964 21.57%
7 28,123 3.09 4,848 17.24%
8 85,340 3.03 12,142 14.23%
9 255,800 3.00 29,184 11.41%
10 768,155 3.00 69,071 8.99%
11 2,265,062 2.95 158,608 7.00%
12 6,588,759 2.91 360,744 5.48%
13 18,667,410 2.83 773,970 4.15%
14 51,448,497 2.76 1,609,395 3.13%
15 137,051,636 2.66 3,166,829 2.31%
16 353,575,584 2.58 6,084,139 1.72%
17 878,804,335 2.49 11,129,325 1.27%
18 2,113,497,469 2.40 19,829,515 0.94%
19 4,908,984,819 2.32 33,830,205 0.69%
20 11,049,271,004 2.25 56,132,767 0.51%
21 24,062,242,901 2.18 89,061,917 0.37%
22 50,742,319,631 2.11 136,358,464 0.27%
counts the positions that can only be reached in one way in that number of moves. Uniq 16
and below could be computed in memory with 8 GB; the higher ply were done in parts using
temporary files. Uniq 22 used 550 GB of temporary space; the final set of positions and
their associated frequencies compresses to 120 GB. The computation of uniq 1 to uniq 22 took
about 2 days on a phenom 1090T using a single core. Uniq 23 and 24 could be reasonably
computed with a bigger hard drive.
Another related stat is the highest frequency at a given depth:
Code: Select all
Depth Max Freq Count
0 1 1
1 1 7
2 1 49
3 2 86
4 4 68
5 12 8
6 36 1
7 96 2
8 272 1
9 784 1
10 2,220 1
11 7,216 1
12 23,364 1
13 85,312 1
14 349,232 1
15 1,456,024 1
16 6,053,074 1
17 22,340,040 1
18 81,217,440 1
19 81,217,440 4
20 200,821,452 1
21 981,690,468 1
22 3,291,762,816 1
can be reached in 7216 different ways in 11 moves. All of the early ply are 12-on-12
positions like this. Clearly not something that can last indefinitely. By 18 ply we get:
which is reached in 81,217,440 different ways. This is basically the end of the road:
at 19 ply there are 4 different positions with the same 81,217,440 frequency which
corrspond to the 4 moves in the above diagram. After this, the lead is taken by 11-on-11
positions which overcome the 2 ply delay caused by the captures. At 22 ply, the most
common position is
which can be reached in 3,291,762,816 ways. (I used 64 bit intergers for this just to
be safe -- and came quite close to needing them!)
Of course a nice side effect of this computation (or perhaps main motivation for doing it)
is that one can compute deep perfts quite quickly given the set of unique positions and how
many times each occurs. One can do shallow perft 5's on each of the 50,742,319,631
positions in uniq 22 to get perft 27. This took under 44 hours on the 6-core phenom (using
all 6 cores this time!) The same set of data is being reused to compute perft 28.
The effect is to get perfect detection of transpositions through the first 22 ply. For checkers
I added a secondary hash table to detect transpositions within each 5 (or 6) ply search and
also some of the transpositions between seperate 5 ply searches.
A significant disadvantage to this approach is that there is no easy way to produce a "divide"
or any other data to help pinpoint discrepancies with other programs.
For those who made it this far, thanks for reading! While I have the uniq data sets on disk,
if there are any other statistics you'd like to see, just let me know. (Distribution of number of
men at each depth or percent of positions with captures, for example.)
-paul
