Answer: Pick-up Sticks Game
Saturday, 12 of January , 2008 at 12:01 am
Question: The Fort Boyard TV Series had a game where 19 sticks were placed on the ground. Two players would take turns picking up sticks. A player is only allowed to pick up 1, 2, or 3 sticks each round. The person who picks up the last stick loses. What is each player’s “optimal” strategy? If both players play “optimal” strategies, who will win?
Answer: According to the Axiom of Determinacy, any finite two-person game, with perfect information, will have a winning strategy for one of the players. This will mean that one of the two players in our game will have an “optimal” strategy.
In order to determine the optimal strategy, will need to make a decision tree. For the Pick-up Sticks Game, we will have the following decision tree:
Player one starts the game on node 19 and is allowed to move to any connected node. Player two then moves to another connected node. This continues until one of the players reaches node 1 and wins the game.
Next, we will need to start coloring the nodes with P and N which are defined as:
N: The node is a winning position for the next player.
P: The node is a winning position for the previous player.
This would mean, if node 19 was colored N, player one would win. However, if node 19 was colored P, player two would win. Also, we already know that node 1 has to be colored P.
In order to find the coloring of the other nodes, we need to follow two simple rules.
1) If all children are N nodes, the color of the parent has to be P.
2) If at least one of child is P, then the parent has to be labeled N.
If we apply these rules to our decision tree, we will get:
Since node 19 is labeled N, player one will win. Player one’s optimal strategy is to always move to a P colored node.
Question: The Fort Boyard TV Series had a game where 19 sticks were placed on the ground. Two players would take turns picking up sticks. A player is only allowed to pick up 1, 2, or 3 sticks each round. The person who picks up the last stick loses. What is each player’s “optimal” strategy? If both players play “optimal” strategies, who will win?
Answer: According to the Axiom of Determinacy, any finite two-person game, with perfect information, will have a winning strategy for one of the players. This will mean that one of the two players in our game will have an “optimal” strategy.
In order to determine the optimal strategy, will need to make a decision tree. For the Pick-up Sticks Game, we will have the following decision tree:
Player one starts the game on node 19 and is allowed to move to any connected node. Player two then moves to another connected node. This continues until one of the players reaches node 1 and wins the game.
Next, we will need to start coloring the nodes with P and N which are defined as:
This would mean, if node 19 was colored N, player one would win. However, if node 19 was colored P, player two would win. Also, we already know that node 1 has to be colored P.
In order to find the coloring of the other nodes, we need to follow two simple rules.
1) If all children are N nodes, the color of the parent has to be P.
2) If at least one of child is P, then the parent has to be labeled N.
If we apply these rules to our decision tree, we will get:
Since node 19 is labeled N, player one will win. Player one’s optimal strategy is to always move to a P colored node.
Comment by eldila
Made Saturday, 12 of January , 2008 at 12:07 am
You should be able to use the same technique to solve the The Determinant Game. I tried a simple recursive algorithm in Java but ran out of memory on my stack. I haven’t made another attempt, but it should be possible to solve it computationally using the coloring technique shown in this problem.