Ch. 1 · Defining Game Trees

Game tree.

~4 min read · Ch. 1 of 5

The diagram shows the first two levels, or plies, in the game tree for tic-tac-toe. This visual representation captures how rotations and reflections of positions are equivalent. The first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. In combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. A game tree can be used to measure the complexity of a game, as it represents all the possible ways that the game can pan out. To better understand the game tree, it can be thought of as a technique for analyzing adversarial games. These games determine the actions that player takes to win the game. In game theory, a game tree is a directed graph whose nodes are positions in a game. Nodes represent arrangements of pieces on a board game. Edges are moves that transfer pieces from one position to another.

Analyzing Adversarial Outcomes

The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes. This count establishes a baseline for measuring how complex a game truly is. Large game trees like those found in chess make computation feasible only through partial search techniques. Algorithms designed to play these classes of games use partial game trees instead of full ones. The complete game tree starts at the initial position and contains all possible moves from each position. It matches the extensive-form game representation obtained from theoretical models. Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. Disjunction represents the first player's alternative moves while conjunction represents all of the second player's moves. Increasing the search depth generally improves the chance of picking the best move except in pathological cases which seem quite rare in practice.

Continue Browsing

Combinatorial game theory Trees (graph theory)

Common questions

What is a game tree in combinatorial game theory?

A game tree is a directed graph whose nodes are positions in a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. Nodes represent arrangements of pieces on a board game while edges are moves that transfer pieces from one position to another.

How many leaf nodes does the complete game tree for tic-tac-toe have?

The game tree for tic-tac-toe has 255,168 leaf nodes representing all possible different ways the game can be played. This count establishes a baseline for measuring how complex a game truly is. The number of leaf nodes equals the total possible distinct sequences of play from start to finish.

Which algorithm solves a game by coloring nodes in a game tree?

Backward induction or retrograde analysis works recursively to solve a game by coloring final plies based on wins for player 1, player 2, or ties. Analysts move up through each ply checking if nodes exist colored opposite as the current player to determine outcomes. The color of the root node determines the nature of the game after all nodes are processed.

Why do chess-playing programs use partial game trees instead of full ones?

Complete game trees for larger games like chess are much too large to search within available time limits. Algorithms designed to play these classes of games use partial game trees instead of full ones to make computation feasible. Alpha-beta pruning allows analysts to skip moves when another option proves better for the same player.

What advantages do randomized algorithms offer when solving game trees?

Randomized algorithms provide speed and practicality compared to deterministic versions that take significant time. These methods allow systems to function where complete enumeration remains computationally prohibitive while foiling an enemy opponent who cannot beat the system by knowing the algorithm used. Randomized algorithms have an expected run time that scales differently than deterministic approaches.

See all questions about Game tree →