## Cut The Knot!An interactive column using Java applets
by Alex Bogomolny |

# Taking Games Seriously

April 2001

What may be said about the book whose preface opens in the following manner?

Does a book need a Preface? What more, after fifteen years of toil, do three talented authors have to add?

In twenty years since it first appeared *Winning Ways for Your Mathematical Plays* became a classic and a rarity. So did its companion book *On Numbers And Games* that was written in just about a week by one of the *WW*'s authors and saw the light of the day five years earlier. The authors of course remained good friends.

There's more good news. Thanks to A. and K. Peters, both books are now in new editions. *ONAG* and the first volume of *WW* are already out. The remaining three volumes of *WW* are scheduled to appear over the year 2001.

How much do the books differ from their first editions? I can't give a comprehensive answer, but there are changes. One of the first pages in *WW* has a one paragraph introduction for each author accompanied by a reasonably sized likeness. So some changes are discernable to a naked eye, provided you have the first edition on hand to compare. The *WW*'s authors claim to have expanded the Extras at the ends of the chapters, have inserted many references for further reading, and have corrected some of the one hundred sixty three mistakes left over in the first edition.

The new edition of *ONAG* offers an especially written prologue and an epilogue with an outline of the more important developments since the first edition. *ONAG*, however still ends with the same

### Theorem 100

*This is the last theorem in this book*.

whose proof is said to be obvious. As before, the book begins with Chapter 0 and, as before, the book is in *number*, part *games*. Some games are numbers, some are not. The games in question are played by two players -- usually *Left* and *Right* -- who make alternate moves. (*WW* has also material on one person games -- puzzles.) Games are described by positions. For each position P, rules of the game determine positions P^{L} available to Left (*Left options*) and positions P^{R} available to Right (*Right options*). Conversely, every position is completely defined by the options available to the players, which is concisely expressed as ^{L} | P^{R}}.

The simplest game of all, the *Endgame*, has both option sets empty and is denoted *normal play*, the player with no options whose turn it is to move is declared a loser. So that in the game 0, the second player to move is a winner. In the game {0|}, Left has a legal move which ends the game, whereas Right has no move at all. In the game {|0}, the situation is reversed. Further notations that reflect the number of move advantages clearly favor Left. Thus,

Naturally, 2 = {0,1|}, 3 = {0,1,2|}, and so on, and similarly for negative integers: -2 = {|0,-1}, etc. In general, a game is negative, positive, or zero, depending on whether Left, Right, or the second player has a winning strategy. Some games are neither. For example, the game *fuzzy* or *confused with 0*, but should not be confused with the subject of *Fuzzy Set Theory*.

The theory and practice of mathematical games often force the players to play several games simultaneously. This can be done in several ways (*ONAG*, Chapter 14). The most common is taking their *disjunctive sum*: the player to move selects a component game, and then makes a move legal in that game. For any game P, *negation* is defined *inductively* as

-P = {-P^{R} | -P^{L}},

which effectively reverses Left's and Right's options. Further, consider the game {0|1}, which is a clear win for Left and is thus positive, and the sum

Any move by Left leads to

A first move by Right leaves two options for Left:

This means that {0|1} + {0|1} + {|0} = 0, and meaningfully *dyadic* fractions are similarly defined in a finite number of steps.

Games can be compared. P > Q, provided the sum *Numbers* are defined inductively as those games P whose options are numbers with an added condition that no left option is greater than or equal to any right option. As there are no options to compare with, 0 is a number, as are all integers defined above and the dyadic fractions at whose creation we just hinted. The adopted notations reflect on the *value* associated with a game. Thus, for example, the game 1 is greater than the game 0.

A left option in a game is said to be *dominated* by any *greater* (or equal) left option. A right option is *dominated* by any *smaller* (or equal) right option. It can be shown that dominated options can be removed without affecting the game's value. In particular, the integer definitions are simplified to

n + 1 = {n|} and -n-1 = {|-n}.

It can also be shown that ^{n+1} = {p/2^{n} | (p + 1)/2^{n}}.

Other numbers (and games) are constructed out of dyadic rationals in an infinite number of steps similarly to *Dedekind's cuts*. For example, since

1/3 = {1/4, 1/4 + 1/16,1/4 + 1/16 + 1/64, ... | 1/2, 1/2 - 1/8, 1/2 - 1/8 - 1/32, ...}

In the same breath, we also get ω = {0, 1, 2, 3, ...|}. And, with this, more numbers like

Further on are obtained marvels like

Little wonder the term *surreal numbers* coined by D. Knuth stuck around. Surreal numbers have been written about by M. Gardner and the term has been officially adopted in the second edition of *ONAG*.

So some games are numbers, while others are not. An additional classification distinguishes between *partisan* and *impartial* games. In the latter, exactly the same options are available to the two players. Examples of impartial games include Nim and its many dependents and incarnations: Scoring, Nimble, Northcott's game, Plainim, and more. Appearances notwithstanding, numbers (as defined above) do not appear as values of impartial games. Furthermore, numbers are also looked at condescendingly as options in the partisan games. The reason is that, in general, a number (in its simplified form) lies between its left and right options. So each player makes himself worse off by moving into a number. In *WW*, this fact appears as *The Number Avoidance Theorem*: DON'T MOVE IN A NUMBER UNLESS THERE'S NOTHING ELSE TO DO. In *ONAG*, numbers are simply regarded as the stopping positions. Once there, simply award the payoff to Left if the number is positive and to Right if its negative. Naturally, if a number is to be reached, Left will try to get its value as large as possible, Right will try to have it small.

But there is a value in trying. Practice. Beat your friends until they learned the game's secrets. Here's one example.

### Contorted Fractions

You are given several fractions that can be modified according to certain rules:

- The number replacing a given one must have strictly smaller denominator, or,
- If the denominator is already 1, it must have numerator strictly smaller in absolute value than that of the original number.

There are two players: *Left* and *Right*. A replacement is only legal for *Left* if it decreases the number, legal for *Right* only if it increases the number. You choose to be either *Right* or *Left* and may force your computer to go first by pressing *You move* button. All numbers in the game are modified by clicking a little off their center line. Clicking on the right increases the number, clicking on the left decreases it. To perform a move, select a fraction, adjust it to the desired value and press the *I move* button.

The game has two parameters. *#Numbers* is the number of fractions in a game. *Max* is the absolute maximum number that may appear in the numerator or denominator of a game.

This game has a curious theory. The numbers that appear in the game are related to the game's value somewhat indirectly. First of all, it's clear that the game is the disjunctive sum of simpler games each consisting of a single fraction. Each of these, depending on the sign, are a one move win to either Left or Right. When several games are played simultaneously, Left will try to decrease the value of a fraction as little as possible, Right will try to increase its value as little as possible.

From position '2/5' Left can move to positions '1/3', '1/4', '-1/2', '0', '-2', etc., and Right can move to positions '1/2', '2/3', '3/4', '1', '10', etc. According to the above piece of wisdom, Left should choose '1/3', Right should choose '1/2'. Symbolically:

'2/5' = {'1/3' | '1/2'}.

What the players are looking for in that game, is the nearest approximation to a rational number by fractions with smaller denominators. These are given by the number's parents on the Stern-Brocot tree. Truly, solving this problem provides a student of fractions with plenty of practice.

A more sophisticated student may surmise that, as the parents are replaced by their parents, the binary encoding and continued fractions come into the play. Each Contorted Fractions game has only two undominated positions. Therefore, its value is necessarily a dyadic number. For a single fraction x, what is the value of the position 'x'? The answer is given by juxtaposing the binary encoding of x on the Stern-Brocot tree and what is known as Berlekamp's rule for interpreting *Hackenbush strings* (*WW*, pp. 77-78) or *sign-expansions* (*ONAG*, p. 31).

As an example, '(1 + Ö5)/2' = 5/3. Now a note for those who would like to pursue the matter further. In the first edition of *ONAG*, there is a remark on page 84 that refers to a note on page 96:

Note to p. 84: Some analytic properties of the function discussed on pp. 83-86 are established by J. G. Mauldon in Quart. J. Math. Oxford Ser., 17 (1966), p.261.

In the second edition, we read instead (p. 84) that the function is traditionally called "Minkowski's Question-Mark Function," and has interesting analytic properties. Talk about changes.

Writing about M. C. Escher [Carnival, p. 102] M. Gardner remarked:

When I first reproduced an Escher picture for my column for April, 1961 (and *Scientific American* ran one of his bird tessellations for cover), I purchased from Escher only one print, a woodcut. For mere $40 to $60 each I could have bought scores of pictures that now would each be worth thousands. But who could then have anticipated the astonishing growth of Escher's fame?"

In recent years I had similar regrets about several missed opportunities to purchase the first editions of *WW* and *ONAG* in 1970-80s. I am happy to own the books now. I am sure that, by supplying the demand, A. and K. Peters will see to it that the books will not fetch much more than their present cost. However, their worth lies elsewhere. The books show the side of mathematics usually missed by math textbooks. As the *WW*'s authors wrote in the preface:

It is not a book on recreational mathematics because there's too much serious mathematics in it. On the other hand, for us, as for our predecessors Rouse Ball, Dudeney, Martin Gardner, Kraitchik, Sam Loyd, Lucas, Tom O'Beirne and Fred. Schuh, mathematics itself is a recreation.

I believe that to become a successful subject, this is how mathematics must be taught to young children -- as a recreation. For a curious and an attentive teacher, the books, especially *WW*, go a long way to suggest how is this possible. It's about time that mathematical games be given a serious consideration by curriculum developers.

### References

- E. R. Berlekamp, J. H. Conway, R. K. Guy,
*Winning Ways for Your Mathematical Plays*, Volume 1, A K Peters, 2001 - J. H. Conway,
*On Numbers And Games*, A K Peters, 2001 - M. Gardner,
*Mathematical Carnival*, Vintage Books, 1977 - M. Gardner,
*Penrose Tiles to Trapdoor Ciphers*, W. H. Freeman and Company, 1989 - D. E. Knuth,
*Surreal Numbers*, Addison-Wesley, 1974

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

62055894 |