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
For this option you should do the following:
See also
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
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.