Minimax

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.

Exercise 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)).

Show example 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))

Test yourself

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
Show answer

To maximize gain — The max player aims to maximize gain.

max branch

if is_max:
    return ____(minimax(child, False) for child in node)

Show answer

if is_max:
    return max(minimax(child, False) for child in node)

Minimax concepts

max player

Maximize
min player

Minimize
leaf

Known value
game tree

Search space

Next lesson: Alpha-beta pruning

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies