(NOTE: Check out the other posts in The Secrets of Nim series.)
Do you read Grey Matters regularly? If so, you'll have a great advantage in figuring out Star Nim. Even if not, you can have some fun playing and figuring out the game right in this post!
First, let's get the rules of Star Nim down. It's a standard Nim game. As defined in the first Nim post, that simply means that the last person to remove an object is the winner.
Star Nim is played on a board like the one below (in fact, that's where you'll be playing it!), which starts with a penny in each circle (8 total). As with all versions of Nim, players alternate taking turns. On each turn, a player may remove 1 penny, or 2 pennies connected by a straight line segment. Neither player may remove 0 objects on their turn.
In the version below, the computer will always go first, and you'll be the 2nd player. This is because the 2nd player can always win with the right strategy, and the purpose of playing this game is to figure out that winning strategy.
To start, click the Start New Game button, and pennies will appear in the circles, except for any pennies the computer has taken as its first move. Click on any penny to remove it, and then the computer will ask if you wish to remove a 2nd penny. If you wish to removed 2nd penny, click OK, and if you don't wish to, click Cancel.
The computer will then make its move, removing either 1 penny or 2 pennies connected by a line, and then it's your turn again. If you click on a penny and no other pennies are along lines connected to that one, the computer will not ask you if you wish to make another move.
Remember that the object of the game is to be the last person to remove a penny, and that you're playing over and over again in order to figure out what the winning strategy is for the 2nd player. Don't read beyond the game until you've at least tried this game several times.
Did you figure it out? This isn't one of the more challenging variants of Nim, so it usually doesn't take too many times to figure out the winning strategy.
A good knowledge of the other versions of Nim is a good help, of course. If you recognize the board from the Penny Star Puzzle variation of the last post's Knight Shift puzzle, you should also realize that the design plays an important part.
Let's start with the last part first. As discussed in Knight Shift post, the pattern of the board can be opened up into a simple circle. If you didn't figure out the strategy already, try playing on the board above while simultaneously making the same moves on a circular version of the board. You'll quickly see why the winning strategy works, as well.
If you can generalize the solution, you can also play on any size board.
Obviously, the first secret to winning this game is to let the other person go first. After the other person has moved, you need to make sure that your move leaves the board with two equally-sized groups of pennies remaining on the board.
With an even number of spots on the board, as we have above, this simply means taking the same number of coins as the first player. If the board has an odd number of spots, such as the 9-spot board in chapter 12 of Martin Gardner's book, Time Travel and Other Mathematical Bewilderments, this strategy requires you to take the opposite number of pennies as the first player. You'd take one penny if the first player took two, and vice-versa.
After that, the strategy is much like that of Multi-Pile Nim when you're left with two equal piles. Simply take the same number of pennies every time as the other player did on the previous turn, making sure to take only the pennies directly across from the ones that were taken. Once you understand this technique, the star's symmetry almost becomes a guide for your next properly play.
How long did it take you to figure it out? Did you try playing Star Nim with anyone else? I'd love to hear about it in the comments!
Posts
No Response to "The Secrets of Nim (Star Nim)"
Post a Comment