2
$\begingroup$

Some time ago, I asked myself if infinite gomoku is a first player win, which seems not proven yet, and while searching for an answer I often heard the term "strategy stealing game".

I just thought it means that the second player will always lose if both players play correctly, or always player one in some rare cases, but now I checked Wikipedia and it seems like that only means that player 2 doesn't have a guaranteed winning strategy in such a game...

And the more I think about it, the less sense it makes for me. Shoudn't it be good if the second player has no way to win for sure? I mean if he had, it would be a second player win game, just as bad as a first player win game.

For example in tic-tac-toe. Player 1 can't win if player 2 doesn't make any mistake, player 2 can't win if player 1 doesn't make any mistake. No one has a guaranteed winning strategy. Is it, or is it not a strategy stealing argument? Shouldn't it be just like that?

$\endgroup$
2
$\begingroup$

A strategy-stealing argument is one that includes the idea "But if player A had a winning strategy, then player B could use that strategy (or a slight modification of it) to win the game."

A classic example is the game of chomp. The game is played on an $m\times n$ grid of squares and players 1 and 2 take it in turns to eat squares. Specifically, a move consists of choosing an uneaten square $(a,b)$ and then eating all squares $(x,y)$ such that $x\geq a$ and $y\geq b$. The square $(1,1)$ is poisoned so whoever is forced to eat it loses.

Theorem. Player 1 has a winning strategy, except in the case $m=n=1$.

Proof. If $m=n=1$, player 1's only possible move is to eat the poisoned square, which loses. So, suppose that $(m,n)\neq(1,1)$ and suppose, towards a contradiction, that player 2 has a winning strategy. That means that, for any first move player 1 might make, player 2 has a reply that allows him to win the game. In particular, if player 1's first move is $(m,n)$, player 2 can force a win by playing some move $(u,v)$. Notice that the position after the moves $(m,n)$ and $(u,v)$ is identical to the position that would have arisen if player 1 had just started by playing $(u,v)$. So, instead of playing $(m,n)$, he could have played $(u,v)$ and then used player 2's supposed winning strategy to win the game. Therefore, player 1 has a winning strategy, contradicting our assumption that player 2 has one – they can't both be able to force a win!

Chomp is a two-player game of perfect information, with no ties, so one of the players must have a winning strategy. Since player 2 does not have a winning strategy, player 1 must do. $\quad\Box$

As for your question about whether this is good or bad, it doesn't really make sense. It's like asking if prime numbers are good or bad. They're neither: they just are.

$\endgroup$
  • $\begingroup$ Ah okay, yes that makes sense. First of all, with "good or bad" I meant how it would effect the game about the question if it is a first player win game or not. In this case, it is. $\endgroup$ – Platurt Dec 4 '14 at 0:17
  • $\begingroup$ In this case, it is. But how about Tic Tac Toe? Wikipedia sais "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.", arguing that because player 1 can, after player 2 placed that O which was part of the strategie, just act as if he were player 2 and place his X in the same position to the 0 like player 2 placed his 0 to the X. But the X before still exist, what proves that this taken slot doesn't bothers for the strategy? I mean, on a 3x3 board player 1 can't just place another x anywhere, there is no infinite space. $\endgroup$ – Platurt Dec 4 '14 at 0:23
  • $\begingroup$ Ok, I'm sorry, I got it now. Needed both examples, chomp and hex, to understand it. Didn't got until now that player 1 doesn't have to just copy the strategy player 2 was using against player 1, but there still has to be a strategie against player 2 in this case since player 2 also would have one against player 1 if he placed his first move in this position. Finally got it, ty guys! $\endgroup$ – Platurt Dec 4 '14 at 0:56
2
$\begingroup$

A strategy stealing game is one in which, if the second player has a winning strategy, the first player can use it and thus win.

For example, in Hex, since all that matters is getting a connected string between two sides, if the second player has a winning strategy, the first player can make an arbitrary move and then play the second player's strategy, considering the second player as the first player.

If the first player is required by the strategy to play in an already occupied location, then play in any unoccupied location, since additional locations occupied is never a disadvantage.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.