Wide open perft()

[ankan]

With my GPU perft program - now with hash table support (1.5 GB hash):

rnbqkbnr/8/8/8/8/8/8/RNBQKBNR w KQkq - 0 1

Code: Select all

GPU Perft 1: 50,   Time taken: 6.064e-005 seconds, nps: 824538

GPU Perft 2: 2125,   Time taken: 0.000267136 seconds, nps: 7954749

GPU Perft 3: 96062,   Time taken: 0.000529504 seconds, nps: 181418836

GPU Perft 4: 4200525,   Time taken: 0.00094864 seconds, nps: 4427944266

GPU Perft 5: 191462298,   Time taken: 0.0106363 seconds, nps: 18000802528

GPU Perft 6: 8509434052,   Time taken: 0.258565 seconds, nps: 32910274087

GPU Perft 7: 390020558283,   Time taken: 4.17592 seconds, nps: 93397409322

GPU Perft 8: 17528222547068,   Time taken: 88.2822 seconds, nps: 198547704194

4k3/pppppppp/8/8/8/8/PPPPPPPP/4K3 w - - 0 1

Code: Select all

GPU Perft 1: 18,   Time taken: 3.5328e-005 seconds, nps: 509510

GPU Perft 2: 324,   Time taken: 0.000229792 seconds, nps: 1409970

GPU Perft 3: 5658,   Time taken: 0.000350976 seconds, nps: 16120760

GPU Perft 4: 98766,   Time taken: 0.000526752 seconds, nps: 187500001

GPU Perft 5: 1683597,   Time taken: 0.000810208 seconds, nps: 2077981151

GPU Perft 6: 28677387,   Time taken: 0.00257053 seconds, nps: 11156224192

GPU Perft 7: 479763588,   Time taken: 0.0291404 seconds, nps: 16463855605

GPU Perft 8: 8014917042,   Time taken: 0.335018 seconds, nps: 23923835296

GPU Perft 9: 132060434889,   Time taken: 2.73257 seconds, nps: 48328370641

GPU Perft 10: 2170519816231,   Time taken: 24.7699 seconds, nps: 87627209427

GPU Perft 11: 35270612954472,   Time taken: 180.043 seconds, nps: 195900966156

GPU Perft 12: 570918858679054,   Time taken: 1282.69 seconds, nps: 445093792332

And for start position:

Code: Select all

GPU Perft 1: 20,   Time taken: 5.2448e-005 seconds, nps: 381330

GPU Perft 2: 400,   Time taken: 0.00020624 seconds, nps: 1939487

GPU Perft 3: 8902,   Time taken: 0.000334688 seconds, nps: 26597905

GPU Perft 4: 197281,   Time taken: 0.000504768 seconds, nps: 390834986

GPU Perft 5: 4865609,   Time taken: 0.000962688 seconds, nps: 5054190822

GPU Perft 6: 119060324,   Time taken: 0.00778451 seconds, nps: 15294513431

GPU Perft 7: 3195901860,   Time taken: 0.10982 seconds, nps: 29101257445

GPU Perft 8: 84998978956,   Time taken: 1.57653 seconds, nps: 53915338429

GPU Perft 9: 2439530234167,   Time taken: 19.6643 seconds, nps: 124059043871

GPU Perft 10: 69352859712417,   Time taken: 269.855 seconds, nps: 257000462146

GPU Perft 11: 2097651003696806,   Time taken: 4409.55 seconds, nps: 475705987850

GPU Perft 12: 62854969236701747,   Time taken: 84496 seconds, nps: 743881355235
... almost 1 day for perft 12

I think there is still some room for improvement. The hast hit rate is significantly lower than my single threaded CPU version.

[Ajedrecista]

Hello:

Some of these perft values were confirmed by JetChess 1.0.0.0 in my slow computer (an Intel Pentium D930 at 3 GHz):

[d]rnbqkbnr/8/8/8/8/8/8/RNBQKBNR w KQkq - 0 1

Code: Select all

Perft(0) =               1
Perft(1) =              50 (0:00:00.000).
Perft(2) =           2,125 (0:00:00.000).
Perft(3) =          96,062 (0:00:00.001).
Perft(4) =       4,200,525 (0:00:00.062).
Perft(5) =     191,462,298 (0:00:01.833).
Perft(6) =   8,509,434,052 (0:00:32.548).
Perft(7) = 390,020,558,283 (0:10:10.237).

[d]4k3/pppppppp/8/8/8/8/PPPPPPPP/4K3 w - - 0 1

Code: Select all

 Perft(0) =                  1
 Perft(1) =                 18 (0:00:00.000).
 Perft(2) =                324 (0:00:00.000).
 Perft(3) =              5,658 (0:00:00.000).
 Perft(4) =             98,766 (0:00:00.009).
 Perft(5) =          1,683,597 (0:00:00.015).
 Perft(6) =         28,677,387 (0:00:00.144).
 Perft(7) =        479,763,588 (0:00:01.127).
 Perft(8) =      8,014,917,042 (0:00:07.716).
 Perft(9) =    132,060,434,889 (0:00:41.464).
Perft(10) =  2,170,519,816,231 (0:04:02.994).
Perft(11) = 35,270,612,954,472 (0:23:19.770).

Ankan's GPU perft is terribly fast! Good job.

Regards from Spain.

Ajedrecista.

[sje]

King and rooks perft()

My idea for presnting this data is to help others to debug their programs by trying perft() calls with limited piece subsets.
[d]

Code: Select all

[] pctran 0
PathTran(0): 1   Pt: 0.000   Wt: 0.000   F/P: inf/0
Total: one

[] pctran 1
PathTran(1): 26   Pt: 0.001   Wt: 0.099   F/P: 262.459/0.00381012
Total: twenty-six

[] pctran 2
PathTran(2): 568   Pt: 0.001   Wt: 0.108   F/P: 5234.44/0.000191042
Total: five hundred sixty-eight

[] pctran 3
PathTran(3): 13,744   Pt: 0.002   Wt: 0.142   F/P: 96365.3/1.03772e-05
Total: thirteen thousand seven hundred forty-four

[] pctran 4
PathTran(4): 314,346   Pt: 0.010   Wt: 0.154   F/P: 2.03604e+06/4.9115e-07
Total: three hundred fourteen thousand three hundred forty-six

[] pctran 5
PathTran(5): 7,594,526   Pt: 0.097   Wt: 0.134   F/P: 5.63417e+07/1.77488e-08
Total: seven million five hundred ninety-four thousand five hundred twenty-six

[] pctran 6
PathTran(6): 179,862,938   Pt: 1.268   Wt: 0.405   F/P: 4.44054e+08/2.25198e-09
Total: one hundred seventy-nine million eight hundred sixty-two thousand nine hundred thirty-eight

[] pctran 7
PathTran(7): 4,408,318,687   Pt: 10.239   Wt: 2.781   F/P: 1.58503e+09/6.30902e-10
Total: four billion four hundred eight million three hundred eighteen thousand six hundred eighty-seven

[] pctran 8
PathTran(8): 106,978,816,283   Pt: 1:18.192   Wt: 20.935   F/P: 5.1099e+09/1.95699e-10
Total: one hundred six billion nine hundred seventy-eight million eight hundred sixteen thousand two hundred eighty-three

[] pctran 9
PathTran(9): 2,649,670,519,428   Pt: 6:13.859   Wt: 1:39.336   F/P: 2.66738e+10/3.749e-11
Total: two trillion six hundred forty-nine billion six hundred seventy million five hundred nineteen thousand four hundred twenty-eight

[] pctran 10
PathTran(10): 65,235,972,078,932   Pt: 26:08.269   Wt: 7:00.822   F/P: 1.5502e+11/6.45077e-12
Total: sixty-five trillion two hundred thirty-five billion nine hundred seventy-two million seventy-eight thousand nine hundred thirty-two

[] pctran 11
PathTran(11): 1,626,958,461,082,572   Pt: 1:28:54.236   Wt: 24:29.798   F/P: 1.10693e+12/9.03403e-13
Total: one quadrillion six hundred twenty-six trillion nine hundred fifty-eight billion four hundred sixty-one million eighty-two thousand five hundred seventy-two

[sje]

King and bishops perft()
[d]

Code: Select all

[] pctran 0
PathTran(0): 1   Pt: 0.000   Wt: 0.000   F/P: inf/0
Total: one

[] pctran 1
PathTran(1): 18   Pt: 0.001   Wt: 0.098   F/P: 182.105/0.00549133
Total: eighteen

[] pctran 2
PathTran(2): 305   Pt: 0.001   Wt: 0.099   F/P: 3066.53/0.000326102
Total: three hundred five

[] pctran 3
PathTran(3): 5,575   Pt: 0.001   Wt: 0.086   F/P: 64209.6/1.5574e-05
Total: five thousand five hundred seventy-five

[] pctran 4
PathTran(4): 99,932   Pt: 0.004   Wt: 0.142   F/P: 699647/1.42929e-06
Total: ninety-nine thousand nine hundred thirty-two

[] pctran 5
PathTran(5): 1,879,563   Pt: 0.026   Wt: 0.083   F/P: 2.24976e+07/4.44492e-08
Total: one million eight hundred seventy-nine thousand five hundred sixty-three

[] pctran 6
PathTran(6): 34,853,962   Pt: 0.234   Wt: 0.153   F/P: 2.27578e+08/4.39411e-09
Total: thirty-four million eight hundred fifty-three thousand nine hundred sixty-two

[] pctran 7
PathTran(7): 667,568,067   Pt: 1.537   Wt: 0.482   F/P: 1.38294e+09/7.23095e-10
Total: six hundred sixty-seven million five hundred sixty-eight thousand sixty-seven

[] pctran 8
PathTran(8): 12,658,837,579   Pt: 9.432   Wt: 2.846   F/P: 4.44788e+09/2.24826e-10
Total: twelve billion six hundred fifty-eight million eight hundred thirty-seven thousand five hundred seventy-nine

[] pctran 9
PathTran(9): 245,447,959,999   Pt: 39.980   Wt: 10.598   F/P: 2.31594e+10/4.3179e-11
Total: two hundred forty-five billion four hundred forty-seven million nine hundred fifty-nine thousand nine hundred ninety-nine

[] pctran 10
PathTran(10): 4,725,379,779,416   Pt: 2:37.868   Wt: 41.541   F/P: 1.13751e+11/8.7911e-12
Total: four trillion seven hundred twenty-five billion three hundred seventy-nine million seven hundred seventy-nine thousand four hundred sixteen

[] pctran 11
PathTran(11): 92,387,695,917,003   Pt: 8:06.837   Wt: 2:08.378   F/P: 7.19649e+11/1.38957e-12
Total: ninety-two trillion three hundred eighty-seven billion six hundred ninety-five million nine hundred seventeen thousand three

[sje]

King and knights perft()
[d]

Code: Select all

[] pctran 0
PathTran(0): 1   Pt: 0.000   Wt: 0.000   F/P: inf/0
Total: one

[] pctran 1
PathTran(1): 11   Pt: 0.000   Wt: 0.066   F/P: 165.725/0.00603409
Total: eleven

[] pctran 2
PathTran(2): 121   Pt: 0.000   Wt: 0.064   F/P: 1883.27/0.000530992
Total: one hundred twenty-one

[] pctran 3
PathTran(3): 1,551   Pt: 0.001   Wt: 0.088   F/P: 17533/5.70355e-05
Total: one thousand five hundred fifty-one

[] pctran 4
PathTran(4): 19,764   Pt: 0.001   Wt: 0.087   F/P: 226867/4.40786e-06
Total: nineteen thousand seven hundred sixty-four

[] pctran 5
PathTran(5): 273,291   Pt: 0.005   Wt: 0.099   F/P: 2.7537e+06/3.63148e-07
Total: two hundred seventy-three thousand two hundred ninety-one

[] pctran 6
PathTran(6): 3,736,106   Pt: 0.027   Wt: 0.061   F/P: 6.05518e+07/1.65148e-08
Total: three million seven hundred thirty-six thousand one hundred six

[] pctran 7
PathTran(7): 54,343,448   Pt: 0.143   Wt: 0.114   F/P: 4.74653e+08/2.1068e-09
Total: fifty-four million three hundred forty-three thousand four hundred forty-eight

[] pctran 8
PathTran(8): 781,298,405   Pt: 0.751   Wt: 0.244   F/P: 3.19657e+09/3.12836e-10
Total: seven hundred eighty-one million two hundred ninety-eight thousand four hundred five

[] pctran 9
PathTran(9): 11,689,654,917   Pt: 3.303   Wt: 0.910   F/P: 1.28369e+10/7.79002e-11
Total: eleven billion six hundred eighty-nine million six hundred fifty-four thousand nine hundred seventeen

[] pctran 10
PathTran(10): 173,060,266,601   Pt: 13.471   Wt: 3.483   F/P: 4.96773e+10/2.01299e-11
Total: one hundred seventy-three billion sixty million two hundred sixty-six thousand six hundred one

[] pctran 11
PathTran(11): 2,642,557,929,049   Pt: 46.586   Wt: 11.992   F/P: 2.20356e+11/4.53811e-12
Total: two trillion six hundred forty-two billion five hundred fifty-seven million nine hundred twenty-nine thousand forty-nine

[sje]

King and queen perft()
[d]

Code: Select all

[] pctran 0
PathTran(0): 1   Pt: 0.000   Wt: 0.000   F/P: inf/0
Total: one

[] pctran 1
PathTran(1): 20   Pt: 0.001   Wt: 0.099   F/P: 201.924/0.00495235
Total: twenty

[] pctran 2
PathTran(2): 301   Pt: 0.001   Wt: 0.109   F/P: 2737.68/0.000365272
Total: three hundred one

[] pctran 3
PathTran(3): 6,063   Pt: 0.001   Wt: 0.096   F/P: 62879.8/1.59033e-05
Total: six thousand sixty-three

[] pctran 4
PathTran(4): 119,006   Pt: 0.005   Wt: 0.131   F/P: 904583/1.10548e-06
Total: one hundred nineteen thousand six

[] pctran 5
PathTran(5): 2,409,458   Pt: 0.031   Wt: 0.094   F/P: 2.53755e+07/3.9408e-08
Total: two million four hundred nine thousand four hundred fifty-eight

[] pctran 6
PathTran(6): 48,001,999   Pt: 0.229   Wt: 0.145   F/P: 3.29135e+08/3.03827e-09
Total: forty-eight million one thousand nine hundred ninety-nine

[] pctran 7
PathTran(7): 967,046,907   Pt: 0.944   Wt: 0.329   F/P: 2.93727e+09/3.40452e-10
Total: nine hundred sixty-seven million forty-six thousand nine hundred seven

[] pctran 8
PathTran(8): 19,334,868,954   Pt: 3.342   Wt: 0.944   F/P: 2.04706e+10/4.88507e-11
Total: nineteen billion three hundred thirty-four million eight hundred sixty-eight thousand nine hundred fifty-four

[] pctran 9
PathTran(9): 388,122,896,174   Pt: 8.757   Wt: 2.360   F/P: 1.64446e+11/6.08101e-12
Total: three hundred eighty-eight billion one hundred twenty-two million eight hundred ninety-six thousand one hundred seventy-four

[] pctran 10
PathTran(10): 7,761,991,712,193   Pt: 20.628   Wt: 5.737   F/P: 1.35289e+12/7.3916e-13
Total: seven trillion seven hundred sixty-one billion nine hundred ninety-one million seven hundred twelve thousand one hundred ninety-three

[] pctran 11
PathTran(11): 155,489,998,980,016   Pt: 39.345   Wt: 10.426   F/P: 1.49136e+13/6.70527e-14
Total: one hundred fifty-five trillion four hundred eighty-nine billion nine hundred ninety-eight million nine hundred eighty thousand sixteen

[] pctran 12
PathTran(12): 3,109,584,192,964,526   Pt: 1:11.958   Wt: 18.907   F/P: 1.6446e+14/6.08049e-15
Total: three quadrillion one hundred nine trillion five hundred eighty-four billion one hundred ninety-two million nine hundred sixty-four thousand five hundred twenty-six

[Ajedrecista]

Hello again:

JetChess 1.0.0.0 has confirmed some of those perft() values; I also calculated a few more:

Kings and queens perft():

[d]3qk3/8/8/8/8/8/8/3QK3 w - - 0 1

Code: Select all

 Perft(0) =                           1
 Perft(1) =                          20
 Perft(2) =                         301
 Perft(3) =                       6,063
 Perft(4) =                     119,006
 Perft(5) =                   2,409,458
 Perft(6) =                  48,001,999
 Perft(7) =                 967,046,907
 Perft(8) =              19,334,868,954
 Perft(9) =             388,122,896,174
Perft(10) =           7,761,991,712,193
Perft(11) =         155,489,998,980,016
Perft(12) =       3,109,584,192,964,526
Perft(13) =      62,240,251,739,849,912
Perft(14) =   1,245,006,297,364,598,621
Perft(15) =  24,915,344,586,870,141,927
Perft(16) = 498,561,350,478,541,599,590

I used JetChess and a MonteCarlo perft estimate for obtain the exact results of Perft(15) and Perft(16), which overflowed the 64-bit integer counters. Please read this post and the following one for obtain more info about this combination of perft counter and MC perft estimate.

------------------------

Kings and rooks perft():

[d]r3k2r/8/8/8/8/8/8/R3K2R w KQkq - 0 1

Code: Select all

Perft(0) =                 1
Perft(1) =                26
Perft(2) =               568
Perft(3) =            13,744
Perft(4) =           314,346
Perft(5) =         7,594,526
Perft(6) =       179,862,938
Perft(7) =     4,408,318,687
Perft(8) =   106,978,816,283
Perft(9) = 2,649,670,519,428

------------------------

Kings and bishops perft():

[d]2b1kb2/8/8/8/8/8/8/2B1KB2 w - - 0 1

Code: Select all

 Perft(0) =                  1
 Perft(1) =                 18
 Perft(2) =                305
 Perft(3) =              5,575
 Perft(4) =             99,932
 Perft(5) =          1,879,563
 Perft(6) =         34,853,962
 Perft(7) =        667,568,067
 Perft(8) =     12,658,837,579
 Perft(9) =    245,447,959,999
Perft(10) =  4,725,379,779,416
Perft(11) = 92,387,695,917,003

------------------------

Kings and knights perft():

[d]1n2k1n1/8/8/8/8/8/8/1N2K1N1 w - - 0 1

Code: Select all

 Perft(0) =                     1
 Perft(1) =                    11
 Perft(2) =                   121
 Perft(3) =                 1,551
 Perft(4) =                19,764
 Perft(5) =               273,291
 Perft(6) =             3,736,106
 Perft(7) =            54,343,448
 Perft(8) =           781,298,405
 Perft(9) =        11,689,654,917
Perft(10) =       173,060,266,601
Perft(11) =     2,642,557,929,049
Perft(12) =    39,965,451,511,890
Perft(13) =   617,103,366,847,549
Perft(14) = 9,452,381,631,216,087

I hope that the new values given by me can be confirmed by someone else.

Regards from Spain.

Ajedrecista.

[sje]

When I first did perft(7) back around 1989, it took about 36 hours. Now it's 1.7 seconds. In late 2002, perft(10) took about 18 days. Now it's 57 minutes. With better hardware and transposition tables, here's the best I can do on my 3.4 GHz Core i7 box.

Code: Select all

[] pctran 7
PathTran(7): 3,195,901,860   Pt: 12.636   Wt: 1.674   F/P: 1.90813e+09/5.24075e-10
Total: three billion one hundred ninety-five million nine hundred one thousand eight hundred sixty

[] pctran 8
PathTran(8): 84,998,978,956   Pt: 2:43.694   Wt: 20.777   F/P: 4.09096e+09/2.44442e-10
Total: eighty-four billion nine hundred ninety-eight million nine hundred seventy-eight thousand nine hundred fifty-six

[] pctran 9
PathTran(9): 2,439,530,234,167   Pt: 28:58.384   Wt: 3:39.565   F/P: 1.11107e+10/9.00033e-11
Total: two trillion four hundred thirty-nine billion five hundred thirty million two hundred thirty-four thousand one hundred sixty-seven

[] pctran 10
PathTran(10): 69,352,859,712,417   Pt: 7:30:07.727   Wt: 57:06.587   F/P: 2.02396e+10/4.9408e-11
Total: sixty-nine trillion three hundred fifty-two billion eight hundred fifty-nine million seven hundred twelve thousand four hundred seventeen

[sje]

And more than 19 hours for the next one, perft(11):

Code: Select all

[] pctran 11
PathTran(11): 2,097,651,003,696,806   Pt: 6:07:09:56.606   Wt: 19:10:03.872   F/P: 3.0399e+10/3.28958e-11
Total: two quadrillion ninety-seven trillion six hundred fifty-one billion three million six hundred ninety-six thousand eight hundred six

[ankan]

My CPU perft program takes almost same amount of time (single threaded running on overclocked 2600k @ 4.2 GHz using 6 GB hash table):

Code: Select all

Perft 1: 20,   Time taken: 8.10502e-006 seconds, nps: 2467606

Perft 2: 400,   Time taken: 1.71106e-005 seconds, nps: 23377326

Perft 3: 8902,   Time taken: 9.81608e-005 seconds, nps: 90687940

Perft 4: 197281,   Time taken: 0.00189898 seconds, nps: 103888093

Perft 5: 4865609,   Time taken: 0.0287545 seconds, nps: 169212043

Perft 6: 119060324,   Time taken: 0.172701 seconds, nps: 689399661

Perft 7: 3195901860,   Time taken: 2.14052 seconds, nps: 1493046967

Perft 8: 84998978956,   Time taken: 26.7454 seconds, nps: 3178079394

Perft 9: 2439530234167,   Time taken: 298.334 seconds, nps: 8177188795

Perft 10: 69352859712417,   Time taken: 3592.63 seconds, nps: 19304212832

Perft 11: 2097651003696806,   Time taken: 60563.3 seconds, nps: 34635684828