Minimax and alpha-beta pruning
for playing games such as chess or draughts
Paul Taylor
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.
See also
- 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 b ≤ a, 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.