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

["Xu, Mousheng (SEA)" <Mousheng.Xu@xxxxxxxxxxxxxxxxxxxxx>]

Folks,
 
Got it with the excellent help of Patrick. 
 
Thanks.
 
-- Mousheng Xu

-----Original Message-----
From: Xu, Mousheng (SEA) 
Sent: Friday, April 13, 2001 12:18 PM
To: 'computer-go@xxxxxxxxxxxxxxxxx'
Subject: RE: computer-go: [Question] Alpha-Beta Pruning & Null Move



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