Difference between revisions of "A1 opening"
(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 | + | The '''a1 opening''' (in the acute corner) is one of only two openings known to be defeatable. The other is the '''b1 opening'''. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
<hex> | <hex> | ||
| Line 14: | Line 8: | ||
</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]). | |
| − | + | 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. | |
| − | </ | + | |
| + | <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. | ||
| − | + | 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 == | ||
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.
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.
Assume, for the sake of obtaining a contradiction, that Red has a winning strategy from this position. Blue answers b2.
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.
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.
