Game Tree · aiwiki.page

A game tree is a rooted, branching representation of the possible ways a game can unfold. Nodes represent positions or histories of play, and edges represent available actions. Terminal nodes specify outcomes and their payoffs. In game theory, this structure underlies the extensive-form representation of strategic interaction; in artificial intelligence, it supports algorithms that choose actions by examining possible responses and future consequences. A game tree is a representation of possibilities, not itself a strategy or a search algorithm. (artint.info)

Structure and interpretation

Formally, a game tree is a rooted directed graph in which every node other than the root has exactly one parent. Consequently, each node is reached through a unique path from the root. The root represents the initial situation, or the current situation from which analysis begins. An internal node identifies the player who acts next, while its outgoing edges identify that player’s available actions. A root-to-terminal path describes one complete course of play. (live.ocw.mit.edu)

Terminal outcomes carry a numerical utility for each player. These payoffs express preferences over outcomes and need not be monetary. Chance events, such as a random draw, can be represented by nodes controlled by “nature,” with a probability distribution over outgoing edges. Thus, a tree can describe deterministic games, games involving randomness, and interactions with more than two players. (artint.info)

Strictly, nodes can be identified with histories: sequences of actions leading from the root. Two different histories may produce the same apparent position but remain distinct nodes because their paths differ. A complete tree includes every permitted continuation, whereas a search procedure usually constructs only a portion of it. Leaves of this partial search tree may therefore be unfinished positions rather than actual terminal outcomes. (ocw.mit.edu)

Minimax and backward evaluation

For a deterministic, two-player zero-sum game with perfect information, the standard evaluation procedure is minimax. One player, conventionally MAX, seeks to maximize a payoff measured from that player’s perspective; the opponent, MIN, seeks to minimize it. Terminal payoffs are propagated upward through recursion, selecting the largest child value at MAX nodes and the smallest at MIN nodes. (inst.eecs.berkeley.edu)

Writing $C(s)$ for the children of node $s$ , the recurrence is

V(s)= \begin{cases} U(s), & s\text{ is terminal},\\ \max_{t\in C(s)}V(t), & s\text{ belongs to MAX},\\ \min_{t\in C(s)}V(t), & s\text{ belongs to MIN}. \end{cases}

Here, $U(s)$ is the terminal payoff. With a complete finite tree, this procedure identifies the payoff MAX can guarantee against optimal opposition and an action attaining that value. (inst.eecs.berkeley.edu)

For example, suppose MAX chooses between two branches. On the first, MIN can select terminal payoffs 3 or 5; on the second, MIN can select 2 or 9. The branch values are therefore 3 and 2, so MAX chooses the first. This illustrates why the largest reachable payoff, 9, need not identify the best action.

Computational cost and selective search

The chief practical difficulty is the tree’s size. If each node has approximately $b$ children and the search reaches depth $d$ , exhaustive minimax has time complexity $O(b^d)$ . The branching factor and depth therefore determine an exponential growth in computational work. Depth-first implementations avoid retaining the entire tree, but exhaustive evaluation can still be impractical. (inst.eecs.berkeley.edu)

Alpha–beta pruning avoids examining branches that cannot change the minimax result. It maintains bounds on values already available to MAX and MIN and stops exploring a branch when those bounds establish its irrelevance. It preserves the root’s minimax value, although tie-breaking among equally good moves may vary. Its effectiveness depends on move ordering: ideal ordering reduces the search cost to approximately $O(b^{d/2})$ , while the worst case remains $O(b^d)$ . (inst.eecs.berkeley.edu)

Another approach limits the search depth and applies a heuristic evaluation function to unfinished positions. Such estimates replace exact terminal payoffs, making the decision depend on evaluation quality as well as search depth. The resulting choice is optimal for the evaluated truncated tree, not necessarily for the complete game. (inst.eecs.berkeley.edu)

Chance and hidden information

At a chance node, evaluation uses an expected value rather than a maximum or minimum:

V(s)=\sum_{t\in C(s)}p(t\mid s)V(t).

Expectimax combines maximizing decisions with this probabilistic evaluation. It can represent random events or an opponent whose actions follow a specified probability model. A stochastic adversarial game may instead combine MAX, MIN, and chance nodes in one tree. Unlike minimax’s worst-case assumption, probabilistic evaluation depends on the accuracy of the assigned probabilities. (inst.eecs.berkeley.edu)

Hidden information requires additional structure. In an extensive-form game, an information set groups decision nodes that the acting player cannot distinguish. A strategy must specify compatible behavior across those nodes rather than exploit knowledge the player does not possess. Perfect information corresponds to singleton information sets. Consequently, ordinary node-by-node minimax does not directly solve arbitrary imperfect-information games. (ocw.mit.edu)

Simulation-based and learned search

Monte Carlo tree search evaluates possibilities through repeated simulations while selectively expanding a partial tree. Its conventional cycle comprises selection, expansion, simulation, and propagation of results back through visited nodes. Search allocation balances exploration and exploitation: investigating less-tested actions while revisiting actions with favorable estimates. (inst.eecs.berkeley.edu)

Tree search can also incorporate learned policies and position values. In the original AlphaGo system, neural networks supplied move probabilities and evaluations that were combined with Monte Carlo tree search for Go. Its policy and value networks were trained using supervised learning and reinforcement learning. These learned components guided exploration and evaluation without requiring enumeration of the complete game tree. (storage.googleapis.com)

References

Artificial Intelligence—10.2.2 Extensive Form of a Gameartint.info
Game Theory, Lecture Notesocw.mit.edu
Game Theory, Lecture 2: Equilibrium Refinementslive.ocw.mit.edu
2 Minimaxinst.eecs.berkeley.edu
6 Summaryinst.eecs.berkeley.edu
CS 188 Spring 2025, Lecture 7inst.eecs.berkeley.edu
3 Expectimaxinst.eecs.berkeley.edu
5 Monte Carlo Tree Searchinst.eecs.berkeley.edu
Mastering the game of Go with deep neural networks and tree searchstorage.googleapis.com