AI · Theory

Minimax Algorithm

Theory

26/215

Minimax Algorithm

Minimax: you maximise your score, the opponent minimises it. Recurse to leaves, back up values. Max node takes the max of children. Min node takes the min. Tic-tac-toe: +1 win, −1 loss, 0 draw. The first move is chosen from those backed-up numbers.

Depth explodes. That is why alpha-beta and depth limits exist. Trace a 2-ply tree on paper: three leaves 3, 5, 2 under a min, then a max above — say the backed-up value before coding.

Minimax Algorithm — output — min children: 3 2 / max chooses: 3. Same tree as the diagram.

Diagram

MAX
       /   \
     MIN    MIN
     / \    / \
    3   5  2   9
     \ /    \ /
      3      2
        \  /
         3

Exam tip

Tiny 2-ply trace + backed-up value.

Example

# Minimax backup
left_min = min(3, 5)
right_min = min(2, 9)
print("min children:", left_min, right_min)
print("max chooses:", max(left_min, right_min))

Minimax Algorithm — output: min children: 3 2 / max chooses: 3. Same tree as the diagram.

Short notes

Max player / min opponent.
Back up leaf scores.
Trapexponential tree.

AI · Theory

Minimax Algorithm

← All stacks

Theory

26/215

Minimax Algorithm

Depth explodes. That is why alpha-beta and depth limits exist. Trace a 2-ply tree on paper: three leaves 3, 5, 2 under a min, then a max above — say the backed-up value before coding.

Minimax Algorithm — output — min children: 3 2 / max chooses: 3. Same tree as the diagram.

Diagram

MAX
       /   \
     MIN    MIN
     / \    / \
    3   5  2   9
     \ /    \ /
      3      2
        \  /
         3

Exam tip

Tiny 2-ply trace + backed-up value.

Example

# Minimax backup
left_min = min(3, 5)
right_min = min(2, 9)
print("min children:", left_min, right_min)
print("max chooses:", max(left_min, right_min))

Minimax Algorithm — output: min children: 3 2 / max chooses: 3. Same tree as the diagram.

Short notes

Max player / min opponent.
Back up leaf scores.
Trapexponential tree.

Minimax Algorithm

Example

Short notes

Questions

Minimax Algorithm

Example

Short notes

Questions