So you’ve got yourself set up to write a console game and I’ve got you looking at the Silver Dollar Game. Surely this is just too simple? In actual fact it probably is. Based on what I’ve said about why program, your going to be a good stage with your programming skill that this game is going to be trivial.
Well, I don’t want to suggest writing a really complicated game in a short blog so I’ll stick with it and learning C++ for console games should be a breeze. So let’s get coding. Unfortunately, before you code up this simple problem you need to consider your software design. Planning is all important so here is the plan for this game.
The game is essentially for one player game with the computer playing the opponent. To be a good opponent the computer needs to be able to find the best next position at each move. The Silver Dollar Game is a variant on the game of Nim. Without going into too many details, the winning position is when all the gaps between pairs of coins is reduced to zero; i.e. all the coins reach the left hand side. To ensure this is the case, moves before this must ensure that you get to make that last move which closes the last gap. The game doesn’t work with just one coin since the first player can simply move the left most coin to the leftmost position. With two coins, the first player cannot move the leftmost coin to the leftmost position because it means player 2 will win. Player 1 needs to ensure that the gap between coin 1 & 2 can be reduced to have at least 2 spaces over a number of turns. This rule is the same for coins 3 & 4, and 5 & 6, etc.
The rule for this is:
- measure the gaps between even pairs of coins starting from the right (i.e. n and n-1, n-2 and n-3, n-4 and n-5, etc.) If there are an odd number of coins, measure the gap between the left of the board and the leftmost coin.
- Using Nim-Sum, (i.e. x-or) combine the gap sizes. If the value is 0, you have a losing position. If the value is not zero, need to use this value to reduce the gap size and retain the winning position.
How does this poor description translate into an algorithm?
- Nim-Sum is; gap1 x-or gap2 x-or gap3 … etc.
- if this is zero, then randomly move a coin since the position is a loss (or ask the other player to go first!)
- if this is not zero (an opportunity to win), then find the first gap where Nim-Sum x-or that gap is smaller than that gap. This smaller gap is the size we want that gap to be so we simply move a coin to make the new gap size, this size!
Simple… next step is write this algorithm in C++. This will be our prototype or pre-dev game!