Difference between revisions of "Winning strategy"
(added a heading and sections to develop) |
(Removed broken link, removed stub warning) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
==Definition== | ==Definition== | ||
| − | |||
| − | + | A ''strategy'' for a player is a rule that specifies the player's next move from every possible position. If we fix a strategy for Red and a strategy for Blue, then the winner of the game is determined, because we can simply play the game to the end, using each player's strategy. | |
| − | + | ||
| − | The reason for the second player's | + | A strategy for Red is called a ''winning strategy'' if it wins against every possible strategy for Blue. Similarly, a strategy for Blue is called a winning strategy if it wins against every possible strategy for Red. |
| − | # The move was so good that no matter what the second player does, the first will win. In this case, the second player should swap colors. | + | |
| + | Instead of strategies for the whole game (starting from the empty board), we can also consider strategies for specific positions. In this case, we must specify not just the pieces on the board, but also whose turn it is. For example, we can say "Red has a winning strategy for this position with Blue to move next". We say that a position is a ''first-player win'' for a player if that player has a winning strategy when she gets to move next, and a ''second-player win'' for a player if that player has a winning strategy when her opponent gets to move next. | ||
| + | |||
| + | ==Existence of a winning strategy for one of the two players== | ||
| + | |||
| + | Since Hex is a finite game (there are only finitely many positions and every game ends after finitely many moves), in every given position, exactly one of the players (the player whose turn it is, or the player whose turn it is not) has a winning strategy. (But it may not always be easy to figure out which one). It is clear that not both players can have a winning strategy, since letting these strategies play against each other, only one player would win. | ||
| + | |||
| + | To show that at least one player has a winning strategy, we can proceed by induction on the number of empty cells on the board. If there are no empty cells on the board, one player [[Theory#No_draw|has already won]], and so that player has a winning strategy by doing nothing. Now consider a position ''P'' with ''n''+1 empty cells on the board, and suppose it is player ''A'''s turn. There are finitely many possible moves for ''A'' from ''P'', and each of them leads to a position with ''n'' empty cells. By induction hypothesis, each of these positions is either winning for ''A'' or winning for the other player ''B''. If all of the positions are winning for ''B'', then ''P'' is also winning for ''B'', because no matter what ''A'' does next, ''B'' will have a way to win. If one of the positions is winning for ''A'', then ''P'' is also winning for ''A'', because ''A'' can just move to that position. | ||
| + | |||
| + | ==Existence of a winning strategy for specific players== | ||
| + | |||
| + | In some cases, it is known which of the two players has a winning strategy (but it may not be known what that winning strategy is). | ||
| + | |||
| + | In [[Hex]] without the swap rule, starting from an empty ''n''×''n'' board, it can be shown that there exists a [[Theory#No_winning_strategy_for_Blue|winning strategy for the first player]]. The proof is by contradiction, and nobody knows what the actual winning strategy is. | ||
| + | |||
| + | In [[Hex]] with the swap rule, there is a [[Theory#Winning_Strategy|winning strategy for the second player]]. | ||
| + | The reason for the second player's winning strategy is simple: After the first player's move, there are two possibilities: | ||
| + | # The move was so good that no matter what the second player does, the first will win. In this case, the second player should swap colors and steal the win. | ||
# The move was bad, so that the first player cannot win. Because the game cannot end in a draw, this means that the second player can win. In this case, don't swap colors. | # The move was bad, so that the first player cannot win. Because the game cannot end in a draw, this means that the second player can win. In this case, don't swap colors. | ||
| − | The | + | To take advantage of this fact, the second player would have to know which opening moves are winning for Red and which ones are winning for Blue, in order to figure out whether to swap or not. The second player would then also have to know a particular winning strategy, so that she does not accidentally lose by making a bad move. Since no such particular strategy is known, each player has to do the best they can, which is why the game is interesting to play. |
| − | + | On an asymmetric board of size ''n''×''m'', where ''n'' ≠ ''m'', the player with the shorter distance between their edges always has a winning strategy, no matter who goes first. In this case, a [[Theory#Winning_strategy_for_non-square_boards|particular winning strategy]] is known. | |
| − | [[ | + | There are some positions on non-empty boards where it is known which player has a winning strategy. Two such positions are the [[a1 opening]] and the [[b1 opening]], both of which are losing. Also, any [[Theory#No_winning_strategy_for_Blue|symmetric position]], i.e., any position that looks the same from Red's and Blue's point of view (with the sides and colors flipped), is a win for the next player to move. Finally, if some position is winning for a player, then adding additional pieces of that player's color to the board, or removing pieces of the opponent's color, yields a position that is still winning for the same player. For this reason, we say that extra pieces of a player's own color "can only help" the player. |
| − | [[category:Theory]] | + | [[category: Theory]] |
| − | + | [[category: Definition]] | |
Latest revision as of 01:06, 12 September 2021
Definition
A strategy for a player is a rule that specifies the player's next move from every possible position. If we fix a strategy for Red and a strategy for Blue, then the winner of the game is determined, because we can simply play the game to the end, using each player's strategy.
A strategy for Red is called a winning strategy if it wins against every possible strategy for Blue. Similarly, a strategy for Blue is called a winning strategy if it wins against every possible strategy for Red.
Instead of strategies for the whole game (starting from the empty board), we can also consider strategies for specific positions. In this case, we must specify not just the pieces on the board, but also whose turn it is. For example, we can say "Red has a winning strategy for this position with Blue to move next". We say that a position is a first-player win for a player if that player has a winning strategy when she gets to move next, and a second-player win for a player if that player has a winning strategy when her opponent gets to move next.
Existence of a winning strategy for one of the two players
Since Hex is a finite game (there are only finitely many positions and every game ends after finitely many moves), in every given position, exactly one of the players (the player whose turn it is, or the player whose turn it is not) has a winning strategy. (But it may not always be easy to figure out which one). It is clear that not both players can have a winning strategy, since letting these strategies play against each other, only one player would win.
To show that at least one player has a winning strategy, we can proceed by induction on the number of empty cells on the board. If there are no empty cells on the board, one player has already won, and so that player has a winning strategy by doing nothing. Now consider a position P with n+1 empty cells on the board, and suppose it is player A's turn. There are finitely many possible moves for A from P, and each of them leads to a position with n empty cells. By induction hypothesis, each of these positions is either winning for A or winning for the other player B. If all of the positions are winning for B, then P is also winning for B, because no matter what A does next, B will have a way to win. If one of the positions is winning for A, then P is also winning for A, because A can just move to that position.
Existence of a winning strategy for specific players
In some cases, it is known which of the two players has a winning strategy (but it may not be known what that winning strategy is).
In Hex without the swap rule, starting from an empty n×n board, it can be shown that there exists a winning strategy for the first player. The proof is by contradiction, and nobody knows what the actual winning strategy is.
In Hex with the swap rule, there is a winning strategy for the second player. The reason for the second player's winning strategy is simple: After the first player's move, there are two possibilities:
- The move was so good that no matter what the second player does, the first will win. In this case, the second player should swap colors and steal the win.
- The move was bad, so that the first player cannot win. Because the game cannot end in a draw, this means that the second player can win. In this case, don't swap colors.
To take advantage of this fact, the second player would have to know which opening moves are winning for Red and which ones are winning for Blue, in order to figure out whether to swap or not. The second player would then also have to know a particular winning strategy, so that she does not accidentally lose by making a bad move. Since no such particular strategy is known, each player has to do the best they can, which is why the game is interesting to play.
On an asymmetric board of size n×m, where n ≠ m, the player with the shorter distance between their edges always has a winning strategy, no matter who goes first. In this case, a particular winning strategy is known.
There are some positions on non-empty boards where it is known which player has a winning strategy. Two such positions are the a1 opening and the b1 opening, both of which are losing. Also, any symmetric position, i.e., any position that looks the same from Red's and Blue's point of view (with the sides and colors flipped), is a win for the next player to move. Finally, if some position is winning for a player, then adding additional pieces of that player's color to the board, or removing pieces of the opponent's color, yields a position that is still winning for the same player. For this reason, we say that extra pieces of a player's own color "can only help" the player.
