Game Trees

EXAMPLE 1 Tic-tac-toe The game tree for tic-tac-toe is extremely large and cannot be drawn here, although a computer could easily build such a tree.We showa portion of the game tic-tac-toe in Figure 8(a). Note that by considering symmetric positions equivalent, we need only consider three possible initial moves, as shown in Figure 8(a). We also show a subtree of this game tree leading to terminal positions in Figure 8(b), where a player who can win makes a winning move.

We can recursively define the values of all vertices in a game tree in a way that enables us to determine the outcome of this game when both players follow optimal strategies. By a strategy we mean a set of rules that tells a player how to select moves to win the game. An optimal strategy for the first player is a strategy that maximizes the payoff to this player and for the second player is a strategy that minimizes this payoff.We now recursively define the value of a vertex.

DEFINITION 1 The value of a vertex in a game tree is defined recursively as:
(i) the value of a leaf is the payoff to the first player when the game terminates in the position represented by this leaf.
(ii) the value of an internal vertex at an even level is the maximum of the values of its children, and the value of an internal vertex at an odd level is the minimum of the values of its children.

The strategy where the first player moves to a position represented by a child with maximum value and the second player moves to a position of a child with minimum value is called the minmax strategy. We can determine who will win the game when both players follow the minmax strategy by calculating the value of the root of the tree; this value is called the value of the tree. This is a consequence of Theorem 3.

THEOREM 3 The value of a vertex of a game tree tells us the payoff to the first player if both players follow the minmax strategy and play starts from the position represented by this vertex.
Proof:We will use induction to prove this theorem.
BASIS STEP: If the vertex is a leaf, by definition the value assigned to this vertex is the payoff to the first player.