Winning moves in Hex
Apr. 9th, 2021 12:47 pmThe game "Hex" is a simple game which apparently has been invented at least twice (Piet Hein and John Nash). The game consists of an n by n grid of hexagons, with two opposite sides marked as blue and the other pair of opposite sides marked as red. The red pair belongs to the red player, and the blue pair belongs to the blue player. Players alternate marking hexs either red or blue. The goal is to form a path of hexs of your color which connect one's two sides.
It is well known that there is a winning strategy for the first player on an n by n board. Proof sketch:
First show that in any completely filled board, there must be a winning path for at least one player. (Note that this step really is not obvious; this isn't true if one did this on a square grid rather than a hex grid.)
Second, note that if the second player had a winning strategy, the first player could simply make some extra random move, and then play using the second player's strategy, with no penalty. This sort of argument is called a "strategy-stealing argument" and it shows up in many arguments about simple board games.
So we know that for any n by n board, the first player has a winning strategy. But here's a fun fact: No one knows a general way to find this strategy. We can do so for some small board sizes, but there's no general rule.
If one plays around on a few tiny boards with n>2 one will notice that edge moves are really bad first moves. In fact, a little work will show you that on a 4 by 4 grid, an initial move on an edge is always a loser for the first player. So I have two questions:
First, can we show that for any n>2, any edge move is a losing first move?
Second, suppose that the first player's move is randomly chosen; can we say anything about the proportion of those moves which lead to a winning board? My guess is that this proportion either goes to 0 or goes to 1 as n grows, but my intuition on which seems to be oscillating violently.