Clearly Combinatorializing Connection Games: Un-all-smalling

Game sums are at the heart of Combinatorial Game Theory. If you give me two different rulesets, a third exists that is the sum of those two and you don't have to specify anything new.

Unfortunately, some games add poorly or uninterestingly. Hex may be a good example, because the game is over when a path is created. The standard Hex rules cause the game to be all-small: if one player has a move option, then the other also does. As I mentioned before (late in the post) it's perhaps more exciting to redefine the game to make it more "sum-friendly" (very arguable). Instead of ending the game when one player has created a path, instead allow the path-creating player to keep painting uncolored hexagons. Thus, the rule is that you cannot play if the opposing color has formed a path. Now the game is no longer all-small.

Paul Ottaway and I had a conversation a year ago where we both argued for this change. I don't know how to change the rules to a 65-year old game, however. Luckily, when played atomically (not part of a sum), the new rules do not change the game play. Make the connecting path and you win.

This works for any connection game that I know of (Y, Twixt, etc). There are many inherently all-small games that cannot accommodate such a change, however. Clobber and MadRooks are games that are all-small and for which I don't see a method to fix that that doesn't change the original game.

The inherent problem here is that prior to combinatorial game theory, games were defined by explaining the conditions for one player to win the game. Under the normal play convention, that's not entirely relevant. Instead, the game author need only describe what the legal plays are for each player from any position. It's a subtle difference that is only important in the context of game sums.

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!

Length of Games

How quickly can a game end? This question came up during a presentation on Thursday of the game Mad Rooks. In this game, Chess-Rook-Like pieces from two teams move around, capturing each other until only one color of rooks remains (then that player wins). If the board starts completely full, then on an 8x8 board, 63 rooks might need to be taken before the game ends.

The presenter noted that he found a scenario where the game could end in 64 moves. Naturally, I wondered whether it could be done in one less. In general, the questions of how fast a game can end, or how long a (short) game can be drawn out are very interesting. I'd also like to know how long a Mad Rooks game can be drawn out. This does not seem trivial!

I could spend tons of class time talking about this last point. Mad Rooks is one of Mark Steere's games (these have been very popular amongst my students for these projects) which are carefully designed to avoid loops. This is often implemented by enforcing the continued reduction of some potential function on the game state from each move. In Mad Rooks, the potential function could map game states into two-element vectors: f(S) = [x, y], where x is the number of uncaptured rooks in the state S, and y is the number of unengaged rooks in the state S. (A rook is "engaged" if it is in line with an opposing rook.) Our potentials can be measured by giving x priority in comparisons, so [x1, y1] < [x2, y2] if: (x1 < x2) or (x1 = x2 and y1 < y2). Now, if for each move, the potential value of the game drops AND we show it can only drop a finite number of times, then at some point the number of uncaptured rooks will be small enough that the game is over.

The rules enforce that if a player moves an engaged rook, it must capture an opposing piece, and if they move an unengaged rook, it must become engaged. Thus, we see that any move must either decrement x (potentially increasing y) or decrement y but leave x alone. Since capturing a rook can only increase y by a bounded value, there is a maximum number of states that can occur during the play of a game.

What is an upper bound we can derive from this? Well, the game starts off with all 64 rooks engaged. Thus, our potential is: [64, 0]. At any given point in the game, capturing a rook could (at most) cause three engaged rooks to no longer be engaged (x decrements, y increases by 3). Also, an engagement move could only cause one previously unengaged piece to be engaged (x remains the same, y decrements). Thus, for each capture, there could be three additional moves to engage pieces. If 63 pieces need to get captured, we see that at most 252 (4 x 63) moves are required.

This is, however, an unreachable upper bound; no matter which piece is killed first, no pieces become unengaged. Also on that last kill, there are no more moves, so three additional engagements are not available; the game is just over. By how much is this upper bound too high, though? In general, for an nxn board, what are the upper and lower bounds on the number of moves?