Author: Tord Romstad
Date: 14:47:56 01/17/06
Go up one level in this thread
On January 17, 2006 at 16:45:41, Robert Hyatt wrote: >On January 17, 2006 at 16:27:42, Dann Corbit wrote: > >>On January 17, 2006 at 16:23:53, Tommi Rimpiläinen wrote: >> >>>Hello! >>> >>>I suppose all the major chess programs use Tord Romstads Fail-low pruning now a >>>days. Fruit uses it and it is likely that Rybka uses it also. It would be >>>interesting to know, what the idea is behind this method of pruning. "Fail-low pruning" was a new name to me, but it is not a bad name. The technique was not invented by me, although I like to think that I played some role in popularising it. I think your belief that it is used in all major chess programs is very wrong, though. >>If it looks like crap, don't search as deep. >> >>>How sound >>>is this idea theoretically? >> >>All pruning beyond Alpha-Beta is unsound (IOW, it could cause you to miss >>somthing and get the wrong answer). However, empirically, it often works quite >>well in practice (e.g. null move pruning is an example of theoretically unsound >>pruning that is so successful practically everyone uses it. And those that do >>not use it either use some related idea or lose all of their chess games). Most modern pruning techniques (recursive null move, ProbCut, MultiCut, fail low reductions, etc) don't prune moves completely, but estimate their values with reduced depth searches. This means that the problem isn't really the risk of getting the wrong answer, but rather the risk of needing a bigger search depth in order to find the right answer >Note that null-move is not _that_ "unsound". The "null-move observation" is >actually pretty well-founded in the game of chess. That is, if I can make a >null move (pass) and you get two consecutive moves and still can't kill me, your >position really sucks... That is not quite as unsound as just saying "I am not >going to search this move at all, or I am not going to search this move as >deeply." Both of which can introduce more errors than null-move easily. NM's >main adversary is zugzwang... I don't agree. Zugzwang is sufficiently rare that it doesn't matter very much in practise, and if you really worry about it you can fix the problem without much cost. Detecting zugzwang in a recursive null move search isn't *that* hard. The real problem with null move, in my opinion, is the difficulty of finding maneuvres where a piece moves across several bad-looking squares on the way to a really good square, without threatening anything serious along the way. 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.