Author: Stuart Cracraft
Date: 16:08:04 12/21/05
Go up one level in this thread
On December 21, 2005 at 16:11:29, Frederik Tack wrote:
>On December 20, 2005 at 19:26:47, Stuart Cracraft wrote:
>
>>On December 20, 2005 at 17:11:41, Frederik Tack wrote:
>>
>>>I'm looking for the best way to implement a repetition detection in the search
>>>tree for my engine without loosing performance.
>>>
>>>I've found some articles on the internet suggesting to create a repetition table
>>>using zobristkeys. I have now implemented this and it works fine, but i've lost
>>>about 10% performance.
>>>
>>>I have now come up with a new idea that should have no impact on performance.
>>>However, i'm not sure if what i'm about to do is completely correct. Here's the
>>>idea. Before starting the analysis, i store every position i've had on the board
>>>from the move history in the transposition table with an evaluation of 0 and a
>>>depth of maxdepth + 1. During the analysis, i use a replacement scheme in the
>>>transposition table that will not replace the position if the depth in the tree
>>>is smaller than depth in the table. Since i've stored the historic positions
>>>with maxdepth + 1, they will never get replaced. This should score every
>>>position that has been on the board before with a draw score.
>>>
>>>The fact is i haven't found any article on the internet discussing this way of
>>>working, so i fear it may have some drawbacks i'm not aware of. Has any1 tried
>>>implementing repetition detection this way or has any1 an idea why this wouldn't
>>>work?
>>
>>10% is too much. Something is wrong.
>>
>>As moves as are made, the Zobrist value for the current
>>board position is updated or downdated incrementally by
>>the makemove and unmakemove routines. I hope you do that
>>and don't recalculate it by a full board scan.
>
>Yes, i do this. I have already implemented an incremental zobristkey for use in
>the transposition table, so no performance is lost here.
>
>>
>>My draw repetition code is:
>>
>>// 50 or more moves since last pawn move?
>>int pawndrawn()
>>{
>> int h;
>> for (h = histptr; h >= 0; h--)
>> if (ABS(hist[h].pc) == WP)
>> if (histptr-h >= 50)
>> return(1);
>> else
>> return(0);
>> return(0);
>>}
>>// how many times the current position has been repeated in the past
>>int reps()
>>{
>> int r, h;
>> r = 0;
>> for (h = 0; h <= histptr; h++)
>> if (hist[h].key == hashkey)
>> r++;
>> return r;
>>}
>>
>>Then this code is placed near the top of my quiescence and
>>tree search routines:
>>
>> if (reps()==3 || pawndrawn()) return(DRAW);
>>
>
>That is also what i do now at the top of my negamax function, except i think
>your method of counting the repetions in every node will be even more time
>consuming than using a repetition table like i do. Robert Hyatt suggested in
>another post to do the test for repetition just after making the move. This
>might be better for performance, since i save a call to negamax in case of a
>repetition, so i'm gonna try this out. If i still have a significant performance
I think that is a good suggestion but I will probably not implement it.
I would be surprised if the savings is anywhere near 10%. But please let
us know what you find between at the top of negamax/quiescence and
instead after the move within negamax/quiescence.
>loss, i think i'll just go for the idea of using the transposition table without
>detecting repetitions that occur only in the principal variation. This has a
>cost of zero, performance and storage wise. Only drawback i see is that i will
>only detect perpetual checks after the first check has been given, which is too
>late.
You are designing for a fast program. Although I have interest in that for
mine, it is less important for me as the technology of the hardware and
compilers will automatically give me the speed in the long-term with no
work. Since I am not commercial, I can wait.
Stuart
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.