Author: Stuart Cracraft
Date: 11:20:51 01/05/06
Go up one level in this thread
On January 04, 2006 at 21:20:19, Dann Corbit wrote:
>On January 04, 2006 at 18:22:51, Stuart Cracraft wrote:
>
>>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.
>
>When you analyzed the test suite, did you give it fixed depth or fixed time or
>what sort of option?
>
>If you give it fixed depth, we cannot expect faster solving, but we can expect
>lower times.
I use fixed time for the test suite described above. I always use fixed time.
Fixed time meaning, at 5 seconds, the search is stopped immediately and
is not allowed to "finish" anything. The value of the "bestmv" variable
is then utilized for the move.
I think this might be more strict than some programmers implementation
of fixed time doing testsuites.
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.