Author: Robert Hyatt
Date: 14:22:13 12/22/05
Go up one level in this thread
On December 22, 2005 at 13:09:08, Stuart Cracraft wrote:
>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
I don't do that in Crafty, I did in Cray Blitz. The idea was the Evaluate()
returned the score in the following way:
if (score < -50) return score;
else return score+100;
That means scores between -50 and +49 can not be produced by actual positional
scoring. I can then return draw scores that look just like mate scores. If I
find a repetition, I "return -50+depth" so that the deepest possible repetition
is favored, to give the opponent a chance to screw up.
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.