The Mathematics of Games

John D. Beasley

• Publisher: Dover Publications
• Year: 2013
• Print ISBN: 9780486449760
• eBook ISBN: 9780486151625
• Topic: Mathematics
• Subtopic: Game Theory
• Index: Mathematics

"Mind-exercising and thought-provoking."—New Scientist
If playing games is natural for humans, analyzing games is equally natural for mathematicians. Even the simplest of games involves the fundamentals of mathematics, such as figuring out the best move or the odds of a certain chance event. This entertaining and wide-ranging guide demonstrates how simple mathematical analysis can throw unexpected light on games of every type—games of chance, games of skill, games of chance and skill, and automatic games.
Just how random is a card shuffle or a throw of the dice? Is bluffing a valid poker strategy? How can you tell if a puzzle is unsolvable? How large a role does luck play in games like golf and soccer? This book examines each of these issues and many others, along with the general principles behind such classic puzzles as peg solitaire and Rubik's cube. Lucid, instructive, and full of surprises, it will fascinate mathematicians and gamesters alike.

1

INTRODUCTION

The playing of games has long been a natural human leisure activity. References in art and literature go back for several thousand years, and archaeologists have uncovered many ancient objects which are most readily interpreted as gaming boards and pieces. The earliest games of all were probably races and other casual trials of strength, but games involving chance also appear to have a very long history. Figure 1.1 may well show such a game. Its rules have not survived, but other evidence supports the playing of dice games at this period.

Figure 1.1 A wall-painting from an Egyptian tomb, c.2000 BC. The rules of the game have not survived, but the right hands of the players are clearly moving men on a board, while the left hands appear to have just rolled dice. From H. J. R. Murray, A history of board games other than chess (Oxford, 1952)

And if the playing of games is a natural instinct of all humans, the analysis of games is just as natural an instinct of mathematicians. Who should win? What is the best move? What are the odds of a certain chance event? How long is a game likely to take? When we are presented with a puzzle, are there standard techniques that will help us to find a solution? Does a particular puzzle have a solution at all? These are natural questions of mathematical interest, and we shall direct our attention to all of them.

To bring some order into our discussions, it is convenient to divide games into four classes:

1. games of pure chance;
2. games of mixed chance and skill;
3. games of pure skill;
4. automatic games.

There is a little overlap between these classes (for example, the children’s game ‘beggar your neighbour’, which we shall treat as an automatic game, can also be regarded as a game of pure chance), but they provide a natural division of the mathematical ideas.

Our coverage of games of pure chance is in fact fairly brief, because the essentials will already be familiar to readers who have made even the most elementary study of the theory of probability. Nevertheless, the games cited in textbooks are often artificially simple, and there is room for an examination of real games as well. Chapters 2 and 3 therefore look at card and dice games respectively, and demonstrate some results which may be surprising. If, when designing a board for snakes and ladders, you want to place a snake so as to minimize a player’s chance of climbing a particular ladder, where do you put it? Make a guess now, and then read Chapter 3; you will be in a very small minority if your guess proves to be right. These chapters also examine the effectiveness of various methods of randomization: shuffling cards, tossing coins, throwing dice, and generating allegedly ‘random’ numbers by computer.

Chapter 4 starts the discussion of games which depend both on chance and on skill. It considers the spread of results at ball games: golf (Figure 1.2), association football, and cricket. In theory, these are games of pure skill; in practice, they appear to contain a significant element of chance. The success of the player’s stroke in Figure 1.2 will depend not only on how accurately he hits the ball but on how it negotiates any irregularities in the terrain. Some apparent chance influences on each of these games are examined, and it is seen to what extent they account for the observed spread of results.

Chapter 5 looks at ways of estimating the skill of a player. It considers both games such as golf, where each player returns an independent score, and chess, where a result merely indicates which of two players is the stronger. As an aside, it demonstrates situations in which the cyclic results ‘A beats B, B beats C, and C beats A’ may actually represent the normal expectation.

Chapter 6 looks at the determination of a player’s optimal strategy in a game where one player knows something that the other does not.

Figure 1.2 Golf: a drawing by C. A. Doyle entitled Golf in Scotland (from London Society, 1863). Play in a modern championship is more formalized, and urchins are no longer employed as caddies; but the underlying mathematical influences have not changed. Mary Evans Picture Library

This is the simplest case of the ‘theory of games’ of von Neumann. The value of bluffing in games such as poker is demonstrated, though no guarantee is given that the reader will become a millionaire as a result. The chapter also suggests some practical ways in which the players’ chances in unbalanced games may be equalized.

Games of pure skill are considered in Chapters 7-10. Chapter 7 looks at puzzles, and demonstrates techniques both for solving them and for diagnosing those which are insoluble. Among the many puzzles considered are the ‘fifteen’ sliding block puzzle, the

N queens’ puzzle both on a flat board and on a cylinder, Rubik’s cube, peg solitaire, and the ‘twelve coins’ problem.

Chapter 8 examines ‘impartial’ games, in which the same moves are available to each player. It starts with the well-known game of nim, and shows how to diagnose and exploit a winning position. It then looks at some games which can be shown on examination to be clearly equivalent to nim, and it develops the remarkable theorem of Sprague and Grundy, according to which every impartial game whose rules guarantee termination is equivalent to nim.

Chapter 9 considers the relation between games and numbers. Much of the chapter is devoted to a version of nim in which each counter is owned by one player or the other; it shows how every pile of counters in such a game can be identified with a number, and how every number can be identified with a pile. This is the simplest case of the theory of ‘numbers and games’ which has recently been developed by Conway.

Chapter 10 completes the section on games of skill. It examines the concept of a ‘hard’ game; it looks at games in which it can be proved that a particular player can always force a win even though there may be no realistic way of discovering how; and it discusses the paradox that a game of pure skill is playable only between players who are reasonably incompetent (Figure 1.3).

Figure 1.3 Chess: a drawing by J. P. Hasenclever (1810-53) entitled The checkmate. Perhaps White has been paying too much attention to his wine glass; at any rate, he has made an elementary blunder, and well deserves the guffaws of the spectators. Mary Evans Picture Library

Finally, Chapter 11 looks at automatic games. These may seem mathematically trivial, but in fact they touch the deepest ground of all. It is shown that there is no general procedure for deciding whether an automatic game terminates, since a paradox would result if there were; and it is shown how this paradox throws light on the celebrated demonstration, by Kurt Gödel, that there are mathematical propositions which can be neither proved nor disproved.

Most of these topics are independent of each other, and readers with particular interests may freely select and skip. To avoid repetition, Chapters 4 and 5 refer to material in Chapters 2 and 3, but Chapter 6 stands on its own, and those whose primary interests are in games of pure skill can start anywhere from Chapter 7 onwards. Nevertheless, the analysis of games frequently brings pleasure in unexpected areas, and I hope that even those who have taken up the book with specific sections in mind will enjoy browsing through the remainder.

As regards the level of our mathematical treatment, little need be said. This is a book of results. Where a proof can easily be given in the normal course of exposition, it has been; where a proof is difficult or tedious, it has usually been omitted. However, there are proofs whose elegance, once comprehended, more than compensates for any initial difficulty; striking examples occur in Euler’s analysis of the queens on a cylinder, Conway’s of the solitaire army, and Hutchings’s of the game now known as ‘sylver coinage’. These analyses have been included in full, even though they are a little above the general level of the book. If you are looking only for light reading, you can skip them, but I hope that you will not; they are among my favourite pieces of mathematics, and I shall be surprised if they do not become among yours as well.

2

THE LUCK OF THE DEAL

This chapter looks at some of the probabilities governing play with cards, and examines the effectiveness of practical shuffling.

Counting made easy

Most probabilities relating to card games can be determined by counting. We count the total number of possible hands, and the number having some desired property. The ratio of these two numbers gives the probability that a hand chosen at random does indeed have the desired property.

The counting can often be simplified by making use of a well-known formula: if we have n things, we can select a subset of r of them in n!/{r!(n - r)!} different ways, where n! stands for the repeated product n × (n-1) × . . . × 1. This is easily proved. We can arrange r things in r! different ways, since we can choose any of them to be first, any of the remaining (r - 1) to be second, any of the (r - 2) still remaining to be third, and so on. Similarly, we can arrange r things out of n in n × (n-1) × . . . × (n - r + 1) different ways, since we can choose any of them to be first, any of the remaining (n - 1) to be second, any of the (n - 2) still remaining to be third, and so on down to the (n - r + 1)th; and this product is clearly n!/(n - r)!. But this gives us every possible arrangement of r things out of n, and we must divide by r! to get the number of selections of r things that are actually different.

The formula n!/{r!(n - r)!} is usually denoted by (ⁿ_r). The derivation above applies only if 1 ≤ r ≤ (n - 1), but the formula can be extended to cover the whole range 0 ≤ r ≤ n by defining 0! to be 1. Its values form the well-known ‘Pascal’s Triangle’. For n ≤ 10, they are shown in Table 2.1.

Table 2.1 The firs...

Table of contents

• Title Page
• Copyright Page
• PREFACE TO THE DOVER EDITION
• ACKNOWLEDGEMENTS
• Table of Contents
• 1 - INTRODUCTION
• 2 - THE LUCK OF THE DEAL
• 3 - THE LUCK OF THE DIE
• 4 - TO ERR IS HUMAN
• 5 - IF A BEATS B, AND B BEATS C . . .
• 6 - BLUFF AND DOUBLE BLUFF
• 7 - THE ANALYSIS OF PUZZLES
• 8 - SAUCE FOR THE GANDER
• 9 - THE MEASURE OF A GAME
• 10 - WHEN THE COUNTING HAS TO STOP
• 11 - ROUND AND ROUND IN CIRCLES
• FURTHER READING
• INDEX
• A CATALOG OF SELECTED DOVER BOOKS IN SCIENCE AND MATHEMATICS
• DOVER BOOKS ON MATHEMATICS