Re: computer-go: Alpha-Beta Search

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Brian, 

Thanks for the reply!


> > 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.

Actually, I didn't have too much doubt  about this, but still I didn't
want people to  be too dogmatic about it.   I am more concerned  about
the next issue I rasied, the validity of the "null move test."



> 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.


Actually, I  am thinking of the  degradation in search quality  of the
reduced depth search.  In chess, if  you pass, that  is such a serious
handicap that you can be quite sure that even the reduced depth search
will return  a score that  is  bounded pessimistically.   Will this be
true in GO?  That's the  question I am  asking.  I think this question
is somewhat independant from the null move assumption question.  

I think even in chess this breaks down somewhat.  People always assume
that null move  pruning in chess endgames  is a problem mainly because
of "zugzwang",  where it's actually beneficial  to pass.   But I think
that  is  minor  compared to the   fact  that reduced depth  searching
progressively throws  away long term  threats, which is a  much bigger
issue in endgames than in middlegames.  An  example of this is that in
king and  pawn endgames,  moving  the king   one square  closer to  an
undefended pawn on   the other side  of the  board might   be a lethal
threat,   but  one that   is not  resolved  without   a several ply of
searching.  And  null move with  serious depth reduction  makes this a
serious problem.  I  am thinking that go is  more like  chess endgames
than it is  like chess middlegames.   If this is  true, then null move
pruning may not have  the positive effect  on program strength that we
would like it to!

Having  said that,  I basically feel   that null move pruning probably
will work ok for go, I am just not ready to assume this quite yet!



> You'll have to try it!

I intend to eventually, but I have to find the time first!


> Brian Sheppard

- Don