Author: David Dahlem
Date: 09:49:43 07/03/05
Go up one level in this thread
On July 03, 2005 at 12:07:24, Tord Romstad wrote: >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 Thanks Tord. I had a feeling that history pruning was not really pruning at all. :-) I'll look at the Fruit and Glaurung code. Regards Dave
This page took 0.03 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.