A game tree represents a game as connected states: each node is a possible position, and each branch is a valid move to another position. It turns an opponent’s choices into a structure that can be explored. section 3.7
A game tree supports Minimax search by:
- Adding every valid move from a state as a child node. section 3.7
- Alternating turns as the search moves deeper through the tree. section 3.7
- Scoring leaf states with a heuristic, then choosing maximum or minimum child scores according to whose turn is simulated. section 3.7
A limited-depth search
A depth of four represents four simulated turns: player A moves, player B moves, then both move again. Because exploring the entire tree can exceed memory and computation limits, the search stops at a chosen depth and evaluates the resulting states. section 3.7
