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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   From: "Thomas Thomsen" <thomas@xxxxxxxxxxxxxxxxx>
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx

   Don Dailey wrote:
   >The tricky part is defining "happy."   Fortunately, "happy" has a very
   >precise definition.  It simply means that given 2  moves in a row, can
   >I achieve a score good enough to achieve at  least my expectation?  If
   >you  can, you are  "happy."   In a  losing position, you  can still be
   >"happy"   given  this    definition   because  you   expectations  are
   >appropriately lowered!    Your "expectation" is  the  "alpha"  part of
   >"alpha/beta pruning" or put another way your proven lower bound.

   Regarding null-moves, I think it helps to distinguish between two kinds of
   applications: (a) uniform search trees, and (b) non-uniform search trees.

I'm not  clear  on the definition of   uniform.  I thought   it was an
idealized tree with the same branching factor AND  fixed depth.  Go is
not this  nor is chess.  In  Go, you might  imagine  using fixed depth
search but I don't see that making any difference for this discussion.

   (a) In Go, the global evaluation function produces a typical uniform search
   tree with an average branching factor of, say, 250. As pointed out, "good"
   and "bad" depends on the context (in alpha-beta terminology: the values of
   alpha and beta). Regarding the global evaluation function, null-move pruning
   only starts to be meaningful when this tree is searched to depth 5 plies or
   more (remember that the null-moves are searched with a depth-reduction of
   2-3 plies).

Null-move  prunning  is meaningful   with a  2   ply search.   A depth
reduction factor of 2 or 3 plys would make the reductions happen after
1 move and call  for a null move followed  by a negative depth  seach!
Since you cannot do a negative ply search, you round up to the closest
thing, zero ply.  In   other words, when you   are this close to  leaf
nodes you are reduced to assuming that whoever  is on the move, can at
least hold the currently calculated static score.  This also means you
can take cutoffs on the 2nd ply  if the score  for the side to move is
already above beta (or his  upper bound expectation)  which in GO,  is
probably reasonable given the assumption that  it never hurts to be on
the move!

This may be a horrible thing, I don't know.  I'm  only saying that the
algorithm is intact.

In Chess, you deal with the same exact situation, and programs benefit
even with 2 ply searches, although the benefit is minor.  But in Chess
this   case becomes  a  quies search  on  the  final  ply with  colors
reversed.

My own chess programs use  a different approach.   Although I don't do
null move  pruning this  close to  leaf nodes,  I do something roughly
equivalent, a static exchange evaluator is  applied when the null move
depth would be zero or less.  What I do is just an optimization, using
a purer form of null move is perfectly valid.

I don't know if global  null move will ever  be useful in Go.  As I've
said before, it's not hard for me to imagine that it might now work so
well in Go.  It will produce severely prunned  trees however, there is
absolutely no question about that. 

I am interested   myself in knowing  if it  "works" and   maybe I will
explore this myself  at some  point.  To me   it "works" if it  can be
shown to be better with  global searching than global searching  would
be without  null move prunning.   I  wouldn't be  trying to prove that
global searching works if I did this, only if null move prunning HELPS
global searching.

Don




   (b) However, for local tactical searches, non-uniform search trees are
   abundant. The goal of killing a block or connecting two blocks produces a
   typical non-uniform search tree, because after the block gets taken off the
   board or the two blocks are connected, the local game ends. Such
   non-uniformity is highly exploitable by null-move techniques.

   For instance, in the context of a ladder, the attacker only plays moves so
   that -- if the defender passes -- the attacker can follow up by taking the
   stones off the board. That produces a search-tree of threat-order 1. What
   I've been fumbling with is that this idea can be generalized to any
   threat-order (so-called lambda-order). For instance, in a loose ladder
   (threat-order 2), the attacker only plays moves so that -- if the defender
   passes -- the attacker can follow up by killing the stones in a normal
   ladder. And in a loose loose ladder (threat-order 3), the attacker only
   plays moves so that -- if the defender passes -- the attacker can follow up
   by killing the stones in a loose ladder. And so on. This saves an enormous
   amount of work, but still guarantees exactness.

   Note that (b) doesn't operate with alpha's and beta's. This is because
   obtaining the goal is thought of as an irreversible feat: if a block can be
   captured in 5 plies, there is no risk of it being de-captured when looking a
   few plies deeper. Similarly, if a block is connected, it cannot be
   de-connected deeper in the search tree. However, (a) is different. It may be
   possible to achieve a very good evaluation at depth 5 plies, but no matter
   how good the evaluation value is, nothing can guarantee that the result is
   not reverted when looking a few plies deeper.

   Best regards,

   -Thomas Thomsen