Author: Robert Hyatt
Date: 13:24:37 08/09/01
Go up one level in this thread
On August 09, 2001 at 12:03:25, Miguel A. Ballicora wrote:
>On August 09, 2001 at 10:39:00, Robert Hyatt wrote:
>
>>On August 09, 2001 at 09:31:02, Alvaro Jose Povoa Cardoso wrote:
>>
>>>Since you are undertaking the Gerbil educational project, I would like to ask
>>>you if you could implement Enhanced Transposition Cuttofs (ETC) in Gerbil with a
>>>switch so that it can be turned on/off.
>>>I know ETC doesn't give much in chess but I would like to experiment in
>>>checkers.
>>>My inplementation is working but it is not elegant at all.
>>>Since we are dealing with the other player I avoided some complications
>>>by creating a special version of Hashprobe() wich returns a score and by use of
>>>an additonal flag informs me if there was a cutoff at the next ply.
>>>So, and using 'crafty language' I do the following:
>>>
>>>for every move at this ply:
>>>
>>>Makemove
>>>
>>>Score =
>>>-ETC_HashProbe(tree,ply+1,depth-INCPLY,ChangeSide(wtm),-beta,-alpha,&cutoff)
>>>
>>>Unmakemove
>>>
>>>if (cutoff) {
>>> if (Score >= beta) {
>>> return (Score);
>>> }
>>>}
>>>
>>>
>>>Best regards,
>>>Alvaro Cardoso
>>
>>
>>
>>That is not the right way to do it. I did it like that for testing, but it was
>>actually a loss for me, because MakeMove() does a lot of work in Crafty. I
>>first wanted to see if the tree would shrink by any significant amount. If it
>>did, I would then write a special hash probe function that would only do the
>>hash signature update extracted from MakeMove() which would be much more
>>efficient. However, I found no appreciable tree size reduction and therefore
>>gave up without going that far.
>
>This is not directly related to ETC but has to do with the last paragraph.
>I am considering to do in my program something that I would call a
>"lazy_makemove()". It just sticks the move in a variable in the position struct,
>and updates the hashtable. Nothing else. Then, the program goes to search, at
>that point it checks if the hashsignature is in the hashtable. If it is, and it
>can return, it saves all the expensive calculations in makemove.
>If it cannot return, it calls to "finish_makemove()" where the makemove is
>completed using as information the move that is stored in the position.
>I won't much because it depends on the % of hitting the hashtables with perfect
>information to return. It could be 10%, which could be as much as 10% of the
>time that makemove takes. If makemove is expensive, it could translate to 3-4%
>of the program execution.
>Has anybody ever done something like this? I am doing already a lazy_unmakemove
>that saved me quite a bit of time since I am doing some incremental updating of
>the attack bitboards. I am still doing very slow...
>
>Regards,
>Miguel
>
>
It will make the code less readable and less understandable, but you could
take this to the ultimate level. Remove the hash probe code at the top of
Search(). When you are ready to make a move, just update the hash signature,
do a probe for the other side, and if you can avoid searching this move due
to the hash hit, do so. Otherwise finish the MakeMove() stuff and call
Search() recursively. This is even more efficient than your idea as you
avoid the recursive call to Search() if the hash will cause a cutoff for
the other side.
But now you have a piece of code that for any ply, is doing some work for
ply=N, and some work for ply=N+1 which can probably lead to some ugly bugs.
But they would be _faster_ bugs. :)
>>
>>In things like this, the first goal is to shrink the tree. If you can do that
>>then you work trying to make the new code as fast as possible. If the new stuff
>>doesn't shrink the tree, then making it faster is worthless...
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.