[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: [Questions] Null Move
From: "Mousheng Xu" <moushengxu@xxxxxxxxxxxxxxxxx>
Date: Tue, 27 Nov 2001 11:03:45 -0800
Mime-Version: 1.0
X-OriginalArrivalTime: 27 Nov 2001 19:03:46.0220 (UTC) FILETIME=[3D5966C0:01C17776]
Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
Precedence: bulk
Reply-To: computer-go@xxxxxxxxxxxxxxxxx
Content-Type: text/plain; format=flowed
Content-Length: 4560
>
> 1. What does "-beta + 1" mean in "val = -AlphaBeta(depth - 1 - R,
>-beta,
> -beta + 1)"? Why set the upperbound to "-beta + 1" when considering a
>null
> move? Especially, why use "1" instead of other values?
>
>Because only 1 makes it a zero width window search. You could use
>other values and it would still work, but it would be needlessly
>slowed down.
How if your score is not integer but float/double? Then "1" is not the
minimum difference between scores.
Like I say, you can use any number you want, it does not affect the
accuracy of the search, only the speed. Try 0.00001 or something and
you probably will not detect a difference.
>This kind of search, with a zero width window ALWAYS fails, either
>high or low. If the score is greater than or equal to beta, it fails
>HI and if it's less than or equal to ALPHA, it fails low. There is
>nothing between beta-1 and beta, that the search can return.
>
>So this is called a zero width window and is used just for testing,
>not to return an actual score.
My feeling is that null move pruning has a reasonable chance to miss the
best branch.
The whole idea of null move pruning is to take a chance on missing the
best branch. The tradeoff is that you get to search deeper in many
branches of the tree. Whether you should do this or not depends on
your analysis of whether it makes your program stronger or not.
In chess, it works incredibly well (and yes, you sometimes prune a move
you shouldn't.) I don't have a clue about whether it is worthwhile
in Go or not.
Suppose given a normal play without null moves, the best path
goes from A to B to C. But while testing the children of A, the null move
returns value > beta and thus skipped the chance of evaluating B (whose
evaluated value is > alpha but < beta).
About the "ALWAYS fail" part: if it always fails, then why bother using a
depth "depth - 1 - R"? To make sure it always fail, one can pass in depth =
0 and not worry about the alpha & beta.
You may be hung up on the context. The term "fail" is not bad, it
means the search returned with a value that is "outside" the window
and we don't know the exact score. But we don't really care less
about the "exact" score since all we want to know is if the score is
greater than or equal to beta, that's all! If it's greater than or
equal, we prune, otherwise we go full width at this branch.
> 2. I have not seen a Web reference talking about the problem of
>consecutive
> null moves. In case, say, 2 null moves are used in a row, e.g., Black
>->
> White skip to Black -> Black skip back to White, is equivalent to Black
>->
> White with depth reduced by R * 2. This is like to evaluate with a
>shallower
> depth and use it. Is there a danger to use a value with shallower
>depth?
>
>
>In principle it doesn't make sense to do 2 null moves in a row. The
>idea of this kind of search is for one side to SKIP a move. If each
>side skips a move, then it's the same as neither side skipping a move.
>
>In practice, I don't think it matters to the coding of the algorithm.
>Remember, the null move test has to be successful to produce a cutoff
>and it's not going to be succesful for both sides.
>
>
> 3. Go is different from Chess in that Go has co-survival but Chess does
>not.
> When a co-survival is reached, a null move for either side is better
>than
> any move. In this case, will
>
> ...
> val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
> if (val >= beta)
> return beta;
> ...
>
> still work? I guess my problem comes from my poor understanding of "val
>=
> -AlphaBeta(depth - 1 - R, -beta, -beta + 1)".
>
> Your help is highly appreciated.
>
> Thanks.
>
> -- Mousheng Xu
>
>I don't know what co-survial means. In Chess, there are many
>situations where it's better to pass than to play a move. In these
>situations, null move pruning is broken because it is based on the
>principle that skipping an opportunity to move is always bad (or at
>best neutral.)
>
>My understanding, from talking to good Go players is that it is NEVER
>an advantage to pass in Go (unless you count Japanese style scoring
>systems, which penalizes you for some moves that have absolutely no
>effect on the ownership of territory.)
>
>I don't know if this is really true or not, but is there ever a reason
>you would want to pass other than to end the game?
>
Besides some trivial cases when it is an advantage to pass in Go, there are
significant cases when you do want to pass. Suppose you are *locally*
evaluating two groups of different sides and they are in co-survival state,
meaning none of the groups has two eyes, but none can kill the other. One
legal move from either side there gives itself the chance to be killed by
the opponent. So the best strategy for both sides is "don't make a move here
so that both of us can survive otherwise I will be killed for sure".
What's the problem? The only thing that will happen is that the
opponent will make a pass in response to your null move pass, and you
will take the cutoff if the search fails hi. If it fails low you
won't. (Probably, you will get a cutoff if your search is designed to
only do the pruning test if the current evaluation is above beta.)
Null move pruning is a special case of selectivity. The function you
really want to write is one that returns an upper bound on the score.
Null move is just one way to do this. The concenpt is very simple: If
your position is so good you can afford to pass, then why bother
searching? Of course to measure this you still have to search, but we
rely on the hope that even a reduced depth search is accurate enough
to say that passing is ok or not. As you suspect, there are cases
where the opponent can move twice in a row and still look bad when in
fact the 2 moves in a row really helped him. In these cases, null
move doesn't work.
The puzzle here is how can the "null move" be compared with the "min" and
"max" nodes? "null move" here is a legal choice, but not to set an upper or
lower bound as people normally do in chess. In the co-survival case, a null
move yields a value > any move for both sides. I am wondering how the value
evaluated for a null move be compared with alpha & beta, and what value is
returned.
Thanks, Don.
-- Mousheng Xu
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp