Game tree

• 1. Introduction

  ›

  Game trees sit at the intersection of mathematics, strategy, and computation. Tic-tac-toe, that deceptively simple grid game, has a complete game tree with exactly 255,168 leaf nodes - each one representing a distinct way the game can end. That number captures every possible sequence of moves from the first X placed to the final square filled. And tic-tac-toe is one of the smallest cases.

  For chess, checkers, and Go, the complete game tree grows so vast that no computer has ever mapped it in full. Yet the game tree as a concept underpins how machines play every one of those games. How does a structure that cannot be fully drawn still guide a program toward the best move? What makes a game tree solvable, and when does randomness become a better tool than logic? Those are the questions this documentary will explore.

• 2. What a Game Tree Is

  ›

  A game tree is a directed graph. Its nodes are positions - arrangements of pieces on a board, for instance - and its edges are the moves that connect one position to the next. Every branch traces one possible line of play, and the leaves at the bottom represent the endpoints: wins, losses, and ties.

  The complete game tree for any sequential game with perfect information begins at the starting position and fans out through every legal move available at every stage. Perfect information means that both players can see the entire state of the game at all times, which is true of chess, checkers, Go, and tic-tac-toe. The complete game tree is equivalent to what game theorists call the extensive-form representation of a game. It captures the sequence of decisions available to each player, what each player knows when they decide, and the outcome of every possible path.

  Two-player games can also be expressed as and-or trees. The first player's choices appear as disjunctions - only one winning move is needed. The second player's possible responses appear as conjunctions - the first player must have an answer to all of them. For the first player to guarantee a win, a winning move must exist against every reply the second player can make.

• 3. Measuring Complexity

  ›

  The number of leaf nodes in a complete game tree is one direct measure of a game's complexity. For tic-tac-toe, that number is 255,168. For chess, the figure is so large that generating the complete tree is not feasible on any existing computer.

  Game trees are not only a theoretical tool; they are a practical measure used to compare games against each other. Any subtree sufficient to solve a game - to find the guaranteed optimal line of play - is called a decision tree, and the sizes of decision trees of various shapes serve as formal measures of game complexity. Smaller decision trees mean a game can be resolved with less computation. Larger ones signal that finding the optimal move demands more search, more memory, and more time.

  This connection between tree size and difficulty is why chess-playing programs do not attempt to map the full tree. Instead they search as many plies - layers of moves - from the current position as time allows. With rare exceptions involving what researchers call pathological game trees, searching deeper generally improves the quality of the move chosen.

• 4. Solving With Backward Induction

  ›

  When a complete game tree can be generated, a deterministic method called backward induction - also known as retrograde analysis - can solve it outright. The algorithm works by coloring nodes from the bottom up.

  At the final ply, every position gets labeled: a win for player one, a win for player two, or a tie. Moving one layer up, the algorithm checks each node against the player whose turn it is. If that player has at least one move leading to a node colored in their favor, that node inherits their color. If every available move leads to the opponent's color, the node takes the opponent's color. Any remaining case becomes a tie. The process repeats, ply by ply, until the root node is colored. Whatever color the root carries determines whether the game is a forced win for the first player, a forced win for the second player, or a guaranteed draw under perfect play.

  This process does not require exploring the entire tree in practice. Alpha-beta pruning, for example, allows the algorithm to skip analyzing a move whenever another move is already known to be better for the same player. Any subtree sufficient for the algorithm to reach the correct answer qualifies as a decision tree.

• 5. The Case for Randomness

  ›

  Randomized algorithms offer two advantages over the deterministic approach when a complete game tree is out of reach: speed and what researchers describe as practicality. The expected run time of the randomized version, for a tree where every node has degree 2, is faster than its deterministic counterpart.

  The practicality advantage is more unusual. A randomized algorithm evaluates the tree in a random order, which means an opponent who knows which algorithm is being used cannot exploit that knowledge to steer the game toward a favorable outcome. The algorithm, in the language of game tree research, is capable of foiling an enemy.

  The implementation works through short-circuiting. When the root node acts as an OR operator, the algorithm returns a win as soon as it finds one winning child, without examining the rest. When the root acts as an AND operator, it returns a loss as soon as one losing child appears. In both cases, unnecessary branches are skipped, keeping computation efficient even when the full tree is never built.

  For the largest games in common play, neither backward induction nor a single randomized pass is enough. Algorithms like Monte Carlo Tree Search - MCTS - use probabilistic sampling to explore the most promising parts of a vast tree without committing to a full traversal, making competition at the highest levels of chess and Go computationally achievable.