Verification of perft(14)

[sje]

Back on 2013.04.02, Peter Österlund reported his calculation of perft(14) had the result of 61,885,021,521,585,529,237. This result, like earlier perft() results, needs independent verification.

My idea is to perform a verification via distributed computing using manual assignment of work units. Each work unit would consist of one million ply 7 positions taken form the list of 96,400,068 unique ply 7 positions. Each work unit would be sent to at least two different participants for confirmation calculation.

Each input work unit would be a text file with one million lines. Each line has seven fields: the FEN record followed by the occurrence count. The output work unit would be the same with an addition of the perft(7) of each FEN position appended to the corresponding input record multiplied by the occurrence count (This eighth field in called the product field.)

Each work unit would require computer time from a few days to a a couple of months with a variance depending on several factors. For every second needed to handle one record, the total work time increases by 11 days, 13 hours, 46 minutes, and 40 seconds (one million seconds.).

Participants would use Dropbox, at at least my Dropbox, for work unit interchange unless everyone would be happy with 65+ MB email attachments.

There would be 94 input work units of one million lines each (ca. 65 MB) and a 95th unit at ca. 26 MB in size. An output work unit might be about 80 MB in size.

The perft(14) result would be the grand total of the product fields of all the output work units.

Work unit data is sorted by ACSII ascending order. The very first record of the first work unit is:

Code: Select all

1Bbqkb1r/1p1ppppp/r4n2/p7/3P4/8/PPP1PPPP/RN1QKBNR b KQk - 0 4 3

The last of the last is:

Code: Select all

rnqQkbnr/ppp1pppp/8/8/8/4P2b/PPPP1PPP/RNB1KBNR b KQkq - 2 4 2

[sje]

I have created all of the 97 input work units. They are named "wuaa", "wuab", etc. The very first of these is available for inspection and testing to anyone considering participating in the project.

See: https://dl.dropboxusercontent.com/u/31633927/p14wu/wuaa

It's 65,614,953 bytes long.

[sje]

The last work unit is also on Dropbox. It has only 400,068 records and is 26,545,608 bytes in length.

https://dl.dropboxusercontent.com/u/31633927/p14wu/wuds

[Ajedrecista]

Hello Steven:

It is a great idea, but I have some doubts:

My idea is to perform a verification via distributed computing using manual assignment of work units.

(Bold added in the quote). Each FEN string must be copied and pasted into a perft counter of our taste (JetChess, gperft, etc.) and the result must be copied and pasted into the original text file? I must misunderstand something because millions of 'copy and paste' are not practical and they are also font of many human errors. I guess that there is some sort of automatization: could you explain it a little more, please?

More doubts:

a) The perft calculations can be stopped and therefore resumed? It would be a good feature.

b) Those calculations can be performed in different computers, specially if the feature of 'stop and resume' is available?

c) Which perft counter will be used?

d) People with 32-bit OS can participate or is this project restricted to 64-bit OS users?

Thanks in advance. Good luck with the project!

Regards from Spain.

Ajedrecista.

[sje]

A work unit is 1,000,000 positions. There are only 97 of these. I will manually send them out and manually receive the results.

The programs which run the work units should do them in batch mode. A program would be given:

1. Name of input work unit file
2. Name of output work unit file
3, Depth (always 7 in this case)

When running, the program checks to see if the output work unit file exists. If the file doesn't, then it is created with zero length.

The program opens the output work unit file and counts the records The file is then closed.

The program then opens the input work unit file, and then reads and skips the first N records where N is the record count of the output file.

The main cycle begins: a record is read form the input, the perft() is calculated, and then the revised record with the product field is appended to the output file. This continues until either EOF or power failure. Note that the output buffer should be flushed at the end of each line.

As long as the last line of the output file is never corrupted, this approach works across interruptions.

The output work unit file is then sent to me.

----

Symbolic will handle all the calculation for a work unit in precisely this way and so requires little human intervention.

An input work unit can be split (see Unix split command), the parts handled by different machines, and then merged (retaining order) before being sent to me.

Any reliable perft() program can be used. If it can't handle the above scheme, then it could be modified or wrapped accordingly. A program which does only one position at a time using command line parameters can be employed by making a supervisory program which would handle the file I/O and call the perft() program directly, once per input record.

----

I should have Symbolic running in work unit mode within a couple of days. It will have two new commands The first is:

Code: Select all

sdp <input-wu-flename> <output-wu-filename> <depth>

"sdp" = "super duper perf-u-lator"

The second is:

Code: Select all

bas <all-output-wu-files-concatenated-filename>

"bas" = ""big-ass sum-o-matic"

The second provides the final result. It needs extended precision arithmetic.

[sje]

I have finished the first version of the external FEN path counter. On the first test, it correctly calculated perft(8) (84,998,978,956) by reading the unique(4) position file (72,078) records, bulk calculating the perft(4) for each, and wrote the output file correctly.

The code is now chomping on the unique(7) file and its 96+ million FEN records, calculating perft(4) for each one. The run will take about 36 hours. The result should match the known value of perft(11) (2,097,651,003,696,806).

Much tuning can be done; the current code uses only a single thread and doesn't use a transposition table.

[sje]

It looks like the program is handling only about 81 positions per second doing a bulk perft(4) on each record. This means nearly 14 days to compute perft(11) using the unique(7) file. The program needs to use a multithreaded perft with transposition assistance and this will need some work.

[sje]

Now running unique(3) with a single threaded perft(7) using a transposition table. The program is doing only about 150 records per hour, so a move to multithreading is much needed. At one record per 24 seconds, it would take about 73 years to calculate perft(14) with the current configuration.

[sje]

I connected the multithreaded path counter to the FEN file scanner and moved the program to my 3.4 GHz Core i7 quad core machine. I had it calculate unique(3) * perft(7) and it processed the 5,362 input records in 75 minutes to produce the correct value for perft(10) (69,352,859,712,417). That's about 1.2 perft(7) calculations per second and it's not going to get much faster without having to take away general position handling code in Symbolic.

Extrapolating rather loosely from the above, it would take about two years and seven months to do perft(14) = unique(7) * perft(7). But it would take only about ten days to handle one of the 97 work units. For someone with a fast, perft-only type program, the required time could be much less.

I'm now going to try work unit zero, also known as wuaa (https://dl.dropboxusercontent.com/u/31633927/p14wu/wuaa). If you have a faster perft() than I, please give it a try.

[sje]

The run on work unit "wuaa" (first of 97) has started. Here are the first ten (first of one million) output records:

Code: Select all

1Bbqkb1r/1p1ppppp/r4n2/p7/3P4/8/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 16509053896
1Bbqkb1r/1p1ppppp/r4n2/p7/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 14802098450
1Bbqkb1r/1p1ppppp/r6n/p7/3P4/8/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 15284820096
1Bbqkb1r/1p1ppppp/r6n/p7/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 13571723219
1Bbqkb1r/1ppppppp/2n2n2/8/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 6494639288
1Bbqkb1r/1ppppppp/2n4n/8/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 5169856607
1Bbqkb1r/1ppppppp/5n2/p7/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 1 4481847253
1Bbqkb1r/1ppppppp/7n/p7/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 1 3548443080
1Bbqkb1r/1ppppppp/n4n2/8/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 6156660907
1Bbqkb1r/1ppppppp/n6n/8/8/3P4/PPP1PPPP/RN1QKBNR b KQk - 0 4 3 4915489341

A slight change: the last (eighth) field is the perft(7) of the position, not the perft(7) times the occurrence count (field seven). The multiplication must be preformed prior to the final summation.

Just think: Only 96,400,068 unique(7) records total.

Chinese proverb: "The longest journey begins with a single step."