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 S, 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, 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.
The strategy-stealing argument applies to any symmetric game (one in which either player have 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 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 other words it is an existential proof of a win or draw for the first player.
In chess, it is common knowledge that having the first move is a small but significant advantage for White, since White can develop her pieces first. However, the strategy-stealing argument cannot be applied to 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.
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. In actual fact, for the strategy-stealing argument to work at all, any given extra moves must not make otherwise optimal positions sub-optimal. So zugzwang is just one of many possible cases that cause the strategy-stealing argument to fail.
