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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

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