Games as Trees

The 15 Game

To play the 15 game, write the numbers 1 through 9 in a square. Player one is X and player two is O. Player one starts by drawing an X through any unchosen number. Then player two circles an unchosen number. The game is won when one player has collected three numbers which add up to 15. In the sample game, player two has won because 8 + 6 + 1 = 15. Note that having 9 and 6 alone would not be a win even though 9 + 6 = 15, because you need three numbers which sum to 15.


Abstract Games

What does it mean for two games to be the same? Why is chess the same game whether you play with plastic pieces or ivory pieces? In what sense is the 15 Game the same as Tic-Tac-Toe? One way to approach these questions is to draw a game tree. A game tree is an abstract representation of an actual game. To draw a game tree, draw one dot to represent the starting position of the game. Now for each legal move that player one has, draw a new branch coming out of the dot. For example, X has nine possible moves at the start of a Tic-Tac-Toe game, so the initial dot will have nine edges coming out of it. The ends ("leaves") of these branches each represent a possible position that player two will see. Add new branches corresponding to the legal moves that player two has. Repeat this process, only stopping when you have reached a position representing the end of the game.
Part of the game tree for 2x2 Tic-Tac-Toe

Playing the Tree-climbing Game

A mathematical tree is a graph with no loops. One point of the graph should be singled out as the root of the tree.

    To play the tree-climbing game, draw any tree. Player one starts at the root and climbs up a branch to any neighboring point. Then player two climbs to any neighbor of that point, and so forth (no backtracking allowed!). The first player to reach the treetop wins. Conversely, the first player who is stuck and cannot climb higher loses.

The Number Game

To play the number game, choose any positive whole number n as your starting position. To make a move, choose a prime p which divides n. Then divide n by whatever positive power of p that you like, as long as the result is still a whole number. For example if n = 12, the valid moves are 3, 2, and 4 (22) resulting in the positions 4, 6, and 3 respectively. A player loses if n = 1 on the start of their turn, since this means they have no legal moves left.
  • What does the game tree for the number game look like starting at n = 12? What is the best strategy for the first player? Who wins the game?
  • Play the number game using different values of n. Which games are a win for the second player? Draw the game trees for some of these games and work out the best strategies.

Finding the Winner of Any Game

Since the game tree knows everything about how a game is played, we can use it to predict who the winner is. To do this, we will use a recursive algorithm. First, let us define some terminology relating to trees. For a point on the tree, the edges rising out of the point are called branches. In a game tree, the branches represent the possible moves that a player has in the given position. A point on a tree is a leaf if it does not have any branches coming out of it -- for game trees, the leafs are the same as the ending positions of the game. Given a point on the tree, the corresponding subtree is the part of the tree which rises out of that point.

Here is a recursive process for creating an algebraic expression involving x from a tree: This is a little tricky to understand in writing, but easier to understand by example. Study the two diagrams below until you understand how to use this recursive algorithm.
To check that you understand the algorithm, try to turn the game tree for the number game starting at n = 12 into an expression. You should get the following answer:
To find out who the winner is, set x = 0 and simplify, using the rules If you get zero, then the first player has a winning strategy. If you get one, then the second player has a winning strategy. This means that you can figure out who wins any game just by finding the game tree, converting it to an expression and simplifying the result when x = 0!

Further Reading

Back to index