What are we taking in Nim?

Nim is a game with many different incarnations. In some cases, it concerns removing items from just one heap, but with restricted amounts. In others, there are multiple heaps on the table at any time. These variations are played by many people, all using the name "Nim" and all with different rules (some people learn the normal play rules, others learn misere). There are many near-gamesters who are an expert at their version of Nim, but have problems if you vary even just the starting position.

Forgetting all this, however, what are those items that players are removing? What are the heaps made out of? I have heard uses of counters, sticks, beans, pennies/coins and others.

In elementary school, I learned the one-pile game as "Nim" and later the multi-pile game as "Sticks". With this second influence, it's very hard for me to not "pick up sticks" when I'm taking my turn in Nim. Not certain this was standard, I consulted Mike Weimerskirch and Thane Plambeck last month. Both of them referred me to the surreal movie Last Year at Marienbad, in which two characters compete at Nim. The games played in the film use matchsticks as props; perhaps sticks are the way to go! (This guy uses sticks, but he also cheats, so perhaps that's a point against it.)

If we consult the authoritative Winning Ways, however, we see that Nim is played with heaps of counters. It's hard to argue with this text! Indeed, Lessons in Play continues this tradition, referring to heaps of counters in the game Nim. Also, Mike told me straight-up that he's a counter man. Again, hard to argue with these Nim masters!

Beans? Beans are gross; who wants to think about playing games with food that will later be cooked. Didn't your parents teach you anything?

Candy, however, is another matter. Candy is delicious (and doesn't get cooked). Who wants to play Candy Nim?

Pennies and various coins make sense, except that the goal of the game is not to make money, but to make (or not make) the last move. Still, I bet these are often used as the "counters".

I'm still not sure what to use, but I'm going to keep with sticks until someone convinces me otherwise!

Game Description: Wythoff's Nim/Game

Last semester, one of my students presented Wythoff's Nim and did a great job explaining all the theory behind it. This is a simple, classic game with some beautiful properties, and something people continue to study variants of.

Wythoff's Nim (often called "Wythoff's Game") is just like playing "regular" Nim with two piles of sticks, except that you are also allowed to take X sticks from both piles, where X is any number. Thus, from the situation where the piles are of size 2 and 4 (we refer to this as (2,4)) legal plays include moving to (1,4) [taking one stick from the first pile], (2,0) [taking all four sticks from the second pile] and (1,3) [taking one stick from each pile]. Just as in Nim, the only location where no plays are available is (0,0).

This game is often envisioned as a Queen moving across a chess board, who starts anywhere on the board, and cannot move up or to the right. Players can thus move her left any number of spaces (subtracting from the first pile), down any number of spaces (subtracting from the second pile), or diagonally down and to the left (subtracting from both piles). This version of the game is visualized in the playable applet on this site.

This is naturally an impartial game, so the question arises: where are the P positions? (0,0) is automatically one, but (1,2) also does not have a safe move (all moves lead to N positions). (3,4) is not, (you can move to (1,2)) but (3,5) is. It turns out there is a very fancy trick for finding the P positions! This is a surprising application of the golden ratio, φ!

All P positions are of the form: (floor(k*φ), floor(k²*φ)) or the reverse. If we think about these as a sequence of pairs, ((a, b)_k), then the sequences (a_k) and (b_k) are Beatty sequences, meaning that they intersect nowhere and contain all the natural numbers (not including zero, so we consider only those where k > 0). Try out the first few pairs, and you'll see that this makes sense. Thinking in terms of the Chess board and the queen, each row should have a P position, and can't have more than one.

Many variants of this game have been studied, many relating to the relevance of Beatty sequences, which I hope to talk about more in the future. This is otherwise an excellent game to learn to exploit the winning "trick" and then show off to your friends with.

Candy Nim

On Friday, I mentioned Michael Albert's "Candy Nim" as a way to entertain yourself when you're losing a game of Nim.

The idea works as follows: you are in a losing Nim position (and the other player seems to know "the trick" to keep on winning). You decide to come up with a secondary goal: try to eat (take) as many of the remaining objects (pieces of candy) as possible. Michael proves that in this case, there is a way to eat at least half of the remaining objects!

Consider the case where there are two piles of objects, both with the same number (they have to be the same, otherwise you're not in a losing position). In this case, no matter how many you eat, the other player will take the same amount, and you'll eat exactly half the candy.

In some cases, there is a better "strategy". For example, if there are three piles, and one of them has size 1, then the other two must look like 2k and 2k + 1 for some k. Now, there is a way to net a 3-to-1 advantage in this situation: take 3 from the pile with 2k+1.

Then our piles go from: 1, 2k, 2k+1 to: 1, 2k, 2k-2. To counter this move, and not lose, the opposing player will take 1 from the second pile. The situation is now: 1, 2k-1, 2k-2 = 1, 2(k-1) + 1, 2(k-1). So long as k-1 isn't 0, lather, rinse, repeat! Continuing this leads to the losing player eating 3k+1 candies, while the winning player eats k+1 candies over the course of the game.

Are there any other good entertainment "games" you can play as a losing player?

Playing While Losing and Collecting Candy

Sometimes gamesters play games even when they are in a losing position. This means that even though we know there is no winning strategy from the current game state, they'll keep playing.

This happens for a lot of reasons. Often, this occurs because the winning strategy for the other player is not known (even though it is known that it exists). For example, the first player to move in Chomp is the winning player, though what that first move should be is unknown. Thus, if someone challenges me to a game of Chomp, but they are going first, I don't immediately quit the game. They will make their first move, and then who knows whether I'm still in a losing position?

Other times, even when a winning strategy is known, there is a chance it is not known by the player in the winning position. You might be in a losing position this turn, but if you make a sneaky enough move, perhaps they won't be able to do it again next turn...

There is the chance also that you play purposefully from a losing position, hoping your opponent will learn how to maintain their "winningness". If I am a parent someday, I bet I will do this more often!

As yet another option, it might just be that your opponent will take it badly if you quit on the game, even though it's clear who will win. You'd like to quit, but they want you to play the whole thing out. This is likely very instructive for them, so you should probably go ahead with it :)

Michael Albert found a way for the losing player to entertain themselves in (some of) these situations while playing the game Nim. The idea is to consider all the objects as pieces of candy, and by removing them from a pile, you get to eat the delicious candy! Naturally, this is not as rewarding as winning, but if you're going to lose, you might as well acquire as much of the candy as you can! He found interesting properties of the game when playing with three piles (most notably that it's always best to take candy from the biggest pile). This implies that the winning player will always make the best responding winning move.

I'll talk some more about "Candy Nim" next week. Have a great weekend!

Playing without Giving away your Strategy

Perhaps you are about to play a series of three games of cram against an opponent in the final round of a cram tournament. Your scored better than your opponent in the tournament thus far and must play first in the first and third games. The winner of the tournament will be the player that wins 2 of those 3 games.

While playing the first game, you can see that you are losing, but suddenly realize there is an really good strategy for winning from the start as long as you go second. Since this tournament uses initial 8 x 8 boards, you can use a symmetry strategy to mimic the other player's moves! Great! The next game is yours!

Unfortunately, you also realize the strategy is easy to follow. As soon as you use it against your opponent, they will be able to implement it themselves in the final game and win.

Is there a way to implement the symmetric-play strategy but disguise it at all? In general, is there a way to mask the fact that you are using a simple strategy to win?

In Nim, it is difficult to follow someone making the correct moves if you do not know how to evaluate the game boards. If it was plainly obvious what the other player was doing (perhaps XOR is your favorite math operator) then perhaps you would pick up on it quickly.

I tried this once, keeping a "turn behind" in the symmetric-play strategy. I kept making the play my opponent had made two turns ago, whenver possible. As I recall, it got messed up and I had to ditch it part way through. Is there any good way to keep this going? I feel this would be more difficult for an opponent to follow... if it works!

Best Intro Game?

I just had a wonderful visit this weekend with my soon-to-be-in-laws and they described playing Candy Land with their grandkids. Although I never played much as a kid, I think it's a good introductory board game. The game has good visuals, both using the imagery of delicious candy, but also using colors instead of words or numbers to describe moving around the board. This definitely appeals to 3-5 year olds---whatever that age range is called---and is likely the first board game many American children play.

What about when it's time to play games in the classroom? What should a student's first game be then?

I'm focused on impartial games, and versions of Nim had popped up in my elementary and middle school classes. Basic Nim is a candidate for a good introductory game: it is both simple and (surprisingly) has a very sneaky trick to determine who is winning. This gives it a very satisfying quality: we learn about the rules of a game and some of it's underlying details and then, happily, we find a strategy to play the game well! This is unlike some other games that are more fun to play but might be disappointing to students because they don't reach this step.

The text Lessons in Play decides not to introduce impartial games until much later, instead beginning with Domineering. This is another nice game, due partly to its simplicity. Another key point here, though, is that this game uses pieces from other known games: a checkerboard and dominoes. This can lend a sense of creativity to students. "Use your imagination to create your own games from the pieces around you!"

I've also heard from people who swear by Hackenbush. This is a game where your turn consists of erasing an edge of a graph (usually drawn on a whiteboard) that corresponds to your color. After your turn, if there are any subgraphs not connected to a ground node, those are also erased. This game has the excellent feature that it is super customizable and doesn't need to use a parallel-to-the-ground board at all. Again, this sort of thinking outside the box can be very beneficial to students!

Note that both Domineering and Hackenbush have easy extensions to impartial games. Thus, that transition can be made easily.

What else do people prefer? Are these two the most common? Is there anyone out there who advises doing impartial games first?

Misere Hardness

I'm very pleased with the way my software engineering class is going. I've accidentally asked the students to code up some difficult games at times, but they've done a good job of figuring out exactly how to fix these issues. For the most part, using a game suite as the continuing project has worked extremely well!

Early on, I asked them to include both nim and misere nim. As with all misere games, misere nim is the same game, except that the person who makes the last move loses. Thame Plambeck used to maintain Advances in Losing, a blog solely about misere games. My first combinatorial game, Atropos, was misere: the first player to create a 3-colored simplex (triangle) loses. The misere notion is very intuitive for many games.

As we continue with the ongoing class project, I have continued to add difficult parts but at some point I stopped asking them to add more games to the suite. Oops! Currently, I've given them another tricky task: have users make moves through a series of mouse clicks (instead of entering choices in text boxes). I figured it was time to throw in some new games along with that. At the same time, I hope they realize they can apply "misereness" with any games, and not just with Nim.

Solution? They've already programmed a simple version of Kayles and Hex, so why not include misere Kayles and misere Hex? Even after thinking about that, I became immediately interested in misere Hex. How does that game work? Whichever player first creates their bridge between both sides loses? Weird! Who wins misere Hex? What is the complexity of this game?

In 1999, Jeffrey Lagarias and Daniel Sleator tackled that first question. They find the immediate intuition---that the first player never has a winning strategy---incorrect and instead base the winnability on the parity of the board size. They do this by showing that the losing player can stretch out the game play until the final hexagon has been colored. Thus, on boards with an even number of hexagons, the first player can win! The proof they give applies to games starting from the initial (empty) game configuration.

Does this answer the complexity question? Not in any obvious way. In order for the complexity to be solved, an algorithm would have to work for any game state. One can invoke a board where the game cannot be dragged out to fill in all the cells. (Give red two nearly-complete paths with only one hex missing, and let the rest of the board be filled in. If it's red's turn, what can they do?) It could be that the proof generalizes well into an algorithm.

Thinking from the complexity angle, as this blog (too?) often does, is there anything we can say about the relationship between the complexity of a game and it's misere counterpart? Again, I am interested in considering Atropos, which is already misere. The non-misere version means that the first player to create a 3-colored triangle wins. In this impartial game, each player may choose to color one circle any of the three available colors. The circles are laid out similarly to hex---so that each has six neighbors---inside a triangle with borders colored to suffice for Sperner's Lemma. This means that any play along the borders can win: there are always two different neighboring colors, so simply paint that circle with the remaining color.

Thus, the strategy from the initial position is easy. Choose one of those bordering circles and paint it the third color. Game over. In mid-game positions, however, a player must choose to paint a circle that neighbors the last-painted circle (if an open circle exists). Thus, the game might not be quite as simple from any given situation; one of the border circles may not be adjacent to the last play. (But why wouldn't the first player have just won the game? Why would you ever get to this situation?)

In general, are there any results about misere games and complexity? It's been a while since we phrased a question, so let's do it: (I've been marking the relevant posts with question# labels).

Question (2): Given a game G and it's misere version, M, must the complexity of determining the winner of one of these games be in P?

I think this is the best way to phrase the "What is the relationship between the complexity of G and M?" question. Consider nim and misere nim: both are easy. With Hex and Atropos, each has a PSPACE-complete version, but the opposite looks like it might be easy. Is there a game I'm overlooking which is hard both normally and misere...ishly? (someone help me out with French!)

Of course, I'm still curious about misere Hex.

Question (3): What is the complexity of determining whether the current player in misere Hex has a winning strategy?

For those interested, user Zickzack at boardgamegeek.com has a good description and list of misere games.