perft for 8x8 checkers (depth = 22)

[Rein Halbersma]

Code: Select all

"W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching to nominal depth=22

perft( 1)            7 nodes,   0.00s,   7.00 Mnps 
perft( 2)           49 nodes,   0.00s,  49.00 Mnps 
perft( 3)          302 nodes,   0.00s, 302.00 Mnps 
perft( 4)         1469 nodes,   0.00s, 1469.00 Mnps 
perft( 5)         7361 nodes,   0.00s, 7361.00 Mnps 
perft( 6)        36768 nodes,   0.00s, 36768.00 Mnps 
perft( 7)       179740 nodes,   0.00s, 179740.00 Mnps 
perft( 8)       845931 nodes,   0.01s,  84.58 Mnps 
perft( 9)      3963680 nodes,   0.06s,  66.06 Mnps 
perft(10)     18391564 nodes,   0.18s, 102.17 Mnps 
perft(11)     85242128 nodes,   0.50s, 170.48 Mnps 
perft(12)    388623673 nodes,   1.53s, 254.00 Mnps 
perft(13)   1766623630 nodes,   4.98s, 354.74 Mnps 
perft(14)   7978439499 nodes,  14.68s, 543.49 Mnps 
perft(15)  36263167175 nodes,  45.69s, 793.68 Mnps 
perft(16) 165629569428 nodes, 149.60s, 1107.15 Mnps 
perft(17) 758818810990 nodes, 522.30s, 1452.84 Mnps 
perft(18) 3493881706141 nodes, 1851.01s, 1887.55 Mnps 
perft(19) 16114043592799 nodes, 6465.48s, 2492.32 Mnps 
perft(20) 74545030871553 nodes, 22457.55s, 3319.38 Mnps 
perft(21) 345100524480819 nodes, 77763.22s, 4437.84 Mnps 
perft(22) 1602372721738102 nodes, 273469.14s, 5859.43 Mnps 
End of program.

The above table reproduces Aart's perft(21) count and gives the first result for perft(22).

I've instrumented my perft code with a 1Gb hash table that keeps track of the search depth and the node count. Total hash entry size is 16 bytes so that gives 64M entries. The table is organized into 64 byte buckets of 4 entries each for cache alignment purposes. I use a simple "shallowest of 4" replacement scheme when a bucket is full. I also use the "undercut" refinement of H.G. Muller to replace the primary hash entry of a bucket (if old depth == new depth - 1).

This scheme speeds up the perft count tremendously. At depth = 22, the branching factor is reduced from 4.6 (in terms of nodes) to 3.5 (in terms of seconds). The perft(22) computation took a little over 3 days on my 3.2 GHz P4 (64-bit Linux, Intel C++ compiler).

Because I use hashing, there is always the chance that I had hard collisions (i.e. different positions mapping to the same 64-bit number). Since there are about 2^64=1.6e19 hash keys, the birthday paradox would predict roughly one error in every 2^32=4e9 positions. I haven't counted yet the number of hash stores, but because perft(21) is correctly reproduces, I have some hopes that perft(22) is also correct. However, any confirmation is welcome!

[Rein Halbersma]

Code: Select all

perft( 1)            7 nodes,   0.00s,   7.00 Mnps            1 unique hash nodes 
perft( 2)           49 nodes,   0.00s,  49.00 Mnps            8 unique hash nodes 
perft( 3)          302 nodes,   0.00s, 302.00 Mnps           57 unique hash nodes 
perft( 4)         1469 nodes,   0.00s, 1469.00 Mnps          273 unique hash nodes 
perft( 5)         7361 nodes,   0.00s, 7361.00 Mnps         1078 unique hash nodes 
perft( 6)        36768 nodes,   0.00s, 36768.00 Mnps         3811 unique hash nodes 
perft( 7)       179740 nodes,   0.01s,  17.97 Mnps        12916 unique hash nodes 
perft( 8)       845931 nodes,   0.02s,  42.29 Mnps        41039 unique hash nodes 
perft( 9)      3963680 nodes,   0.05s,  79.27 Mnps       126379 unique hash nodes 
perft(10)     18391564 nodes,   0.18s, 102.17 Mnps       382180 unique hash nodes 
perft(11)     85242128 nodes,   0.53s, 160.83 Mnps      1150373 unique hash nodes 
perft(12)    388623673 nodes,   1.64s, 236.97 Mnps      3416037 unique hash nodes 
perft(13)   1766623630 nodes,   4.83s, 365.76 Mnps     10011350 unique hash nodes 
perft(14)   7978439499 nodes,  15.00s, 531.90 Mnps     28793156 unique hash nodes 
perft(15)  36263167175 nodes,  47.48s, 763.76 Mnps     83867406 unique hash nodes 
perft(16) 165629569428 nodes, 156.43s, 1058.81 Mnps    276404376 unique hash nodes 
perft(17) 758818810990 nodes, 548.81s, 1382.66 Mnps    993281499 unique hash nodes

Above are the results of a modified run with a global hash storage counter turned on. Note that at d=17, the load factor of my 64M entry hash table is roughly 16. My modified perft code looks like this:

Code: Select all

template<typename Rules, typename Board>
uint64_t Perft::perft_hash(Position<Board>& p, size_t depth)
{
        const PerftNode* PT_entry = PT.find(p);
        if (PT_entry && PT_entry->depth() == depth)
                return PT_entry->nodes();

        uint64_t nodes = 0;
        if (depth > 1) {
                Propagate<Rules, Board> moves(p);
                Generate::generate(p, moves);
                for (size_t i = 0; i < moves.size(); ++i) {
                        p.make(moves[i]);
                        nodes += perft_hash<Rules>(p, depth - 1);
                        p.undo(moves[i]);
                }
        } else
                nodes = Generate::count<Rules>(p);

        PT.insert(p, PerftNode(nodes, depth));
        ++PERFT_NODES;
        return nodes;
}

[Rein Halbersma]

Code: Select all

perft( 1)            7 nodes,   0.00s,   7.00 Mnps            1 unique hash nodes 
perft( 2)           49 nodes,   0.00s,  49.00 Mnps            8 unique hash nodes 
perft( 3)          302 nodes,   0.00s, 302.00 Mnps           57 unique hash nodes 
perft( 4)         1469 nodes,   0.00s, 1469.00 Mnps          273 unique hash nodes 
perft( 5)         7361 nodes,   0.00s, 7361.00 Mnps         1078 unique hash nodes 
perft( 6)        36768 nodes,   0.00s, 36768.00 Mnps         3811 unique hash nodes 
perft( 7)       179740 nodes,   0.01s,  17.97 Mnps        12916 unique hash nodes 
perft( 8)       845931 nodes,   0.05s,  16.92 Mnps        41039 unique hash nodes 
perft( 9)      3963680 nodes,   0.11s,  36.03 Mnps       126379 unique hash nodes 
perft(10)     18391564 nodes,   0.33s,  55.73 Mnps       382180 unique hash nodes 
perft(11)     85242128 nodes,   0.94s,  90.68 Mnps      1150373 unique hash nodes 
perft(12)    388623673 nodes,   2.81s, 138.30 Mnps      3416036 unique hash nodes 
perft(13)   1766623630 nodes,   8.48s, 208.33 Mnps     10011324 unique hash nodes 
perft(14)   7978439499 nodes,  25.06s, 318.37 Mnps     28794894 unique hash nodes 
perft(15)  36263167175 nodes,  76.59s, 473.47 Mnps     83836035 unique hash nodes 
perft(16) 165629569428 nodes, 249.95s, 662.65 Mnps    276160294 unique hash nodes 

And just for completeness, here is the comparison with a different hash function. In my own program, I use incremental Zobrist hashing with 3x64 + 1 random 64-bit integers as generators. The run above is with a modified Jenkins hash (that essentially mixes a stream of bits with itself with bitwise xor and arithmetical plus), that is used in Ed Gilbert's Kingsrow. The Jenkins hash is not incremental and in perft runs this is a clear speed disadvantage (it doesn't have to be for alpha-beta searches with hashing turned off in qsearch).

From Ed, I know that his hash function is very well tested for avalanche and clustering properties. I haven't had time to set up such a test harness, but the similarity in the above numbers of stored hash positions indicate to me that both our hash functions have well-behaved clustering behavior. I'll be testing this in more detail later of course!

[AartBik]

However, any confirmation is welcome!

Hi Rein,
That is an impressive result. Congrats!
It will indeed be interesting to verify perft(22) numbers (or higher) and see if collisions occur.
Aart

[AartBik]

However, any confirmation is welcome!

Rein,
I verified your results for depth 22 using a distributed, brute force implementation (no hash table and, hence, no risk of "hard collisions"). The table below shows the perft breakdown per move from the start position for depths 20 to 22.

Code: Select all

move    divide(20)      divide(21)       divide(22)
-------------------------------------------------------
12-16:  11531470109861  52945190026737  243598269855110
11-16:  11736729175821  53527954221225  246743868125768
11-15:   9515983205474  44775005468548  209016678583301
10-15:  10055597639275  46574865098865  215412869777867
10-14:   8600202424158  39822944739732  184865466345796
 9-14:    9698986164172  45530585259776  213736468971938
 9-13:   13406062152792  61923979665936  288999100078322
-------------------------------------------------------
        74545030871553 345100524480819 1602372721738102

[Rein Halbersma]

However, any confirmation is welcome!

Rein,
I verified your results for depth 22 using a distributed, brute force implementation (no hash table and, hence, no risk of "hard collisions"). The table below shows the perft breakdown per move from the start position for depths 20 to 22.

Code: Select all

move    divide(20)      divide(21)       divide(22)
-------------------------------------------------------
12-16:  11531470109861  52945190026737  243598269855110
11-16:  11736729175821  53527954221225  246743868125768
11-15:   9515983205474  44775005468548  209016678583301
10-15:  10055597639275  46574865098865  215412869777867
10-14:   8600202424158  39822944739732  184865466345796
 9-14:    9698986164172  45530585259776  213736468971938
 9-13:   13406062152792  61923979665936  288999100078322
-------------------------------------------------------
        74545030871553 345100524480819 1602372721738102

Hi Aart,

Thanks for confirming this so quickly. No itch to push things to d=23?
I still don't quite understand why there were no collisions. Probably because the total number of hash writes also contains a lot of positions who were evicted from the hash table previously. The number of *unique* hash stores is quite difficult to detect.

Rein

[64_bit_checkers_engine]

Code: Select all

perft(16) 165629569428 nodes, 149.60s, 1107.15 Mnps 
perft(17) 758818810990 nodes, 522.30s, 1452.84 Mnps 
perft(18) 3493881706141 nodes, 1851.01s, 1887.55 Mnps 
perft(19) 16114043592799 nodes, 6465.48s, 2492.32 Mnps 
perft(20) 74545030871553 nodes, 22457.55s, 3319.38 Mnps 
perft(21) 345100524480819 nodes, 77763.22s, 4437.84 Mnps 
perft(22) 1602372721738102 nodes, 273469.14s, 5859.43 Mnps 
End of program.

These numbers seem too fast for a single core machine.

At 5.8 billion nodes/second you would not even need to do an Alpha-Beta search, you could just use perft and search any move!

I just did perft(18) and it took almost 1 full day. I did not use a hash table, but the hash table could not speed things up that much, could it?

I was averageing 55 - 56 million nodes/second.

[Rein Halbersma]

Code: Select all

perft(16) 165629569428 nodes, 149.60s, 1107.15 Mnps 
perft(17) 758818810990 nodes, 522.30s, 1452.84 Mnps 
perft(18) 3493881706141 nodes, 1851.01s, 1887.55 Mnps 
perft(19) 16114043592799 nodes, 6465.48s, 2492.32 Mnps 
perft(20) 74545030871553 nodes, 22457.55s, 3319.38 Mnps 
perft(21) 345100524480819 nodes, 77763.22s, 4437.84 Mnps 
perft(22) 1602372721738102 nodes, 273469.14s, 5859.43 Mnps 
End of program.

These numbers seem too fast for a single core machine.

At 5.8 billion nodes/second you would not even need to do an Alpha-Beta search, you could just use perft and search any move!

I just did perft(18) and it took almost 1 full day. I did not use a hash table, but the hash table could not speed things up that much, could it?

I was averageing 55 - 56 million nodes/second.

The reason these speeds seem too high to be true is because the way perft node counts have traditionally been represented. The original perft routine (see the chess programming wiki) does not use bulk counting and increments the node counter at the leafs (depth == 0). On this forum, we mostly have optimized perft with "bulk counting", i.e. returning the number of valid moves at frontier nodes (depth == 1). However, we still compute the nps as the number of leaf nodes per second. Of course, this give an artificial speedup equal to the branching factor. With hashing, this distortion becomes even bigger since then also interior nodes are not counted as 1 but by the size of their entire subtree! Hence the 5.8 Gnps.

The correct way to represent the nps with bulk counting, is to increment the node counter immediately after each recursion call, and not at the end of it (as I did, see in one of the posts above). Below I give the results up to depth=15 with the modified perft (with the 32-bit MSVC compiler, rather than the original 64-bit Intel compiler, so 30% slower). The column "leafs" is the perft count itself, whereas the column "nodes" is the number of calls to perft(). As you can see, already at depth=15 the speedup is a factor of 275. Effectively, the 2 Mnps becomes a 500 Mnps. Overall, hashing reduces the average depth from 15 to 13.5.

Code: Select all

perft[ 1/ 0.0] =            7 leafs,            1 nodes,   0.00s,   0.00 Mnps
perft[ 2/ 0.9] =           49 leafs,            8 nodes,   0.00s,   0.01 Mnps
perft[ 3/ 1.8] =          302 leafs,           57 nodes,   0.00s,   0.06 Mnps
perft[ 4/ 2.8] =         1469 leafs,          359 nodes,   0.00s,   0.36 Mnps
perft[ 5/ 3.7] =         7361 leafs,         1384 nodes,   0.00s,   1.38 Mnps
perft[ 6/ 4.7] =        36768 leafs,         5175 nodes,   0.00s,   5.17 Mnps
perft[ 7/ 5.6] =       179740 leafs,        17602 nodes,   0.02s,   1.10 Mnps
perft[ 8/ 6.6] =       845931 leafs,        57799 nodes,   0.03s,   1.75 Mnps
perft[ 9/ 7.5] =      3963680 leafs,       176781 nodes,   0.08s,   2.24 Mnps
perft[10/ 8.5] =     18391564 leafs,       546545 nodes,   0.36s,   1.51 Mnps
perft[11/ 9.5] =     85242128 leafs,      1654924 nodes,   0.83s,   2.00 Mnps
perft[12/10.5] =    388623673 leafs,      5058153 nodes,   2.47s,   2.05 Mnps
perft[13/11.5] =   1766623630 leafs,     15061086 nodes,   7.45s,   2.02 Mnps
perft[14/12.5] =   7978439499 leafs,     44745448 nodes,  22.77s,   1.97 Mnps
perft[15/13.5] =  36263167175 leafs,    132020374 nodes,  69.86s,   1.89 Mnps

You can easily test yourself that the above times to depth are reasonable. Here's the code that I use. The depth==1 condition reflect the bulk counting trick (where I also speed things up even more by simply counting the number of bits in the move patterns, rather than actually generating them!), whereas the PT insert/find statements reflect hashing. Note that update_statistics() is called immediately after the call to perft_bulk_hash().

Code: Select all

template<typename Rules, typename Board>
uint64_t Perft::perft_bulk_hash(Position<Board>& p, size_t ply, size_t depth)
{
        update_statistics(ply);

        const PerftNode* PT_entry = PT.find(p);
        if (PT_entry && PT_entry->is_depth_equal_to(depth))
                return PT_entry->leafs();

        uint64_t leafs;
        if (depth == 1)
                leafs = Generate::count<Rules>(p);
        else {
                Propagate<Rules, Board> moves(p);
                Generate::generate(p, moves);
                leafs = 0;
                for (size_t i = 0; i < moves.size(); ++i) {
                        p.make(moves[i]);
                        leafs += perft_bulk_hash<Rules>(p, ply + 1, depth - 1);
                        p.undo(moves[i]);
                }
        }

        PT.insert(p, PerftNode(leafs, depth));
        return leafs;
}

[64_bit_checkers_engine]

Well, I have a 3.9 GHz Intel Core i7-860 x 4 processors with 8 GB of RAM.

If I run your program with a much larger hash, say 2 GB or 4GB, I should get an even bigger performance increase (more hash entries) so it should even be faster, correct?

Email it to me and I will run it. I would be curious to see if my faster machine can reach perft(23) in a reasonable amount of time

My machine is here:



...and on Amazon.com too

http://liquid-nitrogen-overclocking.hos ... =salesrank

My email is

Liquid Nitrogen Overclocking @ Hushmail . com

(no spaces of course)

Thanks!