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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

I don't really understand.  The whole idea of Alpha-beta pruning is to
look at a tiny fraction  of the leaf nodes.   You can use this saving,
which will be a  factor of thousands or  millions, to spend a thousand
or million times more time on the much fewer leaf nodes you visit.

Alpha beta can also save the actual  time of evaluating a single node.
This  is   accomplished by  knowing   how  much each   evaluation term
contributes to the whole  and only  calculating  terms that  have some
hope of making a difference.

Forget about  null move for  a second.  What  you want is an algorithm
that knows how to accurately estimate a lower bound on  the score.  If
you can do that a lot cheaper than the search you  would have to do to
ascertain this, then you can treat  this estimator as a reliable bound
and get "beta" cutoffs you couldn't normally get with alpha/beta.

That's what null move is.  Just a kind  of estimator.  It doesn't give
you a score, just a bound in one direction.

Go is the kind of game where the value of  being on the move is almost
always better than NOT being on the  move.  Therefore, null move would
probably work well  as  an estimator.   However, it's  still  far from
clear that null move makes any sense for Go, except perhaps in a local
setting like  string tactics.  Null move  is horizon weak and  that is
likely to  kill the idea for Go.    Even in Chess,  null move  is less
effective  in  end  games, which more   resemble  the game  of Go than
middlegames do  because of the   greater potential for  very long term
threats.  Null move is  a risk and does not  guarantee the same result
as  full width  searching,  it is  just  known to  be  extremely  cost
effective in the tradeoff.   In Go it may not work.

It's pretty difficult to look more than a  couple of moves deep in Go,
even with null move and alpha/beta pruning.  Most of the effort has to
be in understanding where  the search effort should  be spent and this
is  very  closely tied  with knowing   which  position is  better than
another.   Go programs are not very good at figuring this out. 

Most of the work I'm doing in Go is to identify with as much certainty
as possible,  which moves cannot be best.   I'm not trying to identify
good moves,  except  by this  process  of elimination.  I  haven't got
around to actually  looking at null move  pruning in Go,  but it's one
possibility in this direction.

I  don't view null  move  as a  threat detector,   although it can  be
formulated  that way or perform  that function.  It's more accurate to
say it identifies   the  places you can  stop  searching  because  the
opponent did something stupid.  So you can  use null move as a pruning
device, or as a threat detector.


Don






   From: "Xu, Mousheng  (SEA)" <Mousheng.Xu@xxxxxxxxxxxxxxxxx>
   Date: Thu, 12 Apr 2001 09:35:07 -0700
   MIME-Version: 1.0
   X-Mailer: Internet Mail Service (5.5.2653.19)
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain;
	   charset="iso-8859-1"
   Content-Length: 1325

   Dear all,

   I just don't see how alpha-beta pruning can save mentionable calculation.
   The most time consuming part is to evaluate the leaf nodes. With alpha-beta
   pruning, you still have to calculate every leaf node. I agree that
   Alpha-beta pruning can reduce tree size, which then can save some memory.
   But does it save calculation?

   Null moves not only applies to "pass"es, but also applies to local
   calculation. If you are focusing calculation around some local area, you may
   want to evaluate the cases when either you or your opponent chooses to play
   somewhere else. I cannot find any good references on the Web about null
   moves. Does any one here has a pointer?

   Thanks a lot.

   -- Mousheng Xu



   The information contained in this email is intended for the
   personal and confidential use of the addressee only. It may
   also be privileged information. If you are not the intended
   recipient then you are hereby notified that you have received
   this document in error and that any review, distribution or
   copying of this document is strictly prohibited. If you have
   received  this communication in error, please notify Celltech
   Group immediately on:

   +44 (0)1753 534655, or email 'is@xxxxxxxxxxxxxxxxx'

   Celltech Group plc
   216 Bath Road, Slough, SL1 4EN, Berkshire, UK

   Registered Office as above. Registered in England No. 2159282