Author: Eiko Bleicher
Date: 23:21:58 01/12/04
Go up one level in this thread
On January 12, 2004 at 22:07:26, Paul Byrne wrote: >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.