Author: Peter McKenzie
Date: 18:10:36 04/17/02
Go up one level in this thread
On April 17, 2002 at 20:20:04, Dann Corbit wrote:
>On April 17, 2002 at 20:05:52, Ricardo Gibert wrote:
>
>>The title of the thread is Null move *generaliztion*. Are there positions that
>>Null move *cannot* solve? Yes. Now the question is, "Under what conditions?"
>>There is no question that a null moving program with modification can
>>theoretically still solve any position. That's not the issue.
>
>I still don't understand how null move (properly implemented) can *ever* cause a
>search to simply fail. After all, the *only* side effect is that it reduces
>search depth by some number of plies (as defined by R).
>
>If we are searching illegal moves, or if we recursively apply null move without
>limit {and surely this is a very bad bug} then all sorts of strange things can
>happen.
I think most programs null move pruning recursively without limit. Its not a
bug, just a tradeoff ... and a pretty good one at that IMHO.
>
>But if:
>1. We only search legal moves
>2. We do not reduce depth infinitely but only finitely
>Then my question is:
>"How can the search fail forever?"
Just one nullmove is enough to have the zugzwang problem, you don't need
recursive null move pruning to see it.
Eg. in my PET position, after 1.a4+ Kb6 2.Bf2 c1=Q 3.Rxc5 Qxc5 4.Kh1! black is
zugged. Lets call this position Z. Any move he makes allows white to draw, so
black plays the nullmove. Now white must make a move, and funnily enough, any
move white makes loses pretty fast.
So when the search reaches position Z, black null moves and gets a huge positive
score. This will typically fail high, UNLESS beta is very high.
And I think that is what makes this a 'never solve' problem. It is possible
that deep searches show white to be in a very bad way, thereby forcing beta to
be very high in position Z. This will mean that when we reach position Z, the
null move might not fail high so we will have to search the other moves ... all
of which will fail low which will lead to the solution being found. Of course,
if you do something too clever like adjust alpha to be your nullmove score, then
you are in real trouble :-)
So this position, while being a chronic problem if null move pruning is applied,
is still solvable in such a case (although very slowly).
Hope that makes sense.
Peter
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.