Author: Gerd Isenberg
Date: 09:27:13 10/26/05
Go up one level in this thread
On October 26, 2005 at 06:58:41, Tord Romstad wrote: >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. Yes, i don't like "history pruning" as well. What about "right wing reductions" ;-) Do you apply "late move reductions" only at "expected" cut-nodes or on all-nodes as well? > >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. As always - thanks for sharing your ideas and improvements. Sounds logical - have to think about the control flow of the search. > >Tord BTW. what about your strange 10% speedup problem you mentioned some time ago in WBF? Is it still present and did you find an explanation - or was it only a temporary chaotical "phantom", which disappeared after some code changes? Thanks, Gerd
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.