Minimax and alpha-beta pruning for playing games such as chess or draughts

March 1999

Minimax is an excellent example of the difference between
• long, complicated but naive coding, in this case especially for the method that finds the list of valid moves for a particular player from a particular position, and
• short, subtle algorithms, in this case alpha-beta pruning.
For this option you should do the following:
• write the minimax algorithm
• adapt your tic tac toe exercise, adding the methods that minimax needs,
• list of valid moves for this player from this position,
• effect (new position) of this move for this player from this position,
and changing the main loop to call minimax for one of the players instead of prompting the user
• adapt a more complicated game (such as Connect Four) in the same way; for this you will need to cut off the game tree at a certain depth, and calling a "crude evaluation", which is another game-specific method;
• speed up the game with alpha-beta pruning.
• Sections 7.7 and 10.2 of Weiss's book,
• A. N. Walker's game theory notes, including alpha-beta pruning at Nottingham University.
• The bible of mathematical games is Winning Ways by E. R. Berlekamp, J. H. Conway and R. K. Guy (Academic Press, 1982); two large volumes, and rather expensive, but absolutely fascinating. Only a tiny fraction of the material is relevant to this module, but you will want to read it anyway. [This book was by 1997 out of stock at the publishers, though not out of print, so is becoming harder to find.] (That's what Walker says about it; minimax does not, I think, occur anywhere in this book, so it's not really relevant to this coursework option at all.)
Received wisdom has it that the "crude evaluation" of a position should be a very simple function. "How many different legal moves do I have?" is thought to be good enough. Complicated functions, with elaborate ways of scoring each square on a board, often turn out to be based on a mis-conception of the game. Any such function that depends on enumerating the possible moves is likely to be worse at winning the game than simply going one level further down the game tree with a simpler evaluation function.

Alpha-Beta Pruning

Alpha-beta pruning does not play any better moves: it just plays the same moves more quickly. Apparently, if used properly, it considers the square root of the number of positions than minimax alone would consider, so, since minimax is exponential in the depth, you can go twice as far down the game tree in the same time - and thereby play better moves.
The addition of alpha-beta pruning to an existing program that uses minimax does not involve very much extra code. You just need
• two extra arguments (traditionally "alpha" and "beta", but "floor" and "ceiling" are more informative names) to the minimax method,
• an adjustment to the initialisation of the maximum or minimum so far before the beginning of the loop,
• appropriate values of the two extra arguments in the recursive calls, and
• a test that breaks the loop early.
The descriptions of alpha-beta pruning by Weiss and Walker are game-theoretic and not, in my view, very clear from the point of view of the logical analysis of algorithms.
When the higher level calls
```   score = minimax (position, depth, floor, ceiling);
```
it's saying that, "whatever value you give me for the score, if it's bigger than ceiling I shall treat it like plus infinity, and if it's smaller than floor I'll treat it like minus infinity".
This means that (at our level) the "maximum so far" of the list is initialised to floor instead of minus infinity, and the loop breaks as soon as one of the recursive calls returns a value above the ceiling.
The maximum so far and the ceiling provide the floor and ceiling for the recursive call, except that, as they are for the other player, their roles are interchanged.
Think about this: the explanation that I have just given follows from the properties of the max(a,b) function: if ba, so max chooses a instead of b, then it doesn't matter how small b is - it might as well be minus infinity.
To take advantage of alpha-beta pruning, the method that lists the available legal moves from any given position must put the best moves (on the basis of naive principles) first. For example, in chess or draughts, you would consider taking an opponent's piece before any other move, and would prefer to queen an advanced pawn instead of moving one on the back rank. Of course, such a move may be a trap, but it's minimax's job to find that out!

This is www.PaulTaylor.EU/algorithms/minimax.html and it was derived from algorithms/minimax.tex which was last modified on 31 December 2007.