MiniMax with Alpha-Beta Cutoff [References]
We are considering two-player, perfect information games. The two players
take turns and try respectively to maximize and minimize a scoring
function. The two players are called respectively MAX and MIN.
We assume that the MAX player makes the first move. We represent the game as a
tree where the nodes represent the current position and the arcs represent
moves. Since players take turns, successive nodes represent positions where
different players must move. We call the nodes MAX or MIN nodes depending
of who is the player that must move at that node.
A game tree could be infinite.
The leaves may represent either terminal positions, i.e. positions where
MAX wins (score: +infinity) or MIN wins (score: -infinity), or a position for
which we have an estimated score. The ply of a node
is the number of moves
needed to reach that node (i.e. arcs from the root of the tree). The
ply of a tree is the maximum of the plies of its nodes. [There
are interesting observations by Pearl on the interaction
of ply and errors in the case of game trees with estimated scores.]
The MINIMAX GAME STRATEGY for the MAX (MIN) player is to select the move
that leads to the successor node with the highest (lowest) score. The scores
are computed starting from the leaves of the tree and backing up their scores
to their predecessor in accordance with the Minimax strategy.
The problem with this strategy is that it explores each node in the tree.
function MINIMAX(N) is
begin
if N is a leaf then
return the estimated score of this leaf
else
Let N1, N2, .., Nm be the successors of N;
if N is a Min node then
return min{MINIMAX(N1), .., MINIMAX(Nm)}
else
return max{MINIMAX(N1), .., MINIMAX(Nm)}
end MINIMAX;
ALPHA-BETA cutoff is a method for reducing the number of nodes explored
in the Minimax strategy. For the nodes it explores it computes, in addition
to the score, an alpha value and a beta value.
- ALPHA value of a node
- Initially it is the score of that node, if the node is a leaf, otherwise
it is -infinity. Then at a MAX node it is set to the largest of the scores
of its successors explored up to now, and at a MIN node to
the alpha value of its predecessor.
- BETA value of a node
- Initially it is the score of that node, if the node is a leaf, otherwise
it is +infinity. Then at a MIN node it is set to the smallest of the scores
of its successors explored up to now, and at a MAX node to
the beta value of its predecessor.
It is guaranteed that:
- The score of a node will always be no less than the alpha value
and no greater than the beta value of that node.
- As the algorithm evolves, the alpha and beta values of a node may change,
but the alpha value will never decrease, and the beta value will
never increase.
- The alpha value of a node is never less than the alpha value of its
predecessor.
- The beta value of a node is never greater than the beta value of its
predecessor.
- When a node is visited last, its score is set to the alpha value of that
node, if it is a MAX node, otherwise it is set to the beta value.
function MINIMAX-AB(N, A, B) is
begin
Set Alpha value of N to A and Beta value of N to B;
if N is a leaf then
return the estimated score of this leaf
else
if N is a Min node then
For each successor Ni of N loop
Let Val be MINIMAX-AB(Ni, Alpha of N, Beta of N);
Set Beta value of N to Min{Beta value of N, Val};
When Beta value of N <= Alpha value of N then exit loop;
Return Beta value of N;
else
For each successor Ni of N loop
Let Val be MINIMAX-AB(Ni, Alpha of N, Beta of N);
Set Alpha value of N to Max{Alpha value of N, Val};
When Alpha value of N >= Beta value of N then exit loop;
Return Alpha value of N;
end MINIMAX-AB;
The MINIMAX-AB function is called with as parameters the root of the game
tree, -infinity as alpha value, and +infinity as beta value.
Here is an example of Alpha Beta Cutoff.
References
Nillson,N.J.: Principles of Artificial Intelligence
Tioga Publishing Co. 1980 Pages 112-125
Rich,E.,Knight,K.: Artificial Intelligence
McGraw-Hill, 1991 Pages 307-319
Luger,G.F.,Stubblefield,W.A.: Artificial Intelligence: Structures
and strategies for complex problem solving, Second Edition
The Benjamin/Cummings Publishing Co. 1993 Pages 137-145
Norvig,P.: Paradigms of Artificial Intelligence Programming
Morgan-Kaufmann, 1992 Pages 596-626
Pearl,J.: Heuristics
Addison-Wesley, 1984 Pages 332-360
ingargiola@cis.temple.edu