Strategy-stealing argument

A strategy-stealing argument can be used on the example of the game of tic-tac-toe, for a board and winning rows of any size. Suppose that the second player (P2) is using a strategy S which guarantees a win. The first player (P1) places an X in an arbitrary position. P2 responds by placing an O according to S. But if P1 ignores the first random X, P1 is now in the same situation as P2 on P2's first move: a single enemy piece on the board. P1 may therefore make a move according to S – that is, unless S calls for another X to be placed where the ignored X is already placed. But in this case, P1 may simply place an X in some other random position on the board, the net effect of which will be that one X is in the position demanded by S, while another is in a random position, and becomes the new ignored piece, leaving the situation as before. Continuing in this way, S is, by hypothesis, guaranteed to produce a winning position (with an additional ignored X of no consequence). But then P2 has lost – contradicting the supposition that P2 had a guaranteed winning strategy. Such a winning strategy for P2, therefore, does not exist, and tic-tac-toe is either a forced win for P1 or a tie. (Further analysis shows it is in fact a tie.) The same proof holds for any strong positional game. == 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 White wins more often than black in high-level games. If the rules are modified to allow players to pass, the symmetry of the initial position makes it possible to use a strategy-stealing argument to show that the first player has at least a draw, as first described by Claude Shannon: if the first player has a winning move in the initial position, let them play it, else pass. On the second player's turn, if the first player had no winning move before, the second player has none now. Therefore, the second player can at best draw, and the first player can at least draw, so a perfect game results in the first player winning or drawing. == 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 points, which makes the starting position asymmetrical, and the strategy-stealing argument will no longer work. An elementary strategy in the game is "mirror go", where the second player performs moves which are diagonally opposite those of this opponent. This approach may be defeated using ladder tactics, ko fights, or successfully competing for control of the board's central point. == Constructivity ==

The strategy-stealing argument shows that the second player cannot win, by means of deriving a contradiction from any hypothetical winning strategy for the second player. The argument is commonly employed in games where there can be no draw, by means of the law of the excluded middle. However, it does not provide an explicit strategy for the first player, and because of this it has been called non-constructive. However, this might be impractical if the number of positions is large. In 2019, Greg Bodwin and Ofer Grossman proved that the problem of finding a winning strategy is PSPACE-hard in two kinds of games in which strategy-stealing arguments were used: the minimum poset game and the symmetric Maker-Maker game. == References ==