Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Minimax chooses the move that maximises our own utility while assuming the opponent minimises it (the opponent plays just as well). It maximises the minimum gain, or equally minimises the maximum loss.
Three Steps
- Generate the whole game tree down to the terminal states
- Calculate utilities:
- assess the utility of each terminal state
- at a MIN node take the minimum of its children, at a MAX node the maximum
- repeat up the tree until the root is reached
- At the root, pick the move with the highest value
Example 1
MAX at root A with moves , each leading to a MIN node:
| MIN node | Leaf utilities | MIN value |
|---|---|---|
| after | 3, 12, 8 | 3 |
| after | 2, 4, 6 | 2 |
| after | 14, 5, 2 | 2 |
Root value , so MAX plays . contains the best leaf (14), but MIN would never allow it.
Example 2
MAX root A, MIN nodes B (leaves E = 9, F = ), C (G = 0, H = 0, I = ), D (J = , K = ):
- B
- C
- D
- A , so MAX picks C and MIN answers with I
Imperfect Decisions
With no time limit minimax makes perfect decisions. For real games (chess, about positions) the full tree is impossible, so two changes are made:
- replace the utility with an evaluation function that estimates the expected utility from a position (e.g. material balance in chess)
- search only part of the tree: replace the terminal test with a cut-off test, such as a depth limit
Alpha-Beta Pruning
Not in the lecture slides, but the standard speed-up for minimax. Keep (best value MAX can guarantee so far) and (best value MIN can guarantee so far), and stop exploring a node once it cannot change the decision.
In Example 1, after gives 3, the first leaf under is 2, so that MIN node is worth at most 2 < 3. Its other leaves (4, 6) are skipped. The result is the same as minimax, with fewer nodes searched.
def minimax(node, is_max):
if node.is_terminal():
return node.utility()
values = [minimax(c, not is_max) for c in node.children()]
return max(values) if is_max else min(values)Minimax handles an opponent. Handling chance and long sequences of decisions leads to Maximum Expected Utility.