Author: Tord Romstad
Date: 11:36:36 01/03/06
Go up one level in this thread
On January 03, 2006 at 14:02:19, Stuart Cracraft wrote:
>Tord - can you please give an example of a late move reduction using a
>move sequence or example so that we can all understand this?
OK, I'll try. I have explained it numerous times in the past, but the
question always comes up again. I suppose I should just write a
Web page about it and post a link in the future. :-)
The idea is based on the simple observation that in a program
with reasonably good move ordering, a beta cutoff will usually
occur either on one of the first few moves of a node or not at
all. This fact can be used to reduce the size of the search tree
(but not without risks, of course). After the first few moves
have been searched, the remaining moves are searched with
reduced depth, unless they appear particularly interesting.
If one of the reduced depth searches return a score bigger than
alpha (which we don't expect to happen), that move is re-searched
with full depth (there are some programmers who don't do such
re-searches, though).
In pseudo code:
int search(int alpha, int beta, int depth) {
int value, moves_searched = 0;
move_t move;
// Transposition table probing, null move search etc. here
...
generate_moves();
while((move = pick_move())) {
make_move(move);
if(moves_searched > 3 && !interesting_move(move)) {
value = -search(-beta, -alpha, depth - 2);
if(value > alpha)
value = -search(-beta, -alpha, depth - 1);
}
else value = -search(-beta, -alpha, depth - 1);
unmake_move(move);
moves_searched++;
if(value > alpha) alpha = value;
if(alpha >= beta) break;
}
return alpha;
}
The main thing missing in the above pseudo code is the
definition of the interesting_move() function. You will
probably find that it is too risky to reduce all moves after
the first three. Most people never reduce captures,
promotions, checks or moves which are extended for
some reason (it clearly doesn't make much sense to reduce
an extended move). Beyond this, the details vary widely
between different implementations.
A popular criterion is to not reduce moves with a good
history (i.e. moves which have often failed high in the past).
This is the origin of the name "history pruning".
If you evaluate internal nodes, you can consider using
evaluation data. Avoid reducing moves which increase
the static eval and brings it close to or above alpha, or
moves which dramatically increases some component
of the evaluation function.
Static or dynamic threat detection can also be used. I
used to do some rather complicated static threat detection
in my previous program, but now I use a simple dynamic
threat detection based on the null move search. The idea
is the same in both cases: If a move appears to contain
some dangerous threat, always search it with full depth.
>How did it do with your tests for suites and actual games? Estimate
>of ELO gain is ... ?
For me, it is a tremendous improvement, in test suites as
well as games (I never test at slow time controls, though).
Estimated Elo gain is >100. I don't remember exactly; I
haven't made any comparisons recently.
Unfortunately it doesn't seem to work so well in most other
programs. Some authors measure only a modest improvement,
or no improvement at all. It is possible that (like most pruning
mechanisms) it works best in programs with a very primitive
evaluation function.
Tord
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.