Theory of Games 83

7.6 Games of perfect information

Let us now consider games somewhat more abstractly in order to develop a little of the

theory of the logic of games. What is a game, really? In the kind of game known as a two-

player game of perfect information, there are two players, who take turns making moves,

and a play of the game consists of a sequence of such moves, played until the outcome

of this particular game play is known. The phrase perfect information is meant to suggest

the idea that both players play from a position of complete knowledge about the state of

the game; neither holds any hidden knowledge or secret powers concerning how the play

could proceed. A position in the game is simply a legal sequence of moves; we imagine

how play might proceed from that position, after those moves had been played. We shall

include in this the empty sequence, which corresponds to the starting position of the game,

as well as the positions arising right when a winner has become known. The collection of

positions for a given game has the structure of a tree, known as the game tree.

A fragment of the game tree for the familiar game of tic-tac-toe is shown in figure 7.1.

The game begins with an empty 3 ×3 grid, and player X may place her mark on any of the

nine squares, followed by player O and then X again in turn. Each player is trying to make

tic-tac-toe, or three in a row, and the first player to do so wins. The initially empty board is

shown, along with the nine possible first moves for player X. In the full game tree, each of

these nine boards leads in turn to eight possible replies by O, for 72 possible boards after

two moves, each of which admits seven possible follow-up moves by X, for 504 possible

boards after three moves, and so on. The entire game tree is quite large. (One can cut down

the game tree a little by observing that there are essentially only three first moves, not nine,

namely, the corner move, side move and middle move; by symmetry, it does not matter

which particular corner or side is chosen—and there are also a few symmetries still after

two moves and sometimes more, but the tree is still very large.) Here, we have pictured

just part of the game tree, showing the choices that arise during the course of a particular

play of the game, one in which X ultimately wins. The game of tic-tac-toe, like chess, is a

bit different from other games that we shall consider in that some plays of tic-tac-toe and

chess lead to a draw situation, where the game is over but neither player has won. In other

common kinds of games, every outcome is a win for exactly one of the players.

Any two-player game of perfect information has an associated game tree, which contains

in a sense all the relevant information about the game, delimiting the space of legal moves

and indicating who wins any particular play (or whether it is a draw). Indeed, every finite

tree can be viewed as a game tree, if one should merely specify of the terminal nodes the

winner of that particular play. The game begins at the top node of the tree, and each player

in turn selects a child node of the current node, until a terminal node is reached and the

outcome becomes known. We therefore define that a finite game consists of a finite tree,

whose terminal nodes are labeled as a win for either the first or the second player, or as a

draw.