Author: Stuart Cracraft
Date: 10:09:08 12/22/05
Go up one level in this thread
On December 22, 2005 at 12:48:26, Robert Hyatt wrote:
>On December 21, 2005 at 13:19:11, Stuart Cracraft wrote:
>
>>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.
>
>
>That isn't quite what I said.
>
>I said:
>
>(1) if you repeat the same position _twice_ in the search, then call it a draw,
>instantly...
>
>(2) if you reach a position for the first time in the game history, and the
>second in the search, do _not_ call it a draw.
>
>So, simply stated:
>
>a position is considered an instant draw if it is either (a) reached twice in
>the search itself, or (b) reached once in the search and twice in the game
>history preceeding the search...
>
>A safer solution, and one I use, is slightly different...
>
>(a) two occurrences in the search is always a draw.
>
>(b) one occurrence in the search and one in the history is also a draw, but not
>during the first couple of plies.
>
>(c) once in the search and twice in the history is always a draw...
>
>(b) saves some time and picks up draws quicker, while still letting the program
>notice that the second repetition (first in the actual search) is not really a
>draw and can be ignored...
Mine is more like:
a position is considered an instant draw if it is either (a) reached twice in
the search itself, or (b) reached once in the search and twice in the game
history preceeding the search...
than the other.
My draw-check reviews the set of positions in the game history from
move 1 in the game up to the leaf of the PV or wherever we happen to
be when the draw-test is done.
It goes backwards in this list looking for recurrences of the same position
as the current board position. If 2 such occurrences including this one,
a draw is returned immediately, if in the search or quiescence. If outside
of the search, the requirement is 3, due to the actual board being involved.
Of more interest to me is the actual draw value itself and other evaluations
not being allowed to become the draw value.
When you have time, please describe your technique for keeping the window
around the draw value wider so that other evaluations do not fall within it.
Why do you do that? What did you notice years ago before you did that in
terms of poorer draw handling (practical board observation.)
Again, only if you have time and feel inclined.
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.