Author: Robert Hyatt
Date: 12:33:51 12/24/05
Go up one level in this thread
On December 24, 2005 at 00:30:26, Stuart Cracraft wrote:
>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?
The CB idea worked, but it has a flaw, namely the hash table. Mate scores are
different, since they are forced wins in X moves, but draw scores are not, and
what can happen is that you can see some really impossible draw scores (+49 for
example, which says "draw in 99 plies" which is not possible for most programs
to actually "see". I quit doing that in the very last CB versions and never did
it in Crafty, because I never played with "adjusting" the hashed draw scores as
I do mate scores...
Crafty simply returns a static draw score, usually 0, but it can vary from -1.0
to +1.0 depending on the "contempt" factor which is set by virtue of knowing
Crafty's rating and the opponent's rating (this is part of the xboard protocol
stuff Tim added specifically for crafty).
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.