A Sample Game Tree

Consider, for example, the following game tree which begins not at the root but in the middle of the game (because otherwise, the tree would be way too big to display). Note that this is different from the game shown in the illustration in the beginning of this section. We have numbered the nodes with numbers 1, 2, …, 14.

The tree is composed of alternating layers where it is either Min’s turn to place an O or Max’s turn to place an X at any of the vacant slots on the board. The player whose turn it is to play next is shown at the left.

The game continues at the board position shown in the root node, numbered as (1) at the top, with Min’s turn to place O at any of the three vacant cells. Nodes (2)–(4) show the board positions resulting from each of the three choices respectively. In the next step, each node has two possible choices for Max to play X each, and so the tree branches again.

When starting from the above starting position, the game always ends in a row of three: in nodes (7) and (9), the winner is Max who plays with X, and in nodes (11)–(14) the winner is Min who plays with O.

Note that since the players’ turns alternate, the levels can be labeled as Min levels and Max levels, which indicates whose turn it is.