Author: Scott Gasch
Date: 15:51:18 08/01/99
Go up one level in this thread
Alpha beta search is a type of depth-first recursive move tree search
that takes advantage of the minimax principle to prune branches of
the tree that cannot influence the evaluation.
That's a mouthful. To understand it you need to understand some
background ideas. The first is that of a move tree. Consider a chess
position where it's white's turn to make a move. Imagine that white
has only two legal moves to make at this point in the game. The two
subsequent positions can be represented as "children" of the original
positions in a tree:
position_1
/ \
/ \
child_1 child_2
Of course now it's black's turn to move. Imagine that at position
child_1 black two moves also. This forms yet another level on the
tree... and so on. Positions where one side has no moves are either
checkmates or stalemates. These are "leaf nodes" in our tree
(i.e. nodes with no children).
Now that you understand a move tree let's look at the purpose of the
ab search again. It is a move tree searcher that evaluates nodes on
the tree. To evaluate a node just means to assign a score to it.
Imagine a function S(n) which, given a position, n, will return a
number based on which side is winning in this position. It returns
positive numbers if white is winning and negative numbers if black is
ahead. The larger the absolute value of the score, the more the side
in question is winning. A score of +/- INFINITY is assigned to a
position where white/black has won the game.
Now assume that we have a node with several children and we know the
scores for all the children. If it is white's turn to move at this
node he will move to the child that has the greatest score (this is
called a "max node"). If it's black's turn he will move to the child
that has the lowest score (a "min node"). Thus, the value of this
node is either the greatest or the least of all the successors
(depending on whose move it is).
So an unoptimized minimax search will recursively traverse the move
tree depth first and assign values to every node at height x. Then,
knowing the values of all nodes at height x, we can get the values at
x-1, and so on up to the top of the tree.
However, this approach turns out to be very slow because the
"branching factor" (number of children nodes from a given position) in
chess is about 35. That means in a tree only four levels high there
are about 35^3 or 42000 nodes. At six levels deep that number
balloons to 52521875 nodes! Considering so many nodes takes a lot of
time!
It turns out, though, that you do not have to consider all these nodes
in order to get a value at the top level node (root node). Why?
Because since you know that white will always play the best move he
can and black will do the same, it is possible, using an ab search, to
narrow the search by not considering branches of the move tree that do
not affect the top level score.
Here's a quick example of ab search in action. I'd suggest that you
take a look at some pseudo code and trace out your own examples on
paper if you are interested in this... this is the best way to get a
good understanding of the concept.
a - white's move
/ \
b c - black's move
/ \ / \
d e f g - white's move
/\ /\ /\ /\
h i j k l m n o - black's move
We want the value of a. To get that we need the values of b and c.
To get the value of b we need the values of d and e. To get d we need
h and i. So we have reached our "depth" and we get the value of h by
running our score function, S(h). It returns -500 -- a pretty "good"
score for black. S(i) is -220. Not as "good". Remember that since
it's black's turn at node d the value of d is the lowest of it's
children. So the value of d gets -500.
Next we evaluate e. However, to get its value we need the values of j
and k. So run S(j) and it returns -1000! Wow, that means that the
value of node e is at least -1000, maybe even worse (lower). If we
compute the value of node k we can figure out the exact value of e --
since e's value will be the min(j, k). But why bother? We already
know that node b will be the greater of d and e. And after running
the S(j) we already know that e < d. So we do not need to waste time
on running S(k) at all. The value of b will be the value of d!
Now, most people do not do it this way in real chess programs. The
score function S(n) will return a "relative" score. That is, S(n)
will be positive if whoever's turn it is to move at n is winning and
negative if the side to move is losing. Why do they do this? Because
it makes writing the ab search function easier. Instead of having min
nodes and max nodes and a seperate search routine for each you can now
have one search routine and when you recurse say:
MakeMove(pos, move);
value = -ab(pos, -beta, -alpha, depth - 1);
UnmakeMove(pos, move);
...
This kind of alpha beta search is sometimes called a NegaMax search.
Also, in real chess programs we care about moves, not values.
However, a move and value are intertwined. For example, in the above
tree when node d got a value of -500 it really got a value of (-500,
d->h). Likewise value of b = (-500, b->d->h). In my chess program I
return MoveValue structs which hold a score and a linked list of moves
from my search routine.
There are many improvements to the alpha beta search -- like
aspiration search and NegaScout (PV search). But the first step is to
understand ab. Hope this helps you with that goal. :)
Scott
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.