Perft(12) count confirmed

[sje]

After nearly 112 machine days of calculation, I have produced the value of perft(12). It is: 62,854,969,236,701,747

This number confirms the value given by Paul Byrne back in 2006 and it is the first such public verification. Because there is no commonality of code between the two calculations there can be no doubt of the validity of the grand total and so of the verification.

Each of the twenty perft(11) calculation output files can be found at:

https://public.me.com/chessnotation -> Perft -> Perft12

Each of the twenty files contains the twenty perft(10) subtotals for a total of 400 perft(10) subtotals. Each file also contains a running time as well.

The page at http://oeis.org/A048987 needs to be updated. As Paul got to the number before I did, he should have the honor of doing the update. If the page isn't updated in a month or so, I'll do it and list Paul's name (and maybe my own as the verifier).

Code: Select all

Move      Perft(11)       Seconds

Na3 2,101,612,201,748,156  239120
Nc3 2,731,501,636,365,779  311238
Nf3 2,704,348,041,301,604  300360
Nh3 2,133,059,306,892,947  245614
a3  1,825,396,176,881,632  210765
a4  2,572,564,331,526,038  572635
b3  2,407,514,849,528,875  264582
b4  2,412,357,918,298,534  233670
c3  2,751,675,948,507,059  257355
c4  3,119,892,147,087,203  410693
d3  4,588,998,634,450,632  326086
d4  6,326,899,070,222,383 1578620
e3  7,160,631,171,539,800  935154
e4  7,263,638,936,690,183 1986240
f3  1,552,858,858,446,419  367715
f4  2,050,768,802,609,121  259852
g3  2,498,600,008,341,437  302698
g4  2,217,762,743,088,597  292931
h3  1,814,268,178,532,771  211051
h4  2,620,620,274,642,577  368624

[sje]

A good candidate for the wiki, eh?

Code: Select all

Na3 1
Nc3 1
Nf3 1
Nh3 1
a3 1
a4 1
b3 1
b4 1
c3 1
c4 1
d3 1
d4 1
e3 1
e4 1
f3 1
f4 1
g3 1
g4 1
h3 1
h4 1
Depth: 1   Count: 20 

Na3 20
Nc3 20
Nf3 20
Nh3 20
a3 20
a4 20
b3 20
b4 20
c3 20
c4 20
d3 20
d4 20
e3 20
e4 20
f3 20
f4 20
g3 20
g4 20
h3 20
h4 20
Depth: 2   Count: 400

Na3 400
Nc3 440
Nf3 440
Nh3 400
a3 380
a4 420
b3 420
b4 421
c3 420
c4 441
d3 539
d4 560
e3 599
e4 600
f3 380
f4 401
g3 420
g4 421
h3 380
h4 420
Depth: 3   Count: 8,902

Na3 8,885
Nc3 9,755
Nf3 9,748
Nh3 8,881
a3 8,457
a4 9,329
b3 9,345
b4 9,332
c3 9,272
c4 9,744
d3 11,959
d4 12,435
e3 13,134
e4 13,160
f3 8,457
f4 8,929
g3 9,345
g4 9,328
h3 8,457
h4 9,329
Depth: 4   Count: 197,281

Na3 198,572
Nc3 234,656
Nf3 233,491
Nh3 198,502
a3 181,046
a4 217,832
b3 215,255
b4 216,145
c3 222,861
c4 240,082
d3 328,511
d4 361,790
e3 402,988
e4 405,385
f3 178,889
f4 198,473
g3 217,210
g4 214,048
h3 181,044
h4 218,829
Depth: 5   Count: 4,865,609

Na3 4,856,835
Nc3 5,708,064
Nf3 5,723,523
Nh3 4,877,234
a3 4,463,267
a4 5,363,555
b3 5,310,358
b4 5,293,555
c3 5,417,640
c4 5,866,666
d3 8,073,082
d4 8,879,566
e3 9,726,018
e4 9,771,632
f3 4,404,141
f4 4,890,429
g3 5,346,260
g4 5,239,875
h3 4,463,070
h4 5,385,554
Depth: 6   Count: 119,060,324

Na3 120,142,144
Nc3 148,527,161
Nf3 147,678,554
Nh3 120,669,525
a3 106,743,106
a4 137,077,337
b3 133,233,975
b4 134,087,476
c3 144,074,944
c4 157,756,443
d3 227,598,692
d4 269,605,599
e3 306,138,410
e4 309,478,263
f3 102,021,008
f4 119,614,841
g3 135,987,651
g4 130,293,018
h3 106,678,423
h4 138,495,290
Depth: 7   Count: 3,195,901,860

Na3 3,193,522,577
Nc3 3,926,684,340
Nf3 3,937,354,096
Nh3 3,221,278,282
a3 2,863,411,653
a4 3,676,309,619
b3 3,579,299,617
b4 3,569,067,629
c3 3,806,229,124
c4 4,199,667,616
d3 6,093,248,619
d4 7,184,581,950
e3 8,039,390,919
e4 8,102,108,221
f3 2,728,615,868
f4 3,199,039,406
g3 3,641,432,923
g4 3,466,204,702
h3 2,860,408,680
h4 3,711,123,115
Depth: 8   Count: 84,998,978,956

Na3 85,849,641,909
Nc3 109,418,317,145
Nf3 108,393,009,416
Nh3 86,659,653,631
a3 74,950,758,099
a4 101,265,301,849
b3 96,577,095,997
b4 97,442,160,946
c3 108,697,368,719
c4 120,549,219,832
d3 176,976,245,463
d4 227,220,482,342
e3 259,522,947,791
e4 263,561,543,780
f3 68,094,899,093
f4 84,792,070,664
g3 99,646,370,024
g4 92,281,289,941
h3 74,778,417,365
h4 102,853,440,161
Depth: 9   Count: 2,439,530,234,167

Na3 2,440,848,135,252
Nc3 3,096,505,857,746
Nf3 3,090,773,583,680
Nh3 2,470,483,499,345
a3 2,149,477,156,227
a4 2,905,552,970,419
b3 2,774,842,822,463
b4 2,772,533,545,113
c3 3,072,577,495,123
c4 3,437,747,391,692
d3 5,071,006,040,569
d4 6,459,463,242,656
e3 7,299,373,354,878
e4 7,380,003,266,234
f3 1,945,020,011,164
f4 2,418,056,589,775
g3 2,853,630,724,145
g4 2,624,128,147,144
h3 2,142,832,044,687
h4 2,948,003,834,105
Depth: 10   Count: 69,352,859,712,417

Na3 70,080,800,068,168
Nc3 91,451,554,526,572
Nf3 89,933,046,388,964
Nh3 71,046,267,678,634
a3 60,403,292,887,824
a4 85,054,341,127,064
b3 79,510,326,025,357
b4 80,419,308,561,211
c3 92,235,553,734,553
c4 103,605,670,223,681
d3 151,857,971,385,067
d4 211,583,204,457,112
e3 241,074,613,621,302
e4 245,841,494,675,197
f3 51,614,296,095,395
f4 68,372,448,303,691
g3 82,762,826,570,051
g4 73,966,186,324,024
h3 60,097,879,424,719
h4 86,739,921,618,220
Depth: 11   Count: 2,097,651,003,696,806

Na3 2,101,612,201,748,156
Nc3 2,731,501,636,365,779
Nf3 2,704,348,041,301,604
Nh3 2,133,059,306,892,947
a3 1,825,396,176,881,632
a4 2,572,564,331,526,038
b3 2,407,514,849,528,875
b4 2,412,357,918,298,534
c3 2,751,675,948,507,059
c4 3,119,892,147,087,203
d3 4,588,998,634,450,632
d4 6,326,899,070,222,383
e3 7,160,631,171,539,800
e4 7,263,638,936,690,183
f3 1,552,858,858,446,419
f4 2,050,768,802,609,121
g3 2,498,600,008,341,437
g4 2,217,762,743,088,597
h3 1,814,268,178,532,771
h4 2,620,620,274,642,577 
Depth: 12   Count: 62,854,969,236,701,747

[sluijten]

... and count^(1/depth) slowly increasing from 20 to 25
(average number of moves for a position)

[Dann Corbit]

[quote="sje"]A good candidate for the wiki, eh?

Likely, it is also valuable for the encyclopedia of integer sequences

[Adam Hair]

A good candidate for the wiki, eh?

Likely, it is also valuable for the encyclopedia of integer sequences

Dann is right.
At http://oeis.org there is a link for contributing sequences.

By the way, congratulations and thanks to you Steven.

[sje]

Likely, it is also valuable for the encyclopedia of integer sequences

The page is here: http://oeis.org/A048987

The first few entries were known from the late 1800s. Ken Thompson added some terms in the 1970s and 1980s, I added a few and was the first to verify a few, Richard Bean did one and Francois Labelle did another. Paul Byrne did perft(12) -- not yet posted at OEIS -- which I just verified, five years after it was first calculated.

Doing perft(13) will cost several thousand US$ in electricity costs and computer depreciation, so I'm not so eager to start.

Attempting perft(13) without transposition assistance appears infeasible at this time, and programs that are limited to 64 bit long hash signatures will surely fail with false positive matches. (Symbolic uses hashes with an effective length of 120 bits.) Therefore, there are some constraints on handling perft(13) on a distributed basis; and even if these are resolved, there is still lots of work to do as much more computing would be needed to perform redundancy checks.

[casey]

Congratulation!

Amazing result and amazing number of machine days.

Can you tell us more about your task:
- What kind of program are you using: mailbox or bitboard, a normal chess program or a special purpose one; 1 or multi-threads; using hash table or not
- What kind of your system: how many computers involve, how strong are they; Windows or others...
- Difficulties you have to solve...

I have been considering to do the same task but for other chess variants so I am eager for knowing more. Thanks.

[sje]

The program is use is my C++ bitboard Symbolic from a few years ago, The only change I made was to increase the hash signature length from (about) 56 bits to (about) 120 bits due to a couple of false positive matches in the early test runs. Symbolic has a multi-threaded movepath enumerator (i.e., perft); threads are assigned one per core with each thread working on a different root move. Each thread has its own transposition table but all threads share a set of binary trees for the upper ply.

The code is a bit tricky and was written long ago. I wouldn't have tried writing it today. In truth, I haven't done much C++ coding in a long while; instead I do paragraphs of Lisp as a distraction in much the same way that other people do crossword puzzles.

Symbolic runs on any Posix compliant platform.

A rather faster calculation could be had by ripping out the non-perft position update code in Symbolic. But I am too lazy to do this and really don't feel like debugging the result.

For anyone trying big perft calculations, I'd suggest doing the little ones first to ensure validity and to tune the program. What works for one person may not work for another.

Perft(13) will be about two quintillion and is the last one that can be done with 64 bit summation arithmetic. I will leave this for others.

[murraycash]

The only change I made was to increase the hash signature length from (about) 56 bits to (about) 120 bits due to a couple of false positive matches in the early test runs.

How did you detect false positive matches on the signature? If you are trailblazing new ply depths no-one has done before, can you know for sure you have avoided all false positive matches?

PS Not calling into question your results but I am doing something similar in checkers. There is always a small chance false positive signatures can happen and wreck the exactness of the results. I'm concluding the entire board position must be stored in the hash table to avoid this (96 bits in checkers).

[sje]

First, I'm not the first to do perft(12), I'm only the first verifier. Paul Byrne did perft(12) nearly five years ago.

Second, my perft(12) result is actually made from 20 different perft(11) results, so there wasn't a single transposition table instance with (potentially) many extra false positive candidates.

Third, I made a lot a test runs with different table sizes, different hash code lengths, and on different machines. This is what triggered a couple of false positives under stress conditions and when comparing results. So I had an initial baseline of what would not be acceptable.

Fourth, I have another program that allows setting the hash code length form one bit on up to any number of bits. I used this program to enumerate unique positions (not paths), a tougher test that allows better chances of false positives. With this program I was able to see what the minimal hash code length was for different unique(n) depths. The rough result is that for every two bits of hash are added, the odds of a false positive drop by half. So adding 64 bits drops the false positive rate by (very roughly) four billion. At this point, the chance of hardware failure is greater than a hash false positive match.