Author: Stuart Cracraft
Date: 16:26:47 12/20/05
Go up one level in this thread
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
This page took 0.01 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.