Perft(13) [3.4 GHz Core i7-2600, 16 GB RAM]

[sje]

Of the 400 initial 2 ply sequences, 1 a3 a6 is the one with the smallest perft counts.

A large transposition table is essential for a table-only implementation. Also, using only 64 bits for a signature is too risky for the number of positions encountered, even if that number is based on separate runs that partition the entire calculation.

See http://oeis.org/A083276 for clues about transposition table sizes. It takes about 10^7 entries to hold all the unique positions from 1 through 6 ply and about ten times as many as that to include the ply 7 positions.

Putting a huge transposition table on a disk has its own problems like burning out the disk with gazillions of non-local accesses over many weeks or months of calculations.



After 10 days:

0 draft 12
8 draft 11
191 draft 10
3539 draft 9
47970 draft 8

Estimated completion: January 2012

[rbarreira]

Putting a huge transposition table on a disk has its own problems like burning out the disk with gazillions of non-local accesses over many weeks or months of calculations.

It might be worth it though, if the decreased disk life is countered by sufficiently big electricity savings.

[hgm]

Also, using only 64 bits for a signature is too risky for the number of positions encountered, even if that number is based on separate runs that partition the entire calculation.

Well, perft(13) has some 2e18 nodes, but the number of internal nodes is only 6.6e16. And as probing frontier nodes in the TT is most likely not competative, only 2.5e15 nodes could do probing. The number of 64-bit keys is 16e18, which already does seem comfortably large compared to that. But in practice you don't probe the TT in every node, as TT hits in earlier levels prune entire sub-trees, whose nodes you then never visit. That you start from the unique perft(4) positions already cuts away 2/3 of the tree for starters.

But note that even my packed 5-entry/cache line proposal had a4-bits key-extension field, so that the signature was in fact 68 bits.

But one could go further by differentiation of the TT entry format by depth: Most probes will be for d=3 or d=4 sub-trees, for which the counts comfortably fit into a 24-bit field. So you could borrow an extra key-extension byte to reduce the collision probability by another factor of 256 for those probes, and by a similar factor for the others (because there are now 256 times less of those). To get the utmost there, you could make it a sliding scale: take 12 bytes per entry (96 bits), and reserve 6 bits per remaining ply for the count, and use the rest for key. Perhaps you could even take 6 entries per cache line in that case (10.5 byte per entry, plus 1 byte LRU info).

[sje]

After 12.5 days:

0 draft 12
8 draft 11
214 draft 10
4030 draft 9
56427 draft 8

That's about seven percent of the total draft 8 counts, so the run should complete in early January 2012. However, most of the "hard" enumerations are still to come; these are the subtrees where both sides have started with a center pawn advance.

I'm guessing that the first draft 12 results will appear sometime in October.

With an estimate of 4,500 hours of running time and a power draw of 150 watts, a total of 2.5 GJ (gigajoules) of energy will be used. This will cost me about US$120 extra on the electricity bill. But it will also help heat my modest home; the oil bill for running the furnace should drop slightly.

[sje]

A passing thunderstorm knocked out power for a while; about 900,000 draft 7 records stored in the transposition table were lost. But 80,000 draft 8 and deeper records were saved on a file and these were used to restart the calculation.

[sje]

Forty hours since the power failure and the run has since produced close to 6,700 new draft 8 records.

Later this week I'll investigate buying a UPS to guard against future power outages. The idea is to get an inexpensive UPS with a USB control connection to the computer so that the box can suspend to disk automatically if needed.

[sje]

The 16th draft 11 record and the largest subtotal so far has just been produced:
[d]rnbqkbnr/1ppppppp/8/p7/1P6/8/P1PPPPPP/RNBQKBNR w KQkq - 0 2[/d]
Perft(11) for the above: 3,850,353,951,070,799

I'm still looking towards a completion in January 2012.

The rule of thumb has been that the run time increases proportionally to the ratio of the unique position counts from ply to ply -- if the transposition table can hold nearly all of the unique positions at the appropriate ply. Perft(12) on the same hardware took 14.5 days, so a growth factor of about 12 brings the conclusion in January 2012 just as does the rough extrapolation from the ongoing count of draft 8 records.

[Vinvin]

Forty hours since the power failure and the run has since produced close to 6,700 new draft 8 records.

How many hours of work has been lost ?

[sje]

Forty hours since the power failure and the run has since produced close to 6,700 new draft 8 records.

How many hours of work has been lost ?

All of the 80,000+ transposition store records of draft 8 or deeper were preserved. But all the draft 7 and shallower records were memory resident only and relocated to the Big Bit Bucket in the sky. Given the relatively early stage of the run, probably only a few days of effort were lost.

The most recent ten records:

Code: Select all

rnbqkbnr/p1p1pppp/1p1p4/8/P1P5/5P2/1P1PP1PP/RNBQKBNR b KQkq - 0 3 8 231287051019
rnbqkbnr/p2ppppp/1p6/2p5/1PP5/8/PB1PPPPP/RN1QKBNR b KQkq - 0 3 8 284039825628
rnbqkbnr/p1p1pppp/1p1p4/8/8/1P1P4/P1PKPPPP/RNBQ1BNR b kq - 1 3 8 278449074288
rnbqkbnr/p1p1pppp/1p1p4/8/P1P2P2/8/1P1PP1PP/RNBQKBNR b KQkq - 0 3 8 280932593248
rnbqkbnr/p1p1pppp/1p6/3p4/3P4/N7/PPPBPPPP/R2QKBNR b KQkq - 1 3 8 566172980479
rnbqkbnr/p2ppppp/1pp5/8/2P5/1Q3N2/PP1PPPPP/RNB1KB1R b KQkq - 1 3 8 308321304995
rnbqkbnr/p1p1pppp/1p1p4/8/8/P2PP3/1PP2PPP/RNBQKBNR b KQkq - 0 3 8 453768719855
rnbqkbnr/p1p1pppp/1p1p4/8/P1P5/6P1/1P1PPP1P/RNBQKBNR b KQkq - 0 3 8 322899718639
rnbqkbnr/p1p1pppp/1p1p4/6B1/3P4/2N5/PPP1PPPP/R2QKBNR b KQkq - 1 3 8 854575930820
rnbqkbnr/p2ppppp/1p6/2p5/1P6/3P4/PBP1PPPP/RN1QKBNR b KQkq - 0 3 8 327423164471

[sje]

And after another power failure, all the draft 7 and lower results generated over the past five days since the last outage were lost. But 107,000+ draft 8 and higher records were saved and the calculation has been restarted.

The most recent records:

Code: Select all

r1bqkbnr/p1pppppp/np6/8/1P6/6P1/P1PPPP1P/RNBQKBNR b KQkq - 0 3 8 120777247481
rnbqkbnr/p1pppppp/8/1p6/8/5PPN/PPPPP2P/RNBQKB1R b KQkq - 0 3 8 109517084445
rn1qkbnr/pbpppppp/1p6/8/8/5P2/PPPPP1PP/RNBQKBNR b KQkq - 2 3 8 130592707466
r1bqkbnr/p1pppppp/np6/8/6P1/1P6/P1PPPP1P/RNBQKBNR b KQkq - 0 3 8 112700020220
r1bqkbnr/p1pppppp/np6/8/8/1P4P1/P1PPPP1P/RNBQKBNR w KQkq - 1 3 9 3585347231199
rnbqkbnr/p2ppppp/1pp5/8/P3P3/7P/1PPP1PP1/RNBQKBNR b KQkq - 0 3 8 285098978110
rnbqkbnr/p1pppp1p/1p4p1/8/4P3/2N5/PPPPQPPP/R1B1KBNR b KQkq - 1 3 8 476531608924
rnbqkbnr/p1pppp1p/1p4p1/3P4/1P6/8/P1P1PPPP/RNBQKBNR b KQkq - 0 3 8 307350610111
rnbqkbnr/p1pppp1p/1p4p1/8/1P1P4/8/P1P1PPPP/RNBQKBNR w KQkq - 0 3 9 9702392771072
rnbqkbnr/p1pppppp/8/1p6/6P1/5P1N/PPPPP2P/RNBQKB1R b KQkq - 0 3 8 106666465934

With hurricane weather moving through over the weekend, I wouldn't be surprised if the power went out for at least a day.

I'm going to have to get a UPS, preferably one that can talk to Linux nicely to request a low-power hibernation with an automatic restart.