Author: Stuart Cracraft
Date: 13:14:53 01/03/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
Thanks so much as this may do quite well in mind as my evaluation function
is only material, pc/sq, and mobility.
I am interested in it first and foremost for the idea and second for the
praxis.
Regards,
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.