From Scratch Web Games: A Beginners Guide to Game Development using HTML, CSS, and JavaScript

Chapter 2 Bonus: Solving NIM

Treasure NIM

For those not already familiar with NIM, this is a simple math-based game where the goal is to get the last item. Players alternate turns where they must take 1 item but can optionally take 2 or 3 items. NIM is a simple game that has a very strong bias to one of the players based on how many items there are. Many games have an optimal strategy, though more complex games may hide this as the rules of those games make the solution to winning the game much harder to see. The rules of this game are simple enough that we can work out the optimal strategy for the game. Once you understand the strategy, and assuming you are not in a losing position, will guarantee you win the game as long as you don’t make a mistake.

To figure out this winning strategy, we simply need to look at the end game and work our way backwards, where we will see a rather interesting pattern.

• If there is only 1 item left, you are going to take that item to win.
• If there are 2 items left, you will take both items to win.
• If there are 3 items left, you will take three items to win.
• If there are 4 items, it doesn't matter how many items you take as there will always be 1-3 items left so your opponent will win.

This means that 4 is vital to control, which then leads to the following:

• If there are 5 items, take 1 item to be at 4 otherwise opponent will win
• If there are 6 items, take 2 items to be at 4 otherwise opponent will win
• If there are 7 items, take 3 items to be at 4 otherwise opponent will win
• If there are 8 items it doesn't matter how many items you take as there will always be 1-3 items left to capture 4 so your opponent will win.

This pattern continues, making 12, 16, 20 … the key numbers to control in order to win. You can mathematically describe this as choice = modulus (remaining / 4). If the result is 0 then you are in a losing position and should randomly pick between 1-3 items and hope your opponent makes a mistake.

Bomb NIM

The variant Bomb NIM works the same way except that the player wants to avoid getting the last items. The strategy for this is the same as above, except that the target numbers are shifted up by 1. After all, if you grab the second to last item, then the opponent is forced to take the last item. So your target numbers then become 2, 5, 9, 13….

Calendar NIM

There are many variations of NIM which try to add additional complexity to the game to make the optimal solution less obvious so the game becomes more challenging. One variant (which itself has several variants) is calendar NIM. This works by having the players start on January 1st of the year with the goal to grab December 31st. Each turn the player can either advance the month by 1 or take 1-3 days. Advancing the month moves to the next month on the same day but if the current day is past the number of days in the month, the current day becomes the last day of that month. So March 31st would become April 30th. The varying number of days, and two dimensions of movement make the solution to this game non-obvious, and makes calculating the next move much more challenging. This is not impossible, however.

To solve this game, we would again, work backwards. Assuming we are in December, the goal becomes very easy. If you are on December 28th, 29th, or 30th then the solution is to take the remaining days. This means that target dates become the 27, 23, 19,… 3rd. But what if we are in another month?

For November we know that once we hit November 30th, the other player would be forced to change the month making the date December 30th which means our next move would be to take December 31st for the win. We can then count back from November 30th, so have target days of 26, 22, 18,…,2. We can continue this process for each month and this will result in the following strategy table:

As you can see, we always want to move to a W date if at all possible. If the opponent is on a W date, we have lost the game unless they make a mistake. The L^ dates are dates that have a win above them so those are good dates to change the month to the next month. If you are not starting on one of those days, you will take the number of days to the next W in that month. As it is not likely that your opponent will let you use a table like this, you would need to memorize the 12 target dates.

This technique is helpful to many games, not just NIM. It also is a technique that I have used to build puzzles for games. Starting with the winning state and working backwards can be a very effective technique for designing puzzles.