Re: computer-go: Alpha-Beta Search

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 03:14 PM 11/18/99 -0500, you wrote:
>
>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.  

See nullmove as a very human way to see things:
  "i'm having a good position,
   does my opponent have some threats (either positionally or tactical)
   that can stop me?"

The reduction factor *can* be a problem. Obviously humans have less
depth limitations than computers. That's why i suggested a selective
search *anyway* after a nullmove, and a selective search anyway
at any leaf for GO.

The advantage of this powerful nullmove is however that
the branching factor gets a lot closer to the 'branching factor' of
a human, which was estimated in chess by De Groot at 1.76 for professional
players.

Greetings,
Vincent

>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

Nullmove doesn't have zugzwang problems with double nullmove in chess. 
Nullmove is now a correct form of searching, with this note that sometimes
you need a few ply more compared with fullwidth search, though still
the nodes needed might be a lot less.

>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
>
>
Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---
... en verder ben ik van ben ik van mening dat Dap het gesticht in moet