Author: Uri Blass
Date: 13:24:42 06/20/01
Go up one level in this thread
On June 20, 2001 at 16:00:53, Peter McKenzie wrote: >On June 20, 2001 at 12:51:58, Uri Blass wrote: > >>On June 20, 2001 at 10:20:07, Robert Hyatt wrote: >> >>>On June 20, 2001 at 07:35:24, Uri Blass wrote: >>> >>>>Crafty needs only 2.2 seconds to calculate perft 5(the number of legal games >>>>with 5 moves) and only 54.76 seconds to calculate perft 6(119,060,324 nodes) >>>> >>>>It is clear that Crafty does not use hash tables to calculate perft faster. >>>> >>>>Is there another program (with free or without free source code) that can >>>>calculate perft (without hash) faster than Crafty? >>>> >>>>Uri >>> >>> >>>You can't use hash tables to do this. Otherwise the node count would not be >>>exact when the hash table cuts off part of the tree. >> >>It is possible to use arrays to calculate things faster(maybe these arrays are >>not called hash tables but bigger arrays can help so bigger memory can help) >> >>I will give an example >> >>Suppose you calculate perft(5) >> >>It is the sum of perft(2) of all the positions after 3 plies. >> >>You found after 1.d4 d6 2.e4 that perft(2)=1023 >> >>When you search later 1.e4 d6 2.d4 you can use the array that tells you that >>perft(2) of this position was searched and is 1023 so you do not need to >>generate the same moves again and you can add 1023 to perft(5). >> >>You only need a function to translate positions to numbers and if you have >>bigger arrays you can translate positions to bigger numbers so the probability >>that 2 positions will get the same number is smaller. >> >>In this case a possible problem if the array is small is that it is possible >>that 1.e4 d6 2.d4 and 1.a4 a6 a5 are translated to the same number so you find >>that the hash signature of 1.e4 d6 2.d4 was searched but this number in the >>array is translated to 1.a4 a6 2.a5 so you find that you cannot use it because >>the positions are different. >> >>Uri > > >I think Steven Edwards used some sort of hashing scheme when he computed the >node count for the full 10ply tree from the root. > >Oh, btw, LambChop can count the 6ply tree from the root in 20sec on PIII >1000mhz. It is faster than crafty because it counts moves at depth 5 not >positions at depth 6 and hence effectively it has to search one ply less in the >tree. It can do this because I have implemented a fully legal static move >generator that does not need makemove to exclude illegal moves. My program also does it(it does not do it correctly for en passant moves and it only checks if they are pseudo legal moves and it also does not generate en passant moves in reply to check) My perft 6 in the initial position is still not correct and I will have to check for new bugs(I believe that the en passant is not the reason). Uri
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.