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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Yes, much of  this is semantics, but  I'll explain why  the literature
refers to it as "null move pruning."   I completely agree however that
it could be called something like, "null  move candidate selection" or
something equivalent and still be valid.

As far as  I know, null move pruning  started with chess.  In chess we
started with full width searching.  When null move pruning came along,
it was  an attempt to  achieve the  same exact results  of full  width
searching but with much less effort.  In theory, a  10 ply search with
null move pruning should return the same score  and move that a 10 ply
full width  search would.   If it  doesn't,  the reason can   never be
because  something was  "selected"  or "extended",  it has  to be that
something was rejected or "pruned."

So semantically, it's quite awkward to view  this any other way.  In a
similar way, it's hard to view check extensions as "prunning."  We can
see that it  could be interpreted that  way, but it's a bit unnatural.
Since check  extensions increase  the effort  to  do a given  depth of
search, you could  say that a  10 ply search  with check extensions is
really a severely  prunned 20 ply search!   

This is  all a by product of  viewing "depth of  full width search" as
the metric by which we interpret everything  else.  Although this is a
very natural metric in chess, it is probably not  a very useful metric
in the computer Go  world, so this is definitely   not a criticism  of
your choice of terminology!

Don


   From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>
   Date: Thu, 26 Apr 2001 21:45:55 +0200

   I think it depends on your point of view whether you call it 'pruning' or
   not. I think an algorithm that selectively decides to extend some variations
   but not others could be called 'pruning' on any variation that didn't get
   extended.

   For this to work, I don't think it's necessary for the pruning search to be
   cheaper, as long as it reduces the total search effort had you searched each
   line equally deep. But in practice I do try to make the null move search
   cheaper of course. Often the fact that the search exceeds a certain
   (smallish) number of nodes is enough since if the opponent can make things
   complicated it's probably worth exploring that line a bit more anyway.

   I'm sure it's quite different from chess, since the whole point is that the
   extra move often DOESN'T return an overwhelming advantage which indicates
   the move would be better spent elsewhere.

   The actual implementation in Goliath is not so great and relies on quite
   some heuristics and fine-tuning as well. But I found that it plays better
   with than without, even though it weighs a bit on the performance.

   > -----Original Message-----
   > From: owner-computer-go@xxxxxxxxxxxxxxxxx
   > [mailto:owner-computer-go@xxxxxxxxxxxxxxxxx]On Behalf Of Don Dailey
   > Sent: Thursday, April 26, 2001 7:24 PM
   > To: computer-go@xxxxxxxxxxxxxxxxx
   > Cc: computer-go@xxxxxxxxxxxxxxxxx
   > Subject: Re: computer-go: [Question] Alpha-Beta Pruning & Null Move
   >
   >
   >
   > Hi Mark,
   >
   > It sounds like your algorithm uses null  move to prune but without the
   > depth   reduction   factor.  This probably   makes   sense in tactical
   > reading.  You are  essentially trying a null move  to see if a line is
   > worth persuing, and this will be much more  accurate than using static
   > pruning rules.  With  a tactical search  in Go, the  tree is very deep
   > with a  very low branching factor.   The point is that depth reduction
   > does not have much meaning in this context because your stopping rules
   > are not primarly  based on depth  (although you probably still have an
   > upper limit.)
   >
   > In  order to  be cheaper,   which would  be  neccesary to   rightfully
   > consider it a pruning algorithm, the null move search has to made very
   > cheap,  especially so if it doesn't  produce rich cutoffs.  Even if it
   > does it needs  to  be cheaper than  the search  you would normally  be
   > doing.  When  the null   move  search  fails,  it  just becomes   pure
   > overhead.
   >
   > It may be that you can take steps to  severely constrain the null move
   > search.  I'm sure you've experimented with this.  In chess, getting an
   > extra  move  is SO  overwhelming, that   it usually returns  something
   > optimistic even  with depth reduction.   With tactical reading you may
   > have  something like this with   some other constraints you might  not
   > normally consider.  I don't really know.
   >
   > Don
   >
   >
   >
   >
   >
   >    From: "Mark Boon" <tesuji@xxxxxxxxxxxxxxxxx>
   >    Date: Wed, 25 Apr 2001 17:38:09 +0200
   >
   >    Don's description of 'null move pruning' is what I thought it
   > would be. I
   >    used something similar in Goliath as one of the criteria to
   > stop reading
   >    certain variations. It had rather vague concepts of 'urgency' and
   >    'stability' to decide whether to (continue to)read in a
   > certain situation or
   >    not. The original driver was that static evaluation turned out
   > to be almost
   >    useless in situations that are not stable. So unstable
   > situations had to be
   >    read further. One of the ways to determine whether a situation
   > was stable
   >    was to allow one side to move twice and see if it would lead to an
   >    unacceptable result for the side that 'passed locally', taking
   > into account
   >    the average value of a move for the side that 'passed'.
   >
   >    I wouldn't know how to measure the speed-up. For my program it actually
   >    caused it to slow down considerably, because it would do much
   > more reading
   >    in variations the static evaluation would have given up. Plus that the
   >    situation after the two moves in a row by one side might still
   > not be stable
   >    and therefore need more reading. But for the accuracy of the
   > reading it was
   >    a great improvement. This method for determining whether a
   > situation was
   >    stable or not was always a last resort. If you can do it by
   > heuristics it is
   >    preferable since it saves a lot of time. The difficulty was to
   > find a good
   >    balance for the heuristics.
   >
   >    In tactical reading, a pass is also sometimes allowed but I
   > wonder if it can
   >    be regarded as a null move. It is used to prevent one side of
   > being forced
   >    to play and actually make his position worse because the only moves
   >    available to him are filling his own liberty or filling his own eye.
   >
   >    One of the best usages of null moves I find in the endgame.
   > Sente moves are
   >    generally doubled in value. To find out if a move is sente,
   > try moving twice
   >    and see if the result gets doubled or more.
   >
   >    Does anyone actually have experience with making a program play endgame
   >    properly? I have briefly looked into it using brute-force in a local
   >    situation, but wasn't very successful. What I wanted for example is a
   >    program to be able to see that the value of a gote move would
   > be higher than
   >    evaluated if it could be followed up by a profitable sente
   > sequence. This is
   >    a very basic technigue that even most kyu players master, but it seems
   >    surprisingly difficult for programs. A slightly more sophisticated
   >    technigue, which I also thought to be easy for computers, is
   > to evaluate
   >    what gote moves either side can make locally, see which side
   > can make the
   >    bigger move and award that side half of the difference. (For
   > example, if
   >    black cannot make any points, but white can make two points,
   > evaluate it as
   >    one point for white.) After a months worth of work the results
   > were still
   >    very poor so I wondered if anyone else tried.
   >
   >        Mark
   >
   >
   >
   >