Game tree

A game tree is a rooted tree whose nodes are possible histories of play and whose edges are legal next actions. Internal nodes specify the acting player or a chance move; terminal nodes carry outcomes or payoffs. In an extensive-form game, information sets additionally say which decision histories the acting player can distinguish.

Distinct histories may reach the same board position, so a game tree can contain repeated states that a state graph would merge. For finite two-player zero-sum games with perfect information, minimax search propagates terminal values upward. Chance nodes require expectations instead of maximizing or minimizing their outcomes.

Backward induction with an $n$-component utility vector. At a node controlled by player $i$, evaluate each child, choose a child maximizing coordinate $i$ and copy its entire vector. A fixed tie rule makes the returned vector well defined. By mathematical induction from terminal positions, the selected continuation is a best response at every node of a finite perfect-information game, giving a pure strategy subgame perfect equilibrium. The vector must be copied intact; separate coordinatewise maxima need not describe any attainable outcome.

Suppose every terminal pair satisfies $|U_A+U_B|\le ϵ$. At a B-node with immediate A-parent, let $\alpha$ be the A-coordinate of a completed alternative already retained by the parent. If a completed B-child supplies B-coordinate $y$, then every eventual B-selected pair $(u,v)$ has $v\ge y$ and hence $u\le ϵ-y$. Therefore $ϵ-y<\alpha$ permits discarding this B-option and skipping its remaining children. Equality is also safe if the parent keeps its existing option on a tie.

The inequality remains valid at completed subtrees because max-n search copies one terminal pair. If the observed pair is $(x,y)$, then $x+y\ge -ϵ$, so $u\le x+2ϵ$ and $x+2ϵ\le \alpha$ is a weaker sufficient test. At $ϵ=0$ this reduces to the usual MIN-node alpha-beta pruning cutoff. A discarded option is not assigned a fabricated exact pair; the proof uses a certified alternative at the immediate parent.

A game tree node whose successor is chosen according to a specified probability distribution. Its expected utility is a weighted sum of successor values, rather than the maximum or minimum used at a player's decision node.

Backward induction on a finite deterministic game tree of a two-player zero-sum game. Terminal payoffs are propagated by maximization at one player's decision nodes and minimization at the other's. With full information, the resulting choices give an optimal strategy against the opposing player's best response. A cyclic state graph requires a winning condition on infinite plays and a graph algorithm rather than unrestricted recursive unfolding.

Alpha-beta pruning evaluates a minimax search tree while omitting branches that cannot change an already available decision. The parameter $\alpha$ bounds what Max can already secure, and $\beta$ bounds what Min can already enforce along the current search path. Once $\alpha \ge \beta$, further children of that node cannot improve the relevant ancestor's choice.

If Max already has an alternative worth five, and a new Min node has a child worth three, that node's value is at most three. Its remaining children can be skipped. Full-depth pruning preserves the root minimax value; applying it to a depth-limited evaluation preserves that truncated value, not necessarily the true game result. Good move ordering makes cutoffs occur sooner.^[ref]

The order in which legal child positions are searched. Good move ordering supplies useful alternatives early and increases alpha-beta pruning; poor move ordering can leave the worst-case time complexity of full minimax search unchanged.