Solved game

Last updated

A solved game is a game whose outcome (win, lose or draw) 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.

Contents

Overview

A two-player game can be solved on several levels: [1] [2]

Ultra-weak solution

Prove whether the first player will win, lose or draw from the initial position, given perfect play on both sides (see § Perfect play, below). This can be a non-constructive proof (possibly involving a strategy-stealing argument) that need not actually determine any details of the perfect play.

Weak solution

Provide an algorithm that secures a win for one player, or a draw for either, against any possible play by the opponent, from the beginning of the game.

Strong solution

Provide an algorithm that can produce perfect play for both players from any position, even if imperfect play has already occurred on one or both sides.

Despite their name, many game theorists believe that "ultra-weak" proofs are the deepest, most interesting and valuable. "Ultra-weak" proofs require a scholar to reason about the abstract properties of the game, and show how these properties lead to certain outcomes if perfect play is realized.[ citation needed ]

By contrast, "strong" proofs often proceed by brute force—using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on the board. However, these proofs are not as helpful in understanding deeper reasons why some games are solvable as a draw, and other, seemingly very similar games are solvable as a win.

Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax algorithm that would exhaustively traverse the game tree. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database and are effectively nothing more.

As a simple example of a strong solution, the game of tic-tac-toe is easily solvable as a draw for both players with perfect play (a result manually determinable). Games like nim also admit a rigorous analysis using combinatorial game theory.

Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if its solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g., Maharajah and the Sepoys). An ultra-weak solution (e.g., Chomp or Hex on a sufficiently large board) generally does not affect playability.

Perfect play

In game theory, perfect play is the behavior or strategy of a player that leads to the best possible outcome for that player regardless of the response by the opponent. Perfect play for a game is known when the game is solved. [1] Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By backward reasoning, one can recursively evaluate a non-final position as identical to the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player, and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.

Perfect play can be generalized to non-perfect information games, as the strategy that would guarantee the highest minimal expected outcome regardless of the strategy of the opponent. As an example, the perfect strategy for rock paper scissors would be to randomly choose each of the options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected outcome.

Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain endgame positions (in the form of endgame tablebases), which will allow it to play perfectly after some point in the game. Computer chess programs are well known for doing this.

Solved games

Awari (a game of the Mancala family)
The variant of Oware allowing game ending "grand slams" was strongly solved by Henri Bal and John Romein at the Vrije Universiteit in Amsterdam, Netherlands (2002). Either player can force the game into a draw.
Chopsticks
Strongly solved. If two players both play perfectly, the game will go on indefinitely.[ citation needed ]
Connect Four
The game of Connect Four has been solved Connect Four.jpg
The game of Connect Four has been solved
Solved first by James D. Allen on October 1, 1988, and independently by Victor Allis on October 16, 1988. [3] The first player can force a win. Strongly solved by John Tromp's 8-ply database [4] (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (as well as 8×8 in late 2015) [3] (Feb 18, 2006). Solved for all boardsizes where width+height equals 16 on May 22, 2024. [5]
Free gomoku
Solved by Victor Allis (1993). The first player can force a win without opening rules. [1]
Ghost
Solved by Alan Frank using the Official Scrabble Players Dictionary in 1987. [6]
Hexapawn
3×3 variant solved as a win for black, several other larger variants also solved. [7]
Kalah
Most variants solved by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). The (6/6) variant was solved by Anders Carstensen (2011). Strong first-player advantage was proven in most cases. [8] [9]
L game
Easily solvable. Either player can force the game into a draw.
Maharajah and the Sepoys
This asymmetrical game is a win for the sepoys player with correct play.[ citation needed ]
Nim
Strongly solved. [10]
Nine men's morris
Solved by Ralph Gasser (1993). Either player can force the game into a draw. [11] [12]
Order and Chaos
Order (First player) wins. [13]
Ohvalhu
Weakly solved by humans, but proven by computers.[ citation needed ] (Dakon is, however, not identical to Ohvalhu, the game which actually had been observed by de Voogt)[ citation needed ]
Pangki
Strongly solved by Jason Doucette (2001). [14] The game is a draw. There are only two unique first moves if you discard mirrored positions. One forces the draw, and the other gives the opponent a forced win in 15 moves.
Pentago
Strongly solved by Geoffrey Irving with use of a supercomputer at NERSC. The first player wins.
Quarto
Solved by Luc Goossens (1998). Two perfect players will always draw. [15] [16] [17]
Renju-like game without opening rules involved
Claimed to be solved by János Wagner and István Virág (2001). [18] A first-player win.
Teeko
Solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw. [19]
Three men's morris
Trivially solvable. Either player can force the game into a draw.[ citation needed ]
Three musketeers
Strongly solved by Johannes Laire in 2009, and weakly solved by Ali Elabridi in 2017. [20] It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy). [21]
Tic-tac-toe
Trivially strongly solvable because of the small game tree. [22] The game is a draw if no mistakes are made, with no mistake possible on the opening move.
Wythoff's game
Strongly solved by W. A. Wythoff in 1907. [23]

Weak-solves

English draughts (checkers)
This 8×8 variant of draughts was weakly solved on April 29, 2007, by the team of Jonathan Schaeffer. From the standard starting position, both players can guarantee a draw with perfect play. [24] Checkers has a search space of 5×1020 possible game positions. [25] The number of calculations involved was 1014, which were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50. [26]
Fanorona
Weakly solved by Maarten Schadd. The game is a draw. [27]
Losing chess
Weakly solved in 2016 as a win for White beginning with 1. e3. [28]
Othello (Reversi)
Weakly solved in 2023 by Hiroki Takizawa, a researcher at Preferred Networks. [29] From the standard starting position on an 8×8 board, a perfect play by both players will result in a draw. Othello is the largest game solved to date, with a search space of 1028 possible game positions.
Pentominoes
Weakly solved by H. K. Orman. [30] It is a win for the first player.
Qubic
Weakly solved by Oren Patashnik (1980) and Victor Allis. The first player wins.
Sim
Weakly solved: win for the second player.[ citation needed ]
Lambs and tigers
Weakly solved by Yew Jin Lim (2007). The game is a draw. [31]
Pokémon Platinum
Weakly solved by YouTuber MartSnack (2024). He was able to produce a sequence of inputs that will always beat the game.

Partially solved games

Chess
Fully solving chess remains elusive, and it is speculated that the complexity of the game may preclude it ever being solved. Through retrograde computer analysis, endgame tablebases (strong solutions) have been found for all three- to seven-piece endgames, counting the two kings as pieces.
Some variants of chess on a smaller board with reduced numbers of pieces have been solved. Some other popular variants have also been solved; for example, a weak solution to Maharajah and the Sepoys is an easily memorable series of moves that guarantees victory to the "sepoys" player.
Go
The 5×5 board was weakly solved for all opening moves in 2002. [32] The 7×7 board was weakly solved in 2015. [33] Humans usually play on a 19×19 board, which is over 145 orders of magnitude more complex than 7×7. [34]
Hex
A strategy-stealing argument (as used by John Nash) shows that all square board sizes cannot be lost by the first player. Combined with a proof of the impossibility of a draw, this shows that the game is a first player win (so it is ultra-weak solved).[ citation needed ] On particular board sizes, more is known: it is strongly solved by several computers for board sizes up to 6×6.[ citation needed ] Weak solutions are known for board sizes 7×7 (using a swapping strategy), 8×8, and 9×9;[ citation needed ] in the 8×8 case, a weak solution is known for all opening moves. [35] Strongly solving Hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete.[ citation needed ] If Hex is played on an N×(N + 1) board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.[ citation needed ]
International draughts
All endgame positions with two through seven pieces were solved, as well as positions with 4×4 and 5×3 pieces where each side had one king or fewer, positions with five men versus four men, positions with five men versus three men and one king, and positions with four men and one king versus four men. The endgame positions were solved in 2007 by Ed Gilbert of the United States. Computer analysis showed that it was highly likely to end in a draw if both players played perfectly. [36] [ better source needed ]
m,n,k-game
It is trivial to show that the second player can never win; see strategy-stealing argument. Almost all cases have been solved weakly for k ≤ 4. Some results are known for k = 5. The games are drawn for k ≥ 8.[ citation needed ]

See also

Related Research Articles

<span class="mw-page-title-main">Hex (board game)</span> Abstract strategy board game

Hex is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash.

<span class="mw-page-title-main">Fanorona</span> Board game from Madagascar

Fanorona is a strategy board game for two players. The game is indigenous to Madagascar.

<span class="mw-page-title-main">Checkers</span> Strategy board game

Checkers, also known as draughts, is a group of strategy board games for two players which involve forward movements of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers is developed from alquerque. The term "checkers" derives from the checkered board which the game is played on, whereas "draughts" derives from the verb "to draw" or "to move".

<span class="mw-page-title-main">Computer chess</span> Computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training. Computer chess applications that play at the level of a chess grandmaster or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, Leela Chess Zero, GNU Chess, Fruit, and other free open source applications are available for various platforms.

Losing chess is one of the most popular chess variants. The objective of each player is to lose all of their pieces or be stalemated, that is, a misère version. In some variations, a player may also win by checkmating or by being checkmated.

<span class="mw-page-title-main">Evaluation function</span> Function in a computer game-playing program that evaluates a game position

An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position in a game tree. Most of the time, the value is either a real number or a quantized integer, often in nths of the value of a playing piece such as a stone in go or a pawn in chess, where n may be tenths, hundredths or other convenient fraction, but sometimes, the value is an array of three values in the unit interval, representing the win, draw, and loss percentages of the position.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

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 take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory 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.

<span class="mw-page-title-main">Connect Four</span> Childrens board game

Connect Four is a game in which the players choose a color and then take turns dropping colored tokens into a six-row, seven-column vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own tokens. It is therefore a type of m,n,k-game with restricted piece placement. Connect Four is a solved game. The first player can always win by playing the right moves.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.
<i>m</i>,<i>n</i>,<i>k</i>-game Abstract board game for two players

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-by-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-by-n board.

<span class="mw-page-title-main">Jonathan Schaeffer</span> Canadian researcher and professor

Jonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the former Canada Research Chair in Artificial Intelligence.

Maharajah and the Sepoys, originally called Shatranj Diwana Shah and also known as the Mad King's Game, Maharajah chess, or Sarvatobhadra "auspicious on all sides", is a popular chess variant with different armies for White and Black. It was first played in the 19th century in India. It is a solved game with a forced win for Black.

<span class="mw-page-title-main">English draughts</span> Board game

English draughts or checkers, also called straight checkers or simply draughts, is a form of the strategy board game checkers. It is played on an 8×8 checkerboard with 12 pieces per side. The pieces move and capture diagonally forward, until they reach the opposite end of the board, when they are crowned and can thereafter move and capture both backward and forward.

<span class="mw-page-title-main">Endgame tablebase</span> Database of precalculated chess analysis

In chess, the endgame tablebase, or simply tablebase, is a computerised database containing precalculated evaluations of endgame positions. Tablebases are used to analyse finished games, as well as by chess engines to evaluate positions during play. Tablebases are typically exhaustive, covering every legal arrangement of a specific selection of pieces on the board, with both White and Black to move. For each position, the tablebase records the ultimate result of the game and the number of moves required to achieve that result, both assuming perfect play. Because every legal move in a covered position results in another covered position, the tablebase acts as an oracle that always provides the optimal move.

<span class="mw-page-title-main">Anti-computer tactics</span> Human methods against game-playing computers

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer. Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn.

<span class="mw-page-title-main">Zillions of Games</span> General game playing software

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.

Computer shogi is a field of artificial intelligence concerned with the creation of computer programs which can play shogi. The research and development of shogi software has been carried out mainly by freelance programmers, university research groups and private companies. By 2017, the strongest programs were outperforming the strongest human players.

<span class="mw-page-title-main">First-player and second-player win</span>

In combinatorial 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.

Solving chess consists of finding an optimal strategy for the game of chess; that is, one by which one of the players can always force a victory, or either can force a draw. It is also related to more generally solving chess-like games such as Capablanca chess and infinite chess. In a weaker sense, solving chess may refer to proving which one of the three possible outcomes is the result of two perfect players, without necessarily revealing the optimal strategy itself.

<span class="mw-page-title-main">Outline of chess</span> Strategy board game

The following outline is provided as an overview of and topical guide to chess:

References

  1. 1 2 3 Allis, Louis Victor (1994-09-23). Searching for Solutions in Games and Artificial Intelligence (PhD thesis). Maastricht: Rijksuniversiteit Limburg. ISBN   90-9007488-0.
  2. ↑ H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games solved: Now and in the future , Artificial Intelligence 134 (2002) 277–311.
  3. 1 2 "John's Connect Four Playground". tromp.github.io.
  4. ↑ "UCI Machine Learning Repository: Connect-4 Data Set". archive.ics.uci.edu.
  5. ↑ "ChristopheSteininger/c4". github.com.
  6. ↑ Frank, Alan (1987-08-01). "Ghostbusters". Word Ways. 20 (4).
  7. ↑ Price, Robert. "Hexapawn". www.chessvariants.com.
  8. ↑ Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
  9. ↑ Solving (6,6)-Kalaha by Anders Carstensen.
  10. ↑ Bouton, C. L. (1901–1902), "Nim, a game with a complete mathematical theory", Annals of Mathematics , 3 (14): 35–39, doi:10.2307/1967631, JSTOR   1967631
  11. ↑ Gasser, Ralph (1996). "Solving Nine Men's Morris". In Nowakowski, Richard (ed.). Games of No Chance (PDF). Vol. 29. Cambridge: Cambridge University Press. pp. 101–113. ISBN   9780521574112. Archived from the original (PDF) on 2015-07-24. Retrieved 2022-01-03.
  12. ↑ Nine Men's Morris is a Draw by Ralph Gasser
  13. ↑ "solved: Order wins - Order and Chaos".
  14. ↑ Pangki is strongly solved as a draw by Jason Doucette
  15. ↑ "Quarto" (PDF). wouterkoolen.info. Retrieved 29 February 2024.
  16. ↑ "414298141056 Quarto Draws Suffice!".
  17. ↑ "Quarto". Archived from the original on 2004-10-12.
  18. ↑ Wágner, János & Virág, István (March 2001). "Solving Renju" (PDF). Széchenyi Egyetem - University of Győr. p. 30. Archived (PDF) from the original on 24 April 2024. Retrieved 24 April 2024.{{cite web}}: CS1 maint: date and year (link)
  19. ↑ Teeko, by E. Weisstein
  20. ↑ Elabridi, Ali. "Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory" (PDF).
  21. ↑ Three Musketeers, by J. Lemaire
  22. ↑ Tic-Tac-Toe, by R. Munroe
  23. ↑ Wythoff, W. A. (1907), "A modification of the game of nim", Nieuw Archief voor Wiskunde, 7 (2): 199–202
  24. ↑ Schaeffer, Jonathan (2007-07-19). "Checkers Is Solved". Science. 317 (5844): 1518–22. Bibcode:2007Sci...317.1518S. doi: 10.1126/science.1144079 . PMID   17641166. S2CID   10274228.
  25. ↑ "Project - Chinook - World Man-Machine Checkers Champion" . Retrieved 2007-07-19.
  26. ↑ Mullins, Justin (2007-07-19). "Checkers 'solved' after years of number crunching". NewScientist.com news service. Retrieved 2020-12-06.
  27. ↑ M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008). "Best Play in Fanorona leads to Draw" (PDF). New Mathematics and Natural Computation . 4 (3): 369–387. doi:10.1142/S1793005708001124. Archived from the original (PDF) on 2016-03-04. Retrieved 2015-04-08.
  28. ↑ Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF). Retrieved 17 January 2017.
  29. ↑ Takizawa, Hiroki (2023-10-30). "Othello is Solved". arXiv: 2310.19387 [cs.AI].
  30. ↑ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance , MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
  31. ↑ Yew Jin Lim. On Forward Pruning in Game-Tree Search Archived 2009-03-25 at the Wayback Machine . Ph.D. Thesis, National University of Singapore, 2007.
  32. ↑ 5×5 Go is solved by Erik van der Werf
  33. ↑ "首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客". blog.sina.com.cn. (which says the 7x7 solution is only weakly solved and it's still under research, 1. the correct komi is 9 (4.5 stone); 2. there are multiple optimal trees - the first 3 moves are unique - but within the first 7 moves there are 5 optimal trees; 3. There are many ways to play that don't affect the result)
  34. ↑ Counting legal positions in Go Archived 2007-09-30 at the Wayback Machine , Tromp and Farnebäck, accessed 2007-08-24.
  35. ↑ P. Henderson, B. Arneson, and R. Hayward, [webdocs.cs.ualberta.ca/~hayward/papers/solve8.pdf Solving 8×8 Hex ], Proc. IJCAI-09 505-510 (2009) Retrieved 29 June 2010.
  36. ↑ Some of the nine-piece endgame tablebase by Ed Gilbert

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.