Author: Tord Romstad
Date: 09:07:24 07/03/05
Go up one level in this thread
On July 03, 2005 at 11:25:16, David Dahlem wrote: >Are there any papers explaining this method? Perhaps someone could post some >simple pseudo code. I'll try. First of all, the name is rather unfortunate. The "history" part of the name is misleading because the use of history counters in this context is not as important as commonly believed, and the "pruning" part of the name is inaccurate because most of us don't really prune the moves at all, but just search them with reduced depth. "Late move reductions" would have been a better name, IMHO. The idea is that in a program with reasonably good move ordering, a fail high will happen either on one of the first few moves or not at all. At a non-PV node, if the first few moves fail low, it is likely that the remaining moves will fail low as well. Late move reductions means that all moves late in the move list are searched with reduced depth (usually reduced by one ply). If one of the reduced moves fail high, most people re-search this move with full depth. Obviously, reducing all late moves without any extra conditions would be far too risky. First of all, captures, promotions, checks and all moves which are extended for some reason should almost certainly almost be searched to full depth. Which other conditions are used varies a lot between different programs. A common condition is to not reduce moves which have good history (i.e. have often failed high in the past). This is the origin of the name "history pruning". You may also want to avoid reducing moves which dramatically increases the pressure against the opponent's king, your passed pawn eval, or similar. An enhancement I found recently (which seems to work well in my program) is the following: If, at the node directly following a reduction, the null move fails low, and the moving piece in the move which refutes the null move is the same as the moving piece in the reduced move, immediately cancel the reduced depth search and re-search with full depth. If you want to have a look at actual code, you can check Fruit or Glaurung. Tord
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.