|Mathematics and Games|
|You are in: Home > Eureka > 27 > Mathematics and Games
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 () 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 x1, x2 .. on the heaps are expressed in the scale of 2 as (aij = 0 or 1; i = 1, 2 ..) and bj = 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 (x1, x2 ..) winning (W) if , 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:-
A player who once moves to a winning position can evidently continue to do so at his subsequent moves, and so eventually win.
* There is a variation in which the last
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 (= integer ) of the variable X (= general state of the game) determined by the properties:-
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
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 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
The values of , obtained (with the help of (4)) according to (2) with this law are
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.
Reproduced from Eureka 27 pages 9-11.
top of page - home - about the site - contact us - sitemap
Last Updated: 3rd March 2004, 5:48pm — HTML conversion Copyright © The Archimedeans 2002-2007
Eureka archives maintained by Eureka Online Editor (email@example.com)
Site maintained by firstname.lastname@example.org