TwiddleLab / Artificial Intelligence / Search, Games and Plans

Minimax

Lesson 5 of 11 · 7 min · Free, no account needed

What you will learn

• Give every ending a score: +1 if you win, -1 if you lose, 0 for a draw.
• Minimax passes scores up the tree: on your levels take the max, on the opponent's levels the min.
• The value at the top is what you can guarantee, however well the opponent plays.
• The rule calls itself on every child: value(position) is a recursive function.

Start the lesson

How the lesson goes

1. Bottom right has a winning ending for X under it. X plays there. What will a smart O do?

   Tap O's reply.

2. Watch the scores climb up the tree.

   Each level passes one score up: X takes the biggest, O takes the smallest.

3. Now with real scores. Bigger is better for you.

   Under each orange node, tap the leaf the opponent picks. Then tap your best move.

   The right branch has a 14, but the opponent will never let you have it: it answers with 2. The left branch guarantees 3 whatever the opponent does, and 3 is the best guarantee.

4. This way of choosing is called minimax.

   On your levels take the max, on the opponent's levels the min, from the leaves up to the top. The top value is what you can guarantee against a perfect opponent. The score of a position is its value.

5. Three levels now. Fill the tree from the bottom.

   Drag a value up to its parent. Purple keeps the biggest child, orange the smallest.

   Bottom up: max(4, 8) = 8, max(9, 3) = 9, max(2, 7) = 7, max(5, 6) = 6. The opponent then takes min(8, 9) = 8 and min(7, 6) = 6. At the top you take max(8, 6) = 8.

6. Game: beat a minimax bot at sticks.

   Take 1 or 2 sticks per turn. Whoever takes the last stick wins. You go first. The bot searches the whole tree.

7. This bot keeps falling into traps. Fix its rules.

   It plays the branch with the biggest leaf. Tap a rule chip to switch it.

   With max on both levels the bot hopes for the 15 and plays the middle branch, where you answer with 1. With min on your level it sees the middle is worth only 1 and plays the left branch, which guarantees 7.

8. Write minimax as a rule a computer can run.

   Drag a word into each blank. The rule uses itself on every child: in code that is a recursive function.

   value(position) asks value(child) for each child, which asks its children, down to the endings. Then it takes the max on your move and the min on the opponent's. Here the top comes out as 7. A function that calls itself is recursive; the cs track writes it in Python.

9. What score can you guarantee at the top of this tree?

   Purple levels are yours (max), orange the opponent's (min).

   Bottom: 5, 7, 9, 6. Opponent: min(5, 7) = 5 and min(9, 6) = 6. Top: max(5, 6) = 6.

10. Two perfect bots play tic-tac-toe. Who wins?

    Both run minimax on the whole tree from an empty board.

Previous lesson: Game Trees · Next lesson: Scoring Positions: Evaluation Functions · Part of the course: Search, Games and Plans

Lessons are interactive and need JavaScript. Turn it on to play them.