A game tree captures all possible plays in a game. If you are familiar with interactive fiction, you can imagine that the author of such a game would have to write down all the possible choices that the player can make, and how those choices affect the state of the game. A game tree is a mathematical construct that allows us to do something similar.
Game Ingredients
We will focus on two-player, turn-based, deterministic games with no draws.
Let's refer to these players as the MAX player and the MIN player. A game consists of a state space and a space of possible actions or moves, . Additionally, we have:
Players: MAX, MIN . Players denotes whose turn it is at state .
Actions: . Actions are the available actions for player at state .
Result: . Result is the state that results from taking action at state .
Terminal-test: . Terminal-test returns true if the state is a terminal state.
Outcome: . Outcome returns:
trueif is a terminal state that is winning for the MAX player,falseif is a terminal state that is winning for the MIN player,otherwise.
Initial state: .
Game Trees
A game tree is recursively defined as follows:
The root of the tree is the initial state .
For any node , the children of are the states that result from taking each available action for Player at .
In particular, if there are no actions available at a state , then the state is a leaf node with no children.