The Chips game - Dynamic programming activity
This is a game between two players. It starts with two piles of chips, tenchips per pile. On each turn, a player may take one chip from one pile, or two chips, one from each pile. If one pile is empty, you can only take one chip from the other pile. The player who takes the last chip or chips wins the game.
- Set up and play the game with another person. Try to win! Play a few more times. Keep track of whether the first player wins or the first player loses. Write W or L here for each game:
- Would you rather be the first player or not? Does it matter? Why or why not?
What you were playing can be called the “10-10” game. If you go first and take one chip from each pile, your opponent becomes the first player in the “9-9” game. If you take one chip from one pile, your opponent becomes the first player in the “9-10” game or the “10-9” game. But these games still have too many chips in them to know exactly what will happen in the end. Let’s make it simpler.
- First, try the “1-1” game. Should the first player always win? How? Try each of the following games, and write W if the first player can guarantee a win, and L if the first player is going to lose. W 1-1 The first player always wins, so I filled in the blank with W
___ 1-0
From now on, you must write out the “m-n” game you give to your opponent.
L 2-0 → 1-0 (W) The first player always loses the 2-0 game, so I filled in the blank with L
3-0 → 2-0 (L) Now you can fill in the blank.
In the next games, the first player should consider all their choices and pick the best one. Be sure to record what “m-n” game you give to your opponent and whether they’ll win or lose!
___ 2-1 → No need to go further than one more game
___3-1 →
___4-0 →
___ 2-2 → 2-1 or 1-2 or 1-1
First / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 100 / - / W / L
1 / W / W
2 / L
3
4
5
6
7
8
9
10
- Let’s organize what we are finding out about these“m-n” games. Use the gridbelow to record whether the first player can guarantee a win (W) or will lose against a sensible opponent (L), starting with the 3-0 game, then 4-0, by going down each column. Figure out how smaller games help you understand larger games. Work slowly! Check your work!
For example, starting with the 3-1 game, you can give your opponent the 2-0 game, the 2-1 game, or the 3-0 game. Which one do you want to give them? Does one of these guarantee you a win?
- Does the first player win the 10-10 game?
- Looking at your analysis of the game, describe a strategy for playing that will guarantee a win to the player who follows it.
There are two lessons to be learned here. First, if you want to solve a problem that is too large to understand at first, start by solving simpler problems. Second, sometimes you can build up the solution for larger problems directly from the solution to smaller problems. This technique is called dynamic programming.
This handout was developed by Craig L. Zirbel;see www-math.bgsu.edu/~zirbel/dpif you want to use it.
Advanced chips game variations
This is a game between two players. It starts with two piles of chips, ten chips per pile.
Variation #1: On each turn, you may take one chip from one pile, or four chips, two from each pile. Does the first player win or lose the 10-10 game?
First / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 100 / -
1
2
3
4
5
6
7
8
9
10
Suggestion: Play out the smallest games, then draw arrows to help you keep track of where to check for the larger games.
Variation #2: On each turn, you may take two chips, one from each pile, or 1, 2, or 3 chips from a single pile. Does the first player win the 10-10 game?
First / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 100 / -
1
2
3
4
5
6
7
8
9
10
Suggestion: Play out the smallest games, then draw arrows to help you keep track of where to check for the larger games.
Developed by Craig L. Zirbel, see