Author: Dann Corbit
Date: 14:26:59 01/17/06
Go up one level in this thread
On January 17, 2006 at 16:59:49, Uri Blass wrote: >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. >>> >>>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). > >It also can cause you to find something because you search deeper. > >I do not understand why it is considered as unsound. >Of course if you compare searching to the same depth than pruning is bad but >this comparison is not relevant in games. > > 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). >> >> >>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 have 2 comments. >1)I do not see why null move pruning has less errors than reductions or pruning >based on other conditions and it is dependent on the other conditions that you >define. > >2)If you compare searching to fixed depth with null move pruning and without it >then the main advantage of not doing null pruning is not the fact that you do >not miss zugzwangs but the fact that you do not prune moves with some threats >that are too deep. These methods are theoretically unsound, but work well in practice. A method is said to be unsound if a search to depth K fails to find the best move at depth K. Alpha-Beta will not fail to find it. It will find exactly the same move as a full minimax search would. Other sorts of reductions like null move do not provide the same guarantee. So "technically" they are unsound. But they work very well in practice. You can also limit the total depth reduction to some fundamental limit (like 1/2 of the full search depth) and in such a case, the right move must eventually be found. But it could take a 2x search to do it.
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.