Game Tree

A game tree is a tree whose nodes are positions in a game and whose edges are the legal moves between them, with the starting position at the root and finished games at the leaves. For a two-player game with alternating turns, each level of the tree belongs to one player, and a leaf carries the result: win, loss or draw, or a numerical payoff. The structure is a complete map of every way the game could unfold, which is why it serves both as a theoretical object, in which game theorists define optimal play, and as a practical data structure that game-playing programs build, partially and on demand, to decide what to do.

Minimax is the method of reading a game tree, and the vocabulary of MAX and MIN comes from it. One player, called MAX, tries to maximize the final value; the other, MIN, tries to minimize it. Values are assigned at the leaves and propagated upward: a node where MAX moves takes the largest value among its children, and a node where MIN moves takes the smallest. The value at the root is what each side can guarantee against best play. The idea descends from John von Neumann's 1928 minimax theorem for zero-sum games and from the extensive-form representation developed in von Neumann and Oskar Morgenstern's 1944 Theory of Games and Economic Behavior. A level of the tree is called a ply, meaning one move by one player, a term commonly credited to Arthur Samuel, whose checkers programs of the 1950s were among the first to learn from play.

Claude Shannon's 1950 paper, Programming a Computer for Playing Chess, in the Philosophical Magazine, connected the game tree to computing and set out the design that chess programs followed for decades. Writing before any machine could play a full game, he observed that the tree is far too large to search to the end, so a program must stop at some depth and apply a static evaluation function to the position reached. His example evaluation counted material with the familiar values of pawn 1, knight and bishop 3, rook 5 and queen 9, with small adjustments for structure and mobility. He distinguished a Type A strategy, which searches every move to a fixed depth, from a Type B strategy, which looks at only selected promising lines, and noted that human players behave more like the latter. The paper is the origin of the evaluation-plus-search architecture that still defines the field.

Size is the obstacle, and the lesson of the game tree is that scale decides which games can be solved. Tic-tac-toe is trivial: there are 255,168 possible games and 5,478 distinct legal positions. Checkers is vastly larger, on the order of 5 × 10^20 positions, and was finally solved in 2007 by Jonathan Schaeffer's team, who showed it is a draw with perfect play. Chess, with about thirty-five moves per position over many dozens of plies, yields figures such as Shannon's 10^120 games, which are not exact counts and depend on assumptions. Deep Blue's 1997 victory over Garry Kasparov came from searching hundreds of millions of positions per second with alpha-beta pruning and a handcrafted evaluation, not from exhaustive enumeration. Go, with a branching factor near 250, long defeated such methods.

A common misconception is that a program must search the full tree to play well, or, conversely, that a perfect-information game tree is the whole story of a game. Programs search a tiny fraction of the tree and rely on evaluation and pruning to make the cut safe or nearly so. Equally, the basic tree describes games of perfect information, in which both players see everything and nothing is left to chance. Poker, with hidden cards, and backgammon, with dice, need chance nodes or information sets, and the corresponding methods, such as counterfactual regret minimization used by modern poker programs, differ from plain minimax. Another pitfall is to mistake the evaluation function for the truth: an evaluation at the search horizon is only a heuristic, and mistakes near the horizon, where a bad event is just beyond the searched depth, are a known failure mode.

AlphaGo in 2016 showed how the old structure could be reused with new components. Described by David Silver and colleagues in Nature in 2016, it still searched a game tree, using Monte Carlo tree search, but replaced the hand-built evaluation and move ordering with deep neural networks, a policy network that proposed promising moves and a value network that estimated who was winning, which together shrank the effective width and depth of the search. AlphaGo's defeat of Lee Sedol in March 2016 is the best-known demonstration. The same framing, a tree of possibilities, a learned guide and a selective search, now appears well beyond board games.

Read game tree as the full space of play from a position, a tree that Shannon showed is too large to search whole and must be cut off by evaluation, so that the history of game-playing AI is the history of how to read as little of it as possible while still choosing well.