Perft 25

[Ajedrecista]

Hello:

Perft 31: 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Ka2 10371366973326742232771
Kb1 13252601250407797823413
Kb2 19366999975110719410642

Count: 42990968198845259466826

That's forty-two sextillion nine hundred ninety quintillion nine hundred sixty-eight quadrillion one hundred ninety-eight trillion eight hundred forty-five billion two hundred fifty-nine million four hundred sixty-six thousand eight hundred twenty-six. By contrast, 2^64-1 is less than a thousandth of this at 18446744073709551615 or eighteen quintillion four hundred forty-six quadrillion seven hundred forty-four trillion seventy-three billion seven hundred nine million five hundred fifty-one thousand six hundred fifteen.

The Lisp program in use stores a hash and a count for each unique depth-1 position, so more than four GB were needed to hold the data because of the length of the hash signatures. This was handled by using ccl64, the 64 bit version of Clozure Common Lisp.

Sorry for bumping this old topic (I discovered it by chance) and for the very long output of this post.

Results by JetChess 1.0.0.0 (single core, w32) using 1024 MB of hash (running in an Intel Pentium D930 (2999 MHz)):

[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Code: Select all

  1  Ka1-b1  13379419933284543
  2  Ka1-a2  10458620597023933
  3  Ka1-b2  19513928050956822

Total:   43351968581265298

43,351,968,581,265,298 (move pathes after 23 half moves).

Time: 131 ms (0:00:00.131).

Code: Select all

  1  Ka1-b1  69372789029739057
  2  Ka1-a2  54229670648519839
  3  Ka1-b2  101180509873108717

Total:   224782969551367613

224,782,969,551,367,613 (move pathes after 24 half moves).

Time: 670 ms (0:00:00.670).

Code: Select all

  1  Ka1-b1  419736306837795168
  2  Ka1-a2  327999083762531157
  3  Ka1-b2  612315810248920416

Total:   1360051200849246741

1,360,051,200,849,246,741 (move pathes after 25 half moves).

Time: 1.132 s (0:00:01.132).

Code: Select all

  1  Ka1-b1  2184210511941397691
  2  Ka1-a2  1706910857137266354
  3  Ka1-b2  3186337832855957271

Total:   7077459201934621316

7,077,459,201,934,621,316 (move pathes after 26 half moves).

Time: 2.699 s (0:00:02.699).

Code: Select all

  1  Ka1-b1  -5227128206127687200
  2  Ka1-a2  -8115750359012173861
  3  Ka1-b2  844241536037317366

Total:   5948107044607007921

5,948,107,044,607,007,921 (move pathes after 27 half moves).

Time: 4.864 s (0:00:04.864).

Code: Select all

  1  Ka1-b1  -4770507526121808229
  2  Ka1-a2  -1401235102567543256
  3  Ka1-b2  8478473141219228117

Total:   2306730512529876632

2,306,730,512,529,876,632 (move pathes after 28 half moves).

Time: 12.536 s (0:00:12.536).

Code: Select all

  1  Ka1-b1  -6447697976467554752
  2  Ka1-a2  -5371963933529090433
  3  Ka1-b2  1282029907223704729

Total:   7909112070936611160

7,909,112,070,936,611,160 (move pathes after 29 half moves).

Time: 23.006 s (0:00:23.006).

Code: Select all

  1  Ka1-b1  -6957651037998863439
  2  Ka1-a2  -4638806270450955975
  3  Ka1-b2  3350697430572130456

Total:   -8245759877877688958

-8,245,759,877,877,688,958 (move pathes after 30 half moves).

Time: 61.990 s (0:01:01.990).

Code: Select all

  1  Ka1-b1  7839005484339763125
  2  Ka1-a2  4296803901974224579
  3  Ka1-b2  -2081302284309786158

Total:   -8392236971705350070

-8,392,236,971,705,350,070 (move pathes after 31 half moves).

Time: 124.922 s (0:02:04.922).

Code: Select all

  1  Ka1-b1  -9173148514598047596
  2  Ka1-a2  3725130762321234904
  3  Ka1-b2  -637322109603466764

Total:   -6085339861880279456

-6,085,339,861,880,279,456 (move pathes after 32 half moves).

Time: 410.541 s (0:06:50.541).

So, things go good until Perft(26). Surely it is due to a similar issue that had qperft (by Muller) some months ago: in that case, replacing lld by I64d in qperft code was enough.

Going with unique positions (running JetChess 1.0.0.0 again, but now with hash = 512 MB and 2 steps):

Code: Select all

Count  0:        124805
Count  1:        124743

Positions:       249548

249,548 (positions after 23 half moves).

Time: 817 ms (0:00:00.817).

Code: Select all

Count  0:        196788
Count  1:        196770

Positions:       393558

393,558 (positions after 24 half moves).

Time: 1.500 s (0:00:01.500).

Code: Select all

Count  0:        679752
Count  1:        681431

Positions:      1361183

1,361,183 (positions after 25 half moves).

Time: 6.603 s (0:00:06.603).

Code: Select all

Count  0:        995228
Count  1:        995500

Positions:      1990728

1,990,728 (positions after 26 half moves).

Time: 9.968 s (0:00:09.968).

Code: Select all

Count  0:       2944387
Count  1:       2944187

Positions:      5888574

5,888,574 (positions after 27 half moves).

Time: 29.396 s (0:00:29.396).

Now: hash = 256 MB and 4 steps (for not overflowing the hash).

Code: Select all

Count  0:       2048745
Count  1:       2049615
Count  2:       2047721
Count  3:       2051948

Positions:      8198029

8,198,029 (positions after 28 half moves).

Time: 109.065 s (0:01:49.065).

Code: Select all

Count  0:       5287579
Count  1:       5285389
Count  2:       5286781
Count  3:       5284510

Positions:     21144259

21,144,259 (positions after 29 half moves).

Time: 286.295 s (0:04:46.295).

Now: hash = 128 MB and 8 steps (for not overflowing the hash).

Code: Select all

Count  0:       4218297
Count  1:       4220105
Count  2:       4219557
Count  3:       4219810
Count  4:       4219399
Count  5:       4219520
Count  6:       4219170
Count  7:       4219863

Positions:     33755721

33,755,721 (positions after 30 half moves).

Time: 4831.371 s (1:20:31.371).

I forgot to click en passant flag for counting unique positions (my bad), but since in this position can not exist en passant captures (at least this is what I think), these counts of unique positions should be good (unique positions for 25 plies match between Steven and me). I was really lucky this time. I hope that someone could check the numbers of unique positions from 23 plies to 30 plies and will post his/her results.

Regards from Spain.

Ajedrecista.

[ibid]

Hello:

Sorry for bumping this old topic (I discovered it by chance) and for the very long output of this post.

Quite alright, I'd missed this one too. And who doesn't enjoy big numbers. :)

Now: hash = 128 MB and 8 steps (for not overflowing the hash).

Code: Select all

Count  0:       4218297
Count  1:       4220105
Count  2:       4219557
Count  3:       4219810
Count  4:       4219399
Count  5:       4219520
Count  6:       4219170
Count  7:       4219863

Positions:     33755721

33,755,721 (positions after 30 half moves).

Time: 4831.371 s (1:20:31.371).

Agreed on this one and all the previous ones. 30 ply took my program 47 seconds...

Also:
31: 77,174,938 (193 seconds)
32: 172,018,607 (256 seconds)

All I have time for tonight. Perhaps a couple more tomorrow. And I'll need to hack in some code for 128 bit integers for some silly perfts. :)

-paul

[Ajedrecista]

Hello Paul!

Hello:

Sorry for bumping this old topic (I discovered it by chance) and for the very long output of this post.

Quite alright, I'd missed this one too. And who doesn't enjoy big numbers.

Now: hash = 128 MB and 8 steps (for not overflowing the hash).

Code: Select all

Count  0:       4218297
Count  1:       4220105
Count  2:       4219557
Count  3:       4219810
Count  4:       4219399
Count  5:       4219520
Count  6:       4219170
Count  7:       4219863

Positions:     33755721

33,755,721 (positions after 30 half moves).

Time: 4831.371 s (1:20:31.371).

Agreed on this one and all the previous ones. 30 ply took my program 47 seconds...

Also:
31: 77,174,938 (193 seconds)
32: 172,018,607 (256 seconds)

All I have time for tonight. Perhaps a couple more tomorrow. And I'll need to hack in some code for 128 bit integers for some silly perfts.

-paul

The slowdown of my count of unique positions was more than noticeable from 29 plies to 30 plies... I do not know why. I am almost sure that if I run the same count (30 plies) with the same programme (JetChess) in an Intel i5-760 of my university, this count will take less than half an hour.

Anyway, you have a beast! Congratulations. I wonder if your programme is single core (I do not think so) and the specifications of your (monster) computer.

Regards from Spain.

Ajedrecista.

[ibid]

Hello Paul!

The slowdown of my count of unique positions was more than noticeable from 29 plies to 30 plies... I do not know why. I am almost sure that if I run the same count (30 plies) with the same programme (JetChess) in an Intel i5-760 of my university, this count will take less than half an hour.

Anyway, you have a beast! Congratulations. I wonder if your programme is single core (I do not think so) and the specifications of your (monster) computer.

Regards from Spain.

Ajedrecista.

Hello,

Latest unique position numbers:
33: 401,072,304
34: 892,103,091
35: 2,379,035,449
36: 4,070,072,767
I think I'll stop at this point, uniq 36 took a little over 7 hours and an awful lot of disk space. (I save positions as a series of moves to reach the position, which is effective enough for 10 ply, not so much for 36....)

The machine is an AMD Phenom 1090T (which is 6 cores, 3.2 GHz) with 8 GB of memory. The program for finding unique positions only uses 1 core though. The perft code does use all 6.

-paul

[ibid]

I think this is (more than) enough, time to stop...

Code: Select all

ply         unique                                         perft
 0               1   ---                                       1   ---
 1               3  3.00                                       3  3.00
 2              15  5.00                                      15  5.00
 3              45  3.00                                      90  6.00
 4              72  1.60                                     396  4.40
 5             104  1.44                                   2,090  5.28
 6             130  1.25                                  10,545  5.05
 7             168  1.29                                  61,641  5.85
 8             202  1.20                                 301,431  4.89
 9             270  1.34                               1,745,898  5.79
10             343  1.27                               8,759,106  5.02
11             475  1.38                              51,930,249  5.93
12             590  1.24                             260,691,777  5.02
13             997  1.69                           1,552,363,462  5.95
14           1,286  1.29                           7,868,676,725  5.07
15           2,125  1.65                          47,200,234,117  6.00
16           2,405  1.13                         240,300,379,067  5.09
17           4,366  1.82                       1,445,829,070,875  6.02
18           5,381  1.23                       7,404,533,753,909  5.12
19          10,718  1.99                      44,668,473,808,109  6.03
20          16,084  1.50                     229,733,948,623,885  5.14
21          41,926  2.61                   1,387,817,752,970,173  6.04
22          72,128  1.72                   7,169,249,864,347,205  5.17
23         249,548  3.46                  43,351,968,581,265,298  6.05
24         393,558  1.58                 224,782,969,551,367,613  5.19
25       1,361,183  3.46               1,360,051,200,849,246,741  6.05
26       1,990,728  1.46               7,077,459,201,934,621,316  5.20
27       5,888,574  2.96              42,841,595,192,026,111,153  6.05
28       8,198,029  1.39             223,667,659,397,044,496,024  5.22
29      21,144,259  2.58           1,354,521,429,451,733,879,128  6.06
30      33,755,721  1.60           7,093,750,708,500,299,683,202  5.24
31      77,174,938  2.29          42,990,968,198,845,259,466,826  6.06
32     172,018,607  2.23         225,800,508,866,416,741,052,000  5.25
33     401,072,304  2.33       1,370,740,627,565,488,881,574,801  6.07
34     892,103,091  2.22       7,219,068,497,258,521,872,245,064  5.27
35   2,379,035,449  2.67      44,024,425,403,664,153,054,685,359  6.10
36   4,070,072,767  1.71     232,412,410,272,588,541,521,139,215  5.28
37                         1,436,535,002,909,160,714,705,256,509  6.18
38                         7,597,355,348,240,889,199,326,467,453  5.29
39                        48,915,573,040,264,513,077,417,979,294  6.44

-paul

[Ajedrecista]

Hi Paul!

I think this is (more than) enough, time to stop...

Code: Select all

ply         unique                                         perft
 0               1   ---                                       1   ---
 1               3  3.00                                       3  3.00
 2              15  5.00                                      15  5.00
 3              45  3.00                                      90  6.00
 4              72  1.60                                     396  4.40
 5             104  1.44                                   2,090  5.28
 6             130  1.25                                  10,545  5.05
 7             168  1.29                                  61,641  5.85
 8             202  1.20                                 301,431  4.89
 9             270  1.34                               1,745,898  5.79
10             343  1.27                               8,759,106  5.02
11             475  1.38                              51,930,249  5.93
12             590  1.24                             260,691,777  5.02
13             997  1.69                           1,552,363,462  5.95
14           1,286  1.29                           7,868,676,725  5.07
15           2,125  1.65                          47,200,234,117  6.00
16           2,405  1.13                         240,300,379,067  5.09
17           4,366  1.82                       1,445,829,070,875  6.02
18           5,381  1.23                       7,404,533,753,909  5.12
19          10,718  1.99                      44,668,473,808,109  6.03
20          16,084  1.50                     229,733,948,623,885  5.14
21          41,926  2.61                   1,387,817,752,970,173  6.04
22          72,128  1.72                   7,169,249,864,347,205  5.17
23         249,548  3.46                  43,351,968,581,265,298  6.05
24         393,558  1.58                 224,782,969,551,367,613  5.19
25       1,361,183  3.46               1,360,051,200,849,246,741  6.05
26       1,990,728  1.46               7,077,459,201,934,621,316  5.20
27       5,888,574  2.96              42,841,595,192,026,111,153  6.05
28       8,198,029  1.39             223,667,659,397,044,496,024  5.22
29      21,144,259  2.58           1,354,521,429,451,733,879,128  6.06
30      33,755,721  1.60           7,093,750,708,500,299,683,202  5.24
31      77,174,938  2.29          42,990,968,198,845,259,466,826  6.06
32     172,018,607  2.23         225,800,508,866,416,741,052,000  5.25
33     401,072,304  2.33       1,370,740,627,565,488,881,574,801  6.07
34     892,103,091  2.22       7,219,068,497,258,521,872,245,064  5.27
35   2,379,035,449  2.67      44,024,425,403,664,153,054,685,359  6.10
36   4,070,072,767  1.71     232,412,410,272,588,541,521,139,215  5.28
37                         1,436,535,002,909,160,714,705,256,509  6.18
38                         7,597,355,348,240,889,199,326,467,453  5.29
39                        48,915,573,040,264,513,077,417,979,294  6.44

-paul

I agree with you: it is time to stop. You reach Perft(39)! You are a perft genius. Impossible for JetChess, which 'upper ply' is 32. The addition of branching factors is very useful: it shows clearly the 'odd-even effect' that I (and other people) had to take in mind for doing serious estimates for Perft(13) of the starting position: without realising on the 'odd-even effect', my estimate (following my clumsy method) was around 1.973e+18 IIRC (~ 0.4% of relative error); but realising this effect, my average estimate was around 1.9804681e+18 (~ 0.03% of error... really between 0.02% and 0.04% because I gave two bounds). Congratulations.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello:

Hello:

Sorry for bumping this old topic (I discovered it by chance) and for the very long output of this post.

Quite alright, I'd missed this one too. And who doesn't enjoy big numbers.

Now: hash = 128 MB and 8 steps (for not overflowing the hash).

Code: Select all

Count  0:       4218297
Count  1:       4220105
Count  2:       4219557
Count  3:       4219810
Count  4:       4219399
Count  5:       4219520
Count  6:       4219170
Count  7:       4219863

Positions:     33755721

33,755,721 (positions after 30 half moves).

Time: 4831.371 s (1:20:31.371).

Agreed on this one and all the previous ones. 30 ply took my program 47 seconds...

Also:
31: 77,174,938 (193 seconds)
32: 172,018,607 (256 seconds)

All I have time for tonight. Perhaps a couple more tomorrow. And I'll need to hack in some code for 128 bit integers for some silly perfts.

-paul

I post the results of unique positions for 31 plies not only for check Paul's results (perfect as expected) but for pointing out (again) speed differences because of hardware. This count was run in an Intel i5-760 (~ 2.8 GHz) in single core mode (JetChess can not used more than one core for the same task).

Hash = 1024 MB and 2 steps for not overflowing the hash:

Code: Select all

Count  0:      38585171
Count  1:      38589767

Positions:     77174938

77,174,938 (positions after 31 half moves).

Time: 501.345 s (0:08:21.345).

I read in JetChess help file that when counting unique positions, real hash is 25% more, so instead of 1 GB (1024 MB), it uses 1.25 GB (1280 MB).

Regards from Spain.

Ajedrecista.

[ibid]

Hello:

Hello:

Sorry for bumping this old topic (I discovered it by chance) and for the very long output of this post.

Quite alright, I'd missed this one too. And who doesn't enjoy big numbers. :)

Now: hash = 128 MB and 8 steps (for not overflowing the hash).

Code: Select all

Count  0:       4218297
Count  1:       4220105
Count  2:       4219557
Count  3:       4219810
Count  4:       4219399
Count  5:       4219520
Count  6:       4219170
Count  7:       4219863

Positions:     33755721

33,755,721 (positions after 30 half moves).

Time: 4831.371 s (1:20:31.371).

Agreed on this one and all the previous ones. 30 ply took my program 47 seconds...

Also:
31: 77,174,938 (193 seconds)
32: 172,018,607 (256 seconds)

All I have time for tonight. Perhaps a couple more tomorrow. And I'll need to hack in some code for 128 bit integers for some silly perfts. :)

-paul

I post the results of unique positions for 31 plies not only for check Paul's results (perfect as expected) but for pointing out (again) speed differences because of hardware. This count was run in an Intel i5-760 (~ 2.8 GHz) in single core mode (JetChess can not used more than one core for the same task).

Hash = 1024 MB and 2 steps for not overflowing the hash:

Code: Select all

Count  0:      38585171
Count  1:      38589767

Positions:     77174938

77,174,938 (positions after 31 half moves).

Time: 501.345 s (0:08:21.345).

I read in JetChess help file that when counting unique positions, real hash is 25% more, so instead of 1 GB (1024 MB), it uses 1.25 GB (1280 MB).

Regards from Spain.

Ajedrecista.

I'm guessing a bit on how JetChess works, but I imagine the bulk of the time difference is that I have the memory to do 77 million positions in a single segment/step instead of two.

For comparison's sake, the 10 ply unique computation for the initial position was done in 400 segments of roughly 213 million positions each. Should I ever try 11 ply, it will probably involve 4096 segments of about 177 million positions. I do use the hard drive to store temporary data to speed things up when doing multi-segment computations.

-paul

[ibid]

Hello:
I post the results of unique positions for 31 plies not only for check Paul's results (perfect as expected) but for pointing out (again) speed differences because of hardware. This count was run in an Intel i5-760 (~ 2.8 GHz) in single core mode (JetChess can not used more than one core for the same task).

Hash = 1024 MB and 2 steps for not overflowing the hash:

Code: Select all

Count  0:      38585171
Count  1:      38589767

Positions:     77174938

77,174,938 (positions after 31 half moves).

Time: 501.345 s (0:08:21.345).

I read in JetChess help file that when counting unique positions, real hash is 25% more, so instead of 1 GB (1024 MB), it uses 1.25 GB (1280 MB).

Regards from Spain.

Ajedrecista.

Another data point...

I downloaded JetChess and ran this same computation on my windows machine -- 3.2 GHz "Phenom" 840 and it took 702 seconds.
There are other things running, but nothing that should have more than a percent or three impact here. Part of this is no doubt due
to the lack of L3 cache on this cpu (the cpu would logically be called an Athlon to anyone but AMD's marketing department).
I suspect most the difference is just general slowness of the AMD cpu though.

-paul

[Ajedrecista]

Hello:

Maximum ply for JetChess is 32... and I wanted to count the number of unique positions. Of course the result is 172,018,607 but the time of calculation is big enough: 4091.172 s (1:08:11.172).

[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Hash = 1024 MB (really 1280 MB), counting with four steps for not overflow the hash:

Code: Select all

8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Count  0:      43003600
Count  1:      43007209
Count  2:      43000527
Count  3:      43007271

Positions:    172018607

172,018,607 (positions after 32 half moves).

Time: 4091.172 s (1:08:11.172).

The count was run in an Intel i5-760 at 2.8 GHz. This time the speed was more than eight times slower; IMHO JetChess suffers calculating big counts of unique positions if the hardware is not faster enough... but it finally succeeds!

Regards from Spain.

Ajedrecista.