Skip to content
December 8, 2013

Minimax and backward induction

In this installment, we’ll look at concepts to determine the best move in a sequential game. This will work for many situations: games like tic-tac-toe and checkers for sure, but also for real-life choices, such as whether to ask someone out on a date.

There are two important types of games that we look at in game theory: simultaneous and sequential.

Final Jeopardy! wagering is a simultaneous game, since you and your opponents each lock in your wagers at the same time without knowing what the other is doing. We usually model these games in a payoff matrix.

Minimax backward induction Slide01 Minimax backward induction Slide02

In a sequential game, on the other hand, the order of play is subject to predetermined rules. In some cases, each player makes one move each turn, then play moves to the next player. Or, the move might change depending on various situations in the game. Selection of clues in Jeopardy! is one example: whoever responded correctly last has the option. We usually model these games in a decision tree. In this example, green moves first, and has two options; then red and green switch off turns.

Minimax backward induction Slide03 Minimax backward induction Slide04

Here’s a decision tree for a game of chess. White has three options; after white moves, black will choose from three responses. Each combination has a payoff for white relating to his relative strength against black. (Computers – and some players – apply point values to each player’s layout to see who has the stronger position.)

Minimax backward induction Slide05

If white is “winning” by some amount then black must be losing by that same amount; hence, this is a zero-sum game.

White might be tempted to move his queen, hoping that black will move his pawn, therefore giving white an edge of +7 – the largest lead available to him.

However, black might see that moving his knight will give white a value of -6, and therefore, to himself, +6. This is the best total available to black.

Minimax backward induction Slide06

Instead of looking at each possibility from front to back, we’ll use backward induction to see which move is best for white. We use the concept of minimax to see how each of white’s options could lead to a specific outcome.

In chess, some people play so that they might get the best possible outcome if their opponent does something stupid. Smart players play so that they will get the best possible outcome assuming the opponent makes his best move.

Minimax backward induction Slide07

This way of limiting the damage is sometimes called “maximizing one’s own minimum”, or maximin – but maximin works for non-zero-sum games as well. (We’ll look at that in a bit.)

To use minimax, do the following:

– Look at your opponent’s best response to each of your options.

Minimax backward induction Slide08

(Remember, the numbers are the outcomes for black. We’ll need to flip those to turn them into white’s payoffs.)

– Consider those the “payoff” of making the associated move. Pick the one that is the worst for your opponent – or, since this is a zero-sum game, the most beneficial to you.

Minimax backward induction Slide09

We’ve found the optimal situation for both players.

Minimax backward induction Slide10

Assuming he knows what he’s doing, black will then choose to move his rook, netting him +2 against white. We call this a subgame perfect Nash equilibrium – neither player can improve on this outcome with optimal play by the other.

The other two routes highlighted in green are also Nash equilibria, but they’re not “subgame perfect”, since white can ultimately do better by moving his knight.

We can also use minimax for zero-sum simultaneous games, like Final Jeopardy! wagering, to determine the Nash equilibrium. More on that in the next installment!

Summary
Title
Minimax and backward induction
Description
How to use minimax and backward induction to determine the best move in a sequential game.
Author
Leave a Comment

What do you think?