Editing Solved game

{{Short description|Game whose outcome can be correctly predicted}}
A '''solved game''' is a [[game]] whose outcome (win, lose or [[tie (draw)|draw]]) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to [[abstract strategy game]]s, and especially to games with full information and no element of chance; solving such a game may use [[combinatorial game theory]] or computer assistance.

==Overview==
A [[two-player game]] can be solved on several levels:<ref name="Allis">{{Cite thesis |last=Allis |first=Louis Victor |title=Searching for Solutions in Games and Artificial Intelligence |date=1994-09-23 |degree=PhD |publisher=Rijksuniversiteit Limburg |isbn=90-9007488-0 |place=Maastricht}}</ref><ref>[[H. Jaap van den Herik]], Jos W.H.M. Uiterwijk, Jack van Rijswijck, ''[https://web.archive.org/web/20170912011410/https://pdfs.semanticscholar.org/8296/bc0ab855841088b31190c9f2923951853d7b.pdf Games solved: Now and in the future]'', ''Artificial Intelligence'' 134 (2002) 277–311.</ref>

===Ultra-weak solution===
: Prove whether the first player will win, lose or draw from the initial position, given perfect play on both sides {{See below|{{slink||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 one algorithm for each of the two players, such that the player using it can achieve at least the optimal outcome, regardless of the opponent's moves, from the start of the game, using reasonable computational resources.

===Strong solution===
: Provide an algorithm that uses reasonable computational resources and finds optimal plays for both players from all legal positions.

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|date=December 2014}}

By contrast, "strong" proofs often proceed by [[Brute force method|brute force]]—[[Computer-assisted proof|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 (board game)|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.<ref name="Allis"/> Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By [[backward chaining|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 value|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 [[Chess endgame|endgame]] positions (in the form of [[endgame tablebase]]s), which will allow it to play perfectly after some point in the game. [[Computer chess]] programs are well known for doing this.

==Solved games==
; [[Oware|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 (hand game)|Chopsticks]]
: Strongly solved. If two players both play perfectly, the game will go on indefinitely.{{cn|date=July 2018}}
; [[Connect Four]]
: [[File:Connect Four.jpg|thumb|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.<ref name="autogenerated1">{{cite web|url=https://tromp.github.io/c4/c4.html|title=John's Connect Four Playground|website=tromp.github.io}}</ref> The first player can force a win. Strongly solved by John Tromp's 8-ply database<ref>{{cite web |url=https://archive.ics.uci.edu/ml/datasets/Connect-4 |title=UCI Machine Learning Repository: Connect-4 Data Set |website=archive.ics.uci.edu}}</ref> (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (as well as 8×8 in late 2015)<ref name="autogenerated1" /> (Feb 18, 2006). Solved for all boardsizes where width+height equals 16 on May 22, 2024.<ref>{{cite web|url=https://github.com/ChristopheSteininger/c4|title=ChristopheSteininger/c4|website=github.com}}</ref>
; Free [[gomoku]]
: Solved by [[Victor Allis]] (1993). The first player can force a win without opening rules.<ref name="Allis" />
; [[Ghost (game)|Ghost]]
: Solved by Alan Frank using the ''[[Official Scrabble Players Dictionary]]'' in 1987.<ref>{{Cite journal |last=Frank |first=Alan |date=1987-08-01 |title=Ghostbusters |url=https://digitalcommons.butler.edu/wordways/vol20/iss4/4 |journal=Word Ways |volume=20 |issue=4}}</ref>
; [[Hexapawn]]
:3×3 variant solved as a win for black, several other larger variants also solved.<ref>{{cite web|url=http://www.chessvariants.com/small.dir/hexapawn.html|title=Hexapawn|first=Robert|last=Price|website=www.chessvariants.com}}</ref>
; [[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.<ref>[http://graphics.stanford.edu/~irving/papers/irving2000_kalah.pdf Solving Kalah] by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.</ref><ref>[http://kalaha.krus.dk/ Solving (6,6)-Kalaha] by Anders Carstensen.</ref>
; [[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.{{Cn|date=November 2022}}
; [[Nim]]
: Strongly solved.<ref>{{citation | last = Bouton | first = C. L. | author-link = Charles L. Bouton | doi = 10.2307/1967631 | issue = 14 | journal = [[Annals of Mathematics]] | pages = 35–39 | title = Nim, ''a game with a complete mathematical theory'' | volume = 3 | year = 1901–1902| jstor = 1967631 }}</ref>
; [[Nine men's morris]]
: Solved by Ralph Gasser (1993). Either player can force the game into a draw.<ref>{{Cite book|last=Gasser|first=Ralph|url=http://library.msri.org/books/Book29/files/gasser.pdf|title=Games of No Chance|publisher=Cambridge University Press|year=1996|isbn=9780521574112|editor-last=Nowakowski|editor-first=Richard|volume=29|location=Cambridge|pages=101–113|language=en|chapter=Solving Nine Men’s Morris|access-date=2022-01-03|archive-date=2015-07-24|archive-url=https://web.archive.org/web/20150724080747/http://library.msri.org/books/Book29/files/gasser.pdf|url-status=dead}}</ref><ref>[http://www.ics.uci.edu/~eppstein/cgt/morris.html Nine Men's Morris is a Draw] by Ralph Gasser</ref>
; [[Order and Chaos]]
: Order (First player) wins.<ref>{{cite web|url=https://boardgamegeek.com/thread/1579397/solved-order-wins|title=solved: Order wins - Order and Chaos}}</ref>
; [[Congkak|Ohvalhu]]
: Weakly solved by humans, but proven by computers.{{Cn|date=November 2022}} (Dakon is, however, not identical to Ohvalhu, the game which actually had been observed by de Voogt){{Cn|date=November 2022}}
;[[Cinc camins#Variants|Pangki]]
:Strongly solved by Jason Doucette (2001).<ref>[http://www.jasondoucette.com/ai.html#Pangki Pangki is strongly solved as a draw] by Jason Doucette</ref>  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 (board game)|Quarto]]
: Solved by Luc Goossens (1998). Two perfect players will always draw.<ref>{{cite web|title=Quarto|website=wouterkoolen.info|access-date=29 February 2024|url=https://wouterkoolen.info/Talks/quarto.pdf}}</ref><ref>{{cite web | url=https://www.mathpages.com/home/kmath352.htm | title=414298141056 Quarto Draws Suffice! }}</ref><ref>{{cite web | url=http://ssel.vub.ac.be/Members/LucGoossens/quarto/quartotext.htm | archive-url=https://web.archive.org/web/20041012023358/http://ssel.vub.ac.be/Members/LucGoossens/quarto/quartotext.htm | archive-date=2004-10-12 | title=Quarto }}</ref>
; [[Renju]]-like game without opening rules involved
: Claimed to be solved by János Wagner and István Virág (2001).<ref>{{Cite web |last=Wágner |first=János |last2=Virág |first2=István |name-list-style=amp |date=March 2001 |title=Solving Renju |url=http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf |url-status=live |archive-url=https://web.archive.org/web/20240424130418/http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf |archive-date=24 April 2024 |archive-format=PDF |access-date=24 April 2024 |website=Széchenyi Egyetem - University of Győr |page=30 |language=en |format=PDF}}</ref> A first-player win.
; [[Teeko]]
: Solved by [[Guy L. Steele, Jr.|Guy Steele]] (1998). Depending on the variant either a first-player win or a draw.<ref>[http://mathworld.wolfram.com/Teeko.html Teeko], by E. Weisstein</ref>
; [[Three men's morris]]
: Trivially solvable. Either player can force the game into a draw.{{Cn|date=November 2022}}
; [[Three musketeers (game)|Three musketeers]]
: Strongly solved by Johannes Laire in 2009, and weakly solved by Ali Elabridi in 2017.<ref>{{Cite web|url=http://www.aui.ma/sse-capstone-repository/pdf/fall2017/WEAKLY%20SOLVING%20THE%20THREE%20MUSKETEERS%20GAME%20USING%20ARTIFICIAL%20INTELLIGENCE%20AND%20GAME%20THEORY%20Ali%20Elabridi.pdf|title=Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory |last=Elabridi|first=Ali}}</ref> It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy).<ref>[https://github.com/jlaire/3M/tree/master/src Three Musketeers], by J. Lemaire</ref>
; [[Tic-tac-toe]]
: Extremely trivially strongly solvable because of the small game tree.<ref>[https://xkcd.com/832/ Tic-Tac-Toe], by R. Munroe</ref>  The game is a draw if no mistakes are made, with no mistake possible on the opening move.
; [[Wythoff's game]]
: Strongly solved by [[Willem Abraham Wythoff| W. A. Wythoff]] in 1907.<ref>{{citation | last = Wythoff | first = W. A. | author-link = Willem Abraham Wythoff | issue = 2 | journal = Nieuw Archief voor Wiskunde | pages = 199–202 | title = A modification of the game of nim | url = https://archive.org/details/nieuwarchiefvoo02genogoog/page/n219/mode/2up | volume = 7 | year = 1907}}</ref>

==Weak-solves==
; [[English draughts]] (checkers){{Anchor|DraughtsEnglish}}
: 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.<ref>{{cite journal | title=Checkers Is Solved | date=2007-07-19 | journal=Science | first=Jonathan | last=Schaeffer| volume=317 | issue=5844 | pages=1518–22 | doi=10.1126/science.1144079 | pmid=17641166 | bibcode=2007Sci...317.1518S | s2cid=10274228 | doi-access=free }}</ref> Checkers has a search space of 5×10<sup>20</sup> possible game positions.<ref>{{cite web | url=http://www.cs.ualberta.ca/~chinook/project/ | title=Project - Chinook - World Man-Machine Checkers Champion | access-date=2007-07-19}}</ref> The number of calculations involved was 10<sup>14</sup>, which were done over a period of 18 years. The process involved from 200 [[desktop computer]]s at its peak down to around 50.<ref>{{cite web | url=https://www.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching/ | title=Checkers 'solved' after years of number crunching | date=2007-07-19 | access-date=2020-12-06 | publisher=NewScientist.com news service | first=Justin | last=Mullins}}</ref>

; [[Fanorona]]
: Weakly solved by Maarten Schadd. The game is a draw.<ref name="Schadd2008">{{cite journal |author1=M.P.D. Schadd |author2=M.H.M. Winands |author3=J.W.H.M. Uiterwijk |author4=H.J. van den Herik |author5=M.H.J. Bergsma |year=2008 |title=Best Play in Fanorona leads to Draw |journal=[[New Mathematics and Natural Computation]] |volume=4 |issue=3 |pages=369–387 |url=http://schadd.com/Papers/2008FanoronaJNMNC.pdf |doi=10.1142/S1793005708001124 |access-date=2015-04-08 |archive-url=https://web.archive.org/web/20160304003200/http://schadd.com/Papers/2008FanoronaJNMNC.pdf |archive-date=2016-03-04 |url-status=dead }}</ref>

; [[Losing chess]]
: Weakly solved in 2016 as a win for White beginning with 1.&nbsp;e3.<ref name=losingchess>{{cite web |last1=Watkins |first1=Mark |title=Losing Chess: 1. e3 wins for White|url=http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/ICGA2016.pdf |access-date=17 January 2017}}</ref>

;[[Reversi|Othello]] (Reversi)
:Weakly solved in 2023 by Hiroki Takizawa, a researcher at [[Preferred Networks]].<ref>{{cite arXiv | title=Othello is Solved | date=2023-10-30 | first=Hiroki | last=Takizawa | class=cs.AI | eprint=2310.19387
 }}</ref> 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 10<sup>28</sup> possible game positions. 

; [[Pentomino]]es
: Weakly solved by H. K. Orman.<ref name=":0">Hilarie K. Orman: ''Pentominoes: A First Player Win'' in ''[http://www.msri.org/publications/books/Book29/contents.html Games of no chance]'', MSRI Publications &ndash; Volume 29, 1996, pages 339-344. Online: [http://www.msri.org/publications/books/Book29/files/orman.pdf pdf].</ref> It is a win for the first player.

; [[3D_tic-tac-toe#%22Qubic%22|Qubic]]
: Weakly solved by [[Oren Patashnik]] (1980) and [[Victor Allis]]. The first player wins.

; [[Sim (pencil game)|Sim]]
: Weakly solved: win for the second player.{{Cn|date=November 2022}}

;[[Lambs and tigers]]
:Weakly solved by Yew Jin Lim (2007). The game is a draw.<ref name=":1">Yew Jin Lim. [http://www.yewjin.com/papers/PhDThesisLimYewJin.pdf On Forward Pruning in Game-Tree Search] {{Webarchive|url=https://web.archive.org/web/20090325093223/http://www.yewjin.com/papers/PhDThesisLimYewJin.pdf |date=2009-03-25 }}. Ph.D. Thesis, [[National University of Singapore]], 2007.</ref>

==Partially solved games==

; [[Chess]]
:{{main|Solving chess}}
: Fully solving chess remains elusive, and it is speculated that the complexity of the game may preclude it ever being solved. Through [[retrograde analysis|retrograde computer analysis]] and [[endgame tablebase]]s, strong solutions have been found for all three- to seven-piece [[Chess endgame|endgames]], counting the two [[King (chess)|kings]] as pieces.
: Some [[Minichess|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 (game)|Go]]
: The 5×5 board was weakly solved for all opening moves in 2002.<ref name=":3">[http://erikvanderwerf.tengen.nl/5x5/5x5solved.html 5×5 Go is solved] by Erik van der Werf</ref> The 7×7 board was weakly solved in 2015.<ref name=":4">{{cite web|url=http://blog.sina.com.cn/s/blog_53a2e03d0102vyt5.html|title=首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客|website=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)</ref> Humans usually play on a 19×19 board, which is over 145 [[Order of magnitude|orders of magnitude]] more complex than 7×7.<ref name=":2">[http://homepages.cwi.nl/~tromp/go/legal.html Counting legal positions in Go] {{webarchive|url=https://web.archive.org/web/20070930044508/http://homepages.cwi.nl/~tromp/go/legal.html |date=2007-09-30 }}, Tromp and Farnebäck, accessed 2007-08-24.</ref>
; [[Hex (board game)|Hex]]
: A [[strategy-stealing argument]] (as used by [[John Forbes Nash, Jr.|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).{{cn|date=September 2022}}  On particular board sizes, more is known: it is strongly solved by several computers for board sizes up to 6×6.{{cn|date=September 2022}}  Weak solutions are known for board sizes 7×7 (using a [[pie rule|swapping strategy]]), 8×8, and 9×9;{{cn|date=September 2022}} in the 8×8 case, a weak solution is known for all opening moves.<ref>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.</ref>  Strongly solving Hex on an ''N''×''N'' board is unlikely as the problem has been shown to be [[PSPACE-complete]].{{cn|date=September 2022}} 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.{{cn|date=September 2022}}

; [[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.<ref>[http://edgilbert.org/Checkers/KingsRow.htm Some of the nine-piece endgame tablebase] by Ed Gilbert</ref>{{better source|date=December 2019}}
:
; [[Morabaraba]]
: Strongly solved by Gábor E. Gévay (2015). The first player wins in optimal play.<ref>{{Cite journal |last=Gevay |first=Gabor E. |last2=Danner |first2=Gabor |date=September 2016 |title=Calculating Ultrastrong and Extended Solutions for Nine Men’s Morris, Morabaraba, and Lasker Morris |url=https://ieeexplore.ieee.org/document/7080922/ |journal=IEEE Transactions on Computational Intelligence and AI in Games |volume=8 |issue=3 |pages=256–267 |doi=10.1109/TCIAIG.2015.2420191 |issn=1943-068X}}</ref> 
:
; [[m,n,k-game|''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.{{Cn|date=November 2022}}

==See also==
*[[Computer chess]]
*[[Computer Go]]
*[[Computer Othello]]
*[[Game complexity]]
*[[God's algorithm]]
*[[Zermelo's theorem (game theory)]]

==References==
{{reflist|30em}}

==Further reading==
<!--TODO: Move it to proper place and remove 'Further readings' section -->
* Allis, ''Beating the World Champion? The state-of-the-art in computer game playing.'' in New Approaches to Board Games Research.

==External links==
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles] by David Eppstein.
* [http://gamescrafters.berkeley.edu/ GamesCrafters] solving two-person games with perfect information and no chance

{{Game theory}}
{{DEFAULTSORT:Solved Game}}
[[Category:Mathematical games]]
[[Category:Abstract strategy games]]
[[Category:Combinatorial game theory]]
[[Category:Solved games| ]]