IN ANY game between two opponents playing alternately, in which the legality of moves is not governed by chance, it is intuitively clear that there must be some best method of playing; and if both play correctly the result of the game is determined by the initial position. In fact if, when it is A's turn he cannot force a win then, however A moves, B can follow with a move after which A again cannot force a win. By repeating these tactics B can at least secure a draw, which should be the conclusion of the game unless B can force a win. This reasoning holds even for card games, with the snag that there the players are not allowed to know the state of the game.

There is a remarkably simple theory for the game with piles of
matches (or nuts, etc.) called Nim. The move consists of taking any
number () of matches from
any one heap, and the player taking the last match wins.* The theory depends on the operation of Nim Addition,
denoted by ;
when the numbers *x*_{1}, *x*_{2} .. on the
heaps are expressed in the scale of 2 as
(*a*_{ij} = 0 or 1; *i* = 1, 2 ..) and
*b*_{j} = 0 or l according as is even or odd, the
Nim Sum is defined to be . This operation
obeys, like ordinary addition, the commutative and associative laws
for bracket-moving; and also has the fundamental property (any
*x*). Now call the position (*x*_{1}, *x*_{2} ..)
winning (W) if , and losing (L) if not.
Then the terminal state (all *x*_{i} = 0, when the games
finishes) is W; and also this classification of states obeys the
characteristic recurrence-relations:-

(1) { | from a non-terminal L it is always possible to move to a W, |

from a W it is impossible to move to a W. |

*A player who once moves to a winning position can evidently
continue to do so at his subsequent moves, and so eventually
win.*

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | .. |

1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 | .. |

2 | 3 | 0 | 1 | 6 | 7 | 4 | 5 | .. |

3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | .. |

4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | .. |

5 | 4 | 7 | 6 | 1 | 0 | 3 | 2 | .. |

6 | 7 | 4 | 5 | 2 | 3 | 0 | 1 | .. |

7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | .. |

... | ... | ... | ... | ... | ... | ... | .. | .. |

* There is a variation in which the last
mover loses.

Cf. C. L. Bouton, *Annals of Mathematics* (Harvard), 2nd Series,
III (1901-2); W. W. R. Ball, *Mathematical Recreations and
Essays*, Ch. I; Hardy and Wright, *Theory of Numbers*,
etc.

More generally, if a draw is impossible, a similar classification exists, provided the moves for the two players are identical and depend only on the state of the game. First let each terminal state be classified W or L according as (by the rules of the game) the player moving to it wins or loses. Owing to the fact that states of the game form a "partially ordered set" it is now possible, with these end-conditions fixed, to work backwards as far as required using (1) at each stage. This procedure is quite practicable, though laborious unless a lucky guess can be made. It follows again from (1) that a player who once moves to a W state can continue to do so, and eventually win either by himself moving to a terminal W, or by his opponent moving to a terminal L.

In Nim a state *X* = (*x*_{1}, *x*_{2} ..) may be regarded as
reducible to a "product" *X*_{1} *X*_{2} .. (in any order) of
irreducible states *X*_{1} = (*x*_{1}, 0 ..), *X*_{2} =
(*x*_{2}, 0 ..) ..; and at each move just one of the irreducible
components (factors) is changed (perhaps into a reducible factor in
other similar games). For games of this restricted type, in which the
last mover wins, the work of classification can be made easier without
recourse to guessing by means of a function (= integer ) of the variable *X* (=
general state of the game) determined by the properties:-

(2) { | any single move alters the value of , |

if , the value of can be decreased to in one move, | |

when X is terminal. |

Taking the existence of for granted,
comparison of (2) with (1) shows that *X* is a W-state if
and only if . It may also be deduced
from (2) that

(3)

This accounts for the advantage of working with , since *all the winning positions will be
known if the value of is calculated
merely for irreducible states*. In practice the values of may be found by working back from the end of the
game, using (2) and (3).

The following game with piles of matches is an example:-

The
move consists of taking any pile and dividing it into two
*unequal* parts. The game is one in which the last mover wins;
and its states may be described by sets of co-ordinates
*x*_{1}, *x*_{2} .., giving the numbers in the
heaps. We may use the same law of combination (*x*_{1}, *x*_{2},
..).(*y*_{1}, *y*_{2}, ..) = (*x*_{1}, *x*_{2}, .. *y*_{1}, *y*_{2}, ..), obtained
simply by putting the two sets of heaps side by side, as before; and
then, since the game is of the type just considered, we have as a
special case of (3):

(4)

The irreducible states are those (*x*) with only one
co-ordinate (i.e. one heap of *x* matches) and the law of
moving is that (*x*) may be replaced by (*u*,
*v*) if

{ | x = u + v, |

all co-ordinates . |

The values of , obtained (with the help of (4)) according to (2) with this law are

x | = | 1, | 2, | 3, | 4, | 5, | 6, | 7, | 8, | 9, | 10, | 11, | 12, | 13, | 14, | 15, | 16, | 17, | .. |

= | 0, | 0, | 1, | 0, | 2, | 1, | 0, | 2, | 1, | 0, | 2, | 1, | 3, | 2, | 1, | 3, | 2, | .. |

Owing to the curious repetitions, these values are quite easy to remember. Thus, as in Nim, a player using the theory can almost invariably win without visible calculation.

*Eureka*, **2**.

Reproduced from Eureka 27 pages 9-11.

HTML conversion Copyright © 2002-4 The Archimedeans.

The game of dividing piles into two unequal parts is known as Grundy's Game; computations have so far failed to determine whether the values for this game, and some other similar games, are ultimately periodic.

Return to Eureka 27 home page

Return to Eureka home page

Return to Archimedeans home page

About Eureka Online

Contact: The Archimedeans (Eureka Online) (archim-eureka-online@srcf.ucam.org)

Online HTML version last updated: 3 March 2004