Winning Ways for Your Mathematical Plays

Volume 1

Elwyn R. Berlekamp

• Éditeur: A K Peters/CRC Press
• Année: 2018
• ISBN:
  9780429945595
• Édition: 2
• Sujet: Matematica
• Sous-sujet: Matematica generale

This classic on games and how to play them intelligently is being re-issued in a new, four volume edition. This book has laid the foundation to a mathematical approach to playing games. The wise authors wield witty words, which wangle wonderfully winning ways. In Volume 1, the authors do the Spade Work, presenting theories and techniques to "dissect" games of varied structures and formats in order to develop winning strategies.

-1-

Whose Game?

‘Begin at the beginning,’ the King said, gravely, ‘and go on till you come to the end, then stop.’

Lewis Carroll, Alice in Wonderland, ch. 12

It is hard if I cannot start some game on these lone heaths.

William Hazlitt, On Going a Journey

Who’s game for an easy pencil-and-paper (or chalk-and-blackboard) game?

Figure 1. A Blue-Red Hackenbush Picture.

Blue-Red Hackenbush

Blue-Red Hackenbush is played with a picture such as that of Fig. 1. We shall call the two players Left and Right. Left moves by deleting any bLue edge, together with any edges that are no longer connected to the ground (which is the dotted line in the figure), and Right moves by deleting a Red edge in a similar way. (Play it on a blackboard if you can, because it’s easier to rub the edges out.) Quite soon, one of the players will find he can’t move because there are no edges of his color in what remains of the picture, and whoever is first trapped in this way is the loser. You must make sure that doesn’t happen to you!

Well, what can you do about it? Perhaps it would be a good idea to sit back and watch a game first, to make sure you quite understand the rules of the game before playing with the professionals, so let’s watch the effect of a few simple moves. Left might move first and rub out the girl’s left foot. This would leave the rest of her left leg dangling rather lamely, but no other edges would actually disappear because every edge of the girl is still connected to the ground through her right leg. But Right at his next move could remove the girl completely, if he so wished, by rubbing out her right foot. Or Left could instead have used his first move to remove the girl’s upper arm, when the rest of her arm and the apple would also disappear. So now you really understand the rules, and want to start winning. We think Fig. 1 might be a bit hard for you just yet, so let’s look at Fig. 2, in which the blue and red edges are separated into parts that can’t interact. Plainly the girl belongs to Left, in some sense, and the boy to Right, and the two players will alternately delete edges of their two people. Since the girl has more edges, Left can survive longer than Right, and can therefore win no matter who starts. In fact, since the girl has 14 edges to the boy’s 11, Left ends with at least 14 − 11 = 3 spare moves, if he chops from the top downwards, and Right can hold him down to this in a similar way.

Figure 2. Boy meets Girl.

Tweedledum and Tweedledee in Fig. 3 have the same number of edges each, so that Left is 19 − 19 = 0 moves ahead. What does this mean? If Left starts, and both players play sensibly from the top downwards, the moves will alternate Left, Right, Left, Right, until each player has made 19 moves, and it will be Left’s turn to move when no edge remains. So if Left starts, Left will lose, and similarly if Right starts, Right will lose. So in this zero position, whoever starts loses.

Figure 3. Tweedledum and Tweedledee, about to have a Battle.

The Tweedledum and Tweedledee Argument

In Fig. 4, we have swapped a few edges about so that Tweedledum and Tweedledee both have some edges of each color. But since we turn the new Dum into the new Dee exactly by interchanging blue with red, neither player seems to have any advantage. Is Fig. 4 still a zero position in the same sense that whoever starts loses? Yes, for the player second to move can copy any of his opponent’s moves by simply chopping the corresponding edge from the other twin. If he does this throughout the game, he is sure to win, because he can never be without an available move. We shall often find games for which an argument like this gives a good strategy for one of the two players–we shall call it the Tweedledum and Tweedledee Argument (or Strategy) from now on.

Figure 4. After their first Battle: Ready for the Next?

The main difficulty in playing Blue-Red Hackenbush is that your opponent might contrive to steal some of your moves by cutting out of the picture a large number of edges of your color. But there are several cases when even though the picture may look very complicated, you can be sure that he will be unable to do this. Figure 5 shows a simple example. In this little dog, each player’s edges are connected to the ground via other edges of his own color. So if he chops these in a suitable order, each player can be sure of making one move for each edge of his own color, and plainly he can’t hope for more. The value of Fig. 5 is therefore once again determined by counting edges–it is 9 − 7 = 2 moves for Left. In pictures like this, the correct chopping order is to take first those edges whose path to the ground via your own color has most edges–this makes sure you don’t isolate any of your edges by chopping away any of their supporters. Thus in Fig. 5 Left would be extremely foolish to put the blue edges of the neck and head at risk by removing the dog’s front leg; for then Right could arrange that after only 2 moves the 5 blue edges here would have vanished.

Figure 5. A Dog with Leftward Leanings.

How Can You Have Half a Move?

But these easy arguments won’t suffice for all Hackenbush positions. Perhaps the simplest case of failure is the two-edge “picture” of Fig. 6(a). Here if Left starts, he takes the bottom edge and wins instantly, but if Right starts, necessarily taking the top edge, Left can still remove the bottom edge and win. So Left can win no matter who starts, and this certainly sounds like a positive advantage for Left. Is it as much as a 1-move advantage? We can try counterbalancing it by putting an extra red edge (which counts as a 1-move advantage for Right) on the ground, getting Fig. 6(b). Who wins now?

Figure 6. What do we mean by Half a Move?

If Right starts, he should take the higher of his two red edges, since this is clearly in danger. Then when Left removes his only blue edge, Right can still move and win. I...