Though I keep talking about the game Hex, please do not assume that I'm a good player at all! I don't know why I have this fascination with a game I rarely play, but apparently I do. Perhaps the reason I like it is that you can define interesting variations on it. The study of Misere Hex has a nice proof that from the staring position, optimal strategies will force the board to fill up.
Alternatively, we could define Either-Color-Hex, which allows a player to paint either red or blue on their turn, but you still only win if a path uses your color. That doesn't change much of anything from standard Hex (why play the other person's color instead of your own?). Now, however, Misere Either-Color-Hex has similar strategies to regular Hex; you're always going to try to create a bridge with the other player's color.
... depending on how you define "winning" and "losing". It seems like we'd like to say that in Hex, you win if you complete your path. However, as we've covered before on this blog, we define this by describing when no further moves are available. Then, under Normal play, you lose if you cannot play on your turn. With Misere play, the opposite is true: you win if you cannot play on your turn. Hex games are "over" when a connecting path is created. Thus, you create your path and now the other player cannot make a move.
Unfortunately, now Either-Color-Hex doesn't work as anticipated. If the Left (Blue) player is about to complete a blue path, the Red (Right) player can color the last open hex blue to complete it. Then a path is complete and Right wins, despite the fact that the path was blue. That doesn't work as expected! (In fact, this game is now an impartial game, which isn't what was expected either.)
Misere Hex still works pretty correctly. Instead of trying to avoid creating a path in your color, you try to avoid creating a path of either color. However, since you can't play opposing pieces, their path will never end the game against your favor. Misere Either-Color-Hex, though, just has the same problem as Either-Color-Hex: both players will avoid creating a path of any color.
Let's see if we can fix this by changing the rules slightly. Instead of ending a game when a path is created, let's rule that a player cannot make a move when a path of the opposing color exists.
Now the Either-Color version of this game works just fine. Right can play the blue hexagon if they want, but the blue path "belongs" to Left. Left will continue to be able to make plays on the board, but Right will not. On their next turn, Left will paint a hexagon and then Right will have no more legal moves. Left wins.
Now the Misere Either-Color version does something strange: players are actively trying to create a path in only the opposing color. Once that is complete, the opponent will have another turn, but you won't have any. This works almost the same as standard Hex, but with the player roles switched! (The exception is on the last move. If Left makes the last hexagon and completes the red path, they won't be able to make any more moves. Unfortunately, since there are no more hexagons, Right wins anyways.)
This Bonus-play Hex has another nice property. When adding with other combinatorial games, it offers a bunch of extra free moves to the player who completes their path. If the board is mostly empty, the winner can keep making moves on that board later on in the game sum. This gives the Hex summand more priority: the winner will be able to use those extra plays later.
I should print out a board for Hex!
Have a great weekend, everyone!
A Domino-Covering Problem
3 months ago