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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Actually, this is  not what null move does  at all if you are  talking
about null move  pruning.  Null move pruning  is simply a technique to
estimate a  lower (or upper)   bound on the  score  that a tree search
would likely return.  It has to work with alpha/beta searches in order
to produce cutoffs.   And it's speculative, it  can give you incorrect
results but  at least in chess  it is so fast and  so reliable that it
easily compensates for the occasional errors.

I  guarantee that null move  pruning will prune  a huge portion of the
search tree in a global searching Go program,  and probably be correct
almost all of the time.  HOWEVER, any good pruning algorithm HAS to be
right "almost all" the time or it's useless.  The  only question in my
mind is how much  is "almost always"  in  GO and is   it enough to  be
useful?

It's very important how  you think about  algorithms like  this.  Null
move pruning is not about pruning "moves", it's about pruning sections
of the search tree.  The  pruning is based  on expectations set by the
alpha beta window.   You might prune after  playing the very best move
possible in some position but again, it's  not the move itself you are
pruning, it's really your evidence that this line won't meet some goal
established by  what has already  been discovered in the  search tree.
With null move pruning you don't  care (or even  know) which moves are
good or bad,  you only care which  positions it makes sense to explore
(just like alpha/beta pruning.)

There are silly approaches like looking at the n  best moves as judged
by some criteria (and completely  ignore the rest.)   I belive this is
almost  certainly doomed to  failure as  a  way to constrain a  global
search.  If you are using a search at all, you  are admitting that you
don't have the  ability  to  judge the quality   of moves   (which  we
probably all admit  we can't do very  well.)  And yet you are  judging
the quality of moves to speed up  the search.  These  are the types of
programs that may actually play worse with increased depth.


Don 



   Date: Sat, 21 Apr 2001 14:00:16 +0200
   X-Authentication-Warning: host1.webarna.es: Host 213-99-105-42.uc.nombres.ttd.es [213.99.105.42] claimed to be 213.99.105.42
   From: Joan Pons Semelis <joan@xxxxxxxxxxxxxxxxx>
   X-Mailer: ProxiMail version 1.0 Beta 2c for USR PalmPilot
	     URL: http://www.proxinet.com/
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text
   Content-Length: 393


   If I've understood correctly null-move will be useful mainly to prune the moves that are worst than pass.
   This really looks interesting in chess, but in go it's hard to have this kind of moves.
   And being usually of the type 
   "don't put your-self in atari"
   are easily avoided by more heuristical means.

   -- 
   Joan Pons i Semelis
    joan@xxxxxxxxxxxxxxxxx

   -- 
   Joan Pons i Semelis
    joan@xxxxxxxxxxxxxxxxx