Perft(12) count confirmed

[murraycash]

Below my new results for perft(24) for 8x8 checkers from the initial position, broken down per move.

Aart, that's very good, I am going to buy a more modern PC then I'll try perft(24) and (25) maybe, let's compare results then.

[ibid]

After nearly 112 machine days of calculation, I have produced the value of perft(12). It is: 62,854,969,236,701,747

This number confirms the value given by Paul Byrne back in 2006 and it is the first such public verification. Because there is no commonality of code between the two calculations there can be no doubt of the validity of the grand total and so of the verification.

Sorry to resurrect the thread... I haven't been here in years. I recently finished a from-scratch bitboard engine and was contemplating breaking it in with a perft 13 computation. I thought I'd check here first and see what others have done.

I am very glad you got the same number I did, avoiding the need for a tiebreaker. :) There was no risk of hash collisions in my computation as I was saving entire positions, but I did have some concerns as multiple machines were used, increasing the chance for hardware issues.

The page at http://oeis.org/A048987 needs to be updated. As Paul got to the number before I did, he should have the honor of doing the update. If the page isn't updated in a month or so, I'll do it and list Paul's name (and maybe my own as the verifier).

Thank you for adding the result there. I must have forgotten back then.

My current estimate for perft 13 is about 6 months on my 6-core phenom, but I could easily be off by a factor of 2 or more here as I haven't actually connected the new engine and perft code yet -- I am basing this on dim memories of perft 12 and guesswork.

Anyhow, should the computation get off the ground, I will update...

-paul

[sje]

On my five year old 2.66 GHz dual Xeon Woodcrest box (4 cores total) with a 12 GB transposition table (2^30 entries split evenly between WTM/BTM), my program Symbolic can do perft(8) in 54 seconds, perft(9) in 444 seconds, and perft(10) in 5,252 seconds. These calculations have been done with some new spinlock code that allows all of the enumeration threads to share the same transposition table. Note that Symbolic is not optimized for perft calculations; instead, the perft code is used to verify the generate/execute/retract logic of the rest of the program.

The transposition entry replacement is done with an eight-way set associative access with the lowest subtotal entry being overwritten. (A vacant entry has a zero subtotal.) It may be that a four-way or a sixteen-way grouping might be better for some long perfts; it takes a lot of time to test this.

Having given this some more thought, I believe that it is necessary that any long perfts should have the first two or three levels of subtotals reported so that others may more easily verify or challenge the calculations.

Because of the unreliability of the local power company, I'd have to buy an emergency electricity generator to handle the sometimes lengthy outages. (I may get one of these anyway, but it's still a hassle.) An alternative is to implement a checkpoint/restart capability and I think I've got a quick and simple scheme that doesn't involve a periodic dump of a transposition table. My idea is to have the program log every subtotal for the top N ply (say, N=4) by writing out the position FEN, draft, and subtotal to a log file. (This log file itself is backed up daily.) Every time that the program needs to be restarted due to a power failure or some other problem, the program first digests the log file and initializes an empty transposition table using the FEN/subtotal records. This works well as so much of the real effort is recorded in only a few thousand different table entries. The same log file can be posted publicly so that others may share in the verification task.

[ibid]

My approach is quite different. While the core functions (movegen, makemove, etc) are not particularly optimized for perft (in fact they are written for losers chess, not regular chess), and the chess engine does contain a basic perft routine for the usual purposes, the deeper perfts were computed with a specialized program.

First I get a list of all unique positions to a given depth -- in the case of the perft 12 computation I used the 988187354 unique positions at 8 ply. http://oeis.org/A083276 for this -- I remembered to update this one. :) And obviously counts of how many times each position occurs. In effect this provides perfect detection of transpositions through that depth.

And then second, simply compute a shallow perft for each of the positions -- in the case of the perft 12 computation that was a whole bunch of perft 4's. I experimented with hash tables for this, but the searches are shallow and there were not many hits between seperate perft 4's -- it was faster just to do very simple perft computations. Clearly a power failure is not a major problem here (although it potentially can negate a significant amount of work during the original uniq computation!)

These days, computing uniq 10 is well within reach, and I would use that instead for perft 13. Ninety billion perft 3's is better than a billion perft 5's by a factor of ten or so.

EDIT: Oops, forgot to mention it, but this approach does make it very difficult to get divided perfts for each initial move or anything like that; I will think on this some, since it really would be useful for verification purposes.

[sje]

Symbolic uses a one-ply bulk count routine when in perft transposition table mode. These one-ply counts are not stored in the transposition table, but all counts of draft two or greater are stored. This arrangement could possibly be adjusted for better efficiency, but I haven't put much too much effort into this as the perft code's purpose is not speed but rather to test the rest of the program.

As I'd written before, I thought of using a scheme similar to yours to partition the work among different users and machines. I wrote a Lisp program to crank out the first few distinct FEN position files:

Code: Select all

$ wc *
       1       7      59 emp0.txt
      20     140    1214 emp1.txt
     400    2800   24960 emp2.txt
    5362   37534  340266 emp3.txt
   72078  504546 4648185 emp4.txt
  822518 5757626 53648090 emp5.txt

with each record having a seventh field that gave the frequency of occurrence. But as you say, this approach (without extra calculation) doesn't give the upper ply subtotals for verification. Also, I suspect some efficiency loss in any approach that doesn't use nearly all of the resources available, like using many GB of RAM for a transposition table.

There is likely some N-dimensional saddlepoint that gives the optimal configuration for a perft(n) computation, but to locate this optimal point might take more time than any of the possible individual computations.

Some kind of verification is needed as the probability of hardware error for lengthy calculations is just too high. Somewhere, possibly from SETI@home, I read that a typical consumer level machine will produce a CPU/memory error about once every hundred days. (Overclocking makes the rate much worse as you would guess.) And so enterprise class machines all use error correcting RAM in spite of its extra cost. But even then, a stray cosmic ray can mischievously flip a CPU register bit on occasion.

[sje]

An alternative is to implement a checkpoint/restart capability and I think I've got a quick and simple scheme that doesn't involve a periodic dump of a transposition table. My idea is to have the program log every subtotal for the top N ply (say, N=4) by writing out the position FEN, draft, and subtotal to a log file. (This log file itself is backed up daily.) Every time that the program needs to be restarted due to a power failure or some other problem, the program first digests the log file and initializes an empty transposition table using the FEN/subtotal records. This works well as so much of the real effort is recorded in only a few thousand different table entries. The same log file can be posted publicly so that others may share in the verification task.

I have since implemented this idea and it appears to work well.

When the program is running a transposition perft calculation, every store into the transposition table looks like this:

Code: Select all

        pbptr->Stash(pos, depth, pathcount);
        if (depth >= 7) pbptr->WriteFCR(pos, depth, pathcount);

The WriteFCR() routine outputs a one line record with the position FEN followed by the depth and path count to a file named "fcr1". A record looks like this:

Code: Select all

rnbqkbnr/ppp1pppp/3p4/8/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 2 7 18246438582

Note that the file output is done only for records with a sufficiently large draft to keep the file size manageable.

After the inevitable power failure occurs, when the lights come back on the file "fcr1'" is manually renamed to "fcr0" and the calculation is restarted. The records are read and loaded into a freshly initialized transposition table and the whole calculation restarts. Nearly all the useful work is retained from the prior run and with much less effort than a full dump/restore of the entire transposition table.

Multiple restarts are supported by a manual concatenation of all the checkpoint files produced. Note that a calculation can use the prior records even if the transposition table size is changed or the restart is on a different machine.

With a draft lower bound of eight ply, a record is produced every minute or so for about a thousand records per day. I'll probably use this setting if I try perft(13).