The Grand Chess Tree

[Sapling]

I've also not seen level 12 with the full statistics so will be excited to put something new out there I'm provisioning a few more compute resources of my own today so should hopefully get to the goal a bit quicker! Estimating around 10-15 days (the rate is increasing as all my workers local cache fill up)

I may switch to computing up to depth 12 for kiwipete (and possibly some other positions) before moving on to startpos perft(13), just to give me some extra time to work on a GPU implementation.

[Ajedrecista]

Hello Tim:

I've also not seen level 12 with the full statistics so will be excited to put something new out there I'm provisioning a few more compute resources of my own today so should hopefully get to the goal a bit quicker! Estimating around 10-15 days (the rate is increasing as all my workers local cache fill up)

I may switch to computing up to depth 12 for kiwipete (and possibly some other positions) before moving on to startpos perft(13), just to give me some extra time to work on a GPU implementation.

If Kiwipete position is of your interest, I only found up to perft(6) on the Internet. I compute further values with gperft 1.1 perft counter:

[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

perft(7) =    374,190,009,323
perft(8) = 15,493,944,087,984

Beware that perft(n) of Kiwipete is going to take way more time that Perft(n) of the starting position. I copy here the divided perft(7) and divided perft(8) of Kiwipete position as proofs:

Code: Select all

Nxd7       8,964,657,917
Nxf7       8,146,033,781
Nxg6       7,679,730,505
Bxa6       6,480,008,058
Qxf6       7,136,487,960
Qxh3      10,314,822,739
dxe6       9,741,806,126
gxh3       7,265,571,564
Nc6        8,102,096,729
Nc4        6,485,370,632
Ng4        6,143,255,313
Nd3        6,010,078,078
Nb5        8,536,331,785
Na4        9,346,560,191
Nb1        7,574,150,349
Nd1        7,560,735,010
Qh5        9,445,639,220
Qg4        9,047,498,461
Bh6        7,594,325,672
Bg5        8,614,847,947
Bf4        7,644,341,581
Be3        8,831,533,611
Bc1        7,188,695,081
Bb5        7,708,742,487
Bc4        8,143,385,765
Bd3        7,843,129,110
Bd1        5,464,336,094
Bf1        7,893,751,276
Qf5       10,870,589,675
Qf4        8,487,829,062
Qd3        7,637,864,872
Qe3        8,885,152,041
Qg3        9,484,342,196
Rb1        7,312,345,541
Rc1        7,249,929,466
Rd1        6,710,600,976
Rf1        6,941,145,758
Rg1        7,743,466,513
d6         7,180,089,264
a3         9,491,604,100
b3         7,059,227,732
g3         6,261,927,843
a4         8,711,431,200
g4         5,928,350,487
Kd1        6,605,992,768
Kf1        6,050,797,903
O-O        8,038,310,789
O-O-O      6,631,088,095
TOTAL    374,190,009,323

Code: Select all

Nxg6       321,396,995,625
Nxd7       392,791,660,921
Nxf7       342,156,201,114
Bxa6       241,387,211,019
Qxh3       426,819,204,139
Qxf6       264,835,246,136
gxh3       299,731,647,143
dxe6       416,725,713,915
Nb1        314,690,850,723
Nd1        313,541,077,840
Na4        386,563,996,492
Nb5        335,285,961,781
Nd3        256,502,027,044
Nc4        270,362,407,999
Ng4        258,333,972,987
Nc6        338,226,587,566
Bc1        299,879,274,628
Be3        367,090,135,640
Bf4        320,459,928,018
Bg5        349,225,586,853
Bh6        309,132,031,261
Bd1        232,299,228,024
Bf1        334,227,994,103
Bd3        323,148,326,669
Bc4        331,999,730,288
Bb5        305,642,680,663
Qg4        378,965,394,329
Qh5        393,307,640,844
Rb1        305,422,602,641
Rc1        302,507,795,871
Rd1        279,687,999,714
Rf1        289,675,094,245
Rg1        320,668,896,061
Qd3        318,831,262,788
Qe3        374,069,077,176
Qg3        401,204,979,014
Qf4        355,165,150,488
Qf5        460,271,562,178
a3         402,654,556,153
b3         287,466,826,392
g3         252,982,671,742
d6         281,928,947,052
a4         363,636,312,256
g4         238,841,590,165
Kd1        274,750,767,755
Kf1        248,309,615,874
O-O        334,274,439,913
O-O-O      276,865,226,742
TOTAL   15,493,944,087,984

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

Meanwhile, I see that your count of full statistics of Perft(12) goes well, with circa 3.8e+15 nodes counted or around 6% done. Let us see if the total count can be finished before the end of February. Good luck!

Regards from Spain.

Ajedrecista.

[Sapling]

Thanks Ajedrecista!

Last night we had a new member join 'PatrickH' who's already contributed 517t positions to startpos perft(12), hopefully if progress continues we'll be on track for completion in around two weeks!

Meanwhile we're thinking of adding more positions at various depths that the contributors can choose from (like kiwipete) to ensure the project still has the excitement of hitting goals whilst the longer tasks are in progress.
Tracked with this Github issue

[Uri Blass]

If you are interested in verifying perft not to have bugs in some rare positions then I suggest to add command perftpgn x.pgn n that calculate the sum of all result of perft(n) for every position in the pgn.

For example perftpgn x.pgn 3 calculate the sum of perft(3) for all positions that happened in the games of the pgn.

You can do the same also for epd files.
My old engine movei that I stopped to work on it many years ago support the command perfrtpgn x.pgn n at console mode so you can compare with it to see if your engine has bugs or maybe movei has bugs.

You can use movei also to calculate perft of the initial position by typing at console mode perft 7 and you can get the following output:

a2a3 106743106
a2a4 137077337
b2b3 133233975
b2b4 134087476
c2c3 144074944
c2c4 157756443
d2d3 227598692
d2d4 269605599
e2e3 306138410
e2e4 309478263
f2f3 102021008
f2f4 119614841
g2g3 135987651
g2g4 130293018
h2h3 106678423
h2h4 138495290
b1a3 120142144
b1c3 148527161
g1f3 147678554
g1h3 120669525
perft(7) = 3195901860,time=7090

perft 8
b2b3 3579299617
b2b4 3569067629
g2g3 3641432923
g2g4 3466204702
d2d3 6093248619
d2d4 7184581950
f2f3 2728615868
f2f4 3199039406
h2h3 2860408680
h2h4 3711123115
a2a3 2863411653
a2a4 3676309619
c2c3 3806229124
c2c4 4199667616
e2e3 8039390919
e2e4 8102108221
b1a3 3193522577
b1c3 3926684340
g1f3 3937354096
g1h3 3221278282
perft(8) = 84998978956,time=103904

[Sapling]

That's a really cool idea @Uri Blass !

I have similar tests set up using Ethereal's perft test suite but those are for the node count only.

So for the other stats I've used the verified results on the CPW perft page

[Ajedrecista]

Hello:

I computed perft(9) = 708,027,759,953,502 of Kiwipete position with gperft 1.1 perft counter. Summary of the position:

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

perft(1) =                  48
perft(2) =               2,039
perft(3) =              97,862
perft(4) =           4,085,603
perft(5) =         193,690,690
perft(6) =       8,031,647,685
perft(7) =     374,190,009,323
perft(8) =  15,493,944,087,984
perft(9) = 708,027,759,953,502

I hope you can verify these results.

Divided perft(9) of Kiwipete position:

Code: Select all

Nxd7       17,841,614,762,771
Nxf7       15,556,584,634,166
Nxg6       14,660,802,752,365
Bxa6       11,610,329,611,080
Qxf6       12,429,245,267,090
Qxh3       20,213,264,583,037
dxe6       19,648,740,553,553
gxh3       13,585,927,848,828
Nc6        15,770,851,252,373
Nc4        11,935,384,349,792
Ng4        10,926,517,539,663
Nd3        10,949,898,218,012
Nb5        16,558,954,887,676
Na4        18,295,514,848,885
Nb1        13,989,775,862,630
Nd1        13,940,234,223,992
Qh5        18,109,546,088,726
Qg4        17,590,420,113,757
Bh6        14,213,390,633,204
Bg5        16,474,645,122,655
Bf4        14,604,950,944,019
Be3        17,283,591,628,447
Bc1        13,381,123,307,084
Bb5        14,439,891,624,558
Bc4        15,457,831,370,434
Bd3        14,796,448,995,983
Bd1         9,684,737,364,184
Bf1        14,859,603,456,059
Qf5        21,378,118,001,692
Qf4        16,226,823,301,871
Qd3        14,529,695,547,948
Qe3        17,154,817,618,150
Qg3        18,682,076,264,644
Rb1        13,746,642,706,679
Rc1        13,537,161,365,309
Rd1        12,517,006,910,284
Rf1        12,893,511,653,497
Rg1        14,734,587,002,952
d6         13,147,124,269,772
a3         18,935,000,323,218
b3         12,953,376,489,356
g3         11,066,640,490,880
a4         16,877,033,270,225
g4         10,348,190,768,599
Kd1        12,124,039,380,826
Kf1        10,712,055,450,053
O-O        15,367,034,402,130
O-O-O      12,287,002,890,394
TOTAL     708,027,759,953,502

This is my limit on this position.

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

Nice graph addition in your site! 29.10% of nodes completed and 31.37% of tasks completed so far. Looks good!

Regards from Spain.

Ajedrecista.

[Sapling]

I computed perft(9) = 708,027,759,953,502 of Kiwipete position with gperft 1.1 perft counter. Summary of the position:
...
Nice graph addition in your site! 29.10% of nodes completed and 31.37% of tasks completed so far. Looks good!

Incredible! I'm very caught up implementing a GPU version of my client. After much trial and error I have got a POC somewhat working that seems very promising. Hopefully with modern GPU's perft 13 will be on the table.

I'll also be starting work on the Kiwipete position once I'm done with the GPU alg or perft 12 finishes, whichever comes first.

And thanks for the feedback, If you've any other suggestions I'd love to hear them! (or join the Discord community to discuss them )

[Sapling]

Hello:

I computed perft(9) = 708,027,759,953,502 of Kiwipete position with gperft 1.1 perft counter. Summary of the position:

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

perft(1) =                  48
perft(2) =               2,039
perft(3) =              97,862
perft(4) =           4,085,603
perft(5) =         193,690,690
perft(6) =       8,031,647,685
perft(7) =     374,190,009,323
perft(8) =  15,493,944,087,984
perft(9) = 708,027,759,953,502

I hope you can verify these results.

@Ajedrecista my results are in for Kiwipete perft(9) and I can verify they match yours!

You can view them here (including full stats):
https://grandchesstree.com/perft/1/results

Another thing to mention, I created a version of my move generator with bulk counting at the leaf nodes, so it only produces the node count stat. But it is getting around 800mnps with a single thread, multi threaded on one machine I'm able to hit 30bnps!

[Sapling]

Perft(12) with full stats completed!

Code: Select all

 {
      "nodes": 62854969236701747,
      "captures": 4737246427144832,
      "enpassants": 8240532674085,
      "castles": 79307385134229,
      "promotions": 1537540318804,
      "direct_checks": 1221307803714074,
      "single_discovered_checks": 2622814797365,
      "direct_discovered_checks": 517907386372,
      "double_discovered_checks": 2754205,
      "total_checks": 1224448528652016,
      "direct_mates": 8321003453595,
      "single_discovered_mates": 2750996818,
      "direct_discovered_mates": 37337408546,
      "double_discovered_mates": 0,
      "total_mates": 8361091858959,
      "total_tasks": 72078,
      "started_at": 1738761004,
      "finished_at": 1740641268,
        }

With many thanks to the 11 contributors:
[Timmoth 46.0k tasks] [PatrickH 10.3k tasks] [ShenniganMan 7.4k tasks] [prljav 5.4k tasks] [HansTibberio 1.1k tasks] [xyzzy 773 tasks] [madbot 509 tasks] [Chester-alt 381 tasks] [someone 226 tasks] [eduherminio 9 tasks] [moose_curse 3 tasks]

This job was confirmed by running a separate verification task using different Zobrist Hash values and bulk counting to confirm the node count for each task.

It took 21 days in total, but 50% of the goal was achieved in the last week (due to an increase in contributors + various optimizations)

We're currently computing Kiwipete depth 10 which is estimated to take about a week whilst we experiment with different parameters to maximize each workers performance.

For start pos depth(13) each task will start from depth 7 requiring around 3% of the work (depth 12 was computed from depth 4 which is around 40%) - this reduction is due to spawning tasks for the 96 million unique positions that occur out of the 3.2 billion possible at depth 7.

Check out the full results table here

[Sapling]

Perft 13 is complete! Here are the full stats:

Code: Select all

{
   "nodes":1981066775000396239,
   "captures":164887578949283272,
   "enpassants":316969102478579,
   "castles":3566807841445861,
   "promotions":99123062527888,
   "direct_checks":44116169280443933,
   "single_discovered_checks":115927410110562,
   "direct_discovered_checks":20435529375001,
   "double_discovered_checks":128622730,
   "direct_mates":344473703225753,
   "single_discovered_mates":168726679343,
   "direct_discovered_mates":2099815858505,
   "double_discovered_mates":618,
   "total_checks":44252532348552226,
   "total_mates":346742245764219
}

What I find very interesting is that this is the first depth that a double discovered check mate is possible!

Many thanks to the contributors:

Code: Select all

full tasks     fast tasks    name
36934861	0	 "PatrickH"
29279138	74134897 "Timmoth"
15319993	0	 "prljav"
4216495		4445521  "xyzzy"
3879530		3680932  "McTwist"
2704899		1074469  "Matt"
2326718		12558534 "HansTibberio"
1719384		0        "OWR"
15147		0        "eduherminio"
3903		416611   "Chester-alt"
0		89104    "madbot"

(full tasks are a heavier workload that calculate the full statistics, fast tasks are for verification)

There is quite a bit of work necessary before we move on to depth 14, and as I've just started a new job I expect it to take a little while before we're ready. But once we start I estimate it to take around a month to compute with current resources.