Perft 12 in progress

[Don]

I think it would be actually be very simple to periodically checkpoint the calculation, perhaps every hour or so. If you attempt the perft(13) as you say this may really become important but there are other benefits, such as being able to stop the calculation arbitrarily and pass it to another machine or just continue it at any arbitrary point in time.

If the hash table prefers depth, I don't think you have to do much of anything at all, just save the hash to disk every hour and reload the hash table on startup. If it does not, a tiny second auxiliary hash table which never overwrites a deeper entry will do the job. Essentially you just want to save the first N levels of the tree, where N may just be 3 or 4 or whatever you consider easily manageable.

There are more complicated schemes but this can be implemented in 10 minutes. There is also a very simple way to arbitrarily partition the work to any resolution you desire. Pick a starting point close to the root, such as after the 4th move and assign a job lot number based on the least significant bits of the position signature. If you want 64 "job lots" use 6 bits. Each process starts it's calculation at the 4th ply but is given a job lot number and it skips everything else except the entries with the specified job lot number. The only wrinkle is that you have to combine all the results at the end to get perft numbers. That is another 5 minute job, you are just combining several hash tables into one. You just want to make sure your hash table is large enough to accommodate all the entries of interest (and you don't overwrite deeper entries.)

To get the final numbers once you have the checkpoint file you just start the calculation from scratch and it's quickly re-generated. If you store 4 levels perft(N) will take about the same amount of time as perft(N-4)

Don

What if the power goes off in the middle of the calculation?

Is your perft designed to be able to checkpoint from time to time to store intermediate results? Or I suppose if you save and restore the hash table you will get most of it back in short time?

Having a dump/restore on the transposition table would certainly help, but as this is a one-time calculation I didn't implement the option. Also, the partial sums for positions near the root are kept in a shared access tree and that would have to be saved as well. But this tree is loaded with pointers and so there's another complication for externalization.

If I ever try perft(13), I'll reconsider the dump/restore option.

What I need is an extension cord. A long one that can reach up north to Quebec where the electricity is cheaper and more reliable.

[sje]

There is also a very simple way to arbitrarily partition the work to any resolution you desire. Pick a starting point close to the root, such as after the 4th move and assign a job lot number based on the least significant bits of the position signature. If you want 64 "job lots" use 6 bits. Each process starts it's calculation at the 4th ply but is given a job lot number and it skips everything else except the entries with the specified job lot number.

You're right that work can be distributed based on positions at a fixed depth. A simple allocation of the position subspace should work well and it can be done without a signature distribution scheme.

At ply four, there are 72,708 distinct positions (vs 197,281 total), and at ply five there are 822,518 distinct positions (vs 4,865,609 total). Either would be good for bite-sized task allocation and there would be little need for dump/restore checkpoints. Also, the CIL Toolkit already has the code that lists each position along with its frequency of occurrence as needed for a multiplier for producing a final enumeration result.

Maybe I might give perft(13) a try starting early next winter as the waste heat will help warm my modest home.

[sje]

Looking through the log files of the 17 perft(11) sub-totals, I've calculated the machine time so far as 5,741,519 seconds (66d 10h 51m 59s). This figure will increase significantly as the answers for 1 d4, 1 e4, and 1 h4 are found. I'll guess that the final time usage will be about 100 days.

The 100 day figure for perft(12) gives a first order estimate of 2,000 machine-days for perft(13); that's about five and a half years. If enough people are interested, we can make a collective attempt on perft(13) via distributed computing. My first idea here is to hand out each of the 5,362 distinct ply three positions among those of us with an interest, with a program, and with a machine capable of doing a reliable perft(10) in a reasonable time.

[Dann Corbit]

I am very curious about the results for 1. e3

The goodness of an opening seems to have some sort of correlation to how quickly the tree expands (which makes some sense, because it means that you have more choices).

1. e4 and 1. d4 seem to have very large trees, and e3 does also.
It makes me wonder if 1.e3 is a good alternative opening move for white.

[sje]

I am very curious about the results for 1. e3

The goodness of an opening seems to have some sort of correlation to how quickly the tree expands (which makes some sense, because it means that you have more choices).

1. e4 and 1. d4 seem to have very large trees, and e3 does also.
It makes me wonder if 1.e3 is a good alternative opening move for white.

The intermediate results including the file for 1 e3 can be found at

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

Looks like another five days or so if no more power failures; 1 d4 is running on a laptop so it won't be killed by a few minutes of outage.

[sje]

Code: Select all

[] df (h4)
rnbqkbnr/pppppppp/8/8/7P/8/PPPPPPP1/RNBQKBNR b KQkq - 0 1
[] emptran 11
Na6 87,021,512,667,642
Nh6 90,052,762,990,721
Nf6 110,823,970,590,036
Nc6 113,526,623,843,569
a6 74,891,547,461,938
b5 99,848,751,664,463
b6 98,709,976,255,557
a5 105,500,114,211,367
c5 128,256,515,413,957
c6 114,451,887,528,427
d6 189,935,366,110,401
f5 85,002,875,391,032
d5 264,231,322,510,205
f6 64,232,914,757,489
g6 104,715,522,171,468
g5 117,634,502,885,289
h6 73,538,385,526,439
h5 81,300,261,025,135
e5 311,596,726,321,626
e6 305,348,735,315,816
Depth: 11   Count: 2,620,620,274,642,577   Elapsed: 368624  (7.1092e+09 Hz / 1.40663e-10 s)

18 down, 2 to go (d4 e4)

Sum (18/20): 49,264,431,229,789,181

Time used so far: 6,110,143 seconds (~70.72 days)

[sje]

The perft(11) calculations for 1 d4 and 1 e4 are still running after almost 16 machine days of calculation each.

The machine running the 1 d4 job has so far come up with perft(10) sums for the second moves of Na6 Nc6 Nf6 Nh6 a5 a6 b5 b6 c5 c6 d5 d6. The 1 e4 calculation only has the first ten of the above twelve. These perft(10) subtotals are all fairly large; all are in the hundreds of trillions.

For 1 e4 c5, there are over 350 trillion ten ply move pathways.

For 1 d4 d5, the number is over 500 trillion.

[sje]

Code: Select all

[] df (d4)
rnbqkbnr/pppppppp/8/8/3P4/8/PPP1PPPP/RNBQKBNR b KQkq - 0 1
[] emptran 11
Na6 213,972,965,480,983
Nc6 280,881,273,289,707
Nh6 213,864,707,919,474
Nf6 270,131,366,575,432
a6 182,409,922,498,155
a5 260,465,729,486,218
b5 243,529,690,524,887
b6 243,175,561,298,324
c6 258,049,365,173,699
c5 369,151,346,851,332
d6 470,567,584,500,406
d5 511,655,585,575,290
e6 683,528,765,708,597
f5 203,203,898,433,015
f6 157,686,238,242,807
e5 857,863,017,722,896
g6 243,682,493,093,023
g5 206,852,780,540,218
h6 191,025,296,530,368
h5 265,201,480,777,552
Depth: 11   Count: 6,326,899,070,222,383   Elapsed: 1.57862e+06  (4.00786e+09 Hz / 2.4951e-10 s)

Sum nodes (19/20): 55,591,330,300,011,564
Sum seconds (19/20): 7,688,763 (~88.99 days)

Only one more to go (1 e4).

[sje]

About five more days are needed to finish the last perft(11) [e4] and so completing perft(12) for the initial array.

Well, if here are no more power outages, that is.

Perft(10) for 1 e4 d5 is over 847 trillion; the perft(10) for 1 e4 e5 should be even larger, perhaps above one quadrillion.

Perft(11) for 1 e4 has been running for over 19 days of 2 GHz Intel Core Duo 2, 64 bit, two-thread machine time.

[sje]

Code: Select all

[] df (e4)
rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq - 0 1
[] emptran 11
Na6 243,011,720,565,619
Nc6 322,243,431,003,903
Nh6 247,548,509,621,337
Nf6 322,498,545,193,098
a6 220,667,988,887,274
a5 301,048,758,504,883
b5 255,343,453,796,465
b6 271,166,900,252,258
c5 358,293,399,033,196
c6 335,696,875,588,308
d6 504,518,569,529,071
d5 847,544,872,707,824
e5 683,912,587,436,650
f5 256,187,254,981,860
f6 165,087,945,220,409
g5 250,822,856,327,010
g6 296,936,730,716,555
h5 312,553,080,290,766
e6 860,620,575,659,426
h6 207,934,881,374,271
Depth: 11   Count: 7,263,638,936,690,183   Elapsed: 1.98624e+06  (3.65698e+09 Hz / 2.7345e-10 s)

Total nodes: 62,854,969,236,701,747 (This is the Final Answer!)

Total seconds: 9,675,003 (~111.98 days)