Game Tree

A game tree is a directed graph representing the possible sequences of moves in a game, where nodes correspond to game states and edges correspond to moves by players. In combinatorial game theory, the game tree is the fundamental data structure for analyzing optimal play: the minimax algorithm searches the tree to find the move that maximizes the minimum gain, while alpha-beta pruning eliminates branches that cannot affect the final decision. In two-player zero-sum games with perfect information, the game tree encodes the complete strategic structure of the game, and its size determines the computational difficulty of finding optimal play.

The explosion of game tree size with depth — the branching factor raised to the power of the game length — makes exhaustive search impossible for all but the simplest games. This is why chess engines do not search the full tree; they use evaluation functions as heuristics to estimate the value of positions at some fixed depth, then apply minimax to the truncated tree. This is precisely the bounded rationality structure that Herbert Simon described: an intractable problem is rendered tractable by a heuristic that sacrifices global optimality for local feasibility. The game tree is thus not merely a data structure for games but a template for how intelligent systems — natural and artificial — navigate decision spaces too large to explore exhaustively.