A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be "unsolved". Games for which only some positions have been solved are said to be "partially solved". This article focuses on two-player games that have been solved.
- Proving whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This proof can be non-constructive (possibly involving a strategy-stealing argument) that need not determine any moves of the perfect play.
- Providing an algorithm that secures a win for one player or a draw for either against any possible moves by the opponent from the beginning of the game by producing at least one complete ideal game (all moves start to end) with proof that each move is optimal for the player making it. It need not enable a computer program using the solution to optimally play against an imperfect opponent. For example, the checkers program Chinook will never turn a drawn position into a losing position (the weak solution of checkers proves that it is a draw) but it might turn a winning position into a drawn position because Chinook expects the opponent not to play a move that will not win but could lose, and it therefore incompletely analyzes these moves.
- The strongest sense of solution requires an algorithm which can produce perfect play (moves) from any position, i.e. even if mistakes have already been made on one or both sides.
A minimax algorithm can exhaustively traverse the game tree of any two-person game that has finitely many positions. For many non-trivial games this algorithm would require too much time to generate a move in a given position; a game therefore is not considered to be weakly or strongly solved unless existing hardware can reasonably quickly run the algorithm. Many algorithms rely on a huge database and are effectively nothing more.
For example of a strong solution consider the game of tic-tac-toe, which is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim also admit a rigorous analysis using combinatorial game theory.
Even a strongly solved game can remain 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.
In game theory, perfect play is the behavior or strategy of a player that causes the best possible outcome for that player regardless of the response by the opponent. 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 that of 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 equally evaluated positions. 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.
- 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.
- Connect Four
- Solved first by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988). 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 (Feb 18, 2006).
- Draughts, English (i.e. checkers)
- This 8×8 variant of draughts was weakly solved on April 29, 2007 by the team of Jonathan Schaeffer, known for Chinook, the "World Man-Machine Checkers Champion". From the standard starting position, both players can guarantee a draw with perfect play. Checkers is the largest game that has been solved to date, with a search space of 5×1020. The number of calculations involved was 1014, and those were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.
- Weakly solved by Maarten Schadd. The game is a draw.
- A strategy-stealing argument (as used by John Nash) will show 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 ultra-weak solved as a first player win.
- Strongly solved by several computers for board sizes up to 6×6.
- Jing Yang has demonstrated a winning strategy (weak solution) for board sizes 7×7, 8×8 and 9×9.
- A winning strategy for Hex with swapping is known for the 7×7 board.
- 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.
- A weak solution is known for all opening moves on the 8×8 board.
- 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.
- Strongly solved.
- 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)
- Weakly solved by H. K. Orman. It is a win for the first player.
- 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.
- Weakly solved: win for the second player.
- 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. It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy).
- Trivially solvable. Either player can force the game into a draw.
Partially solved games
- Solved by retrograde computer analysis for all three- to six-piece, and some seven-piece endgames, counting the two kings as pieces. It is solved for all 3–3 and 4–2 endgames with and without pawns, where 5–1 endgames are assumed to be won with some trivial exceptions (see endgame tablebase for an explanation). The full game has 32 pieces. Chess on a 3×3 board is strongly solved by Kirill Kryukov (2004). It has been speculated that solving chess may be impossible with current technology.
- International Draughts
- All positions with two through seven pieces were solved. Positions with 4×4 and 5×3 pieces where each side had one king or less. Positions with five men versus four men, five men versus three men and one king, and four men and one king versus four men. Solved in 2007 by Ed Gilbert of the United States, computer analysis show that highly likely it always end in a draw if both players play perfectly.
- The 5×5 board is weakly solved for all opening moves. Humans usually play on a 19×19 board which is over 145 orders of magnitude more complex than 7×7.
- Reversi (Othello)
- Weakly solved on a 4×4 and 6×6 board as a second player win in July 1993 by Joel Feinstein. On an 8×8 board (the standard one) it is mathematically unsolved, though computer analysis shows a likely draw. No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist.
- 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.
- V. Allis, Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Department of Computer Science, University of Limburg, 1994. Online: pdf
- 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.
- "How to Always Win Chopsticks". wikiHow. Retrieved 28 April 2013.
- John's Connect Four Playground
- Schaeffer, Jonathan (2007-07-19). "Checkers Is Solved". Science. Retrieved 2007-07-20.
- "Project - Chinook - World Man-Machine Checkers Champion". Retrieved 2007-07-19.
- Mullins, Justin (2007-07-19). "Checkers 'solved' after years of number crunching". NewScientist.com news service. Retrieved 2007-07-20.
- 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.
- Solving Kalah by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
- Solving (6,6)-Kalaha by Anders Carstensen.
- Nine Men's Morris is a Draw by Ralph Gasser
- Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
- Teeko, by E. Weisstein
- Three Musketeers, by J. Lemaire
- Yew Jin Lim. On Forward Pruning in Game-Tree Search. Ph.D. Thesis, National University of Singapore, 2007.
- 3×3 Chess by Kirill Kryukov.
- See Solving chess
- Some of the nine-piece endgame tablebase by Ed Gilbert
- 5×5 Go is solved by Erik van der Werf
- Counting legal positions in Go, Tromp and Farnebäck, accessed 2007-08-24.
- 6×6 Othello weakly solved
- Allis, Beating the World Champion? The state-of-the-art in computer game playing. in New Approaches to Board Games Research.