RE: computer-go: Alpha-Beta Search

["Sheppard, Brian" <BSheppard@xxxxxxxxxx>]

> Nullmove  is based on certain domain  specific assumptions that may or
> may not apply to GO.  Since I am  very new at the  game, I don't claim
> to know  whether it would work   for go, but  I think  it  might.  The
> "assumption"  null move makes  is that  it  is ALWAYS (or very  nearly
> always) better to  be on the move.   Or put another  way,  it is NEVER
> good to  "pass."  How valid is this  assumption in GO?

The null move assumption is very, very valid. Even more valid than for
chess.
Keep in mind that Pass is a legal move in Go, so if the null-move asumption
were invalid then professional players would pass instead of playing. Since
they never do this the assumption must be valid.

And it is easy to see why. A stone is only a liability when it deprives you
of room to live. Therefore, it pays to play until every string has exactly
two liberties, and then pass.

In Japanese rules it costs you a point to play on territory that you own,
but for the purpose of analyzing which moves to play this is not relevant.
(I.e. you can analyze as if the game were a Chinese game (except that
you have to score seki differently), then play the corresponding move with
confidence that the move is correct in the Japanese rules.) The null-move
assumption (i.e. that it is better to play than to pass during analysis)
is completely valid.

> Another aspect to null   move, that  may be  a  factor is   the actual
> validity of the "null move test."  The null move test is a "null move"
> followed by a reduced depth search.   The assumption is that this test
> will  return a lower  bound that is  very UNLIKELY  to disagree with a
> full  width   search   of this particular   subtree.   The   null move
> assumption could very well be correct, and yet it's still possible the
> "null   move test"    methodology  is  not.   Do  you   understand the
> difference?  The point is that it's a question of resource management.
> Does a null move followed by a reduced  depth search, save enough time
> and   simultaneously provide a reliable    lower bound to the  current
> context of  the search?

Really good question! It is possible for null-move searching to provide
a lower bound that is so "loose" that you do not obtain any alpha-beta
cutoffs from it. The efficiency of null-move depends greatly on the
chance that a move will be cut off.

On the other hand, another aspect of the odds are greatly in your favor:
the branching factor is so high that null-search costs very little. It
follows
that even a low rate of cutoffs will prove useful.

You'll have to try it!

Brian Sheppard