Author: Stuart Cracraft
Date: 09:20:54 12/21/05
Go up one level in this thread
On December 20, 2005 at 20:32:15, Robert Hyatt 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.
>>
>>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);
>>
>>Someone once suggested the above 3 should be a 2 since if it
>>could be forced once (be at 2) it should be forced again. I think it
>>was Tom K. of TSCP fame. But I did some tests with both and
>>preferred 3. Perhaps I should make it 2 after all.
>>
>>--Stuart
>
>
>The best solution is this:
>
>repeat twice in the search -> draw. Repeat three times otherwise -> draw.
>Three times could be two in the actual game history so the next repeat is an
>instant draw, etc...
>
>works for me and has for years...
Great. I've just reimplemented it to be reps()==2 in the search() and
quiesce() calls and reps()==3 outside of the search. Thanks.
Now rerunning some tests to compare practical follow-on effects.
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.