Author: Stuart Cracraft
Date: 21:30:26 12/23/05
Go up one level in this thread
On December 22, 2005 at 17:22:13, Robert Hyatt wrote:
>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.
Okay - the CB method sounds good. Why not in Crafty and what did you do in
Crafty for returning draws?
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.