Course contentsShow
← Computer Science
Lesson 2765 of 2,87261. AI and Search AlgorithmsFree lesson

Game Trees and Ply Depth

Understanding game trees as state-space representations with nodes as game states and edges as moves.

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.