Introductory Combinatorial Game Theory
Lesson 4 (Games With Possible Draws)

Notice that all the games we've considered are finite games, and these games must end with a definite winner. In this chapter, we shall consider some finite but possibly loopy games (e.g. think of the perpetual check situation in international chess). Let us begin by playing the game of Nim City, but with a wholly different map:


As before, we begin with some cars (placed at some of the cities). A city may contain more than one car. At each player's turn, he may pick up one of the cars, travel through any road, and stop the car at the destination. Since the towns are large one may assume that a town can hold any number of cars. The player who brings all the cars back to the hometown wins. Now the map is problematic because there are cycles abound, namely BEH and EGH. If we were to compute our Nim values accordingly, we would end up with:


So we're unable to determine the status of B, E, F, G and H. Here we shall give a method for finding the Nim values for some of these towns. We will explain why this works when we cover the theory of general games.



Finding Nim Values (More!)

First we label the home town with 0. We then repeatedly apply the following golden rule:

At each stage, for a particular unlabelled town T, consider the set of all labelled towns which are accessible from T. As before let m be the smallest non-negative integer which does not occur in this set. If for each unlabelled town U which is accessible from T, there is a path from U to a town already labelled with *m, then we label town T with *m as well.

Talk is nothing without some action. Let us proceed to analyse our game of Nim City above.

First start with town B. The only labelled town accessible from B is town A, which has a Nim score of *1. Hence, if B is to be labelled, the label must be 0. In addition, for a move from B to E, there is a corresponding path from E to the hometown (which is of value 0). Hence, B should be labelled with 0.

Next, let us look at F. There are two paths from F to labelled towns: namely C and the hometown (of Nim scores *1 and 0 respectively). Now let us consider if F should be labelled with *2. F has only one move to an unlabelled town, which is E. But from E, there exists a path to D which is already given a value of *2. Thus, F should be rightfully labelled as *2.

As a final example, look at town H. It has a path to a town B, which we had just labelled with 0 two paragraphs ago. Now shall we label H with *1? Yes we should, because H has two paths to an unlabelled towns G and E, which can be countered with paths to C and A, both of which are already labelled with *1. Hence, we may label H as *1.

So far so good:


Let's see if we label the last two towns. We can't label E since E has paths to towns A, D, H and hometown, which are labelled with *1, *2, *1 and 0 respectively. E cannot be labelled with *3 since there are no paths to towns which are already labelled with *3. Similarly, we can't label G with 0 since G has a path to itself and there is no path from G to a town labelled 0.

Finally, the remaining towns are labelled with infinity.


Subsequently, in place of the infinity symbol I will use 'inf'. (Well, I could have used the Symbols font-set, but Unix users wouldn't be able to view it.)




Analysing the Game

Now for the main result:

Let m1, m2, ... , mk be the Nim values of the initial starting positions of the cars (some of these values may be 'inf'). Then we have three cases (assuming optimal play between the players): If all of the values are finite, then the result is the same as the game of Nim with piles of m1 sticks, m2 sticks, ... . Suppose exactly one of the value (say m1) is infinite. If there is a path from m1 to a town marked with finite m1', such that the Nim game of m1', m2, m3, ... , mk is a losing position (i.e. 2nd player wins), then our original game is a winning position. Otherwise, the game ends in a draw. If more than one of the values is infinite, then the game ends in a draw.

Thus we have parts (i), (ii), (iii). Perhaps an example will help for (i): let us first begin with three cars at B, D and H. These have Nim values 0, *2, and *1 respectively. So by rights, this should be a first player win. The following table illustrates player A's winning strategy as well as how B's futile attempts to foil it. Do take note of the corresponding Nim values.

A's move		B's move
Game Value	Nim Value	Game Value	Nim Value
(B,D,H) (B,A,H)	(0,*2,*1) (0,*1,*1)	(B,A,H) (B,A,E)	(0,*1,*1) (0,*1,inf)
(B,A,E) (B,A,A)	(0,*1,inf) (0,*1,*1)	(B,A,A) (E,A,A)	(0,*1,*1) (inf,*1,*1)
(E,A,A) (home,A,A)	(inf,*1,*1) (0,*1,*1)	(home,A,A) (home,home,A)	(0,*1,*1) (0,0,*1)

And player A promptly wins the game by moving the last car back home. Notice that twice, B tried to confuse A by moving a car from *m to a position marked infinity. However, by virtue of our analysis, there is definitely a position from this infinity to another town marked *m, and play continues. One question to ponder upon: is it possible for this process to continue indefinitely, i.e. what if we end up rotating between different towns labelled *m? If yes, how do we break out of this loop?



Much Ado About Infinity

We wish to consider parts (ii) and (iii), which involve the tricky concept of infinity. This section might require some thought. Read slowly!

Suppose exactly one of the initial towns T is labelled infinity. And suppose further there is a path from T to a town labelled *m such that *m together with all the other labellings is a losing position. Now the first player simply makes this move to *m, conveniently winning the game.

To see that cases (ii)(b) and (iii) result in a draw, it suffices to show each player may hinder his opponent's victory indefinitely. Let us see how a player might go about doing this. Suppose without loss of generality that the other labels give an (XOR)-sum of *n.

1. For case (ii)(b), there is a unique town T which is labelled 'inf'. Consider all possible Nim values accessible from town T. If it excludes one of the values 0, *1, *2 ... *(n-1), then the player may simply reduce *n to this value, thus giving another case of (ii)(b).
   
   
2. On the other hand, if it includes 0, *1, *2 ... *(n-1) but excludes *n, the very fact that T is not numbered tells us that there is a move from T to another town U (labelled 'inf') from which there is no move to *n. Now the player simply makes this move, which gives us back to case (ii)(b).
   
   
3. For case (iii), the player simply makes the move from one town labelled 'inf' to another, thus giving back case (iii).

But why should a player stick to these rules, you may ask? Indeed, pick any player. If it's currently case (iii) or case (ii)(b) for him, there's no way he can turn it into a case (i) - losing config. If he foolishly turns the game into a case (ii)(a), his opponent would grab the opportunity to win! So his best strategy is to wander around the safe areas of cases (ii)(b) and (iii). And the above reasoning serves to show that such a strategy indeed does exist.




Back to the main page...