Difference between revisions of "Reverse Hex"

From HexWiki
Jump to: navigation, search
(Created an article on Reverse Hex.)
 
(Remove odd board swap maps - they're always all blue)
 
(19 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 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.
+
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 different (and simpler) proof.
+
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. 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).
+
'''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.
−
 
+
−
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.
 
'''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. 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. □
+
'''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 different from (and simpler than) Lagarias and Sleator's.
+
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 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. □
+
'''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 ==
 
== 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.  
+
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.  
  
−
=== Anti-templates ===
+
=== Co-templates ===
  
−
A [[template]] in Hex guarantee that a player can [[virtual connection|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.
+
In Hex, a [[template]] guarantees that a player can [[virtual connection|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 an anti-template is the [[bridge]]:  
+
The simplest example of a co-template is the [[bridge]]:  
 
<hexboard size="2x2"
 
<hexboard size="2x2"
 
   coords="none"
 
   coords="none"
Line 43: Line 43:
 
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.
 
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]]:
+
Although not all Hex templates are co-templates, many of them are. For example, the [[ziggurat]] is a co-template:
 
<hexboard size="3x4"
 
<hexboard size="3x4"
 
   visible="area(a3,d3,d1,c1)"
 
   visible="area(a3,d3,d1,c1)"
Line 50: Line 50:
 
   contents="R c1 E 1:(b2 d2) 2:(d1 c2) 3:(a3 b3) 4:(c3 d3)"
 
   contents="R c1 E 1:(b2 d2) 2:(d1 c2) 3:(a3 b3) 4:(c3 d3)"
 
/>
 
/>
−
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.
+
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.
  
−
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:
+
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:
 
<hexboard size="4x3"
 
<hexboard size="4x3"
 
   edges="all"
 
   edges="all"
Line 60: Line 62:
 
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.
 
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.
+
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 ===
 
=== 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.
+
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 75: Line 112:
 
             E 1:e6 2:e5 3:e4 4:e3 5:e2 6:d6 7:d5 8:d4 9:d3 10:c6 11:c5 12:c4 13:b6 14:b5 15:a6"
 
             E 1:e6 2:e5 3:e4 4:e3 5:e2 6:d6 7:d5 8:d4 9:d3 10:c6 11:c5 12:c4 13:b6 14:b5 15:a6"
 
   />
 
   />
−
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.
+
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 ==
 
== Computer Reverse Hex ==
Line 89: 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", July 2017. [https://arxiv.org/abs/1707.00627 arXiv:1707.00627]
+
* 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.

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:

21213344

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:

abcdef

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:

123456789510111294131412831514117215131061

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.
Retrieved from "https://www.hexwiki.net/index.php?title=Reverse_Hex&oldid=8756"