Difference between revisions of "Reverse Hex"
(→Co-templates: Expanded the section on co-templates.) |
(Remove odd board swap maps - they're always all blue) |
||
| (16 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | Reverse Hex, sometimes also called "Rex" or "Misère Hex", is a variant of Hex played under the misère condition, that is, the | + | 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 ''n'' is even, and the second player has a winning strategy if ''n'' is odd. The game seems quite interesting when played on small boards (like 8x8) and with the swap rule. |
== Theory == | == Theory == | ||
| Line 5: | Line 5: | ||
=== Existence of a winning strategy === | === 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 | + | 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 simplified version of their 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. | For ease of exposition, we assume, as usual on this Wiki, that the two players are Red and Blue, and that Red goes first. | ||
| Line 11: | Line 11: | ||
'''Theorem 1 (even boards).''' When ''n'' is even, Red has a winning strategy for Reverse Hex on an empty ''n''×''n'' board. | '''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. | + | '''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. Since whenever it is Red's turn, there are still at least 2 empty cells on the board, Red is never forced to play in the imaginary blue cell. If Blue plays there, the imaginary stone becomes a real stone, and Red places a new imaginary blue stone somewhere on the board. Then Red continues to play the second-player winning strategy as before. Unless Blue loses earlier, the game continues until Blue, on the final move, replaces the imaginary blue stone with a real one. Therefore, Red's imaginary win becomes a real win. |
| − | + | ||
| − | + | ||
'''Theorem 2 (odd boards).''' When ''n'' is odd, Blue has a winning strategy for Reverse Hex on an empty ''n''×''n'' board. | '''Theorem 2 (odd boards).''' When ''n'' is odd, Blue has a winning strategy for Reverse Hex on an empty ''n''×''n'' board. | ||
| − | '''Proof.''' | + | '''Proof.''' Suppose, for the sake of obtaining a contradiction, that Red has a winning strategy. Then Blue can play as follows: Blue pretends to be the first player, and before the game starts, plays an imaginary blue winning move. Then Blue follows the first-player winning strategy. Should Red ever play where the imaginary blue stone was, Blue continues to pretend that that stone is blue, but also places a new imaginary red stone elsewhere. Since whenever it is Blue's turn, there are still at least 2 empty cells on the board, Blue is never forced to play in a place where there is an imaginary stone. Unless Red loses earlier, Red's final move will be where the current (red or blue) imaginary stone is. Since Blue followed a winning strategy, Blue wins the game under the pretense that Blue's initial imaginary stone was blue. Since that stone is actually red, Blue wins anyway. |
=== Postponing the loss === | === 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 | + | 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 a simplification of the proof by Lagarias and Sleator. |
'''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. | '''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 | + | '''Proof.''' By definition, the winning player has a winning strategy, which we assume they follow. 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 Theorems 1 and 2, the only time this can fail is when it's the losing player's turn but there are fewer then 2 empty cells on the board. Thus, the losing move is the one that fills the very last cell. □ |
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. | 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. | ||
| Line 31: | Line 29: | ||
== Strategy == | == Strategy == | ||
| − | Little is | + | 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 === | === Co-templates === | ||
| Line 54: | Line 52: | ||
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. | 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 [[Interior template#The hammock|hammock]], all of the interior templates on [[Interior template | + | With the exception of the [[Interior template#The hammock|hammock]], all of the interior templates on the page "[[Interior template]]" have [[pairing strategy|pairing strategies]] similar to the ziggurat, so all of them are co-templates. (This also includes the [[Interior template#Long version of templates|"long" templates]] and [[Interior template#Template extensions|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: | 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: | ||
| Line 68: | Line 66: | ||
=== Pairing strategies === | === Pairing strategies === | ||
| − | As we already saw in the example of the ziggurat above, pairing strategies are important in Reverse Hex. | + | As we already saw in the example of the ziggurat above, [[pairing strategy|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: | ||
| + | <hexboard size="3x5" | ||
| + | edges="all" | ||
| + | coords="none" | ||
| + | contents="R a1 c2 d3 e2 e3 B a2 b3 c1 e1 E a:b1 b:d1 c:b2 d:d2 e:a3 f:c3" | ||
| + | /> | ||
| + | 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. | ||
| + | |||
| + | === Opening Moves === | ||
| + | |||
| + | The following boards show which player wins if the first move is played in a given cell. The odd board sizes are left out since, as they are a 2nd player win, all cells would be shaded blue. | ||
| + | |||
| + | <hexboard size="2x2" | ||
| + | coords="none" | ||
| + | contents="S red:all blue:b1,a2" | ||
| + | /> | ||
| + | |||
| + | <hexboard size="4x4" | ||
| + | coords="none" | ||
| + | contents="S red:all blue:b3,c2" | ||
| + | /> | ||
| + | |||
| + | <hexboard size="6x6" | ||
| + | coords="none" | ||
| + | contents="S red:all blue:b5--e2" | ||
| + | /> | ||
=== ''k''×''n'' Reverse Hex === | === ''k''×''n'' Reverse Hex === | ||
| Line 93: | Line 126: | ||
* 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. | * 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", | + | * 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. [https://doi.org/10.1007/978-3-319-50935-8_13 doi:10.1007/978-3-319-50935-8_13]. Also available at [https://arxiv.org/abs/1707.00627 arXiv:1707.00627]. |
| + | |||
| + | [[Category:Other games]] | ||
Latest revision as of 03:06, 9 November 2024
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 n is even, and the second player has a winning strategy if n is odd. The game seems quite interesting when played on small boards (like 8x8) and with the swap rule.
Contents
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 simplified version of their 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. Since whenever it is Red's turn, there are still at least 2 empty cells on the board, Red is never forced to play in the imaginary blue cell. If Blue plays there, the imaginary stone becomes a real stone, and Red places a new imaginary blue stone somewhere on the board. Then Red continues to play the second-player winning strategy as before. Unless Blue loses earlier, the game continues until Blue, on the final move, replaces the imaginary blue stone with a real one. Therefore, Red's imaginary win becomes a real win.
Theorem 2 (odd boards). When n is odd, Blue has a winning strategy for Reverse Hex on an empty n×n board.
Proof. Suppose, for the sake of obtaining a contradiction, that Red has a winning strategy. Then Blue can play as follows: Blue pretends to be the first player, and before the game starts, plays an imaginary blue winning move. Then Blue follows the first-player winning strategy. Should Red ever play where the imaginary blue stone was, Blue continues to pretend that that stone is blue, but also places a new imaginary red stone elsewhere. Since whenever it is Blue's turn, there are still at least 2 empty cells on the board, Blue is never forced to play in a place where there is an imaginary stone. Unless Red loses earlier, Red's final move will be where the current (red or blue) imaginary stone is. Since Blue followed a winning strategy, Blue wins the game under the pretense that Blue's initial imaginary stone was blue. Since that stone is actually red, Blue wins anyway.
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 a simplification of the proof by Lagarias and Sleator.
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, which we assume they follow. 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 Theorems 1 and 2, the only time this can fail is when it's the losing player's turn but there are fewer then 2 empty cells on the board. Thus, the losing move is the one that fills the very last cell. □
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.
Opening Moves
The following boards show which player wins if the first move is played in a given cell. The odd board sizes are left out since, as they are a 2nd player win, all cells would be shaded blue.
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.
