20 August 2007

an interesting fact about a variant of Hex

I have long known about the game of Hex, which is played on a hexagonal lattice. The game is played on a rhombus-shaped section of a hexagonal lattice, with markers of two colors; the board is illustrated at left. One player places red markers, the other blue markers; they alternate in playing. The red player is attempting to create a chain of red hexagons extending from the top of the rhombus to the bottom (these are both shaded red in the screenshot); the blue player is simultaneously attempting to create a chain of blue hexagons from the left side to the right.

There's a nice theorem which states that a game of Hex can never end without a winner. Say you're playing red. If you have blocked off all possible horizontal chains that blue might make, you must have made your own red chain connecting the top and the bottom, and vice versa. (This isn't exactly a proof but it's the gist of any formal proof of the result.)

However, I learned recently from
Bollobas and Riordan's book Percolation that although this is true, an analogous result is not true if one were to play Hex on a square lattice. If we think of one color of hexagons as "open" and the other as "closed", then the earlier result about Hex says that in the rhombus-shaped triangular lattice of points (which is dual to the hexagonal lattice), there's either an open path from the top of the lattice to the bottom or a closed path from the left to the right.

On the square lattice, there is the question of the right way to define adjacency; are two squares which touch each other only at a corner adjacent to each other? It turns out that if we say they are (so each square has eight neighbors) then it's possible to color the squares of the board so that there's a red vertical path and a blue horizontal path. (This doesn't create a problem for a hypothetical game of Hex on a square lattice, though, because we just award the win to the player who completes their path first.) If we let each square have four neighbors, though, then ties are possible; one could have a situation where the entire board is filled in and there's no red vertical path or blue horizontal path. (An example for both of these occurs if we divide the board into four quadrants, and color the entire northeastern and southwestern quadrants red and the northwestern and southeastern quadrants blue.)

But Lemma 5.9 of Bollobas and Riordan tells us that
If we colour the squares of an n by m chessboard [blue] and [red] in an arbitrary manner, then either a rook can move from the left side ot the right passing only over [blue] squares, or a king can move from top to bottom using only [red] squares, but not both.

(I've changed the colors; Bollobas and Riordan use the more traditional black and white.)

However, there's a difference between the two cases, even so. If you color in all the hexagons in an n-by-n section of the hexagonal lattice uniformly at random -- so each is red or blue with probability 1/2, and each hexagon is independent -- then by a symmetry argument, the probability of having a red vertical path and a blue horizontal path are equal, and thus are both 1/2. This doesn't mean Hex is fair -- the first player is in fact guaranteed to win under perfect play. But in the square-lattice version of the game, I suspect the player who is allowed to consider squares which share a corner as adjacent has a very large advantage.

Carl Witty said...

If we let each square have four neighbors, though, then ties are possible; one could have a situation where the entire board is filled in and there's no red vertical path or blue horizontal path.

Another example is a simple red-blue checkerboard.

But in the square-lattice version of the game, I suspect the player who is allowed to consider squares which share a corner as adjacent has a very large advantage.

Perhaps this could be (approximately) fixed by using a rectangular board, so that the king-adjacency player has to make a longer path than the rook-adjacency player.

Isabel said...

Carl,

for some reason the standard coloring didn't occur to me!

and you've got a good point with the rectangular board. But the game still loses some of its elegance in any version where we let one player win by rook-adjacency and the other by king-adjacency; even though the two players have to do things which are perceived to be of "equal difficulty" (one has to make a short path under rook-adjacency, the other a long path under king-adjacency) they don't have to do the same thing.