Author: Stuart Cracraft
Date: 10:19:11 12/21/05
Go up one level in this thread
On December 21, 2005 at 12:20:54, Stuart Cracraft wrote:
>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
Followup tests were fine, even one problem better, within the
area of statistical anomaly. The suite is not optimized against
but merely serves to point out any bonehead change that would
grossly affect results.
My draw meter is resting easier now. No contempt feature yet tho.
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.