Minimax
- Algorithms course
- Expert
- Lesson 31/41
- 4 min
Minimax value in a game tree.
Minimax
Minimax is an algorithm that finds the optimal move in two-player zero-sum games. In the game tree, the max player tries to maximize gain while the min player tries to minimize the opponent's gain.
Leaf nodes have known values. At internal nodes, the next player picks the max or min of children.
The algorithm is recursive and scans the whole tree up to depth d; complexity is O(b^d).
Minimax recursion
Minimax works recursively: at each internal node, the next player selects the max or min of children's values.
minimax(node, is_max): if the node is a leaf, return its value; otherwise compute children's minimax and apply max or min.
The two players alternate; therefore is_max flips at each level.
Practice minimax function
Write minimax(node, is_max). node is a nested list; a leaf is an integer. The max player picks the largest, the min player the smallest. Print 3 with print(minimax([[3, 5], [2, 9]], True)).
Starter code
def minimax(node, is_max):
# Simple minimax valueSample solution
def minimax(node, is_max):
# Simple minimax value
if not isinstance(node, list):
return node
if is_max:
return max(minimax(child, False) for child in node)
return min(minimax(child, True) for child in node)
print(minimax([[3, 5], [2, 9]], True))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the max player's goal?
if is_max:
return max(values)- To please the opponent
- To shrink the tree
- To increase speed
- To maximize gain Correct answer
Explanation: The max player aims to maximize gain.
2 max branch
if is_max:
return ____(minimax(child, False) for child in node)if is_max:
return max(minimax(child, False) for child in node)Explanation: The max player picks the largest value.
3 Minimax concepts
| Term | Meaning |
|---|---|
max player |
Maximize |
min player |
Minimize |
leaf |
Known value |
game tree |
Search space |