In
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
, the strategy-stealing argument is a general
argument
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...
that shows, for many
two-player game A two-player game is a multiplayer game that is played by precisely two players. This is distinct from a solitaire game, which is played by only one player.
Examples
The following are some examples of two-player games. This list is not intended ...
s, that the second player cannot have a guaranteed
winning strategy
Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and simil ...
. The strategy-stealing argument applies to any
symmetric game
In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to ...
(one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage. A key property of a strategy stealing argument is that it proves that the first player can win (or possibly draw) the game without actually constructing such a strategy. So, although it might tell you that there exists a winning strategy, the proof gives you no information about what that strategy is.
The argument works by obtaining a
contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making an arbitrary first move – which by the conditions above is not a disadvantage – the first player may then also play according to this winning strategy. The result is that both players are guaranteed to win – which is absurd, thus contradicting the assumption that such a strategy exists.
Strategy-stealing was invented by
John Nash in the 1940s to show that the game of
hex is always a first-player win, as ties are not possible in this game.
[.] However, Nash did not publish this method, and
József Beck
József Beck (Budapest, Hungary, February 14, 1952) is a Harold H. Martin Professor of Mathematics at Rutgers University.
His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in ''discrepancy theory' ...
credits its first publication to
Alfred W. Hales
Alfred Washington Hales (born November 30, 1938) is an American mathematician, a professor emeritus of mathematics at the University of California, Los Angeles, and one of the namesakes of the Hales–Jewett theorem. He was born in Pasadena, Califo ...
and Robert I. Jewett, in the 1963 paper on
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...
in which they also proved the
Hales–Jewett theorem
In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial ...
.
[.] Other examples of games to which the argument applies include the
''m'',''n'',''k''-games such as
gomoku
''Gomoku'', also called ''Five in a Row'', is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Be ...
. In the game of
Chomp
Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it" (remove from the board), tog ...
strategy stealing shows that the first player has a winning strategy in any rectangular board (other than 1x1). In the game of
Sylver coinage
Sylver coinage is a mathematical game for two players, invented by John H. Conway. It is discussed in chapter 18 of
'' Winning Ways for Your Mathematical Plays''. This article summarizes that chapter.
The two players take turns naming positive ...
, strategy stealing has been used to show that the first player can win in certain positions called "enders". In all of these examples the proof reveals nothing about the actual strategy.
Example
A strategy-stealing argument can be used on the example of the game of
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...
, 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 A strong positional game (also called Maker-Maker game) is a kind of positional game. Like most positional games, it is described by its set of ''positions'' (X) and its family of ''winning-sets'' (\mathcal- a family of subsets of X). It is played ...
.
Chess
There is a class of
chess
Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...
positions called
Zugzwang
Zugzwang (German for "compulsion to move", ) is a situation found in chess and other turn-based games wherein one player is put at a disadvantage because of their obligation to make a move; a player is said to be "in zugzwang" when any legal move ...
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.
[. See in particular Section 22.2.2.2, The Strategy-Stealing Argument]
p. 376
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 statistics from modern high-level games have White's winning percentage about 10% higher than Black's.
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 fight
A ''ko'' (Japanese: コウ, 劫, ''kō'', from the translation of the Sanskrit term kalpa) fight is a tactical and strategic phase that can arise in the game of go.
''Ko'' threats and ''ko'' fights
The existence of ''ko'' fights is implied by th ...
s, 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
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, Exclusive or, either this proposition or its negation is Truth value, true. It is one of the so-called Law of thought#The three tradit ...
. However, it does not provide an explicit strategy for the first player, and because of this it has been called non-constructive.
This raises the question of how to actually compute a winning strategy.
For games with a finite number of reachable positions, such as
chomp
Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it" (remove from the board), tog ...
, a winning strategy can be found by exhaustive search. 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 computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
in two kinds of games in which strategy-stealing arguments were used: the
minimum poset game
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
and the symmetric
Maker-Maker game.
References
{{Game theory
Mathematical games
Arguments