Determinacy - Determinacy From Elementary Considerations

Determinacy From Elementary Considerations

All finite games of perfect information in which draws do not occur are determined.

Familiar real-world games of perfect information, such as chess or tic-tac-toe, are always finished in a finite number of moves. If such a game is modified so that a particular player wins under any condition where the game would have been called a draw, then it is always determined. The condition that the game is always over (i.e. all possible extensions of the finite position result in a win for the same player) in a finite number of moves corresponds to the topological condition that the set A giving the winning condition for G_A is clopen in the topology of Baire space.

For example, modifying the rules of chess to make drawn games a win for Black makes chess a determined game. As it happens, chess has a finite number of positions and a draw-by-repetition rules, so with these modified rules, if play continues long enough without White having won, then Black can eventually force a win (due to the modification of draw = win for black).

It is an instructive exercise to figure out how to represent such games as games in the context of this article.

The proof that such games are determined is rather simple: Player I simply plays not to lose; that is, he plays to make sure that player II does not have a winning strategy after I's move. If player I cannot do this, then it means player II had a winning strategy from the beginning. On the other hand, if player I can play in this way, then he must win, because the game will be over after some finite number of moves, and he can't have lost at that point.

This proof does not actually require that the game always be over in a finite number of moves, only that it be over in a finite number of moves whenever II wins. That condition, topologically, is that the set A is closed. This fact--that all closed games are determined--is called the Gale-Stewart theorem. Note that by symmetry, all open games are determined as well. (A game is open if I can win only by winning in a finite number of moves.)