0

## The Secrets of Nim (Whim)

Published on Sunday, December 11, 2011 in , , ,

(NOTE: Check out the other posts in The Secrets of Nim series.)

In past posts on Nim, I've discussed multi-pile standard Nim, multi-pile Misère Nim, and how to better visualize your moves for either kind of multi-pile Nim.

I've even discussed Werner Miller's brilliant Wise-Guy Nim variation, in which you allow the other player to decide whether the game will be standard or Misère, after which you subtly alter the rules in your favor.

What would happen if, instead of deciding the goal beforehand, the goal was declared after the game had started?

This unusual variation was developed by John Horton Conway (seen on video in my Iteration, Feedback, and Change: Artificial Life post), who dubbed it “Whim”.

Whim starts just like any other multi-pile Nim game, but with no determination as to whether the last person to remove a match is the winner (standard) or the loser (Misère).

The big difference with Whim is that only once during the game (NOT once per player), one player may, instead of removing objects, make a "Whim move", in which that player declares the goal to be standard or Misère. At this point, the goal of the game is frozen, and no further Whim moves can be made by either player. What effect does this have on strategy?

Since the strategy for both versions of multi-pile Nim are the same up until the final moves, you might figure that this would make analyzing the strategy easy. A complication quickly arises, however, when you realize that not only must a goal be declared at some point during the game, but that the temptation to use the Whim move is itself a factor.

Think about by imagining that you're playing first. Let's say you analyze the layout as I've taught in previous posts, and you determine that no objects need to be removed. If you're applying the strategy from my Visualizing Multi-pile Nim post, this would mean that you noted that all the powers of two are “paired up”.

In this case, it's easy. Instead of making a move, you make the Whim move, declaring the game to be either standard or Misère as you wish (on a whim, as it were). This forces the other player into a losing move either way (their move must “unpair” a power of two), and you will win the game as long as you stick to the proper strategy.

Now let's look at the opposite situation. You analyze the layout, and the normal strategy for Nim says you need to remove some objects. You could remove those objects, but the other player could make the Whim move, and then you're left with another losing position AND no way out (assuming the other player understands and plays regular Nim strategy). The only other possibility here is to intentionally make a losing move (a move that still leaves one of the powers of two “unpaired”)!

It gets worse. The other player must use the same logic, and make another losing move, too. As soon as either player fails to make what would ordinarily be a losing move, the other player can use the Whim move, and win the game from there.

Consider also that the goal must be declared at some point in the game, and the closer you get to the end, the more you need to know the goal in order to win the game. If both players are well versed in multi-pile Nim strategies, this becomes a very big problem, and one that's not easily analyzed.

Despite the difficulty of the analysis, the proper strategy is surprisingly simple and elegant.

You need to treat the Whim move as a separate pile of its own. If there is any pile consisting of 4 or more objects, you imagine that this imaginary “Whim pile” contains 1 object, and analyze the play as if this pile were actually there. Once every pile contains less than 4 objects, you need to think of the imaginary Whim pile as containing 2 objects.

The imaginary Whim pile only gets removed when one of the players makes the Whim move (declares the goal of the game). After that, play is straightforward for anyone who understands multi-pile Nim.

Due to the fact that the rules of Whim create an unusual hole, yet don't provide any apparent way to fill it (until the idea of imaginary piles is properly considered), seasoned Nim players can be stumped by these new rules, even after playing multiple games!