On the Wikipedia page for strategy-stealing arguments, there is an example of such an argument applied to tic-tac-toe:
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.
My confusion is about the part in bold. I understand the second part – if you have more squares marked, you will always do at least as well as a setup where you have fewer squares marked – but I don't understand why this won't interfere with the optimal strategy.
Can someone explain why being forced to make a move that you've already made will not interfere with a winning strategy?
Thanks!
Best Answer
In short, because — as emphasized by the last phrase of your bolded passage — having extra pieces on the board in Tic-Tac-Toe is never bad. It's not just 'having more squares' vs. 'having fewer squares'; it's that if position A is exactly position B with an extra X on it, then position A is always at least as good for player X as position B is.
So now suppose you're X, the first player, and you're strategy-stealing; and suppose you come across a moment where the square you're 'supposed' to make your move in — vs. the opponent's given plays — is already taken. Then if that square weren't filled, you would be moving to fill it, meaning that you're moving to some position $P_0$ where (by the assumptions) you're guaranteed to have a winning position. But instead, because you already hold the square you're putting your X somewhere random on the board instead. Then that position is simply $P_0$+X. By the argument in the previous paragraph, this is at least as good for you as position $P_0$ is; but since we knew (by strategy) that $P_0$ was a winning position for you, then the new position $P_0$+X is winning too.