Author: Paul Byrne
Date: 19:07:26 01/12/04
Last month's perft activity reminded me of some related code I started on ages ago and never finished, so over xmas and new years I completed it and decided to try to confirm the perft 11 result. The program just completed, after a little over 11 days, obtaining perft 11 of 2,097,651,003,692,820 Unfortunately, this is not the same result as the distributed perft project got: 2,097,651,003,696,806 Which is not to say the distributed perft is wrong of course. It is quite possible I have a silly bug, or hardware problems (the CPU is a recent upgrade). In any case, here are some details on how my program works, in order to do the perft 11 in just 11 days on an athlon 2400+ computer. I gather the distributed project worked by taking the 5362 unique positions that can be reached in 3 ply, computing the perft 8 for each, and adding them up, weighted by the number of times each position occurs, of course. My code simply takes the 988,187,354 unique positions at 8 ply and computes perft 3 for each.... No hashing is done for the perft 3's -- they are not deep enough for transpositions within each perft, and the number of hits between them was quite low, so I scrapped the hash tables altogether. Incidentally, I used the same set of positions to compute perft 10 -- using a bunch of perft 2's of course -- and obtained the exact same value given on http://www.albert.nu/default.asp?sub=programs/default.asp?sub=dperft/main.htm Which would seem to imply the unique position generator is likely correct. This result took under 10 hours. The hard work, of course, is in obtaining the list of unique positions at 8 ply. A chess position can be compacted to 24 bytes reasonably quickly; I used a 32 bit value to keep track of the weighting of each position; throw in a 32 bit pointer and you are up to 32 bytes per position... so my 512 MB can reasonably hold about 13 to 14 million positions. Going over and hitting the disk drive is about as ugly as you'd expect. The positions were partitioned into multiple sets, each of which about 13 million. In the case of uniq 8, this amounted to 75 sets. An easy way to do this is to compute (hash_key mod 75)... which gets you 75 sets very close in size. It is also quite slow, since the program in effect looks at the 8 ply positions 75 times, each time selecting only those positions in the current set. It took 12 hours to compute uniq 8 this way (starting with uniq 7 of course -- no need to make extra work). The resulting files are almost 9 GB, btw. Here are my results on the number of unique positions (note the en passant file was only set if there is a *legal* en passant capture on the next ply): 1 20 2 400 3 5,362 4 72,078 5 822,518 6 9,417,681 7 96,400,068 8 988,187,354 In any case, I will refrain from heaping on even more meaningless numbers, and will look over my code a bit and see if I can spot any obvious errors to account for the different perft 11 result... -paul Pop Quiz for the bored: :) + What is the shortest line which results in a position with an illegal en passant capture? That is, a position with a pawn that is in place to do the capture, but cannot due to a revealed check or something. + The highest weight in uniq 5 is 87. That is, there is at least one position that can be reached in 87 different ways in 5 moves. Find such a position.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.