Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Nim Game Strategy Formula?
Is there a formula you can use (besides) binary to help figure out a winning strat for a nim game.
There are 15 objects in one row on a table. Each player can take 1, 2, or 3 objects at a time. The player who takes the last object wins.
There are 15 objects in one row on a table. Each player can take 1, 2, or 3 objects at a time. The player who takes the last object loses.
There are 77 objects on the table. Each player can remove 1 to 9 objects from the (single) pile. The player who takes the last object loses.
Any help would be so very appreciated!
2 Answers
- 8 years agoFavorite Answer
Yes!
There are one or two points to make about Nim in general:
1) You cannot always force a win.
2) One of the factors is whose turn it is.
3) To win you need to leave the game in a "safe state" after your turn.
The first person to gain control of the game should win as long as he or she always leaves the game in a safe position. Note, you cannot always guarantee to gain control because if it is your turn to go first the rules may have decreed that the objects are already safe.
To work out how to win it is easier to start at the end rather than the beginning. Let's take your rules where a player can pick up 1, 2 or 3 and the last player to pick up wins.
Imagine a game with only 1 object. The person whose turn it is has to win.
Imagine 2 objects. Next player wins again assuming the best move is made.
3 objects, next player wins.
4 objects, next player loses. If we call the players a and b we can soon see why (NB "a - 1" means "a" takes one):
a - 1; b - 3; b wins
a - 2; b - 2; b wins
a - 3; b - 1; b wins
So leaving 4 objects after your turn is a safe position.
What about 5? Assume b's turn then if that happens then b takes 1 and leaves 4 which is a safe state. The game above is then played and b wins. So in a table it might look like this (assume a's turn next):
Objects Last Win Move Last Lose Move
1 a wins take 1 b wins ?
2 a wins take 2 a wins take 1
3 a wins take 3 a wins take 2
4 b wins ? a wins take 3
5 a wins take 1 b wins ?
6 a wins take 2 a wins take 1
7 a wins take 3 a wins take 2
8 b wins ? a wins take 3
9 a wins take 1 b wins ?
10 a wins take 2 a wins take 1
11 a wins take 3 a wins take 2
12 b wins ? a wins take 3
13 a wins take 1 b wins ?
14 a wins take 2 a wins take 1
15 a wins take 3 a wins take 2
So a quick rule for the last player wins version would be to always leave an exact multiple of 4 (i.e. 4, 8, 12). For a last player loses game then the rule is leave one more than a multiple of 4 (i.e. 5, 9, 13).
There is also the strategy where you play the last player wins and the last player loses the same way until just before the final safe position, Then you play differently.
The table above demonstrates that the last player loses scenario can be the same as the other version but with one extra boject. That is, the safe positions are just moved forwards one place.
The 77/1-9 game, therefore, has safe positions at 10, 20, 30, 40, 50, 60 and 70 for last player wins. Add 1 to those number for last player loses.
