Perft(13)

[sje]

I have started the perft(13) calculation using Symbolic's new logging facility that dumps high-value transposition table entries. The first few of these are:

Code: Select all

rnbqkbnr/1ppppppp/8/p7/8/N7/PPPPPPPP/R1BQKBNR b Kkq - 1 3 8 103657570459
rnbqkbnr/1ppppppp/8/p7/8/2N5/PPPPPPPP/R1BQKBNR b Kkq - 1 3 8 129158606374
rnbqkbnr/1ppppppp/8/p7/8/N4N2/PPPPPPPP/1RBQKB1R b Kkq - 1 3 8 120819698454
rnbqkbnr/1ppppppp/8/p7/8/2N2N2/PPPPPPPP/1RBQKB1R b Kkq - 1 3 8 151118522372
rnbqkbnr/1ppppppp/8/p7/8/N6N/PPPPPPPP/1RBQKB1R b Kkq - 1 3 8 96823013418
rnbqkbnr/1ppppppp/8/p7/8/2N4N/PPPPPPPP/1RBQKB1R b Kkq - 1 3 8 121030085662
rnbqkbnr/1ppppppp/8/p7/8/NP6/P1PPPPPP/1RBQKBNR b Kkq - 0 3 8 112810075335
rnbqkbnr/1ppppppp/8/p7/8/P1N5/1PPPPPPP/1RBQKBNR b Kkq - 0 3 8 112740334697
rnbqkbnr/1ppppppp/8/p7/P7/2N5/1PPPPPPP/1RBQKBNR b Kkq - 0 3 8 81861066059
rnbqkbnr/1ppppppp/8/p7/1P6/N7/P1PPPPPP/1RBQKBNR b Kkq - 0 3 8 168197872796
rnbqkbnr/1ppppppp/8/p7/8/1PN5/P1PPPPPP/1RBQKBNR b Kkq - 0 3 8 156761258268
rnbqkbnr/1ppppppp/8/p7/8/N1P5/PP1PPPPP/1RBQKBNR b Kkq - 0 3 8 148750745936

For each record, the first six fields are the position FEN, the seventh field is the draft, and the last field is the perft(draft) of the position.

There will be many thousands of these records. All of the above are perft(8) subtotals; eventually the subtotals for draft counts from nine to twelve will appear. The twenty records for draft twelve and the four hundred records for draft eleven will constitute the proof of work and form the data that can be used by others to challenge or verify the results.

The calculation is currently running on an older 2 GHz Intel Core 2 Duo with a 2^26 entry transposition table. The run could take a couple of years, but more likely I will move the calculation to a faster machine with more threads and more memory.

[sje]

The first draft nine records have appeared:

Code: Select all

rnbqkbnr/1ppppppp/8/p7/8/N7/PPPPPPPP/1RBQKBNR w Kkq - 0 3 9 2736703434862
rnbqkbnr/1ppppppp/8/p7/8/2N5/PPPPPPPP/1RBQKBNR w Kkq - 0 3 9 3471973704722

The first draft ten records should appear in a few hours and the first draft eleven records in a few days.

[Edmund]

May I ask how you are guarding against transposition table collisions?

[sje]

May I ask how you are guarding against transposition table collisions?

Collisions are expected. The concern is with false positive matches. Symbolic handles this problem by using a 120 bit position hash which likely is at least a third longer than it needs to be. The idea is to make the probability of a false positive match be less than the probability of a random hardware error.

[Edmund]

Thank you.

120bit seems reasonable.
With about 10^36 possible hashkeys, about 10^8 transpositiontable entries and about 10^22 total positions, the probabiltity for a false positive is roughly (10^8 * 10^22) / 10^36 = 10^(-6)

[sje]

The first rather shaky time estimate can be made based on the count of records produced in the first three hours. On the current Core 2 Duo machine, perft(13) will take just under two years to complete.

I've been considering buying a new Linux box instead of another Macintosh as I'm not happy with the direction that Apple has been taking with their walled garden approach. I found an inexpensive 3 GHz Athlon II X4 system (64 bit quad core, no L3 cache) that might be a good match. It uses an AMD3 socket which can accommodate a Phenom II chip if needed. With the machine packed with 16 GB RAM, the perft(13) calculation might take only a few months.

[sje]

The first draft ten records have appeared:

Code: Select all

rnbqkbnr/1ppppppp/p7/8/8/N7/PPPPPPPP/1RBQKBNR b Kkq - 1 2 10 55513774849955
rnbqkbnr/1ppppppp/p7/8/8/2N5/PPPPPPPP/1RBQKBNR b Kkq - 1 2 10 72547403776158

The program has generated 940 of the eventual 822,518 distinct draft eight records after about 67,500 seconds elapsed time. So, a first order estimate of total elapsed time is some 684 days with the current machine.

[sje]

After 55 hours of wall time, the perft(13) calculation has generated 2,438 perft(8) subtotals of the 822,518 needed. This gives an estimated total running time for perft(13) of about 777 days (ca. 2 years, 1 month, 14 days) using only the 2 GHz Core 2 Duo box.

So now I'm considering getting a new Linux box that will spend most of it's time on the problem and complete the calculation in six months or so. The likely specs:

3.4 GHz Intel Core i7-2600 (see: http://ark.intel.com/Product.aspx?id=52213)

Intel Desktop Board DX58SO (see: http://www.intel.com/products/desktop/m ... erview.htm)

12 GB DDR3-1333 RAM (3 x 4 GB to use all three memory channels)

A UPS with at least 30 minutes of power time

[sje]

Subtotal results after 81 hours wall time:

0 of 20 perft(12)
0 of 400 perft(11)
9 of 5,362 perft(10)
181 of 72,078 perft(9)
3,434 of 822,518 perft(8)

Estimated total time with current slowpoke machine: 808 days

The first perft(11) subtotals should appear in about ten days.

[sje]

A correction: the Intel Desktop Board DX58SO is not compatible with the Core i7-2600. The compatible boards are listed here:

http://processormatch.intel.com/CompDB/ ... br=i7-2600

It looks like the DP67BG is the one to get. Does it run Linux? I don't know, but I'll bet I could get Linux running on my electric shaver if I beat on it hard enough, so I'm not too concerned.

The DP67BG has a silk screened skull diagram with disk activity LEDs for the eyes. Gosh, what will they think of next?

Also:

The intermediate results of the perft(13) calculation can be had at:

https://public.me.com/chessnotation -> Perft -> Perft13 -> fcr1

This file is updated daily, at least on those days when I remember to do the backup.