AI Glossary / Graphs and symbolic AI / Intermediate

Game tree

Definition

A game tree represents the possible sequences of decisions in a game. Nodes describe decision situations or histories, edges represent available actions or chance outcomes, and terminal nodes record the resulting payoffs.

What it means

The tree starts from a current or initial situation and branches whenever different continuations are possible. Unlike a single planned path, it includes responses that other participants might choose. A strategy must account for relevant alternatives rather than assume a cooperative opponent.

In simple two-player games, levels may alternate between the players. Other games include chance events, more players or situations where a player cannot distinguish between several possible histories.

A game tree is a representation, not one particular solving algorithm. Minimax, backward induction, expectation calculations and other methods use different assumptions about the game and the participants.

How it works

Specify the initial position, legal actions, state transitions and whose turn it is. Expand each action to its resulting situation. Continue until terminal outcomes, or stop at a chosen search boundary when the full tree is too large.

In a deterministic two-player zero-sum game, minimax can propagate terminal values upward: a maximizing player selects the largest child value and a minimizing opponent selects the smallest. Chance nodes require probabilities and an appropriate expectation calculation instead of pretending chance is an adversarial player.

A truncated search uses evaluation estimates at its boundary, so its result depends on those estimates. The same underlying position may occur through several action sequences; a literal tree repeats it, while implementations can use a game graph or transposition table to share work. Repetition rules and history-dependent facts must still be represented correctly.

Three practical examples

• A board-game program examines legal moves and opponent replies before selecting its next action.
• A teaching simulator represents sequential resource-allocation choices and displays how later decisions affect earlier incentives.
• An AI testing environment uses a small game tree to verify that an agent distinguishes adversarial responses from chance outcomes.

Think of it this way

Think of a branching conversation script that includes what another person might say after each response. One route describes a possible conversation; the whole script represents alternatives.

The analogy highlights contingent planning. Real conversations have uncertain meanings and an enormous range of responses, so a small explicit game tree cannot automatically capture their full strategic structure.

Worked example

Backing up a small minimax tree

Suppose MAX chooses between actions Left and Right. After either action, MIN chooses between two terminal outcomes. Under Left, MAX's payoffs are 6 and 2. Under Right, they are 4 and 3. Assume these are the complete legal continuations of a deterministic zero-sum game.

MIN chooses the lower payoff to MAX: Left therefore has value min(6, 2) = 2, and Right has value min(4, 3) = 3. At the root, MAX chooses max(2, 3) = 3 and selects Right.

Choosing Left merely because it contains the largest leaf, 6, would assume that MIN selects a favorable reply. The game tree shows why that assumption is unjustified under minimax.

Now change the second level to fair chance instead of MIN. Left's expected payoff becomes (6 + 2)/2 = 4, and Right's becomes (4 + 3)/2 = 3.5. An expected-payoff-maximizing decision would select Left. The structure's node types and probability assumptions therefore matter as much as the leaf numbers.

Illustrative case study

The fictional Birch Games team builds an instructional game with a randomized event after the player's move. An early search prototype treats every non-player node as an opponent choosing the worst outcome.

The resulting behavior is overly conservative relative to the game's stated expected-score objective. Reviewers label the nodes explicitly and separate opponent choices from random events with known probabilities. They use the small worked tree as a diagnostic case before testing larger positions.

Birch also labels cutoff evaluations as estimates rather than final game results. The case illustrates representation and algorithm alignment. It does not claim that expectation-based choice is always appropriate or that a particular search depth guarantees strong play.

Common misconceptions and mistakes

• A game tree is one sequence of moves. It represents many possible continuations and the decisions connecting them.
• The highest payoff leaf determines the best first move. Other players or chance may prevent that leaf from being reached.
• Every second level is a minimizing opponent. Node roles depend on the game, not on a universal alternating pattern.
• Searching to a fixed depth solves the game exactly. Exactness requires appropriate terminal information or justified bounds, not merely a depth limit.

Business use

Game trees are useful when decision order and responses matter. A small tree can expose assumptions hidden in a spreadsheet of final outcomes, including who can choose after seeing another action.

For larger AI systems, the main practical issues are branching growth, evaluation quality and information available to each participant. With roughly b choices per decision and depth d, a full tree can contain on the order of b to the power d leaves. Pruning and shared-state techniques reduce work in suitable settings, but their guarantees depend on the method and game assumptions.

People also ask

Is a game tree the same as a decision tree classifier?

No. A classifier branches on feature tests to predict labels; a game tree represents actions and possible continuations in a game.

Can two nodes represent the same position?

Yes, if different histories reach that position. Sharing the computation requires retaining any history that affects legal moves or payoffs.

How is hidden information represented?

Extensive-form models can group indistinguishable decision nodes into information sets, preventing a strategy from using information the player does not have.

Check your understanding

In the worked minimax game, why is Right preferable even though Left contains payoff 6?

Answer: MIN can choose the payoff-2 continuation after Left. Right guarantees payoff 3 against the modeled minimizing reply, which is better than Left's value 2.

Related terms

• Minimax
• Alpha-beta pruning
• Chance nodes
• Information sets
• Transposition table
• Evaluation function
• backward induction
• chance node
• extensive-form game
• information set

Learn next

Add a third action whose MIN replies give payoffs 5 and 1. Recompute the root choice, then replace that action's MIN node with a chance node having probabilities 0.9 and 0.1. State clearly which game you are solving in each calculation.

More in Graphs and symbolic AI

• Gain parameter - A gain parameter is a coefficient that scales a signal or a component of a system's response.
• Gain ratio - Gain ratio is a decision-tree split criterion that divides information gain by the split information of the candidate test.
• Game theory - Game theory studies situations in which the outcome for each decision-maker depends on choices made by others as well as their own.
• Gaussian process - A Gaussian process is a collection of random variables for which every finite collection has a joint Gaussian distribution.
• Generalization hierarchy - A generalization hierarchy organizes concepts or descriptions from more specific to more general.
• Generalization loss - Generalization loss is a model's expected loss on examples drawn from the target data distribution.

Sources

AIMA's author-provided slides define game trees, minimax, chance nodes and resource-limited search: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter06.pdf

The authors' algorithm collection provides related game-search pseudocode: https://aima.eecs.berkeley.edu/algorithms.pdf

Rubinstein's author notes discuss Bayesian games and differences in players' information: https://arielrubinstein.tau.ac.il/econt2/lectures/G03.pdf

The Left/Right tree and Birch Games case are original examples. Historical game-program comparisons in source teaching materials are not presented as current capabilities.

Previous: Game theory Next: Gamma correction