Difference between revisions of "Reverse Hex"

Revision as of 19:59, 23 January 2022

Reverse Hex, sometimes also called "Rex" or "Misère Hex", is a variant of Hex played under the misère condition, that is, the first player to build 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. □

Strategy

Little is know 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.

Anti-templates

A template in Hex guarantee that a player can connect certain groups of stones. An anti-template in Reverse Hex is a kind of dual concept: it is a pattern that guarantees that the player is unable to prevent the stones from connecting.

The simplest example of an anti-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 anti-templates, there are other examples of Hex templates that are also anti-templates, for example the ziggurat:

To see that it is an anti-template, 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.

Just like Hex templates can sometimes be defeated by creating a bigger threat elsewhere, anti-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 anti-templates, then the anti-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. Specifically if there is a set of pairs of empty cells such that Red loses whenever Red occupies at least one of each pair, then Blue has a winning strategy.

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 anti-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", July 2017. arXiv:1707.00627