Game Description: Mad Rooks

This semester I am lucky enough to be working with a student on an implementation of Mad Rooks for the Android OS. In a previous post, I talked a bunch about the length of a Mad Rooks game, but I realized I didn't have a stand-alone post on the game itself.

Mad Rooks is another game developed by Mark Steere who has created a large number of excellent combinatorial games. This particular game is a sort of King-of-the-Hill Long-Distance Clobber. Both players begin with pieces that act like rooks in Chess in that they can move as many spaces horizontally or vertically on a checker board without jumping pieces. If a rook moves onto a space occupied by an opponent, the opponent's piece is removed (captured). A rook is called "engaged" if it can make a capturing move. Each turn, a player either uses one of their rooks to capture a piece or moves one of their unengaged rooks so that it is engaged.

Just as with Clobber, this game is all-small, which means if there is a move for one player, then both players have a move. Although this does not mean that each game has a nimber value (though it always seems like it should to me) it does mean that every instance of an all-small games has an infinitesimal value. Infinitesimals are smaller than all positive numbers, yet greater than all negative numbers (the only infinitesimal number is 0). Values such as Up, and * are infinitesimals.

It is especially interesting to look at end states in Mad Rooks, where suddenly making engaging moves instead of capturing with another piece is a better move, though engaging when you have to is often disastrous. It doesn't always even matter who has more pieces. Consider a board with rooks only on every square along the diagonal of the checkerboard. Now, if only one of those is Blue but the rest are Red, the next person to play loses the game, despite the fact that Red outnumbers Blue seven-to-one! (Try it!)

One reason some players may prefer this game to Clobber is that in the end all pieces of one player are captured, leaving the winner as the last color standing. In Clobber, you can't look at the final position and determine who won the game, but you can in Mad Rooks!

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: Weak Hex (Whex)

When I was first interested in Adjacent Hex (Adjex) a few years back, a friend of mine pointed out another similar game to me: Weak Hex. Weak Hex, or Whex, is extremely similar to adjacent hex because both players must move adjacent to another player's move. Instead of playing next to the last move of either player, however, both must play adjacent to the last move of the red player!

Here is the description from the original Whex paper by Argimiro A. Arratia Quesada:

Players can not colour an arbitrary vertex but must proceed as follows: Player
1 begins the game and he must do it by colouring red a vertex adjacent to
the source. From this move and on, Player 2 must colour blue an uncoloured
vertex adjacent to the vertex last coloured red (i.e. coloured by Player 1), and
Player 1 replies by colouring red an uncoloured vertex adjacent to the vertex
that he coloured red last.

(If no adjacent moves are available, the next player immediately loses.)

This game is intended for play on a graph instead of the standard hex board, but we can consider that also. In this case, the "source" is likely to be an entire red side (the sink, then, is the other red side). The goal for the red player is to connect the two red sides, and the goal for the blue player is to prevent such a connection. This matches up precisely with the winning conditions of standard Hex, so it is possible to play Whex on the regular hexagonal grid.

Additionally, the game is shown to be PSPACE-complete, so it is certainly hard to play in the general case! This is the same as with Hex and Adjex. In Hex, it is known that the first player has a winning strategy, but that strategy itself is not known. In Whex, however, not only does the first player have a winning strategy, but it can be described very quickly! In fact, I bet you can come up with it yourself!

(Find an opponent, see if you can come up with a method to always win playing first (as red), then come back and finish reading!)

Okay, on your first turn, play in the hexagon "on the bottom"


On each subsequent turn, play in one of the hexagons directly towards the upper-right-hand (red) side. Blue can only choose to occupy (at most) one of those on their turn, so you will get to take the other. Since you don't have to worry about playing adjacent to them, they can't deter you (as is possible in Adjex). Enjoy your march to victory!

If you play with the pie rule, I'm not sure what happens!

Blog Layout & Table Updates!

Thanks for tuning in! Molly Dannaher, one of my students in combinatorial games last semester, provided the excellent artwork here, which comes straight from my marker board!

Also, I have many several updates to the game table over the past week, but there's still much more to add.

There was no update Friday as I was home sick.

Thank you for all the emails about potential post topics. I've been a bit weighed down with other work, but I do have lots I want to talk about!

Why bother about Computational Complexity?

In a recent phone call with my Ph.D. advisor, Shang-Hua Teng, I was reminded how important the computational complexity is for combinatorial games. The punchline is very simple:

"Hard games give humans a chance to beat machines."

If no efficient algorithm exists to determine who wins a game, then a program cannot always efficiently choose the best move to make. Hardness results are evidence that this is the case (although we still don't know that no efficient algorithm can solve NP-hard or PSPACE-hard problems). These games give us some sense of safety that the computer doesn't already have the game won.

This also applies to the concept of experts and novices. It's not too hard to become an expert in an easy game like Nim. Learn the evaluation trick (computable in polynomial time) and you're good to go. At this point, if you play against someone who doesn't know that simple trick, you can beat them every time (unless they are very lucky). In a game such as Go, much more practice is required to become an expert. There is no quick evaluation algorithm to learn. However, since the strategies are not as clear cut, there is a bigger chance that the novice will be able to beat the expert.

When first designing Atropos, our goal was not just to find a 2-player game, but to find a (PSPACE) hard game. We changed the rules until we could get a proof of the hardness working. At that point we were quite satisfied! Some other games I've defined seem less impressive without a similar result. Learning that games are provably hard usually makes me want to play them more!

(I'm trying to keep track of game facts on this table, with quite a bit of bias towards computational complexity! Please let me know if there's something you'd like to add!)

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.

Graph NoGo is NP-hard

Last week, I mentioned we had some computational complexity results concerning the game NoGo, which was the "new game" played at the game workshop at BIRS this year. After getting more comfortable with the game play, it felt like the game might be another great example of PSPACE-completeness. I put some effort into solving this, knowing it would be great to resolve the complexity while at the workshop.

Finding gadgets is tough, sometimes especially when dealing with the sort of grid-geometry of the NoGo board. Thus, I took a step backwards and considered NoGo played on a general graph. The rules to this game are still the same: each connected subgraph where all vertices have the same color must be adjacent to a vertex in the graph which is uncolored. Still, I had no luck finding a PSPACE-complete reduction. Instead, I took another step backwards and considered showing NP-hardness for Graph NoGo.

Woohoo! Success! Here is the plan for this proof: we will reduce from the Independent Set problem, known to be NP-hard. Given an instance of the Independent Set Problem (G, k), construct a Graph NoGo situation, G', that only the black player can move on, where each play corresponds to choosing a vertex in G, the original graph, to be part of the independent set. If the black player can make k plays on the new game, G', then there will exist a corresponding independent set of k vertices on G. To turn this into a Graph NoGo situation where the only question is: "Can the black player win if they are playing next?" instead of "Can the black player make k plays?" we will add (k-1) unconnected nodes where only the White player can move. Now, in order for Black to win, they must be able to make k (or more) plays (assuming they are going first).

So, there are two things to show. First, we need gadgets in Graph NoGo where only one of the players can play. Second, we need to be able to glue those pieces together so that playing in one of these locations means you can't play in an "adjacent" one. As it turns out, neither of these is terribly hard.

As above, if G is our graph for the Independent Set problem, then for each vertex in G, we will use the following gadget for our game of Graph NoGo:

Here, x is the place Black can choose to play their stone in. The only other blank spot cannot be played by either Black or White. Notice that White cannot play on vertex x.

Now, for each edge in G connecting two vertices, we will connect only the x vertices of the gadgets with another gadget:
Now, if Black plays in one of the vertex-gadgets, he can't play in the neighboring ones. Thus, any set of Black plays on the Graph NoGo board G' corresponds to an independent set on G. For example, two adjacent vertices in G, x and y, and the edge that connects them will look like this:
Thus, if we can always efficiently answer the question "Can the Black player win this game of Graph NoGo?" we can also solve Independent Set in polynomial time. Thus, Graph NoGo is NP-hard.

One nice property of this reduction is that it preserves planarity of the graph. Thus, if Independent Set is hard on a planar graph (is it?) then so is Graph NoGo.

So, how do we now take either of those two steps forward, to reach a PSPACE result or an actual NoGo result? Perhaps next week...