How if your score is not integer but float/double? Then "1" is not the minimum difference between scores.
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.
My feeling is that null move pruning has a reasonable chance to miss the best branch. 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).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.
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".
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?