Re: computer-go: [Question] Alpha-Beta Pruning & Null Move

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

The very best practical article I've ever seen on NULL move pruning is
an article by Donninger a few years ago in the ICCA journal:

  Donninger, C. (1993). 

  Null Move and Deep Search: 
     Selective-Search Heuristics for Obtuse Chess Programs. 
  ICCA Journal, Vol. 16, No. 3, pp. 137-143. (A) 


Null  move  pruning  was designed  with  Chess  in mind,  and   is not
appropriate for   some games, but  may  very well be   appropriate for
others.

To  have any chance,  a  game must have  the characteristic  that it's
rarely if ever a disadvantage to be on the move.   It works quite well
for chess and certainly qualifies as  one of the few truly significant
breakthrough ideas.  Go also   has this characteristic, even  more  so
than Chess.  That doesn't prove it would be effective in Go however.

A game must have one other characteristic.  Giving up a move must be a
serious enough disatvantage, that   even a reduced depth search  would
expose this.  I could easily believe that this might  not work for GO,
but the truth is I just don't know.

I can give you  the basic null move algorithm  in just a few words and
cut through the mystique.  It's a simple idea:

  At any node in the search tree, where the remaining depth of search
  is d,  do a search where the first move is a pass and the depth is
  reduced to d-n.   n can be 2 or 3 or whatever gives good results.
   
  The score that is returned is treated like a lower bound, which means
  it may even produce a beta cutoff.

  The depth must be reduced in the "null move test" or it's no faster
  than doing the original search.   	

  I am leaving out many details and enhancements.  I will elaborate
  if anyone is interested, but the article I quoted says it much 
  nicer. 


The nice thing about NULL move is that it's recursive, and can recover
from errors as  you search  deeper.  In chess,  null move  can make it
take  an extra ply or   two to see some  tactics  because of long term
threats that   the reduced search  might not  quite  get to.   But the
tactic will still  be seen  on  some later iteration, and  often still
faster than a full width search would have noticed it.

Null move is just a kind of  lower bound test.  If you  can think of a
good test that returns a lower bound on the  score and is rarely wrong
(at least in the context of what the search  is likely to return) then
you have something than can substitute for null move.

Actually,  I think all  the good programs  use  such bounds test.  The
test they use  is extremely simple but effective.   They assume that n
liberties is safe!  This is nothing more than a simple bounds test.

I'm guessing that these programs use only 2  scores to do the tactical
searches, whether the string is won or  not.   If not, this is probably
an  enhancement.    But  the point  is   that bounds  test   has to be
particularly  effective because it would  always produce a cutoff when
it was successful.


Don




   From: "Thomas Thomsen" <thomas@xxxxxxxxxxxxxxxxx>
   Date: Sun, 15 Apr 2001 09:56:17 +0200
   MIME-Version: 1.0
   Content-Transfer-Encoding: 7bit
   X-Priority: 3
   X-MSMail-Priority: Normal
   X-Mailer: Microsoft Outlook Express 4.72.3110.5
   X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain;
	   charset="iso-8859-1"
   Content-Length: 694

   Mousheng Xu wrote:
   >I cannot find any good references on the Web about null
   >moves. Does any one here has a pointer?

   Regarding null-moves and alpha-beta in general, take a look at the articles
   of Ernst A. Heinz. For instance:

   - Heinz, E.A. (1999). Adaptive Null-Move Pruning. ICCA Journal. Downloadable
   from: http://supertech.lcs.mit.edu/~heinz/node17.html .

   Regarding null-moves for obtaining exact results in binary search trees
   (including kind of a "theory" of null-moves), you might also want to take a
   look at:

   - Thomsen, T. (2000). Lambda-search in game trees - with application to Go".
   CG2000 conference. Downloadable from: www.t-t.dk/publications .

   Best regards,

   -Thomas Thomsen