Inspired by the comments on this post, I’ve had some ideas brewing for a while—I’m just only now getting around to writing them up.

The topic is visualizing winning strategies for "nim-like" games. What do I mean by that? By a nim-like game I mean a game in which two players take turns removing objects from some piles (subject to some rules), and the last player to play is the winner (or, sometimes, the loser).

A cute variant, due to Paul Zeitz (and introduced to me by Sue VanHattum), is to think of a pet shop with different types of pets; players take turns visiting the pet shop and buying some pets, until the store is all out of pets.

For games with only two piles, or a pet store with only two types of pets, playing the game can also be thought of as making moves on a square grid. The -coordinate represents, say, the number of Xoloitzcuintli, and the y-coordinate the number of Yaks; the square with coordinates means that the pet store has xolos and yaks left. Buying some xolos corresponds to moving left; buying yaks means moving down; buying an equal number of each means moving diagonally down and left; and so on.

Here are a few examples of nim-like games:

• In the game of nim, you may only buy one type of animal on each turn (but you can buy as many as you want). On a grid, you are allowed to move any distance left or down (but not both).

  The interesting thing is that we can visualize the winning strategy for this game in the following way. (Zachary Abel has a much more detailed explanation of this idea.) A winning position is a square that guarantees a win—that is, if it is your turn and you are on a winning square, then (assuming you make the right move and continue to play perfectly) you will win the game. I’ll indicate winning positions by light green squares, like this: . A losing position is a position such that you can’t win no matter what move you make (assuming your opponent plays perfectly). I’ll indicate losing positions by dark blue squares, like this: . In fact, the winning positions are exactly those from which there exists at least one legal move to a losing position; and the losing positions are those from which every legal move is to a winning position.

  Here’s what it looks like for nim:

  

  Not too exciting, but it makes sense. If the pet store has an equal number of each type of pet remaining, the first person to move is going to lose: their move will result in an unequal number of pets (i.e. a square off the main blue diagonal), and all their opponent has to do is buy an equal number of the other type of pet to restore balance. Ultimately the losing player will be forced to clean the store out of one type of pet, and the other player then wins by cleaning the store out of the other type.

• In Wythoff’s game, you may buy any number of a single type of animal, or an equal number of both. On a grid, you are allowed to move any distance left, down, or at a 45 degree angle left and down.

  The visualization for this game, of course, is much more interesting:

  

  You can read all about the fascinating analysis of this game (and its visualization) on Zachary Abel’s blog.

• In a comment, Max described a game from the International Olympiad in Informatics:

  You start with a rectangle, and you can cut it either vertically or horizontally at integer sizes, each time keeping the larger piece; the goal is to obtain a unit square (so that your opponent can’t move).

  It’s not as obvious, but this is also a nim-like game. The two dimensions of the rectangle correspond to the number of pets of two different types. For example, a rectangle corresponds to 10 xolos and 7 yaks. The rectangle must be cut either vertically or horizontally, meaning that you can only buy one type of pet on a given turn. The interesting twist is that you must keep the larger piece resulting from a cut, which is equivalent to saying that you may buy any number of pets but only up to half the number of pets the store currently has. For example, if the store has xolos and yaks, you may buy up to xolos, or up to yaks. Buying any more than that would correspond to cutting the rectangle and keeping the smaller piece, which is not allowed.

  Naturally, I wondered what the visualization of this game looks like. I figured it had to be something interesting, and I wasn’t disappointed! Here it is (note that the bottom-left square represents here, whereas in the visualizations for nim and Wythoff’s game it represented ):

  

  Woah, neat! It looks as if the losing squares fall along diagonal lines of slope for all integer n (that is, , , , , , and so on)—though the lines don’t all pass through the origin. It’s not surprising that the main diagonal consists of all losing positions—the strategy is the same as for nim; the fact that one can only buy up to half of a certain type of animal doesn’t make any difference. If it is your opponent’s turn to move and the store has an equal number of xolos and yaks, if they buy a certain number of yaks you can buy the same number of xolos, and vice versa. Eventually the store will have one of each, at which point your opponent loses since they can’t buy any more animals (they would only be allowed to buy, say, half a yak, but the pet store has the sensible policy of not chopping pets in half—too messy).

  However, apparently there are additional losing positions other than the main diagonal. For example, according to the graph, if the store has 4 xolos and 19 yaks, then the next player to move is going to lose! You can verify for yourself that from this point, the only legal moves are to light green (i.e. winning) positions, and that from any of these positions the other player can make a legal move to another dark blue (i.e. losing) position, and so on.

Some directions we could go from here:

• Can you think of any variant nim-like games to explore? I have a very general program for creating game visualizations like the above, so if you describe a variant game in the comments I will be happy to try to generate a visualization for it.

• What about nim-like games with three (or more) piles? To visualize the strategies for these, we have to use three (or more!) dimensions. I hope to eventually come up with a way to do this, at least for three dimensions. I happen to know that nim is much more interesting in three dimensions than in two!

• Can you prove that the visualization of the rectangle-cutting game really looks like the above? Can you come up with a nice way to characterize the winning strategy, or at least the losing positions?