Strategy-stealing argument
From Wikipedia, the free 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).
A typical strategy-stealing argument, for tic-tac-toe, 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 her first move at random; thereafter she should pretend to be the second player, "stealing" the second player's strategy, and follow strategy S, which by hypothesis will result in a victory for her. If strategy S calls for her to move in the square that she chose at random for her first move, she should choose at random again. This will not interfere with the execution of 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.
The strategy-stealing argument applies to any symmetric game (one in which the two players have corresponding moves available to them, so that it makes sense to pretend to be the other player and steal their strategy) in which an extra move can never be a disadvantage. Examples of games to which the argument applies are the m,n,k-games such as gomoku, hex, and the Shannon switching game. In the latter two games ties are not possible, so the argument shows that they are first-player wins.
The strategy-stealing argument is non-constructive. It proves that a strategy exists, but provides no help in discovering what that strategy is.
In chess, it is common knowledge that having the first move is a small but significant advantage for White, since White can develop his pieces first. However, the strategy-stealing argument does not technically work for chess. Aron Nimzovich or another hypermodern once joked that after 1. e4, "White's game is in its last throes." According to this view, 1. e4 leaves White with a weak pawn structure, which Black can exploit. However, even a quiet first move, such as 1. a3 or 1. Nf3, changes the position in a way that could, at least theoretically, prove disadvantageous to White in the future. The strategy-stealing argument works only if the first player's move cannot have any theoretical drawbacks.
It is known that in some chess positions, a player wins if it is his opponent's turn, but loses or draws if it is his own turn. The compulsion to move, leading to a sub-optimal result, is called zugzwang. The initial position of the chess game is probably not zugzwang, but the existence of zugzwang disqualifies the strategy-stealing argument from applying to chess.
