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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Tristan,

Your description is  a good description  of what null  move pruning is
all about.  Slightly   more precise is to    say, "if I  am not  happy
playing 2  moves in a row, I'm  not going to look  at  anything at all
from this position."

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.

Don


   From: "Tristan Cazenave" <cazenave@xxxxxxxxxxxxxxxxx>
   References: <200104211200.OAA31828@xxxxxxxxxxxxxxxxx>
   Date: Sat, 21 Apr 2001 23:30:34 +0200
   MIME-Version: 1.0
   Content-Transfer-Encoding: 7bit
   X-Priority: 3
   X-MSMail-Priority: Normal
   X-Mailer: Microsoft Outlook Express 5.00.2919.6700
   X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6700
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain;
	   charset="iso-8859-1"
   Content-Length: 641

   > 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.

   In my opinion, Null move is rather: it is useless to try to live with one move,
   if I cannot live by playing two moves of the same color in a row.

   In my experiments, Null move enables to speed up by a factor of two
   capturing problems search.

   Any other one has measured the usefulness of Null Move
   in their programs ?

   Tristan.