Author: Tord Romstad
Date: 06:28:24 08/12/04
Go up one level in this thread
On August 12, 2004 at 08:42:28, martin fierz wrote: >>hi tord, >> >>i'm intrigued by your last sentence - that null move at all nodes more than >>doubles your node count! i wonder how this is possible at all? why? if i >>understand what you write you have an oracle which can tell you whether you >>should do a null-move search at a given node or not. >> >>int alphabeta(....) > >grrr, hitting tab-return is not such a good idea :-) Happens to me too, sometimes. :-) >let me continue: you have > >int alphabeta(...) > { > ... > if(null_oracle(position) == NULL_OK) > do_nullmove_search() > ... > } Almost, but there is one important part missing above: I return a fail high score *before* doing the null move search when I am very sure of a fail high. It's more like this: int alphabeta(...) { if(almost_certainly_fail_high(position, beta)) return beta; else if(probably_fail_high(position, beta)) do_nullmove_search() ... } >if you remove that null_oracle thing you get twice as many nodes? If I remove the almost_certainly_fail_high() and probably_fail_high() functions (I don't have functions with these two exact names, but you get the idea), I search twice as many nodes. >i don't >understand how that can happen. your null_oracle would basically be telling you >not to do a null move search if it thinks it will fail low anyway. so for all >nodes where you don't have to do a null move search with R=3 you have to do a >normal search. you save yourself searching the R=3 part, but that should be very >small compared to the normal search part, shouldn't it? > >what am i missing? That recursive null move pruning is not the only kind of pruning I do. At fail low nodes, most of the moves are not searched with full depth. When the first 3 moves have failed low, I search all remaining moves with reduced depth except when they look especially interesting or forcing. If a move searched with reduced depth surprisingly turns out to fail high, it is re-searched with full depth. For some reason, most of the published research on selective search mechanisms has concentrated on ways to reduce the work at fail-high nodes. Nullmove pruning, Multicut pruning and ProbCut are a few examples. Pruning techniques for fail-low nodes are much less commonly seen. The only ones I can think of is futility pruning and razoring, but these are too dangerous to use except when the remaining depth is very small. Reducing the search depth towards the end of the move list is my own attempt to do selective search at expected fail-low nodes. It is probably possible to invent better techniques (and it wouldn't surprise me if it has already been done in some of the professional engines), but at least in my engine, what I do works far better than nothing. Tord
This page took 0.01 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.