Strategy-stealing argument
|
|
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.
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.
It would be tempting to try to apply the strategy-stealing argument to chess and argue that chess can't be a second-player win, because if it were then the first player could open h3 and then follow the second-player strategy with some trivial adjustment when it comes to moving the h-pawn. However, there seems to be no obvious way to prove that the "trivial" adjustment is in fact trivial, or even possible. Chess does have positions where an extra move is a disadvantage: see zugzwang.