Author: Tord Romstad
Date: 03:58:41 10/26/05
Go up one level in this thread
On October 26, 2005 at 05:59:30, Svein Bjørnar Myrvang wrote: >Can anyone guide me to some good articles on the subject? I can't seem to find >anything. Thanks in advance, >Svein In a program with decent move ordering, you would expect a beta cutoff at non-PV nodes to occur in one of the first moves played, or not at all. Beta cutoffs late in the move list are very rare. This simple observation can be used as a basis for reduction techniques. The basic idea is this: Search the first few moves at each node with full depth. If no beta cutoff is found, search the remaining moves with reduced depth. If one of the reduced moves returns a score >= beta, re-search this move with full depth. You will probably find that this simple approach reduces your tree size dramatically, but the risks are far too big. Blindly reducing all moves late in the move list is too dangerous, and you need some extra conditions. Most people never reduce captures, promotions, checks, or moves which are extended for some reason. If you evaluate internal nodes, you can also see how each move changes the components of the evaluation function, and make exceptions for moves which dramatically increases your passed pawn score, the pressure against the opponent king, and so on. There is lots of scope for experiment here, and I suspect that the implementations in current programs are very far from optimal. Another very popular condition is to collect statistics about how often every move has failed high or low in the past, and to avoid reducing moves which have a high (fail high)/(fail low) ratio. This condition is the reason for the name "history pruning", which in my opinion is very unfortunate. History is just one of several conditions which can be used, and we are not talking about pruning, but reductions. I prefer the term "late move reductions", but it seems I am quite alone. I have found the technique to work even better (especially in tactical positions) with the following enhancement: If, at the node directly following a reduction, the null move fails low, and the moving piece in the move that refuted the null move is the same as the moving piece in the reduced move, immediately cancel the reduced-depth search and re-search the move with full depth. The point is that in cases like this, the reduced depth move often contain some serious tactical threat, and deserves a deeper search. Tord
This page took 0.02 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.