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