[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: computer-go: [Question] Alpha-Beta Pruning & Null Move
Got it. Thanks, Don.
-----Original Message-----
From: Don Dailey [mailto:drd@xxxxxxxxxxxxxxxxx]
Sent: Friday, April 13, 2001 3:31 PM
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: Re: computer-go: [Question] Alpha-Beta Pruning & Null Move
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