Search inconsistency
bruce moreland
wrote:
>I am still seeing fail high's followed by fail low's. Search
>inconsistencies. They disappear when I turn off my very simple QSearch
>pruning (skip this capture if Eval+CaptureValue - Margin <=Alpha) AND
>null-move.
>
>What about nullmove? Can it cause this strange fail high - low occurences? I
>noticed that when I disable nullmove at the root (and the QSearch pruning)
>that the faults disappear.
If you make any sort of significant pruning or evaluation decision
based upon the value of alphaor beta, you will have problems.
The reason is, you might visit this node again with a different value
of alpha or beta, and a different decision may be made, which may
result in a different score, which may result in that score
propagating to the root, causing a contradictory failure.
You have stop and think about what is going on in the search. The
null move, as implemented typically, does a search and compares this
result against some derivative of beta, and if depending upon the
result of the comparison, it might forward prune. If you come back to
this node with a different value of beta, it might not forward prune,
and when you go off to do the real search, you might get a result back
that contradicts the original forward pruning decision.
So yes, the null move is a great example of something that can mess up
your search.
You can get this same problem in other ways, for instance, forward
pruning based upon hash table scores. Those scores in the hash table
are for positions, not for paths taken to reach those positions, and
they also may not take into account paths taken from those positions.
So you can get erroneous draw scores, or scores that have been reduced
due to the presence of erroneous draw scores (this is why it doesn't
work to just not store nodes with draw values attached to them).
Problem with all of this is that the things that cause the search to
be unstable also add strength to the program. So you can have
something that is perfect and plays bad, or something that offends
your sense of neatness occasionally, but is stronger. You can take
your choice.
>I use simple Alpha Beta with aspiration window at the root. So when I
>disable null-move at the root I don't get fail high's followed by fail lows
>at the root.
Right. You won't have any problems if you don't reference the values
of alpha or beta in order to make forward pruning decisions, and if
you don't have any path-based scores such as 3x repetition and 50-move
rule, or other similar deals.
>Another thing: notice Margin above. When I widen the aspiration window by
>Margin*2 or so, the fail high-low phenomenon disappears. So this is what I
>do now:
Yes, this is the "I kicked it and it healed itself" effect. You can
make the problem less obvious by fiddling with alpha and beta.
Perhaps the mistake will go away. Maybe it will reappear somewhere
else. The root question is whether the search instabilities are more
harmful than the search inefficiences caused by searching a wider
window, and this does nothing to answer that, it just makes you feel
better about what you are seeing.
It's way better to understand what is going on instead of treating
symptoms.
>1. Turn null move (R=3) off at Depth==Depth (=the root)
>2. In stead of [PreviousAlpha-Window, PreviousAlpha+Window] I do:
>[PrevAlph-Window-Margin*2, PrevAlph+Window+Margin*2]
>where Margin is the QSearch pruning margin.
I think R=3 produces more instability than R=2, but I don't know if it
plays better or worse.
bruce
>No inconsistencies anymore.
>
>Reactions please?
>
>
>Bas Hamstra.
Robert Hyatt
: I am still seeing fail high's followed by fail low's. Search
: inconsistencies. They disappear when I turn off my very simple QSearch
: pruning (skip this capture if Eval+CaptureValue - Margin <=Alpha) AND
: null-move.
: What about nullmove? Can it cause this strange fail high - low occurences? I
: noticed that when I disable nullmove at the root (and the QSearch pruning)
: that the faults disappear.
: I use simple Alpha Beta with aspiration window at the root. So when I
: disable null-move at the root I don't get fail high's followed by fail lows
: at the root.
: Another thing: notice Margin above. When I widen the aspiration window by
: Margin*2 or so, the fail high-low phenomenon disappears. So this is what I
: do now:
Null move can cause lots of things. One simple thing to do is that if you
fail high on the "null-window (pvs)" search, but fail low on the re-search,
ignore the fail high completely.
: 1. Turn null move (R=3) off at Depth==Depth (=the root)
: 2. In stead of [PreviousAlpha-Window, PreviousAlpha+Window] I do:
: [PrevAlph-Window-Margin*2, PrevAlph+Window+Margin*2]
: where Margin is the QSearch pruning margin.
: No inconsistencies anymore.
: Reactions please?
: Bas Hamstra.
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Bas Hamstra
inconsistencies. They disappear when I turn off my very simple QSearch
pruning (skip this capture if Eval+CaptureValue - Margin <=Alpha) AND
null-move.
What about nullmove? Can it cause this strange fail high - low occurences? I
noticed that when I disable nullmove at the root (and the QSearch pruning)
that the faults disappear.
I use simple Alpha Beta with aspiration window at the root. So when I
disable null-move at the root I don't get fail high's followed by fail lows
at the root.
Another thing: notice Margin above. When I widen the aspiration window by
Margin*2 or so, the fail high-low phenomenon disappears. So this is what I
do now:
1. Turn null move (R=3) off at Depth==Depth (=the root)
Bas Hamstra
definitely takes away the "insecure" feeling I was having. I was set on the
wrong leg (dutch expression, ahem meaning pointed in the wrong direction) by
some other responses in a dutch newsgroup that said "must be bugs". I
misinterpreted because it was supposed to be obvious that pruning can mess
things up, which I didn't know until now.
You are perfectly right about inconsistencies don't "feel" good. I hate it.
But in the end I too have to choose for what works best, of couse.
Thanks, guys.
Bas Hamstra (FICS rating of Zen is 1750 now, just started).
bruce moreland wrote in bericht <368584c7....@news.seanet.com>...
>On Fri, 18 Dec 1998 00:28:56 +0100, "Bas Hamstra" <bas.h...@wxs.nl>
>wrote:
>
>>I am still seeing fail high's followed by fail low's. Search
>>inconsistencies. They disappear when I turn off my very simple QSearch
>>pruning (skip this capture if Eval+CaptureValue - Margin <=Alpha) AND
>>null-move.
>>
>>What about nullmove? Can it cause this strange fail high - low occurences?
I
>>noticed that when I disable nullmove at the root (and the QSearch pruning)
>>that the faults disappear.
>
>>I use simple Alpha Beta with aspiration window at the root. So when I
>>disable null-move at the root I don't get fail high's followed by fail
lows
>>at the root.
>
>Right. You won't have any problems if you don't reference the values
>of alpha or beta in order to make forward pruning decisions, and if
>you don't have any path-based scores such as 3x repetition and 50-move
>rule, or other similar deals.
>
>>Another thing: notice Margin above. When I widen the aspiration window by
>>Margin*2 or so, the fail high-low phenomenon disappears. So this is what I
>>do now:
>
>Yes, this is the "I kicked it and it healed itself" effect. You can
>make the problem less obvious by fiddling with alpha and beta.
>Perhaps the mistake will go away. Maybe it will reappear somewhere
>else. The root question is whether the search instabilities are more
>harmful than the search inefficiences caused by searching a wider
>window, and this does nothing to answer that, it just makes you feel
>better about what you are seeing.
>
>It's way better to understand what is going on instead of treating
>symptoms.
>
>>1. Turn null move (R=3) off at Depth==Depth (=the root)
>>2. In stead of [PreviousAlpha-Window, PreviousAlpha+Window] I do:
>>[PrevAlph-Window-Margin*2, PrevAlph+Window+Margin*2]
>>where Margin is the QSearch pruning margin.
>
>I think R=3 produces more instability than R=2, but I don't know if it
>plays better or worse.
>
>bruce
>