Mathematics and Games

BY P. M. GRUNDY

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 (>= 1) 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 +_N; when the numbers x1, x2 .. on the heaps are expressed in the scale of 2 as x_i = \sum_j a_{ij} 2^j (aij = 0 or 1; i = 1, 2 ..) and bj = 0 or l according as \sum_i a_{ij} is even or odd, the Nim Sum x_1 +_N x_2 +_N .. is defined to be \sum_j b_j 2^j. This operation obeys, like ordinary addition, the commutative and associative laws for bracket-moving; and also has the fundamental property x +_N x = 0 (any x). Now call the position (x1, x2 ..) winning (W) if x_1 +_N x_2 +_N .. = 0, and losing (L) if not. Then the terminal state (all xi = 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.

Nim Addition Table
e.g. 3 +_N 6 = 5
01234567..
10325476..
23016745..
32107654..
45670123..
54761032..
67452301..
76543210..
.........................

* 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 = (x1, x2 ..) may be regarded as reducible to a "product" X1 X2 .. (in any order) of irreducible states X1 = (x1, 0 ..), X2 = (x2, 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 \Omega(X) (= integer >= 0) of the variable X (= general state of the game) determined by the properties:-

(2) { any single move alters the value of \Omega(X),
if 0 <= \omega < \Omega(X), the value of \Omega can be decreased to \omega in one move,
\Omega(X) = 0 when X is terminal.

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

(3)    \Omega(XY..) = \Omega(X) +_N \Omega(Y) +_N ...

This accounts for the advantage of working with \Omega, since all the winning positions will be known if the value of \Omega is calculated merely for irreducible states. In practice the values of \Omega 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 x1, x2 .., giving the numbers in the heaps. We may use the same law of combination (x1, x2, ..).(y1, y2, ..) = (x1, x2, .. y1, y2, ..), 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)    \Omega[(x_1, x_2, ..)] = \Omega[(x_1)] +_N \Omega[(x_2)] +_N ...

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, u != v
all co-ordinates >= 1.

The values of \Omega[(x)], 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,..
\Omega[(x)]=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.

Additional notes to the online version

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