Opponent Models in Sequential Decision Problems
The simplicity of Tic-Tac-Toe does not remove the need to match an algorithm to the opponent information available.
The Opponent Information Problem
Tic-Tac-Toe looks small enough to solve by planning every possibility. However, the board size is not the only issue. A decision method must also fit the kind of opponent it expects. A mathematically powerful method can be a poor choice when it depends on information that is unavailable or assumes that the opponent will behave in a particular way.
The central question is not simply “Which algorithm is strongest?” It is “What does the algorithm need to know about the opponent, and do we actually have that information?”
Minimax and the Imperfect Move
Minimax is a game-theory method that assumes a particular way of playing by the opponent. It avoids a state from which the player could lose. That caution is appropriate under the opponent behavior assumed by minimax, but it can be unsuitable when the real opponent may make an incorrect move.
A Position Minimax Rejects
Suppose one possible Tic-Tac-Toe state could lead to a loss if the opponent responds well, but could lead to a win if the actual opponent makes an incorrect move. Should a minimax player choose that state?
- 1Minimax evaluation
Minimax notices that the state could lead to a loss and therefore rejects it.
- 2Actual opponent behavior
If the actual opponent is imperfect, the opponent may make the incorrect move that allows the player to win.
- 3Decision mismatch
The state that minimax rejects could have been useful against this particular opponent.
Minimax can be unsatisfactory against an imperfect opponent because its opponent-playing assumption causes it to discard a possibility that could produce a win.
The Model Dynamic Programming Needs
Dynamic programming has a different requirement. It can compute an optimal solution for any opponent, but only after receiving a complete specification of that opponent. For every board state, the specification must include the probabilities that the opponent will make each possible move.
The requirement is stronger than knowing that the opponent is generally strong or generally weak. Dynamic programming needs the opponent's move probabilities in each board state. Without those probabilities, it does not yet have the information needed to evaluate the possible next states.
When the opponent's behavior is not available beforehand, it may be estimated from experience by playing many games. The resulting model is known only up to some level of confidence. Dynamic programming could then use that approximate model, but the process has already used experience to obtain information about behavior before choosing an action.
Policies Across the Whole Game
A policy is a rule that assigns a move to every possible game state. In Tic-Tac-Toe, a state is a particular configuration of Xs and Os on the three-by-three board. A policy therefore describes behavior throughout the game, not just the move chosen for the current board.
This changes the question being asked. A single-position question is “What should I do in this one position?” A policy question is “What move does this rule choose for every position the player may encounter?” The second question describes a complete behavior rule.
Searching Policies Instead of Modeling Behavior
Evolutionary methods use the policy view directly. Rather than first writing down a complete probability model of the opponent, they search through possible policies. Each candidate policy is tested by playing some number of games against the opponent. Its estimated winning probability then helps determine which policies are considered next.
Evaluating a Candidate Policy
Imagine that a candidate policy specifies a move for every Tic-Tac-Toe board configuration. How can an evolutionary method use it?
- 1Represent behavior
Treat the complete state-to-move rule as one candidate policy.
- 2Play games
Use the candidate policy in a number of games against the opponent.
- 3Estimate performance
Estimate how often the candidate policy wins from the games played.
- 4Guide the search
Use the estimated winning probability to help determine which policies are considered next.
The method searches for a policy with a high probability of winning by evaluating complete policies through play.
| Method | Starting requirement | How the opponent issue appears |
|---|---|---|
| Minimax | An assumption about how the opponent plays | It may reject a state that could win if the opponent makes an incorrect move. |
| Dynamic programming | A complete opponent specification | It needs the probability of each possible opponent move in each board state. |
| Evolutionary methods | Candidate policies and games for evaluation | They search through policies and estimate winning probability through play. |
The methods differ in the information they require before selecting or evaluating behavior.
Mistakes About Opponent Models
Common mistake Treating minimax as automatically suitable for every opponent.
What it looks likeAssuming that avoiding every state from which a loss is possible must be best against an opponent who may make mistakes.
Why it failsMinimax may reject a state that could lead to a win when the actual opponent chooses an incorrect move.
Do this insteadState the opponent-playing assumption explicitly and check whether it matches the opponent being faced.
Common mistake Calling dynamic programming model-free.
What it looks likeApplying dynamic programming without specifying how likely each opponent move is in each board state.
Why it failsDynamic programming requires a complete opponent model, including move probabilities for each state.
Do this insteadSupply the complete model, or recognize that the needed information must first be estimated from experience.
Common mistake Defining a policy as the move for only the current board.
What it looks likeRecording one move for the position currently visible and calling that record a complete policy.
Why it failsA policy assigns a move to every possible game state.
Do this insteadDescribe a policy as a rule covering the player's behavior throughout the game.
Common mistake Saying that evolutionary methods simply ignore the opponent.
What it looks likeAssuming that searching through policies means the opponent has no role in evaluation.
Why it failsCandidate policies are evaluated by playing games against the opponent, and their estimated winning probability guides the search.
Do this insteadDistinguish avoiding a complete starting probability model from ignoring opponent behavior altogether.
Choose the Method
For each situation, identify the most appropriate description: minimax, dynamic programming, or evolutionary policy search. Then explain what opponent information the method uses. Situation A: You have an assumption about how the opponent plays, but no state-by-state move probabilities. Situation B: You know the probability of every possible opponent move in every board state. Situation C: You do not have the opponent's behavior model in advance, but you can play many games and evaluate complete policies.
Hints
- Minimax is tied to an assumption about opponent play.
- Dynamic programming needs move probabilities for each possible move in each board state.
- Evolutionary methods evaluate complete policies through games.
What do you think happens?
A candidate policy gives a move for the current board but says nothing about other board configurations. Can it yet be evaluated as a complete policy in the evolutionary approach?
Reveal answer
No, because a policy describes behavior for every possible game state.
The evolutionary approach searches through complete policies and evaluates them by playing games. A single current move is not the same as a rule covering the player's behavior throughout the game.
When comparing decision methods, separate three questions: What does the method assume about the opponent? What information must be available before it can evaluate actions? Does it search over actions from a model or over complete policies through experience? Keeping these questions separate prevents minimax, dynamic programming, and evolutionary methods from being described as having the same limitation.
The Decision-Method Checklist
- 1Minimax is tied to an assumption about how the opponent plays and may reject a state that could win against an imperfect opponent.
- 2Dynamic programming can compute an optimal solution for any opponent only when it receives a complete opponent model.
- 3That model must include the probabilities of each possible opponent move in each board state.
- 4A policy is a rule that assigns a move to every possible Tic-Tac-Toe state.
- 5Evolutionary methods search through possible policies and use games against the opponent to estimate winning probability.
Key Takeaways
- A decision algorithm must match the opponent information available, even in a small game such as Tic-Tac-Toe.
- Minimax can be unsuitable when an opponent may make an incorrect move because it rejects states from which a loss is possible.
- Dynamic programming requires a complete state-by-state opponent model containing move probabilities.
- A policy maps every possible game state to a move rather than describing only the current action.
- Evolutionary methods evaluate complete policies through games instead of beginning with a complete probability model of the opponent.