Author: Rémi Coulom
Date: 06:12:14 07/12/02
Go up one level in this thread
On July 12, 2002 at 08:08:20, Vladimir Medvedev wrote:
>How to handle position repetitions during search?
>
>I use the following method:
>
>(pseudo-code)
>
>int CountSearchRepetitions[MAXSIZE];
>int CountHistoryRepetitions[MAXSIZE];
>
>int AlphaBeta(Position pos, int alpha, int beta)
>{
> if( current_ply > 0 && CountHistoryRepetitions[ pos.GetHash() % MAXSIZE ]>0
>)
> {
> return min( 0, beta );
> }
>
> if( CountSearchRepetitions[ pos.GetHash() % MAXSIZE ] > 1 )
> {
> return min( 0, beta );
> }
>
> while( get_next_move() )
> {
> pos.MakeMove();
> SearchRepetition[ pos.GetHash() % MAXSIZE ] ++;
> int eval = - AlphaBeta( pos, -beta, -alpha );
> SearchRepetition[ pos.GetHash() % MAXSIZE ] --;
> pos.UnmakeMove();
>
> ........
>
> }
>}
>
>Is this correct? Shouldn't I return 0 instead min(0, beta)?
Both are correct. Returning 0 might be better. This is what is called
"fail-soft" alpha-beta. It is all right to return values that are higher than
beta if they are lower bounds of the evaluation, or values that are lower than
alpha if they are higher bounds. Returning values outside [alpha,beta] can help
a lot if you have to do a re-search (like in the PVS), and is essential in
algorithms like MTD(f).
See
http://www.ics.uci.edu/~eppstein/180a/990202b.html
>Is it good to add repetitions in game history to repetitions on the current
>branch?
I am not sure I understand: do you mean game history before the root node? Yes,
you have to take it into consideration: just suppose there is a move that
triggers a repetition from the root position of the search, because your
opponent has just taken back its last move. You do not want to run into this
repetition by mistake, if your evaluation is positive.
Remi
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.