## Friday, January 28, 2011

While at the CGT (Combinatorial Game Theory) workshop earlier this month, I watched Ryan Hayward give an excellent talk about Hex and "Rex" (Misere Hex). Ryan is an excellent Hex player and even better Hex theorist (and also a good curling skipper). I was determined to play some Hex with him, but needed a little extra help since I had played so little. Thus, I suggested we play a variant: Adjacent Hex.

The game is exactly like standard Hex, except it mimics the play restrictions like Atropos: after an opponent paints a hexagon their color, you must play adjacent to their last move. If all the adjacent hexagons are already colored, you may choose to play in any uncolored hexagon on the board. (We've been referring to this as a "jump".)

Ryan and I played one game with these rules. At one point, I thought I was doomed, but Ryan pointed out a really good move for me. I can't recall whether that move led me to win, but either way it was clear his Hex skills were helping out. We proceeded to play two other games using different rules for jumping, but both agreed the original game was best.

I convinced Alan Guo to play a few games with me. We went back and forth, winning and losing, but building up some good intuitive strategies for the game.

Since returning to Wittenberg, I am undefeated. (My aide, Ernie, would like to add: "So far.") I've played against a number of students, and even beat the combined talents of my aide and teaching assistant, Patrick, earlier this week. Obed, the director of our math resource center, has vowed to get a set to practice with his own students.

This game plays very nicely: knowledge of Hex will help out, though knowing that playing in one hexagon will win you the game doesn't always help if your opponent never plays adjacent to that spot. In most of the games I've played, players are usually fighting to be the one working on their own path, which is sometimes harder than it sounds. Usually one player is currently working on a path, while the other player is just trying to derail that path using the adjacency rule. If their derailing is successful (this can be quite tricky) then that player starts building a path fragment and the other player is now trying to thwart that plan.

Sometimes play moves into an area that is closed off where the color of the hexagons does not matter. Now both players are competing to force their opponent to paint the last hexagon in the region, ensuring that they will be the one to "get the jump" and play wherever they want. A few times I've been in great situations where I decided not to connect two of my important paths because doing so would give my opponent a jump. This is a tough choice!

One nice property of this game is (I think) that it is "automatically" PSPACE-complete. If I understand Stefan Reisch's original "Hex is PSPACE-complete" proof, the gadgets in the reduction don't have any adjacent uncolored hexagons [citation needed], thus ensuring that each move gives the opponent a jump and the adjacency rule doesn't come into play. (I wonder how helpful it would be to produce a translation of Reisch's paper.)

In my office, I have a 14 x 14 hex board, just ready for adjacent-minded opponents!