Re: computer-go: [Questions] Null Move

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: "Mousheng Xu" <moushengxu@xxxxxxxxxxxxxxxxx>
   Date: Mon, 26 Nov 2001 10:47:16 -0800
   Mime-Version: 1.0
   X-OriginalArrivalTime: 26 Nov 2001 18:47:17.0242 (UTC) FILETIME=[C57595A0:01C176AA]
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; format=flowed
   Content-Length: 1231

   Some questions about Null Move:

   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.

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.

Since we are using negamax, what is beta for us is alpha for the child
and visa versa.   So we have to  swap positions in the parameter list.
But since the opponent also views our good as  his bad and visa versa,
we have to also negate the values.

So alpha  and beta get  swapped  and negated.   What would normally be
this:

	(beta-1,  beta)    ; our zero width window test search parameters

becomes this:

       ( -beta,  -(beta-1) )

get rid of the parenthesis and it becomes this:   (  -beta, -beta + 1 )




   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?




Don




   _________________________________________________________________
   Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp