Reverse Hex - Revision history

Mason: Remove odd board swap maps - they're always all blue

2024-11-09T03:06:25Z

Remove odd board swap maps - they're always all blue

Mason: Add opening move evaluations

2024-10-13T18:58:13Z

Add opening move evaluations

Selinger: /* Existence of a winning strategy */ typo

2024-06-16T00:15:14Z

‎Existence of a winning strategy: typo

Selinger: The revised proofs are actually very similar to Lagarias and Sleator's proof.

2024-06-16T00:10:07Z

The revised proofs are actually very similar to Lagarias and Sleator's proof.

Selinger: Simplified the proofs of Theorem 1-3.

2024-06-15T23:58:27Z

Simplified the proofs of Theorem 1-3.

Selinger: /* Existence of a winning strategy */ Switched the players in the proof of Theorem 2, to make it easier to follow

2024-06-14T00:44:54Z

‎Existence of a winning strategy: Switched the players in the proof of Theorem 2, to make it easier to follow

Selinger: /* Existence of a winning strategy */ Replaced the proof of Theorem 2 by a new one. This new proof avoids the symmetry strategy at the beginning of the game.

2024-06-14T00:37:22Z

‎Existence of a winning strategy: Replaced the proof of Theorem 2 by a new one. This new proof avoids the symmetry strategy at the beginning of the game.

Selinger: Reduce jargon

2022-07-10T15:22:36Z

Reduce jargon

Selinger: Added category

2022-02-14T15:25:37Z

Added category

Selinger: added links

2022-02-14T15:22:35Z

added links

@@ Line 86: / Line 86: @@
 === Opening Moves ===
-The following boards show which player wins if the first move is played in a given cell.
+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"
    />
@@ Line 101: / Line 96: @@
    coords="none"
    contents="S red:all blue:b3,c2"
    />
@@ Line 112: / Line 102: @@
    contents="S red:all blue:b5--e2"
    />
 === ''k''×''n'' Reverse Hex ===

← Older revision		Revision as of 18:58, 13 October 2024
Line 84:		Line 84:
	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.		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.
		+
		+	<hexboard size="2x2"
		+	coords="none"
		+	contents="S red:all blue:b1,a2"
		+	/>
		+
		+	<hexboard size="3x3"
		+	coords="none"
		+	contents="S blue:all"
		+	/>
		+
		+	<hexboard size="4x4"
		+	coords="none"
		+	contents="S red:all blue:b3,c2"
		+	/>
		+
		+	<hexboard size="5x5"
		+	coords="none"
		+	contents="S blue:all"
		+	/>
		+
		+	<hexboard size="6x6"
		+	coords="none"
		+	contents="S red:all blue:b5--e2"
		+	/>
	=== ''k''×''n'' Reverse Hex ===		=== ''k''×''n'' Reverse Hex ===

@@ Line 15: / Line 15: @@
 '''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 is. Since Blue followed the first-player 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.
+'''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 ===

@@ Line 5: / Line 5: @@
 === 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.
@@ Line 19: / Line 19: @@
 === 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.

@@ 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.
-'''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.
-'''Proof.''' Extend the empty ''n''×''n'' board by adding one more dead empty cell (so that the extended board has ''n''² + 1 cells, with the final color of the additional cell not affecting the winning condition). Since the extended board has an even number of cells and is symmetric with respect to Red and Blue, the proof of Theorem 1 applies, so the extended board is a first player win. Let Blue go first, so that Blue has a winning strategy. We consider two cases. Case&nbsp;1: Blue's winning strategy starts by playing in the dead cell. In this case, Red is the first player on the remaining ''n''×''n'' board, and since Blue is winning, the ''n''×''n'' board is a second player win. Case&nbsp;2: Blue's winning strategy starts by playing somewhere other than the dead cell. Then Red can respond in the dead cell, and Blue will play a second move on the ''n''×''n'' board. Now the ''n''×''n'' board contains two blue stones, and Blue has a second player winning strategy from this position. But then Blue also has a second player winning strategy on the empty ''n''×''n'' board: Blue can simply pretend that there are two blue stones on it. Should Red play in one of these two cells, Blue plays in the other. At the end of the game, Red has one more stone than what Blue had pretended, so Blue is still winning. So the ''n''×''n'' board is a second player win as claimed. □
+'''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 is. Since Blue followed the first-player 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 ===
@@ Line 25: / Line 23: @@
 '''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.

@@ Line 17: / Line 17: @@
 '''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. □
+'''Proof.''' First consider an empty ''n''×''n'' board to which we have added one more dead empty cell (so that the extended board has ''n''² + 1 cells, with the final color of the additional cell not affecting the winner). Since the extended board has an even number of cells and is symmetric with respect to Red and Blue, the proof of Theorem 1 applies, so Red has a first-player winning strategy on the extended board. We now consider two cases. Case&nbsp;1: Red's winning strategy starts by playing in the dead cell. In this case, Blue is the first player on the remaining ''n''×''n'' board, and since Blue is losing, the ''n''×''n'' board is a first player loss. Case&nbsp;2: Red's winning strategy starts by playing somewhere other than the dead cell. Then Blue can respond in the dead cell, and Red will play a second move on the ''n''×''n'' board. Now the ''n''×''n'' board contains two red stones, and Red has a second player winning strategy from this position. But then Red also has a second player winning strategy on the empty ''n''×''n'' board: Red can simply pretend that there are two red stones there. Should Blue ever play in one of these cells, Red plays in the other. At the end of the game, Blue has one more stone than what Red had pretended, so Red is still winning. So the ''n''×''n'' board is a second player win as claimed. □
 === Postponing the loss ===

← Older revision		Revision as of 15:22, 10 July 2022
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 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.	+	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 ==

← Older revision		Revision as of 15:25, 14 February 2022
Line 110:		Line 110:

	* 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].		* 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]]

@@ Line 17: / Line 17: @@
 '''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. □
+'''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 ===
@@ Line 54: / Line 54: @@
 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 the page "[[Interior template]]" have [[#Pairing strategies|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.
+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:
@@ Line 68: / Line 68: @@
 === 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).