Strategy-stealing argument

Last updated

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game (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.

Contents

The argument works by obtaining a contradiction. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making their 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. [1] However, Nash did not publish this method, and Beck (2008) credits its first publication to Alfred W. Hales and Robert I. Jewett, in the 1963 paper on tic-tac-toe in which they also proved the Hales–Jewett theorem. [2] Other examples of games to which the argument applies include the m,n,k-games such as gomoku. In the game of Sylver coinage, strategy stealing has been used to show that the first player wins, rather than that the game ends in a tie. [3]

Example

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. [1] [2] Suppose that the second player is using a strategy, S, which guarantees them a win. The first player places an X in an arbitrary position, and the second player then responds by placing an O according to S. But if they ignore the first random X that they placed, the first player finds themselves in the same situation that the second player faced on their first move; a single enemy piece on the board. The first player may therefore make their moves 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, the player may simply place his 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 the second player has lost – contradicting the supposition that they had a guaranteed winning strategy. Such a winning strategy for the second player, therefore, does not exist, and tic-tac-toe is either a forced win for the first player or a tie. Further analysis shows it is in fact a tie.

The same proof holds for any strong positional game.

Chess

Philidor, 1777
abcdefgh
8
Chessboard480.svg
Chess qlt45.svg
Chess klt45.svg
Chess rdt45.svg
Chess kdt45.svg
8
77
66
55
44
33
22
11
abcdefgh
Black is in zugzwang, since they must move their rook away from their king.

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. [4] 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, [5] 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. [4] This raises the question of how to actually compute a winning strategy.

For games with a finite number of reachable positions, such as chomp, a winning strategy can be found by exhaustive search. [6] 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. [7]

Related Research Articles

Mathematical game game defined by mathematical parameters

A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games need not be conceptually intricate to involve deeper computational underpinnings. For example, even though the rules of Mancala are relatively basic, the game can be rigorously analyzed through the lens of combinatorial game theory.

Tic-tac-toe Paper-and-pencil game for two players and some devices

Tic-tac-toe, noughts and crosses, or Xs and Os is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

Game tree tree diagram used to find and analyze potential moves in a game

In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.

Combinatorial game theory branch of game theory about two-player sequential games with perfect information

Combinatorial game theory (CGT) 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 in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

m,n,k-game abstract board game for two players, in which 2 players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically or diagonally

An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. Thus, tic-tac-toe is the 3,3,3-game and free-style gomoku is the 15,15,5-game. An m,n,k-game is also called a k-in-a-row game on an m×n board.

3D tic-tac-toe abstract strategy board game, generally for two players

3D tic-tac-toe, also known by the trade name Qubic, is an abstract strategy board game, generally for two players. It is similar in concept to traditional tic-tac-toe but is played in a cubical array of cells, usually 4x4x4. Players take turns placing their markers in blank cells in the array. The first player to achieve four of their own markers in a row wins. The winning row can be horizontal, vertical, or diagonal on a single board as in regular tic-tac-toe, or vertically in a column, or a diagonal line through four boards.

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 structure; it is impossible for such objects to be "completely random".

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.

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 similarly, "determinacy" is the property of a game whereby such a strategy exists.

Harary's generalized tic-tac-toe or animal tic-tac-toe is a generalization of the game tic-tac-toe, defining the game as a race to complete a particular polyomino on a square grid of varying size, rather than being limited to "in a row" constructions. It was devised by Frank Harary in March 1977, and is a broader definition than that of an m,n,k-game.

Zillions of Games commercial general game playing system

Zillions of Games is a commercial general game playing system developed by Jeff Mallett and Mark Lefler in 1998. The game rules are specified with S-expressions, Zillions rule language. It was designed to handle mostly abstract strategy board games or puzzles. After parsing the rules of the game, the system's artificial intelligence can automatically play one or more players. It treats puzzles as solitaire games and its AI can be used to solve them.

First-player and second-player win

In game theory, a two-player deterministic perfect information turn-based game is a first-player-win if with perfect play the first player to move can always force a win. Similarly, a game is second-player-win if with perfect play the second player to move can always force a win. With perfect play, if neither side can force a win, the game is a draw.

A positional game is a kind of a combinatorial game for two players. It is described by:

Ultimate tic-tac-toe twist to the original game tic-tac-toe

Ultimate tic-tac-toe is a board game composed of nine tic-tac-toe boards arranged in a 3 × 3 grid. Players take turns playing in the smaller tic-tac-toe boards until one of them wins in the larger tic-tac-toe board. Compared to traditional tic-tac-toe, strategy in this game is conceptually more difficult and has proven more challenging for computers.

Notakto

Notakto is a tic-tac-toe variant, also known as neutral or impartial tic-tac-toe. The game is a combination of the games tic-tac-toe and Nim, played across one or several boards with both of the players playing the same piece. The game ends when all the boards contain a three-in-a-row of Xs, at which point the player to have made the last move loses the game. However, in this game, unlike tic-tac-toe, there will always be a player who wins any game of Notakto.

A strong positional game is a kind of positional game. Like most positional games, it is described by its set of positions and its family of winning-sets. It is played by two players, called First and Second, who alternately take previously-untaken positions.

In a positional game, a pairing strategy is a strategy that a player can use to guarantee victory, or at least force a draw. It is based on dividing the positions on the game-board into disjoint pairs. Whenever the opponent picks a position in a pair, the player picks the other position in the same pair.

Combinatorial Games: Tic-Tac-Toe Theory is a monograph on the mathematics of tic-tac-toe and other positional games, written by József Beck. It was published in 2008 by the Cambridge University Press as volume 114 of their Encyclopedia of Mathematics and its Applications book series (ISBN 978-0-521-46100-9).

References

  1. 1 2 Beck, József (2008), Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, 114, Cambridge: Cambridge University Press, p.65, 74, doi:10.1017/CBO9780511735202, ISBN   9780511735202, MR   2402857 .
  2. 1 2 Hales, A. W.; Jewett, R. I. (1963), "Regularity and positional games", Transactions of the American Mathematical Society , 106 (2): 222–229, doi: 10.2307/1993764 , JSTOR   1993764, MR   0143712 .
  3. Sicherman, George (2002), "Theory and Practice of Sylver Coinage" (PDF), Integers, 2, G2
  4. 1 2 Bishop, J. M.; Nasuto, S. J.; Tanay, T.; Roesch, E. B.; Spencer, M. C. (2016), "HeX and the single anthill: Playing games with Aunt Hillary", in Müller, Vincent C. (ed.), Fundamental Issues of Artificial Intelligence (PDF), Synthese Library, 376, Springer, pp. 369–390, doi:10.1007/978-3-319-26485-1_22 . See in particular Section 22.2.2.2, The Strategy-Stealing Argument, p. 376.
  5. Fairbairn, John, History of Komi , retrieved 2010-04-09
  6. rjlipton (2013-10-02). "Stealing Strategies". Gödel's Lost Letter and P=NP. Retrieved 2019-11-30.
  7. Bodwin, Greg; Grossman, Ofer (2019-11-15). "Strategy-Stealing is Non-Constructive". arXiv: 1911.06907 [cs.DS].