Reverse Hex

Reverse Hex, sometimes also called "Rex" or "Misère Hex", is a variant of Hex played under the misère condition, that is, the player who builds a chain between their edges loses. Like Hex, the game cannot end in a tie. It has been proved with a non-constructive proof that the first player has a winning strategy on any empty n×n board if and only if n is even. The game seems quite interesting when played on small boards (like 8x8) and with the swap rule.

Theory

Existence of a winning strategy

On an empty n×n board, Reverse Hex (without the swap rule) is a first-player win if n is even and a second-player win if n is odd. Here, by a first-player win, we mean that it can be proven that the first player has a winning strategy, not that it is actually known what the strategy is. In his 1957 Scientific American column on Hex, Martin Gardner attributed this result to Robert O. Winder, who never published it. A proof was later published by Lagarias and Sleator. The following is a different (and simpler) proof.

For ease of exposition, we assume, as usual on this Wiki, that the two players are Red and Blue, and that Red goes first.

Theorem 1 (even boards). When n is even, Red has a winning strategy for Reverse Hex on an empty n×n board.

Proof. Since one player must always win, either Red or Blue has a winning strategy. Suppose, for the purpose of obtaining a contradiction, that Blue has a winning strategy. Then Red can play as follows: At the start of the game, Red pretends there is a blue stone somewhere on the board. Then Red follows the second-player winning strategy that we assumed to exist. This strategy will never require Red to play in the cell with the imaginary stone in it. Should Blue ever play there, there are three cases: (a) There are no empty cells left in the game. In this case, Red has won, since the imaginary blue stone is now a real stone, and it no longer matters whether it was placed at the beginning or the end of the game. (b) Exactly one empty cell is left. This cannot happen since it is Red's turn and therefore there is an even number of empty cells on the board. (c) There are two or more empty cells left. Since the imaginary blue stone has just become a real stone, Red simply places another imaginary blue stone somewhere on the board and continues to play the second-player winning strategy as before (i.e., Red's next move will be somewhere other than where Red just placed an imaginary blue stone — such a cell exists because there is more than one empty cell).

The game continues until case (a) is reached, at which point Red wins, contradicting our initial assumption that Blue had a winning strategy. □

Theorem 2 (odd boards). When n is odd, Blue has a winning strategy for Reverse Hex on an empty n×n board.

Proof. Assume, for the sake of contradiction, that Red has a winning strategy and plays it. Blue can play as follows. Initially, Blue follows a pairing strategy: As long as Red plays somewhere other than on the long diagonal, Blue just mirrors Red's moves. For example, if Red plays a2, Blue plays b1. This continues until Red plays on the diagonal. Since we assumed that Red is following a winning strategy, the remaining game (where Blue goes first and there is an even number of empty cells) is a second-player (i.e., Red) win. Blue steals Red's strategy by pretending the stone Red just placed on the diagonal is actually blue, placing another imaginary red stone somewhere on the board, and using the same method as in Theorem 1. This results in Red losing, i.e., making a connection between Red's edges, even under Blue's pretense that the diagonal stone is blue. Since that stone is actually red, Red loses anyway, contradicting the initial assumption that Red was following a winning strategy. □

Postponing the loss

Lagarias and Sleator also proved that the losing player can postpone the loss as long as possible, losing the game only when the board is completely filled. The proof is also non-constructive. The following proof is different from (and simpler than) Lagarias and Sleator's.

Theorem 3. In Reverse Hex on an empty n×n board, the losing player has a strategy by which the game does not end until the board is completely filled.

Proof. By definition, the winning player has a winning strategy. The losing player plays by attempting to "steal" this strategy. Specifically, on even-sized boards, the losing player uses the stealing strategy that would have worked for odd-sized boards, and vice versa. As noted in the proof of Theorem 1, the only time this fails is when case (b) is reached, i.e., when there is a single empty cell left on the board. At this point, the losing player is forced to play in the only remaining cell and loses the game. □

Theorem 3 suggests a possible scoring method for Reverse Hex: the winner could be given a number of points that is determined by the number of empty cells left on the board at the time of the win.

Strategy

Little is known with certainty about Reverse Hex strategy. Apparently what is good in Hex (center, corners, "defensive" play and virtual connections) is generally bad in Reverse Hex. It is usually possible to see some moves ahead because good moves are often good for both players. Despite the appearances the opening and middle-game phases are fairly important.

Co-templates

In Hex, a template guarantees that a player can connect certain groups of stones. Reverse Hex has a dual concept, which we may call a co-template: it is a pattern that guarantees that the player is unable to prevent the stones from connecting.

The simplest example of a co-template is the bridge:

The idea is that Blue can refuse to play in the bridge until there are no more empty cells elsewhere. At that point, if Blue takes one of the empty cells in the bridge, Red is forced to take the other.

Although not all Hex templates are co-templates, many of them are. For example, the ziggurat is a co-template:

To see why, note that Blue can guarantee that Red occupies at least one of each pair of cells containing the same number. Namely, if Red moves in the ziggurat, Blue responds by playing in the other cell with the same number. Blue only moves in the ziggurat if there are no more empty cells elsewhere. Blue can then simply refuse to play in the other cell with the same number until Red is forced to do so when Red runs out of other moves.

With the exception of the hammock, all of the interior templates on the page "Interior template" have pairing strategies similar to the ziggurat, so all of them are co-templates. (This also includes the "long" templates and extensions mentioned on that page.) The hammock, on the other hand, is not a co-template; in fact, for every possible Blue intrusion in the hammock, Red has a pairing strategy allowing Red to disconnect the hammock's two endpoints.

Just like Hex templates can sometimes be defeated by creating a bigger threat elsewhere, co-templates can also sometimes be defeated. For example, consider the following situation, with Blue to move:

If Blue moves at "*", Blue loses immediately, so Blue has no choice but to play in the bridge. Now Red can play at "*", forcing Blue to play in the bridge again and lose.

However, when Red's board edges are connected by a sequence of non-overlapping co-templates, then the co-templates cannot be defeated and Red is sure to lose.

Pairing strategies

As we already saw in the example of the ziggurat above, pairing strategies are important in Reverse Hex.

A pairing strategy is specified as a set of pairs of empty cells (each cell may belong to at most one pair).

• In Hex, a pairing strategy allows the second player to make sure they occupy at least one member of each pair.

• In Reverse Hex, a pairing strategy allows the first player to make sure they occupy at most one member of each pair (or equivalently, the second player can be forced to occupy at least one member of each pair). Moreover, if there is an even number of empty cells on the board, the first player can choose which of the two cells to occupy in one of the pairs.

For example, consider the following position, with Blue to move:

Consider the pairs (c,b) and (d,f). Blue, the first player to move in this position, can occupy c, force Red to occupy b, and force Red to occupy at least one of (d,f). Therefore, Red makes a connection (either via d and b or via f and b), and Blue wins.

Alternatively, consider the pairs (f,c), (a,b), (d,e). Blue can occupy f, force Red to occupy c, and force Red to occupy at least one of (a,b) and at least one of (d,e). This is another winning pairing strategy for Blue. There are many others for this position.

k×n Reverse Hex

In Hex, it is known that on non-square boards (k×n boards where k ≠ n), the player with the shorter distance between their edges has a winning strategy, no matter who goes first. The proof is by a pairing strategy:

The exact same pairing strategy makes the entire board into a large co-template. Therefore in Reverse Hex, the player with the larger distance between their edges has a winning strategy, no matter who goes first.

Computer Reverse Hex

Young and Hayward created a Reverse Hex solver called Solrex and solved Reverse Hex up to size 6×6.

References

• Martin Gardner. "Mathematical games: Concerning the game of Hex, which may be played on the tiles of the bathroom floor". Scientific American 197(1):145–150, June 1957.

• Martin Gardner. "Mathematical games: Games of strategy for two players: Star Nim, Meander, Dodgem, and Rex". Scientific American 232(6):106–111, June 1975.

• Jeffrey Lagarias and Daniel Sleator, "Who wins Misère Hex?". In: The Mathemagician and Pied Puzzler: A Collection in Tribute to Martin Gardner, Elwyn Berlekamp and Tom Rodgers, editors, chapter 3, pages 237–240. A.K. Peters, 1999.

• Kenny Young and Ryan B. Hayward. "A Reverse Hex Solver". In: Proceedings of the 9th International Conference on Computers and Games (CG 2016), Spring Lecture Notes in Computer Science, vol 10068. doi:10.1007/978-3-319-50935-8_13. Also available at arXiv:1707.00627.