Game tree

A game tree represents a game as a rooted tree whose branches show possible moves and whose nodes show decision points or outcomes.

Extensive-form game: A game representation that specifies players, decision order, available actions, and outcomes. Game trees are the tree-shaped representation of an extensive-form game.
Minimax: A decision rule that chooses a move by minimizing the opponent’s best possible payoff. Minimax evaluates alternating choices from terminal outcomes back to the root.
Chess: A two-player strategy board game in which players move pieces to checkmate the opposing king. Chess engines search trees of legal move sequences to select moves.
Normal-form game: A game representation that lists each player’s strategies and the resulting payoffs. It records strategic outcomes without displaying the sequence of moves as a tree.
Node (graph theory): A vertex in a graph, connected to other vertices by edges. Each game-tree node marks a decision point or terminal position.
Alpha–beta pruning: A search optimization that skips branches unable to affect a minimax decision. It reduces the number of game-tree branches that need evaluation.
Tic-tac-toe: A two-player game in which players place marks on a three-by-three grid to form a line. Its small tree can be explored completely to establish optimal play.
Game graph: A directed graph whose vertices are game states and whose edges are legal moves. Unlike a tree, it can merge paths that reach the same state or contain cycles.
Edge (graph theory): A connection between two vertices in a graph. Each edge represents a move from one game position to another.
Game-tree search: A procedure for exploring possible game states to select an action. It traverses the tree to compare consequences of candidate moves.

Linked from 18 pages