Author: Edward Screven
Date: 19:01:22 01/25/01
Go up one level in this thread
On January 25, 2001 at 19:05:12, Robert Hyatt wrote:
>>we must think about the null move heuristic differently, because i
>>don't think its typical implementation is at all similar to what
>>david suggested.
>>
>>sure, there is a reduced depth search involved, but it's part
>>of the pruning test, not the pruning action. the pruning action
>>is all or none -- completely prune the move from the parent node
>>or search it in full.
>
>Think about it differently. IE at ply=N, I play a move and I am
>about to do a normal search to depth=X to see how this move works.
>But first, I assume my opponent does nothing, and I then do a much
>shallower search with me to move again. If this is bad for me, there
>is no need for me to search this move to the full depth, I can get away
>with searching it to the shallower depth, proven by the null-move observation...
yes, i know how the null move heuristic works. and this is how you
could think about it differently. imagine a program with a main
Search() loop that looked something like
for move in legal_moves {
DoMove(move)
if PruneTest(move,alpha,depth) {
-- do nothing, we are pruning this move
} else {
score := Search(depth-1)
... handle fail high, etc. ...
}
UndoMove(move)
}
what i understand david to be suggesting, is that one could change
this to be something like
for move in legal_moves {
DoMove(move)
if PruneTest(move,alpha,depth) {
reduction := PRUNE_REDUCTION_CONSTANT;
} else {
reduction := 0;
}
score := Search(depth-reduction-1)
... handle fail high, etc. ...
UndoMove(move)
}
in other words, reduce the child search depth if PruneTest() returns
true instead of just killing the move altogether.
would you say then PruneTest() is dependent or independent of
david's idea? i say independent, because david's idea isn't to
change the way in which one decides to prune, but rather what to
do after one makes a decision to prune.
now what could PruneTest() be? well it might just be a function
that applies a null move, then does a reduced depth search, and
then returns true iff the resulting score is <= alpha (from the
perspective of the side to move in the main loop.)
as i'm sure you realize, this is an implementation of the null
move heuristic that has the same behaviour as the more common
one. (the more common one is less awkward of course.)
so if one believes that PruneTest() is indendent of david's idea,
then i think one would also believe that null move pruning has
nothing to do with david's idea.
- edward
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.