Game Trees and Ply Depth
What You'll Learn
You'll learn how game trees represent all possible game states as nodes and all legal moves as edges, and how "ply depth" measures how many moves ahead we're looking.
The Game Tree Model
In adversarial games like chess or tic-tac-toe, we need a way to explore all possible futures. A game tree is a state-space representation where:
- Nodes = game states (board configurations)
- Edges = moves (actions that transform one state into another)
- Root = current game position
- Children = all states reachable by one legal move
Think of it like a family tree, but instead of ancestors, you're mapping every possible sequence of moves from now until the game ends.
What Is Ply Depth?
Ply is a single move by one player. The ply depth is how many individual moves deep we search in the tree.
- 1-ply: Look at all positions after your next move
- 2-ply: Look at your move, then opponent's response
- 3-ply: Your move → opponent's move → your move again
For example, searching 4-ply in chess means examining all sequences: you move, opponent moves, you move, opponent moves.
Why It Matters
Deeper search = better decisions, but exponentially more computation. In chess, with ~35 legal moves per position, 4-ply explores roughly 35⁴ ≈ 1.5 million positions!
Key Takeaway: Game trees model adversarial games as state-space graphs where each node is a game state and each edge is a move; ply depth measures how many moves ahead the search explores, directly affecting both decision quality and computational cost.