Let’s Play a Game, Part 2: Game Trees and Totally Finite Games

After that nice plug last week from Uncertain Principles, I really wanted to get Part 2 posted right away, but real life and school had to be taken care of first. (Getting toward the end of the term, thesis is due soon, have to do my taxes, a friend is coming to visit… It’s going to be a busy few weeks!) However, I can’t let that stop me from posting about math! This post will continue the discussion of game theory that leads into Hypergame, but we won’t get there just yet. Although I originally intended this to be only two parts, there’s just too much of interest along the way, and besides, I want to end this post with several questions to think about.

Winning Strategies from Game Trees

So, when we last left off, we had established a family of games in which each game has a pretty simple winning strategy for one of the two players (a subfamily of the Nim games, as miller pointed out). But these are by no means the only games for which one player can always win if he/she plays perfectly, and many of these games have far less orderly strategies. In general, any game for which we can build a structure called a game tree has a winning strategy, and in fact we can extract the strategy from the tree in an algorithmic way. For example, here’s the game tree for the game G(6, 3) described in Part 1:

Note first of all that each node in the tree represents the state of the game (number of counters in this case) after a particular player’s move, and that each of the branches below each node is one of the next player’s options for how to move. For instance, following the leftmost path down the tree, each player could remove two counters, resulting in a win for Player 1 (since Player 1’s last turn ends with no counters remaining).

I’ve labeled each node with a star, starting at the bottom (the “leaves” of the tree). The labeling rule is as follows: If a node is a leaf, it is a win for the player whose level it’s on, so label it with that player’s color. Otherwise, if a node is on Player 1’s level, it is a win for Player 1 if and only if ALL of its “children” are Player 1’s color; otherwise it is a win for Player 2. Likewise for nodes on Player 2’s level. (More intuitively, what this means is that at any point in the game, if it is Player 1’s turn, Player 1 can win as long as he/she has at least one option that leaves NO good moves for Player 2.)

By propagating this labeling rule back up the tree to the start, it’s easy to see that each node must get exactly one color, and so the starting node must be a win for either Player 1 or Player 2. Thus, any game for which we can construct a game tree must have a winning strategy for one player; which consists of always choosing a correct colored node of the tree on each turn. Note that this means the winning strategy need not be easy to describe (as it was for the Nim games described in Part 1); in fact, for many games the winning strategy is so complicated that even once it’s been discovered, it’s nearly impossible for a human to keep track of. This means, among other things, that the existence of a winning strategy for one player does not guarantee that that player will win in a real-life gameplay, and so the enjoyment and sense of competition is in no way diminished.

Regardless of the ability of humans to actually follow winning strategies for sufficiently complicated games, a popular problem in this area of game theory is to take a specific well-known game and attempt to find the winning strategy (or at least determine which player has it) by constructing the game tree (usually via computer). When someone has successfully done this for a particular game, the game is said to be solved. A couple of interesting games that have recently been solved: Connect Four was solved in 1988 (which counts as recent in mathematics, where some of the best techniques still come from the ancient Greeks), with a win for the first player if you start in the center. Ghost was solved by, among other people, Randall Munroe of that bastion of geeky goodness, xkcd (not the first to solve it, as he admits, but probably the first to do so on an airplane).

All this is taking us somewhat away from Hypergame, but it’s interesting material in its own right and it’s the motivation for the concepts that first led to Hypergame. I promise we’ll get there!

Game Trees from Totally Finite Games

So apart from attempting t0 construct it, how do we know if a given game even has a game tree? We can certainly think of games that don’t have game trees–tennis, for instance. But is there a set of properties that together guarantee the existence of a game tree, and therefore a winning strategy? The answer is yes, and it’s not hard to convince yourself that they work:

1. The game has two players which move alternately, with each player having complete knowledge of the other’s moves and options.
2. There is no chance.
3. No ties (every play of the game ends in a distinct winner).
4. Every play of the game ends after finitely many moves (the game can’t go on forever).
5. At any point in the game, the player whose turn it is has finitely many options for his/her next move.

Any game that has all five properties is called totally finite.

Clearly the Nim games from Part 1 satisfy all five conditions; what are some games that don’t? Well, most card games fail both (1) and (2), since they involve chance dealings from the deck as well as players hiding their cards from everyone else. Tic-tac-toe satisfies everything but (3), since the game can end in a tie. (Incidentally, am I the only one who learned to call a tie in tic-tac-toe a “cat’s game”? I’ve always know it that way, but recently I got some strange looks for it.)

An example that satisfies all but (4) and (5) is the one I mentioned at the end of Part 1: the game G(m, n) with the rules modified so that each player can remove any real number between 0 and n (not including 0 and n), rather than just whole numbers. (5) fails because there are infinitely many numbers between 0 and n, and (4) fails because if they wanted to, the players could remove 1, 1/2, 1/4, 1/8, …

Some interesting things to note about the last two examples: First of all, although tic-tac-toe allows ties, we can still construct a [pseudo] game tree. However, neither player has a winning strategy, because if both are playing perfectly, they will tie. Strictly speaking, what we can construct is not a true game tree because we can’t apply the labeling rule to its nodes, but it still suffices to map out all possible plays of the game, and the tree is still finite.

Secondly, the modified G(m, n) still has a winning strategy, even though we can’t construct a (finite) game tree. As commenter kezdro pointed out, the winning strategy is exactly the same: (assuming n divides m) the second player should always remove n – (whatever Player 1 last removed). Interestingly, the misere form of this game–whoever brings the total down to 0 loses–does not have a winning strategy. If both players are playing perfectly the game will go on forever.

So a winning strategy does not necessarily require a game tree, but a game tree (a true one) guarantees a winning strategy, and a totally finite game guarantees a game tree. THAT’S the motivation for the five properties described above, but it’s going to get us into trouble if we’re not careful…

Supergame!

So, let’s play a game. The rules of Supergame are pretty simple: on the first move, Player 1 picks any totally finite game. From this point on, the chosen game is played, with Player 2 acting as the first player in that game. Now I’ll end with a couple of questions, the same questions William Zwicker asked his students when he first came up with the idea:

1) Who [if either] has the winning strategy for Supergame?

2) Is naming “Supergame” a legal first move in a play of Supergame?

[Update: Corrected both the game tree and the explanation of the labeling rule--I had it completely backwards! To be fair, it was about 4 in the morning when I did that part.]

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

[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.