Introductory Combinatorial Game Theory
Lesson 6 (Introducing Partial Games)

Since the first lesson, we have described a general method for analyzing games such as Nim, Nimble, Dawson's Chess and Kayles. These games all share an important characteristic: in any configuration, the moves available to either player are identical. Such a trait is most obvious in the game Nim, which makes no restriction on any player's moves due to his identity. For Drawson's Chess, this is not so apparent; since a player can only move pawns which belong to him. Games which possess such a characteristic are said to be non-partizan (or impartial games), as opposed to partizan games (or partial games), which will be introduced next.

For instance, let us look at the game Hackenbush. Let us call our players Left and Right. In the figure below, players Left and Right alternately removes an edge, such that any portion of the diagram which is disconnected from the floor (baseline) has to be removed. Also, Left can only remove a bLue edge, while Right can only remove a Red edge. A player loses if he cannot make a legal move.





Basic Concepts of Games

As introduced previously, given any two games G and H, we may add them up to give a sum G+H. Now we shall introduce another concept: the negative of a game. Simply put, the negative of G (denoted -G) is simply the game G with its 'board flipped', so that players Left and Right have their choices swapped. Apparently, if G is advantageous to player Left, then -G is disadvantageous to Left.

For example, to obtain the negative of our above Hackenbush game, we simply switch the blue and red edges:


Prior to this, we did not have the opportunity to introduce the negative of a game, since the negative of an impartial game is precisely the same game. We may now define subtraction of two games: the game G - H is simply defined by G + ( - H ).

In general, we denote a game by { G^L | G^R }, where G^L and G^R are lists of possible options for players Left and Right. The zero game (denoted 0) is simply { | } (i.e. a game in which neither player has a valid move). For instance, the game below is denoted by:
{ { | 0 } | {{ | 0} | 0}, 0 }



Actually, we can extend this definition a little for any game G:

If the 2nd player has a winning strategy for G, we write G = 0.   If Left has a winning strategy for G (regardless of who starts), then G > 0.   If Right has a winning strategy for G (regardless of who starts), then G < 0.   If the 1st player has a winning strategy for G, we write G || 0.

We can summarise the above definitions in the following table:

		Left starts
		Left wins	Right wins
Right starts	Left wins	G > 0	G = 0
	Right wins	G || 0	G < 0

For convenience, we shall write G >= 0 for the case when G = 0 or G > 0. Similarly, G <= 0 when G = 0 or G < 0. Also, we write G = H, G < H, G > H and G || H for the cases G-H = 0, G-H < 0, G-H > 0 and G-H || 0 respectively.


Rules of Arithmetic

Clearly, for any games G, H and K, we have the rules of commutativity (G + H = H + G) and associativity (   (G + H) + K = G + (H + K)   ).

It turns out that in addition, our rules of thumb for arithmetic hold as well (we shall supply the proofs later):

	G = 0	G < 0	G > 0	G || 0
H = 0	G + H = 0	G + H < 0	G + H > 0	G + H || 0
H < 0	G + H < 0	G + H < 0
H > 0	G + H > 0		G + H > 0
H || 0	G + H || 0

G + (-G) = 0. If G = 0, then -G = 0. If G < 0, then -G > 0. If G > 0, then -G < 0. If G || 0, then -G || 0.

Using the above relations, we obtain:

	G = H	G < H	G > H	G || H
H = K	G = K	G < K	G > K	G || K
H < K	G < K	G < K
H > K	G > K		G > K
H || K	G || K

Some Proofs

Here we shall include some proofs for the above results. Only the more difficult proofs are included.

1. Let us look at the case for G = 0. Suppose first H > 0. Hence, the second player wins in G while player Left wins in H. We need to prove that Left has a winning strategy in the sum G + H. This is really quite easy: the player Left simply refuses to play in the G-component of the game sum. Unless Right plays in G, in which case Left promptly responds in the game G as well. Since G = 0, Left can be assured of having the last move of game G. Hence, Left wins the game, which completes the proof. The other cases of H < 0, H = 0 and H || 0 may be proven similarly (i.e. the winning party simply refuses to play in the G-component, unless it is in response to his opponent's move).
   
   
2. Suppose now G > 0, H > 0, hence the player Left wins in both G and H. He may win in the game G + H as well by adopting the following strategy: at his turn, he always chooses to play in the same component as his opponent's last move. If the event that Left gets the first move, he may start in either component.
   
   
3. To see that G + (-G) = 0, the second player simply mimics the first player's move in a different component. For instance, if the first player chooses to play from G, then the second player responses with a corresponding move from -G and vice versa.
   
   

In a nutshell, we may perform arithmetic (addition and subtraction) on games as if they were numbers. It is even possible to compare between different games to see which is greater.

In the next lesson, we shall assign numbers to games and show that addition (and negation) of the games correspond to the addition (and negation) of the respective numbers. Such games are known as cold games.




Back to the main page...