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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

max           [ 7 ]                  [    ]

             /  |  \            /  |   |   |  \   \

min       (7) (8)  (9)        (1) (2) (3) (4) (5)  (700)


Since I don't understand your diagram, I'll have to do my own.

This represents a 2  ply search.  After  the first player  (max) plays
his  first  move the opponent  has   3 choices, and   since he  is the
minimizer will choose the score 7.

Now at  this point, the first player  already has  established a lower
bound.    He knows that by   playing the first move,   he can get a 7.
Perhaps he can do better, but if push comes to shove, he can fall back
on this.

The  magic of  alpha  beta is  that once   we know what   score we are
guaranteed (even in the worst case), we do not have to worry about ANY
nodes where the score is  shown to be worse.   In the diagram We don't
really  care about 2, 3, 4,  5 or 700 because  we know  that we cannot
allow the opponent to get 1.

In my crufty diagram, there are 9 leaf nodes, but an alpha beta search
will only look at 4 of them.

By the way,  the second player in  my diagram also establishes his own
bounds too, and together,   at any point we  have  2 bounds from  each
players point of view, and upper bound and a lower bound.  If any node
is found to be outside of this, you can immediately drop it.

I hope that helps.


Don
        







   From: "Xu, Mousheng  (SEA)" <Mousheng.Xu@xxxxxxxxxxxxxxxxx>
   Date: Fri, 13 Apr 2001 12:18:01 -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: 1753

   Don & David,

   First, let me tell you how I understand alpha-beta pruning. Normally,
   alpha-beta pruning applies to minimax trees, right? For example, given


   Max            7

		/    |     \

   Min        7       6        3  

		/  |  \  /  |  \  /  |  \   

   Max    9 8 7 6 5 4 3 2 1


   After you have visited leaves 9, 8, 7, the root value is set to 7. When you
   visit leaf 6, since 6 < 7, and you know every leaf at the same branch (i.e.,
   leaf 5 and 4) is smaller than 6, so you don't go evaluate 5 & 4. For the
   same reason, after you visit leaf 3, you don't visit leaf 2 & 1.

   Now the question is: without evaluating leaf 5 & 4, how do you know they
   have values < 6? Don mentioned to estimate a lower bound (& a upper bound?).
   Don, here do you mean to, for instance, estimate the values of all the
   leaves (6, 5, 4) have an upper bound of 6 without evaluating them
   individually? Well, if this is so, then I'd agree with you that this
   estimation is usually very unreliable in middle games. I don't know if this
   (estimating lower/upper bounds) is what Dave is doing as well. 

   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