Strategy-stealing argument
Encyclopedia
In combinatorial game theory
, the strategy-stealing argument is a general argument
that shows, for many games, that the second player cannot have a winning strategy (i.e., a strategy that will always win the game for them, no matter what moves the first player makes).
The strategy-stealing argument applies to any symmetric game
(one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage. Examples of games to which the argument applies are hex
, chomp
and the m,n,k-games such as gomoku
. In hex ties are not possible, so the argument shows that it is a first-player win.
goes like this: suppose that the second player has a guaranteed winning strategy, which we will call S. We can convert S into a winning strategy for the first player. The first player should make his first move at random; thereafter he should pretend to be the second player, "stealing" the second player's strategy S, and follow strategy S, which by hypothesis will result in a victory for him. If strategy S calls for him to move in the square that he chose at random for his first move, he should choose at random again. This will not interfere with the execution of S, and this strategy is always at least as good as S since having an extra marked square on the board is never a disadvantage in tic-tac-toe.
Thus the existence of an infallible winning strategy S for the second player implies the existence of a similarly infallible winning strategy for the first player, which is a contradiction since the players cannot both have infallible winning strategies. Thus no winning strategy for the second player exists, and tic-tac-toe is either a forced win for the first player or a tie. (Further analysis shows it is a tie.)
positions called Zugzwang
in which the player obligated to move would prefer to "pass" if this were allowed. Because of this, the strategy-stealing argument cannot be applied to chess. However, virtually all students of chess
agree that the first move is a small but significant advantage for White.
, which makes the starting position asymmetrical, and the strategy stealing argument will not work anymore.
, the most widely used basis for constructive interpretation of logical formulae, this is constructive.
The argument is commonly employed in games where there can be no draw to show that first player has a winning strategy, such as in Hex. This application of the argument is usually non-constructive, where the inference from the absence of a strategy and the impossibility of a draw is made by means of the law of the excluded middle. For finite games, and games where the appropriate instance of Markov's rule can be constructively established by means of bar induction
, then the non-constructive proof of a winning strategy for the first player can be converted into a winning strategy.
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
, the strategy-stealing argument is a general argument
Argument
In philosophy and logic, an argument is an attempt to persuade someone of something, or give evidence or reasons for accepting a particular conclusion.Argument may also refer to:-Mathematics and computer science:...
that shows, for many games, that the second player cannot have a winning strategy (i.e., a strategy that will always win the game for them, no matter what moves the first player makes).
The strategy-stealing argument applies to any symmetric game
Symmetric game
In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. ...
(one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage. Examples of games to which the argument applies are hex
Hex (board game)
Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go...
, chomp
Chomp
Chomp is a 2-player game of strategy played on a rectangular "chocolate bar" made up of smaller square blocks . The players take it in turns to choose one block and "eat it" , together with those that are below it and to its right...
and the m,n,k-games such as gomoku
Gomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...
. In hex ties are not possible, so the argument shows that it is a first-player win.
Example
A strategy-stealing argument for tic-tac-toeTic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
goes like this: suppose that the second player has a guaranteed winning strategy, which we will call S. We can convert S into a winning strategy for the first player. The first player should make his first move at random; thereafter he should pretend to be the second player, "stealing" the second player's strategy S, and follow strategy S, which by hypothesis will result in a victory for him. If strategy S calls for him to move in the square that he chose at random for his first move, he should choose at random again. This will not interfere with the execution of S, and this strategy is always at least as good as S since having an extra marked square on the board is never a disadvantage in tic-tac-toe.
Thus the existence of an infallible winning strategy S for the second player implies the existence of a similarly infallible winning strategy for the first player, which is a contradiction since the players cannot both have infallible winning strategies. Thus no winning strategy for the second player exists, and tic-tac-toe is either a forced win for the first player or a tie. (Further analysis shows it is a tie.)
Chess
There is a class of chessChess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
positions called Zugzwang
Zugzwang
Zugzwang is a term usually used in chess which also applies to various other games. The term finds its formal definition in combinatorial game theory, and it describes a situation where one player is put at a disadvantage because he has to make a move when he would prefer to pass and make no move...
in which the player obligated to move would prefer to "pass" if this were allowed. Because of this, the strategy-stealing argument cannot be applied to chess. However, virtually all students of chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
agree that the first move is a small but significant advantage for White.
Go
In Go passing is allowed. When the starting position is symmetrical (empty board, neither player has any points), this means that the first player could steal the second player's winning strategy simply by giving up the first move. Since the 1930s, however, the second player is typically awarded some compensation pointsKomidashi
in the game of Go are points added to the score of the player with the white stones as compensation for playing second. Black's first move advantage is generally considered to equal somewhere between 5 and 7 points by the end of the game. Standard komi is 6.5 points under the Japanese and Korean...
, which makes the starting position asymmetrical, and the strategy stealing argument will not work anymore.
Constructivity
The argument shows that the second player cannot win, by means of deriving a contradiction from any purported winning strategy for second player. According to the BHK interpretationBHK interpretation
In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer, Arend Heyting and independently by Andrey Kolmogorov...
, the most widely used basis for constructive interpretation of logical formulae, this is constructive.
The argument is commonly employed in games where there can be no draw to show that first player has a winning strategy, such as in Hex. This application of the argument is usually non-constructive, where the inference from the absence of a strategy and the impossibility of a draw is made by means of the law of the excluded middle. For finite games, and games where the appropriate instance of Markov's rule can be constructively established by means of bar induction
Bar induction
Bar induction is a reasoning principle used in intuitionistic mathematics, introduced by L.E.J. Brouwer.It is useful in giving constructive versions of classical results.It is based on an inductive argument....
, then the non-constructive proof of a winning strategy for the first player can be converted into a winning strategy.