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?
Minimax evaluation: Minimax notices that the state could lead to a loss and therefore rejects it.
Actual opponent behavior: If the actual opponent is imperfect, the opponent may make the incorrect move that allows the player to win.
Decision 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?
Represent behavior: Treat the complete state-to-move rule as one candidate policy.
Play games: Use the candidate policy in a number of games against the opponent.
Estimate performance: Estimate how often the candidate policy wins from the games played.
Guide 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. |
Mistakes About Opponent Models
Treating minimax as automatically suitable for every opponent.
Minimax may reject a state that could lead to a win when the actual opponent chooses an incorrect move.
Fix:
State the opponent-playing assumption explicitly and check whether it matches the opponent being faced.Calling dynamic programming model-free.
Dynamic programming requires a complete opponent model, including move probabilities for each state.
Fix:
Supply the complete model, or recognize that the needed information must first be estimated from experience.Defining a policy as the move for only the current board.
A policy assigns a move to every possible game state.
Fix:
Describe a policy as a rule covering the player's behavior throughout the game.Saying that evolutionary methods simply ignore the opponent.
Candidate policies are evaluated by playing games against the opponent, and their estimated winning probability guides the search.
Fix:
Distinguish 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
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
- Minimax is tied to an assumption about how the opponent plays and may reject a state that could win against an imperfect opponent.
- Dynamic programming can compute an optimal solution for any opponent only when it receives a complete opponent model.
- That model must include the probabilities of each possible opponent move in each board state.
- A policy is a rule that assigns a move to every possible Tic-Tac-Toe state.
- Evolutionary 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.