Minimax

  MIN of [3, 12, 8]     =  3
  MIN of [2, 4, 6]      =  2
  MIN of [14, 5, 2]     =  2
MAX of [3, 2, 2]      =  3

minimax value of the root: 3
terminals examined: 9 [3, 12, 8, 2, 4, 6, 14, 5, 2]

so MAX plays the FIRST branch, and can guarantee at least 3

All nine terminals were examined, in left to right order. That is the fact the next chapter attacks: two of those nine could not possibly have changed the answer, and alpha-beta pruning is the observation that says which two.

Why the traversal is depth first

The recursion above reaches a leaf before it evaluates anything, which is depth first order, and that is not an accident of the code.

A MAX node's value needs all its children, so the whole subtree under each child must be finished before the parent can report. Depth first order finishes subtrees in the order they are needed and holds only the current path plus the siblings at each level, giving space O(b*m).

Breadth first order would be useless here. Minimax has no early exit of its own: the answer is not found when a good leaf is met, it is found when the last subtree reports. So there is nothing to gain from examining shallow nodes first and a great deal of memory to lose.

Its properties

O(bm) is the sentence that kills it on a real game**, and the figures are in Games as Search: Shannon's 30 legal moves and 40 moves of play give about 10 to the power 120 nodes. Minimax on a full chess tree is not slow, it is impossible. The two repairs are the subject matter of the rest of the topic.

The two repairs

Both are needed and they are independent, which is worth saying because students often think alpha-beta is what makes chess programs possible on its own. It is not.

Cut off the depth and evaluate. Replace TERMINAL(s) with a test that also stops at a fixed depth, and replace UTILITY there with an evaluation function estimating who is winning. This changes the answer from exact to approximate and is what makes any game program possible at all.

def minimax_cutoff(node, depth):
    if TERMINAL(node) or depth == 0:
        return EVALUATE(node)
    if PLAYER(node) is MAX:
        return max(minimax_cutoff(child, depth - 1) for child in children)
    return min(minimax_cutoff(child, depth - 1) for child in children)

Prune. Do not examine nodes that cannot affect the answer. This changes the work and not the answer at all, which is why it is the more elegant of the two and why it has its own chapter.

A program with a cutoff and no pruning reaches a shallow depth and plays weakly. A program with pruning and no cutoff still cannot finish. Chess programs use both, and Games as Search records Shannon's own third idea, quiescence, as the refinement of the first.

The three-player case, and why MU's algorithm stops at two

Brief, because a paper can ask whether minimax generalises. It does, and the generalisation is instructive.

With three or more players, a single number no longer suffices: each node must carry a vector of utilities, one per player, and each player maximises its own component. The game is generally no longer zero sum, alliances become rational, and the pruning of the next chapter largely stops working because a bound on one player's value says little about another's. So the two-player zero sum restriction in MU's label is doing real work, not simplifying for convenience.

Distinctions

What it does not mean

Minimax does not predict the game. It computes a guarantee under optimal opposition. A weak opponent gives MAX more than the minimax value.

MIN is not maximising a second number. Because the game is zero sum, minimising MAX's value is the whole of MIN's objective.

It is not a search for a good move by trial. It is an exact computation of a value, from which the move follows.

It does not stop when it finds a winning leaf. A MAX node cannot report until every child has reported, so a win at the first leaf proves nothing until the siblings are known. That is precisely what alpha-beta pruning changes.

The values on the leaves are not scores of the position in play. They are utilities of finished games. Numbers estimating an unfinished position come from an evaluation function, which is a separate idea.

Quick revision

• Minimax value: the utility reached under optimal play by both sides. Terminal: the utility. MAX node: the maximum of its children. MIN node: the minimum.
• All values are from MAX's point of view; zero sum is what allows one number.
• On the standing tree the three MIN nodes are worth 3, 2 and 2, and the root is 3. MAX plays the first branch and is guaranteed at least 3.
• A guarantee, not a prediction. A blundering MIN gives MAX more.
• Nine terminals examined, left to right. Two of them could not have changed the answer, which is the next chapter.
• Depth first traversal, because a node needs every child before it can report. Time O(b**m), space O(b*m).
• O(bm) makes full chess impossible: about 10 to the power 120 nodes. Two independent repairs: a depth cutoff with an evaluation function, which makes the answer approximate, and pruning**, which does not change the answer at all.
• Three or more players needs a vector of utilities per node, is generally not zero sum, and largely defeats pruning.

Test yourself

1. Define the minimax value of a node in all three cases. At a terminal node it is the utility to MAX. At a MAX node it is the maximum of the minimax values of its children. At a MIN node it is the minimum of them.

2. Compute the minimax value of the standing tree and say which move MAX plays. The three MIN nodes take the smallest of their terminals, giving 3, 2 and 2. The root MAX takes the largest of those, which is 3. MAX plays the first branch.

3. What does the value 3 actually guarantee? That by playing the first branch MAX finishes with at least 3 whatever MIN does, and that no other move guarantees more, since MIN can hold both remaining branches to 2.

4. Why does minimax not stop as soon as it finds a good leaf? Because a MAX node's value is the maximum over all its children, so it cannot be reported until every child has reported. A good leaf in the first subtree says nothing until the others are known. Pruning is the separate observation that some of them need not be examined.

5. Give minimax's time and space complexity and say why the time figure matters. Time O(b**m) and space O(b*m). The time figure matters because on chess, with about 30 legal moves per position and about 40 moves of play, it means of the order of 10 to the power 120 nodes, so the full computation is impossible rather than merely slow.

6. Name the two repairs and say precisely what each changes. A depth cutoff with an evaluation function, which stops the search early and estimates the value of the position reached, changing the answer from exact to approximate. And pruning, which avoids examining nodes that cannot affect the result, changing the amount of work and not the answer at all.

7. Why does MU's label restrict adversarial search to two players, and what breaks with three? With three or more players each node needs a vector of utilities, one per player, and each player maximises its own component. The game is then generally not zero sum, alliances can be rational, and a bound on one player's value tells you little about another's, so alpha-beta pruning largely stops working.