Computational Games, part 1

Consider this simple, two-player game. The rules are easy:

  • Both players take turns adding tokens to a central pile, which starts empty.
  • Each player on their turn can add either one or two tokens.
  • The player who adds the tenth token wins.

Go ahead: find a friend and play this game. You don’t even need tokens to play; on your turn just announce how many you’re adding to the pile and what the new value of the pile is. Play the game a few times.

I’ll wait here.

Got it? Great!

While you were playing, you probably discovered that when the score reached a certain point, it became evident that one of the players was going to win no matter what the other did. In other words, the game was essentially over at some point before the score reached ten. There are a few such points in the game. I’ll leave it to you to discover where they are.

This game, which we’ll call “1, 2, … 10,” falls under the category of computational games. With such games, we can use a computer to map out all possible states and moves and completely solve them. Once solved and armed with the tree of all possible moves, a human (or computer) can be unbeatable.

Other computational games include:, Tic-Tac-Toe (or Naughts and Crosses), Othello, Checkers, Connect 4, Nim, Mancala, Chess, and Go. They share a common set of characteristics:

  • Fixed number of players
  • All players have full information; nothing is hidden from any of the players
  • No randomization, such as dice rolls or drawing cards from a shuffled deck

Many beloved games are not computational games, such as poker (hidden cards and randomization), Chutes and Ladders (randomization), Yahtzee (dice rolls), Stratego (hidden pieces), and Hangman. It doesn’t mean we can’t write computer programs to play these games; they just don’t fall under the category of computational games.

Now that we know what computational games are, let’s set about visualizing them as trees.

We’ll represent each state of the 1, 2, … 10 game as a pair of integers: the player number (1 or 2) and how many tokens are in the pile. The initial state is (1, 0). Each state has two possible next moves, the result of adding 1 or 2 to the pile. (Except near the end of the game, where some of the states have only one possible next move.) Here are the first few turns of the game.

The first two moves of the game.

Notice that each row alternates between player 1 and 2. In the top row (the initial state), it is player 1’s turn. The middle row is player 2’s turn. And the bottom row is player 1’s turn.

Some terminology and concepts are worth going over:

In computer science, each of the boxes is called a node. The whole thing is called a tree, even though it is typically drawn upside-down. The topmost node is the root. The nodes at the bottom are called leaves. Each parent node has at least one child, except the leaves that have no children. The root of the tree has no parent.

Let’s draw a few more moves. As you can see, the tree is lop-sided: there are more moves on the left side of the tree because each move increments the score by one, whereas the right side increments by two.

The full game. Not all moves are shown.

At the bottom of the tree are all the end-game states, where the score is 10. We will label each of the states depending on whether they are a winning state or a losing one.

Normally you’d think of the “10” states as wins, but look closely: they are actually losses. Consider the (2,10) state at the far right. It is player 2’s turn and the score is 10. Therefore, player 2 has lost the game because, in reality, the other player won by placing the last two tokens. If player 2 finds himself in that position, he has lost. We label (2,10) as a loss.

Indeed, each of the “10” states are losses for that particular player. All the (1,10) states are losses for player 1 and all the (2,10) states are losses for player 2. We’ll color the losing states red.

The losing states (the “10” states) are colored red.

Now, if the leaf states are losses, the ones immediately above (their parents) them must be wins. Take a look at the (1,8) state just above the losing (2,10) at the far right. It must be a win for player 1 because all she has to do is play two tokens and force player 2 to lose. Player 1 is guaranteed to win from this position.

(I should make it clear at this point that both players are playing to win. No one makes a boneheaded move. Of course player 1 could lose by playing only one token, but she’d be stupid to do so. She’s going to win by playing two tokens.)

The (2,9) states are likewise wins for player 2. He’s guaranteed to win by putting player 1 into a losing position.

In fact, all states that are parents of a losing state are wins. We will color all of them green.

All states with a losing child are wins (green).

What about the other nodes? Consider the (1,7) position, whose children are (2,8) and (2,9). How should we color it?

Unfortunately, it is a loss for player 1 because no matter what move she makes, player 2 will win. We must color the (1,7) node red to signify it is a losing position. The (2,7) state near the middle of the drawing is also a losing state by similar reasoning.

I hope you discovered this tidbit while you were playing the game with a friend. If it was your turn and the score was 7, you were going to lose no matter what you did. (In fact, it wasn’t a game of trying to be first to reach 10; instead the goal was to be first to reach 7.) All “7” states are losses and we should color them red.

All the “7” states are losses (red).

At this point, we can establish a couple of general rules for identifying whether a state is a win or a loss:

  • A state is a win if at least one child state is a loss.
  • A state is a loss if all child states are wins.
  • A state is a draw if there are no losing children and at least one of them is a draw.

The third rule (draw) doesn’t apply to this game because it cannot end in a draw. I’ve included it here for future reference.

Note that to identify whether a particular state is a win or a loss, you don’t need to look any further down the tree than the next move. Start by labeling the leaf states (the ones at the bottom) and work your way up to the root of the tree, applying the three rules above. This leads us to the final coloring.

The final coloring of the game tree.

Something amazing has happened here: the initial state (1,0) is a win! Put another way: player 1 is going to win the game if she doesn’t make any mistakes. Every time.

What move should she make to assure herself of a win? She should aim to force player 2 to lose by playing one token. Player 2, finding himself in the losing (2,1) state, can do nothing to guarantee himself a win.

Armed with this complete game tree, both players can use the information to try to win the game. All they have to do is look for their current position in the tree and see if there are any moves that put the other player into a losing state. If there is at least one, take it. But if there are none, perhaps they should just resign. Or hope the other player goofs up.

What’s next? Try playing the games described below. See if you can figure out whether the first or second player wins, and what the winning strategies are.

Even or Odd: Start with 15 tokens in the pile. Each player takes turn removing one, two, or three tokens from the pile and keeping them. When all the tokens have been removed, the winner is the player who ends up with an even number of tokens.

Nim: Start with three piles of tokens of 3, 4, and 5, respectively. Each player can remove any number of tokens from any one pile on their move. The winner is the player who removes the last token.

To code up the “1, 2, … 10” game in Java, continue to part 2.

I’m indebted to Dr. Daniel Garcia of UC Berkeley whose Games Crafters undergraduate research group introduced me to the field of computational game theory.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s