Difference between revisions of "A1 opening"

From HexWiki
Jump to: navigation, search
(Updated the proof to use terminology like "dominated" and "dead", and made it more general.)
m (added a link)
 
(6 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
<hex>
 
<hex>
R5 C5 border
+
R5 C5 Q1
play numbered a1
+
numbered a1
 
</hex>
 
</hex>
  
 
(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]).
 
(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]).
  
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.
+
Like the [[Hex_theory#No_winning_strategy_for_Blue|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.
 
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.
 +
 +
The above statements about the a1 and b1 openings hold for boards of size ''n''×''n'', where ''n'' ≥ 3. For smaller board sizes, the situation is different but fairly trivial: on the 1×1 board, a1 is (obviously) winning, and on the 2×2 board, a1 is losing and b1 is winning. On [[Hex_theory#Winning_strategy_for_non-square_boards|non-square boards]], the player with the shorter distance to cover has a winning strategy regardless of the opening move.
  
 
== Sketch of proof ==
 
== 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.
+
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.
+
Assume a symmetric board of size at least 3×3. 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.
  
 
<hexboard size="5x5" contents="R a1 b1"/>
 
<hexboard size="5x5" contents="R a1 b1"/>
Line 26: Line 28:
 
<hexboard size="5x5" contents="R a1 b1 B b2 E *:a2 *:a3"/>
 
<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.
+
The cells marked "*" are [[captured cell|captured]], 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"/>
 
<hexboard size="5x5" contents="B a1 b1 B b2 B a2 a3"/>

Latest revision as of 16:28, 25 May 2023

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.

abcde123451

(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.

The above statements about the a1 and b1 openings hold for boards of size n×n, where n ≥ 3. For smaller board sizes, the situation is different but fairly trivial: on the 1×1 board, a1 is (obviously) winning, and on the 2×2 board, a1 is losing and b1 is winning. On non-square boards, the player with the shorter distance to cover has a winning strategy regardless of the opening move.

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.

Assume a symmetric board of size at least 3×3. 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 captured, 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.