Skip to content
Foundations of AI

Background

Game Trees

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 S\mathcal{S} and a space of possible actions or moves, A\mathcal{A}. Additionally, we have:

  • Players: S⟶{\mathcal{S} \longrightarrow \{ MAX, MIN }\}. Players(s)(s) denotes whose turn it is at state ss.

  • Actions: S⟶A\mathcal{S} \longrightarrow \mathcal{A}. Actions(s)(s) are the available actions for player(s)(s) at state ss.

  • Result: S×A⟶S\mathcal{S} \times \mathcal{A} \longrightarrow \mathcal{S}. Result(s,a)(s, a) is the state that results from taking action aa at state ss.

  • Terminal-test: S⟶B\mathcal{S} \longrightarrow \mathbb{B}. Terminal-test(s)(s) returns true if the state ss is a terminal state.

  • Outcome: S⟶B∪{⊥}\mathcal{S} \longrightarrow \mathbb{B} \cup \{\bot\}. Outcome(s)(s) returns:

    • true if ss is a terminal state that is winning for the MAX player,

    • false if ss is a terminal state that is winning for the MIN player,

    • ⊥\bot otherwise.

  • Initial state: s0∈Ss_0 \in \mathcal{S}.

Game Trees

A game tree is recursively defined as follows:

  • The root of the tree is the initial state s0s_0.

  • For any node ss, the children of ss are the states that result from taking each available action for Player(s)(s) at ss.

  • In particular, if there are no actions available at a state ss, then the state is a leaf node with no children.

Expand a position to explore legal moves. The player taking the final object wins.