Assignment:
In the game of Hex the two players eliminate (weakly) dominated strategies. What remains of the game once the elimination process ends?
Hex Hex7 is a two-player game conducted on a rhombus containing n2 hexagonal cells, as depicted in Figure 3.14 for n = 6. The players control opposite sides of the rhombus (in the accompanying figure, the names of the players are “Light” and “Dark”). Light controls the south-west (SW) and north-east (NE) sides, while Dark controls the north-west (NW) and south-east sides (SE). The game proceeds as follows. Dark has the opening move. Every player in turn chooses an unoccupied hexagon, and occupies it with a colored game piece. A player who manages to connect the two sides he controls with a continuous path8 of hexagons occupied by his pieces is declared a winner. If neither player can do so, a draw is called. We will show that a play of the game can never end in a draw. In Figure 3.14, we depict a play of the game won by Dark. Note that, by the rules, the players can keep placing game pieces until the entire board has been filled, so that a priori it might seem as if it might be possible for both players to win, but it turns out to be impossible, as we will prove. There is, in fact, an intuitive argument for why a draw cannot occur: imagine that one player’s game pieces are bodies of water, and the other player’s game pieces are dry land. If the water player is a winner, it means that he has managed to create a water channel connecting his sides, through which no land-bridge constructed by the opposing player can cross. We will see that turning this intuitive argument into a formal proof is not at all easy.9
For simplicity, assume that the edges of the board, as in Figure 3.14, are also composed of (half) hexagons. The hexagons composing each edge will be assumed to be colored with the color of the player who controls that respective edge of the board. Given a fully covered board, we construct a broken line (which begins at the corner labeled W). Every leg of the broken line separates a game piece of one color from a game piece of the other color (see Figure 3.14).
(a) Prove that within the board, with the exception of the corners, the line can always be continued in a unique manner.
(b) Prove that the broken line will never return to a vertex through which it previously passed (hint: use induction).
(c) From the first two claims, and the fact that the board is finite, conclude that the broken line must end at a corner of the board (not the corner from which it starts). Keep in mind that one side of the broken line always touches hexagons of one color (including the hexagons comprising the edges of the rhombus), and the other side of the line always touches hexagons of the other color.
(d) Prove that if the broken line ends at corner S, the sides controlled by Dark are connected by dark-colored hexagons, so that Dark has won (as in Figure). Similarly, if the broken line ends at corner N, Light has won.
(e) Prove that it is impossible for the broken line to end at corner E.
(f) Conclude that a draw is impossible.
(g) Conclude that it is impossible for both players to win.
(h) Prove that the player with the opening move has a winning strategy.
Guidance for the last part: Based on von Neumann’s Theorem, and previous claims, one (and only one) of the players has a winning strategy. Call the player with the opening move Player I, and the other player, Player II. Suppose that Player II has a winning strategy. We will prove then that Player I has a winning strategy too, contradicting von Neumann’s Theorem. The winning strategy for Player I is as follows: in the opening move, place a game piece on any hexagon on the board. Call that game piece the “special piece.” In subsequent moves, play as if (i) you are Player II (and use his winning strategy), (ii) the special piece has not been placed, and (iii) your opponent is Player I. If the strategy requires placing a game piece where the special game piece has already been placed, put a piece on any empty hexagon, and from there on call that game piece the “special piece.”
Provide complete and step by step solution for the question and show calculations and use formulas.