What exactly is a strategy stealing game and is it bad?

2k Views Asked by At

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?

2

There are 2 best solutions below

3
On BEST ANSWER

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.

0
On

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.