Perft(14) verification

[sje]

Perft(14) verification

For all perft() calculations for draft values from ten to thirteen, Symbolic produced two tables: a table of the 20 ply one subtree totals and a table of the 400 ply two subtree totals. These are nice statistics to have, and they also provide a proof of the grand total. Also, individual entries can be challenged more easily than would be a recalculation of the entire tree.

The perft(14) calculation is being done differently; instead of brute force of either the ply one or the ply two subtrees, the 96,400,068 (= unique(7)) ply seven subtrees are calculated. From these, the 20 ply one and 400 ply two subtotals can be computed as follows:

1) First of all, finish and hopefully verify the 96,400,068 perft(7) sums.

2) Load the entire 96,400,068 set into memory as a hash keyed binary tree. (Needs just under 4 GiB.)

3) Using the tree, calculate the perft(8) subtree counts for unique(6) (= 9,417,681 entries)

4) Using the result, build another in-memory tree and calculate the perft(9) subtree counts for unique(5) (= 822,518 entries)

5) Using the result, build another in-memory tree and calculate the perft(10) subtree counts for unique(4) (= 72,078 entries)

6) Using the result, build another in-memory tree and calculate the perft(11) subtree counts for unique(3) (= 5,362 entries)

7) Using the result, build another in-memory tree and calculate the perft(12) subtree counts for unique(2) (= 400 entries)

8) Using the result, build another in-memory tree and calculate the perft(13) subtree counts for unique(1) (= 20 entries)

The outputs from steps 7 and 8 are the two tables we want. All of the values should fit into a 64 bit unsigned integer.

[sje]

Additional, incidental verification

Note that each calculation step also provides some more verification.

First, if a probe of the tree doesn't come up with a match, then there's a big problem that's been detected.

Second, if not every entry in the tree is probed at least once, then there's a big problem that's been detected.

Third, if the grand totals of the sums of products don't match from step to step, then there's a big problem that's been detected.

[sje]

Independent verification is the most desirable kind. Every work unit result needs to be verified, although this may take some time.

At present, there are four work units with independently verified results: 000 036 042 964.

Arkan has also produced results for 033 038 and 041. Symbolic should finish 033 and 038 in a week or so; 041 is running on an old and slow machine, so it may not be finished for another month or two.

Oscar, running in testing mode, has also provided verification of 964.

The 300,000+ different chess position calculations verified so far are less than a third of one percent of the total position count. However, taken together, they provide a variety which is large when compared to the complexity of move generation, execution, and retraction. So I'm strongly convinced of the soundness of the algorithms in use. My only major concern is hardware failure in the context of undetected CPU/memory errors.

[sje]

Work unit result 033 verified

At long last, the old and slow notebook running Symbolic's calculation of 033 has completed the work unit. The signature:

Code: Select all

MD5 (wu7.033.sum) = d5a2f1148ef4959bf82fc214e9ebe55a

Which matches Arkan's result:

Code: Select all

d5a2f1148ef4959bf82fc214e9ebe55a wu7.033.op