Difference between revisions of "A1 opening"

From HexWiki
Jump to: navigation, search
(Reformulated the proof sketch, using dead cell and captured cell terminology.)
(Updated the proof to use terminology like "dominated" and "dead", and made it more general.)
Line 1: Line 1:
 
{{wrongtitle|title=a1 opening}}
 
{{wrongtitle|title=a1 opening}}
  
The '''a1 opening''' (in the acute corner) is one of only two openings known to be defeatable. The other is [[B1 opening|b1]].
+
The '''a1 opening''' (in the acute corner) is one of only two openings known to be defeatable. The other is the '''b1 opening'''.
 
+
(This does not mean that these are the worst possible opening moves. Compare with the diagrams on [http://www.cs.ualberta.ca/~queenbee/openings.html the openings page at the queenbee site])
+
 
+
Like the proof that Hex is a win for the first player, the proof that A1 loses is non-constructive: Although we know that it exists, the winning strategy has not been found for regular sized Hex boards.
+
 
+
Due to the symmetry of the Hex board, the same is true of the opposite hexes, but they are not usually referred to explicitly because their coordinate depends on the size of the board.
+
  
 
<hex>
 
<hex>
Line 14: Line 8:
 
</hex>
 
</hex>
  
== Sketch for proof ==
+
(This does not mean that these are the worst possible opening moves. There might be other opening moves that are also losing but for which it is harder for Blue to carry out the win. Compare with the diagrams on [https://web.archive.org/web/20091013152809/http://www.cs.ualberta.ca/~queenbee/openings.html the openings page at the Queenbee site]).
  
Let's assume a1 is a winning first move for Red. There exists a [[winning strategy]] for Red beginning with 1.a1.
+
Like the proof that Hex is a win for the first player, the proof that a1 (or b1) loses is non-constructive: Although we know that it exists, the winning strategy has not been found for regular sized Hex boards.
  
Blue answers a2.  
+
Due to the symmetry of the Hex board, the same is true of the opposite hexes, but they are not usually referred to explicitly because their coordinate depends on the size of the board.
<hex>
+
R5 C5 border
+
play numbered a1 a2
+
</hex>
+
  
This [[Dead cell|kills]] the piece at a1, i.e., makes it into a [[dead cell]].
+
== Sketch of proof ==
Consequently, the resulting position is strategically equivalent to the position where a1 and a2 are occupied by blue pieces.
+
  
<hex>
+
In the following, when we say that a position is "winning" or "losing", we always mean under optimal play by both players.
R5 C5 border
+
 
Ha1 Ha2
+
To show that each of a1 and b1 is a losing opening move, we will prove a stronger statement: the position with red pieces in ''both'' a1 and b1 (and no other pieces on the board), with Blue to move, is losing for Red. Since an additional red piece can only help Red, it then follows that having just a single piece at a1 or b1 is also losing for Red.
</hex>
+
 
 +
<hexboard size="5x5" contents="R a1 b1"/>
 +
 
 +
Assume, for the sake of obtaining a contradiction, that Red has a winning strategy from this position. Blue answers b2.
 +
 
 +
<hexboard size="5x5" contents="R a1 b1 B b2 E *:a2 *:a3"/>
 +
 
 +
The cells marked "*" are [[dominated cell|dominated]], and therefore behave as if they had blue pieces in them. This makes the red pieces at a1 and b1 [[dead cell|dead]]. Therefore, after Blue's move at b2, the position is strategically equivalent to the one where a1, a2, a3, and b1 are blue.
 +
 
 +
<hexboard size="5x5" contents="B a1 b1 B b2 B a2 a3"/>
 +
 
 +
Since we assumed that Red had a second-player win from the position with red pieces at a1 and b1, it follows by symmetry that Blue has a second-player win from the position with blue pieces at a1 and a2. Since additional blue pieces can only help Blue, it follows that Blue also has a second-player winning strategy from the position with 5 blue pieces shown above, and therefore from the position after Blue's move at b2. This contradicts the assumption that Red was supposed to be winning. 
  
From Blue's point of view, this position is at least as good as 1.a1 was from Red's point of view, because Blue has [[captured cell|captured]] a1, and the additional piece at a2 can only help Blue. Since we assumed that Red had a winning strategy from 1.a1, it follows that Blue has a winning strategy from 1.a1, 2.a2. This is a contradiction, since it is not possible for both players to win.
+
Therefore, the initial assumption was wrong, and Red does not have a winning strategy for the position with red pieces in a1 and b1. Since a draw is not possible, the position is losing for Red.
  
Therefore, the initial assumption was wrong, and 1.a1 is not a winning move for Red. Since a draw is not possible, 1.a1 must therefore be a losing move.
+
== a2 is a losing answer to a1 ==
  
== a2 has been proved a losing answer ==
+
If Red opens at a1, then Blue a2 is a losing response for Blue. To see why, note that we proved above that the position with blue pieces at a1 and a2, with Red to move, is losing for Blue. Replacing the blue piece at a1 by a red piece can only help Red, so is still losing for Blue.
[http://hex.kosmanor.com/hex/b1loses.html A sketch of the proof on kosmanor page]
+
  
 
== References ==
 
== References ==

Revision as of 23:10, 13 June 2020

The title given to this article is incorrect due to technical limitations. The correct title is a1 opening.

The a1 opening (in the acute corner) is one of only two openings known to be defeatable. The other is the b1 opening.

1
WARNING: Unrecognized token: border

(This does not mean that these are the worst possible opening moves. There might be other opening moves that are also losing but for which it is harder for Blue to carry out the win. Compare with the diagrams on the openings page at the Queenbee site).

Like the proof that Hex is a win for the first player, the proof that a1 (or b1) loses is non-constructive: Although we know that it exists, the winning strategy has not been found for regular sized Hex boards.

Due to the symmetry of the Hex board, the same is true of the opposite hexes, but they are not usually referred to explicitly because their coordinate depends on the size of the board.

Sketch of proof

In the following, when we say that a position is "winning" or "losing", we always mean under optimal play by both players.

To show that each of a1 and b1 is a losing opening move, we will prove a stronger statement: the position with red pieces in both a1 and b1 (and no other pieces on the board), with Blue to move, is losing for Red. Since an additional red piece can only help Red, it then follows that having just a single piece at a1 or b1 is also losing for Red.

abcde12345

Assume, for the sake of obtaining a contradiction, that Red has a winning strategy from this position. Blue answers b2.

abcde12345

The cells marked "*" are dominated, and therefore behave as if they had blue pieces in them. This makes the red pieces at a1 and b1 dead. Therefore, after Blue's move at b2, the position is strategically equivalent to the one where a1, a2, a3, and b1 are blue.

abcde12345

Since we assumed that Red had a second-player win from the position with red pieces at a1 and b1, it follows by symmetry that Blue has a second-player win from the position with blue pieces at a1 and a2. Since additional blue pieces can only help Blue, it follows that Blue also has a second-player winning strategy from the position with 5 blue pieces shown above, and therefore from the position after Blue's move at b2. This contradicts the assumption that Red was supposed to be winning.

Therefore, the initial assumption was wrong, and Red does not have a winning strategy for the position with red pieces in a1 and b1. Since a draw is not possible, the position is losing for Red.

a2 is a losing answer to a1

If Red opens at a1, then Blue a2 is a losing response for Blue. To see why, note that we proved above that the position with blue pieces at a1 and a2, with Red to move, is losing for Blue. Replacing the blue piece at a1 by a red piece can only help Red, so is still losing for Blue.

References

References for proofs can be found on the Hex Theory page.