Let’s Play a Game!

Finally, a math post! I was going to talk about Ramsey theory, but I need some diagrams for that and I’m going to have to postpone until I have a chance to make them. But that’s okay, because Hypergame is great fun and an insidious little paradox to boot.

First, a little history: The Hypergame paradox was discovered/invented in the 80’s by William Zwicker, a math professor at Union, while creating a test for a course he was teaching on game theory for non-majors. He came up with the idea for a bonus question, which he called Supergame, and then extended it to the Hypergame paradox, which has since been published in a variety of places (he tells me it has sometimes been attributed incorrectly). Hypergame is particularly interesting in that it requires very little mathematical experience to appreciate the paradox, and yet it ties into some very deep theorems in several areas of mathematics.

I first learned about Hypergame last year when Prof. Zwicker gave a seminar on it, and this discussion will follow a similar format, since I like the way he presented it. In this post I’ll give a very brief introduction to the kinds of games we’re interested in in this area of game theory, and in the next post I’ll discuss Supergame, Hypergame, and the nature of the paradox.

Let’s play a game!

We’re going to play a game called G(6, 3). It’s a two person game, and you can go first. The rules are as follows: We start with a total of six counters, and we’ll each take turns removing some of the counters–exactly one or two counters each turn. The winner is the one who takes the last counter.

To the left is a picture of how our game might play out. In this case, the second player won. Now, maybe that was just lucky, but you’ll notice there is no luck at all in this game. Even in as simple a game as this, it all comes down to strategy. Is there a different set of moves you could have chosen that would have forced me to lose?

It turns out, in this case, no. No matter what sequence of moves you make, I can make the right countermoves to win. In this particular game, my winning strategy is fairly simple: however many counters you removed on your previous move, I’ll remove three minus that number.

To see why this will always work, note that at the start the number of counters (6) is a multiple of 3. Also, at the end of each one of my turns, exactly three counters have been removed (if you removed 2, then I removed 1, and vice versa), but at the end of one of your turns, the remaining counters are never a multiple of 3. Eventually the number of counters must reach 0, which is a multiple of three, which can only happen at the end of my turn, so I will always win! (Gosh, I like this game!)

So in the game G(6, 3), the second player has a winning strategy–a way of deciding how to move at any stage in the game to guarantee a win. Note that in this game, the winning strategy can be described very simply; this is not always the case. Note also that the second player doesn’t have to follow the winning strategy, but if not, he/she risks losing.

A Family of Games

We can change G(6, 3) in several interesting ways. One option is to change the initial number of counters; 9 or 12, perhaps. It’s not hard to see that in the games G(9, 3) and G(12, 3), the second player still has a winning strategy. What if the initial number of counters is not a multiple of three–does the second player have a winning strategy in G(11, 3)? If not, does the first player have a winning strategy?

It turns out (but I won’t prove here) that in games like this, that satisfy certain basic properties, exactly one of the players MUST have a winning strategy. In G(11, 3), the first player can always win by first removing 2, and then playing as the second player in what is now G(9, 3).

How else can we modify our game? Well, we can change the maximum number of counters each player can remove on a turn–in particular, in the game G(m, n), each player may remove between 1 and n-1 counters per turn. So for G(20, 7), for instance, we start with 20 counters and each player may remove 1, 2, 3, 4, 5, or 6 of them. Player 1 has the winning strategy, which is to remove 6 counters on the first move, and on each subsequent turn, if Player 2 removed x counters, Player 1 should remove 7-x counters (which is always a legal number). In fact, we can generalize this statement: For any game G(m, n), if m is a multiple of n, Player 2’s winning strategy is to remove n minus the number of pieces Player 1 last removed. If m is not a multiple of n, Player 1’s winning strategy is to remove the appropriate number of pieces to make what remains a multiple of n (divide m by n; the remainder is what Player 1 should remove), and then play as the second player.

So for every pair of positive whole numbers m and n, with m≥n, we have a game we can play for which one of the players always has a winning strategy. (Actually, you could allow n>m, but it would end pretty quickly.) These make up a family of games of the form G(m, n). How many of them are there?

This family of games are all pretty easy, but they have certain properties that they share with some much more challenging games like chess, checkers, and so on, and those properties will lead us nicely into Hypergame, in the next post.

In the meantime, I leave you with two questions:

1) Any game G(m, n) is guaranteed to end after a finite number of moves, no matter what each player does on each turn. What if we relax the rules so that on each turn, a player can remove any number between 0 and n (not including 0 and n), including fractions?

2) Is the statement “This sentence is false.” true or false?

*****

I’m still working on style and level of mathematical sophistication here, so any feedback is appreciated. I know there are a few of you readers out there, and I know you have varying degrees of experience, so tell me–is this too easy? Too hard? Just right? How’s the clarity of my explanations?

–––––––––––––––––––––––––––––––––––––––––––––––

[1] William S. Zwicker, “Playing Games with Games: the Hypergame Paradox”, American Mathematical Monthly 94 (1987), no. 6, 507–514.

The inspiration for this series of posts (and some of the structure) comes from a seminar given by Prof. William Zwicker at Union College, November 2007, as well as personal discussion.