Strategy-stealing argument

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player 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.

Example

A 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 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 a square that he has already moved in, 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 chess 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. It is not currently known whether White or Black can force a win with optimal play, or if both players can force a draw. However, virtually all students of chess consider White's first move to be an advantage and statistics from modern high-level games have White winning's percentage about 10% higher than Black's.

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,^[1] the second player is typically awarded some compensation points, which makes the starting position asymmetrical, and the strategy-stealing argument will no longer work.

Constructivity

The argument shows that the second player cannot win, by means of deriving a contradiction from any purported winning strategy for the second player. According to the BHK interpretation, 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 the 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.

References