Solved game
Solved game
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 or computer assistance.
Overview A two-player-game can be solved on several levels:
Ultra-weak solution : Prove whether the first player will win, lose or draw from the initial position, given perfect play on both sides . 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.
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. The first player can force a win. Strongly solved by John Tromp's 8-ply database (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (as well as 8×8 in late 2015) In 2025, the classic 7x6 board was strongly solved in terms of a win-draw-loss look-up table. ; Free gomoku : Solved by Victor Allis (1993). The first player can force a win without opening rules. ; hexapawn :3×3 variant solved as a win for black, several other larger variants also solved. ; 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. ; 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. ; nim : Strongly solved. ; nine-men's-morris : Solved by Ralph Gasser (1993). Either player can force the game into a draw. ; order-and-chaos : Order (First player) wins. ; Ohvalhu : Weakly solved by humans, but proven by computers. (Dakon is, however, not identical to Ohvalhu, the game which actually had been observed by de Voogt) ;Pangki :Strongly solved by Jason Doucette (2001). 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. ; renju-like game without opening rules involved : Claimed to be solved by János Wagner and István Virág (2001). A first-player win. ; teeko : Solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw. ; three-men's-morris : Trivially solvable. Either player can force the game into a draw. ; Three musketeers : Strongly solved by Johannes Laire in 2009, and weakly solved by Ali Elabridi in 2017. It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy). ; tic-tac-toe : Extremely trivially strongly solvable because of the small game tree. 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.
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. Checkers has a search space of 5×1020 possible game positions. 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.
; fanorona : Weakly solved by Maarten Schadd. The game is a draw.
; losing-chess : Weakly solved in 2016 as a win for White beginning with 1. e3.
;Othello (Reversi) :Weakly solved in 2023 by Hiroki Takizawa, a researcher at Preferred Networks. However, the paper's conclusions are contested. 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. 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.
;Lambs and tigers :Weakly solved by Yew Jin Lim (2007). The game is a draw.
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 and 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. The 7×7 board was weakly solved in 2015. Humans usually play on a 19×19 board, which is over 145 orders of magnitude more complex than 7×7. ; 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). On particular board sizes, more is known: it is strongly solved by several computers for board sizes up to 6×6. Weak solutions are known for board sizes 7×7 (using a swapping strategy), 8×8, and 9×9; in the 8×8 case, a weak solution is known for all opening moves. Strongly solving Hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete. 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.
; 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. : ; Morabaraba : Strongly solved by Gábor E. Gévay (2015). The first player wins in optimal play. : ; *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.