Author: Stuart Cracraft
Date: 15:22:51 01/04/06
Go up one level in this thread
On January 03, 2006 at 14:36:36, Tord Romstad wrote:
>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
Hi -- after reading the above, I implemented a try at late move reduction in
my program, which has very simple evaluation, in the hopes that it
would help.
My implementation is much more simple due to just "testing the water".
It gives a tempting result.
I.e. all is the same except the interesting move which is defined
as not a capture, not a promotion, has zero history heuristic cutoffs
up to this point in the search, no previous extensions for this move,
no previous reductions for this move (though there may be extensions
for the parent node), and legals searched so far is not <= 3.
Anyway, with this brutish implementation (how they usually start), I saw
it keep the same test suite result on WAC Win-at-Chess with the same
score (257/300 vs. 256/300) but 1.5 plies overall average deeper
search across the suite and a 0.6 smaller branching factor (from 2.78 to 2.18)
for the late move reduction version.
On a straightforward fixed-depth search of 10 ply in the opening position,
the late move reduction version took 22x less time for the search than
the version without this feature, specifically 1.95 seconds instead of
42.96 seconds.
It seems like this has made the program far more selective but not
sacrificed tactical skill which is the first such result I've had clearly
in this manner.
I smell a good thing here but obviously don't have it implemented right,
when it would give a better result on the testsuite. I have not tested
it in Arena against other programs yet because my program is not yet
at a point to be a challenge to anyone except me.
Stuart
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.