# Solved game
A solved game is a game whose outcome under perfect play has been determined, in the strict sense of combinatorial game theory one of three graduated results: the game-theoretic value of the initial position is known (ultra-weakly solved), a strategy achieving that value from the opening is known (weakly solved), or a strategy is known for every legal position (strongly solved).[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) The term applies mainly to two-person, zero-sum games of perfect information such as tic-tac-toe, [Connect Four](https://www.edgepedia.org/connect-four), checkers, chess, and Go.[2](https://homepage.iis.sinica.edu.tw/~tshsu/tcg/2011/slides/slide5.pdf)
| Key fact | Detail |
|---|---|
| Ultra-weakly solved | The game-theoretic value of the initial position has been determined, with no strategy given.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) |
| Weakly solved | A strategy exists for achieving the game-theoretic value from the opening position, assuming reasonable computing resources.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) |
| Strongly solved | For all possible positions, a strategy is known for determining the game-theoretic value for both players.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) |
| Connect Four | First player wins; a knowledge-based solution was presented by Allis in 1988, and a strong solution by brute-force enumeration was published by Tromp in 1995.[3](https://www.mdpi.com/2073-8994/18/2/293) • [4](https://github.com/brianhliou/solved-games) |
| Checkers | Solved in 2007: perfect play by both sides leads to a draw, established by Jonathan Schaeffer's team after eighteen years of computation over roughly 5 × 1020 positions.[5](https://www.combinatorial-game-theory.com/essays/how-hard-is-it/) • [6](https://www.researchgate.net/publication/231216842_Checkers_Is_Solved) |
| Hex | Ultra-weakly solved for all board sizes by a strategy-stealing argument proving a first-player win, a proof that names no moves.[4](https://github.com/brianhliou/solved-games) • [1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) |
| Not solved | Chess (state-space complexity about 1050) and Go (about 10171) have superhuman programs but no solution.[7](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf) |
## The three levels of solving
The now-standard definitions were given by Luis Allis and are quoted in the checkers-solving literature.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) A game is ultra-weakly solved when only the value of the initial position, for example "first player wins" or "draw", has been determined. It is weakly solved when a strategy that achieves that value from the opening is also known. It is strongly solved when such a strategy is known for every legal position, so a player can find the optimal move from any state of the game.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf)
All definitions carry a qualification on resources. In a limited sense chess is already solved, because an alpha-beta search given infinite time would return the game-theoretic value; the resource constraints are what preclude calling it solved.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) The three claims are also independent in cost. A reader told that a game has been weakly but not strongly solved should not conclude that the weaker result was the cheaper one: on a game with transpositions the weak solution is the harder of the two, and the strong solution is what somebody would produce first if they could produce either.[8](https://www.combinatorial-game-theory.com/essays/what-solved-means/) The general pattern is that weak solutions are what large-scale computation produces, strong solutions are what small games permit, and ultra-weak solutions are what a mathematical argument occasionally hands over for free.[8](https://www.combinatorial-game-theory.com/essays/what-solved-means/)
**A fourth level.** Schaeffer and Lake added a further category, ultra-strongly solved: for all positions of a strongly solved game, a strategy is known that improves the chances of achieving more than the game-theoretic value against a fallible opponent. Knowing that a position is a draw means only that this is the best result against a perfect opponent; many opponents, particularly humans, are fallible, and selecting moves based on the probability of opponent error increases the expected outcome.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) A 2024 proposal adds a related intermediate notion, "semi-strongly solved", with an algorithm that was applied to semi-strongly solve 6 × 6 Othello.[9](https://arxiv.org/abs/2411.01029)
## What has been solved
**Small and moderate games.** [Tic-tac-toe](https://www.edgepedia.org/tic-tac-toe) is solved manually, with a state-space complexity of about 103 board configurations.[7](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf) Games that are strongly solved range from straightforward cases like tic-tac-toe to harder ones such as chess and endgames in checkers, where databases covering every possible position have been built.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) Connect Four, with about 1014 positions, was solved in 1988: Allis presented a formal, knowledge-based solution proving that the first player can always force a win under perfect play.[3](https://www.mdpi.com/2073-8994/18/2/293) • [7](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf) A strong solution by brute-force enumeration was published by [John Tromp](https://www.edgepedia.org/john-tromp) in 1995.[4](https://github.com/brianhliou/solved-games) Other solved games named in the early literature include Qubic, Nine Men's Morris, and Go-Moku.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) Six men's morris has been strongly solved more recently, a draw over all 42,372,745 positions, as a first published solution.[4](https://github.com/brianhliou/solved-games)
**Checkers.** In 2007 a team led by Jonathan Schaeffer, a computer scientist at the [University of Alberta](https://www.edgepedia.org/university-of-alberta) known for the Chinook checkers program, announced in *Science* (volume 317, pages 1518–1522) that checkers is solved: perfect play by both sides leads to a draw.[6](https://www.researchgate.net/publication/231216842_Checkers_Is_Solved) The proof required eighteen years of computation across a search space of 5 × 1020 positions, and the paper described checkers as the hardest popular game solved so far, about a million times more complex than Connect Four.[5](https://www.combinatorial-game-theory.com/essays/how-hard-is-it/) • [6](https://www.researchgate.net/publication/231216842_Checkers_Is_Solved) The result covers 8 × 8 American checkers ([English draughts](https://www.edgepedia.org/english-draughts)); other checkers variants are a different story.[10](https://checkersonline.io/blog/is-checkers-solved/)
**Ultra-weak results without strategies.** Hex is known to be a win for the first player on all diamond-shaped boards, but no one knows a strategy for achieving this result; the proof is a strategy-stealing argument that names no moves.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) • [4](https://github.com/brianhliou/solved-games) This illustrates why ultra-weak solutions are described as of theoretical interest but meaning little in practice.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf)
## What is not solved
Chess and Go remain unsolved despite programs that play better than any human.[7](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf) Their state-space complexities, roughly 1050 for chess and 10171 for Go, put complete solutions far out of reach; a chess lookup table covering every position would be completely impractical, larger than the number of atoms in the observable universe.[11](https://boardgames.stackexchange.com/questions/5819/chess-and-variations-endgame-complexity) • [7](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf) Complexity-theory results reinforce the gap: for an arbitrary Go position on an n × n board, deciding whether Black can force a win is exponential-time complete, and related board-game hardness proofs typically reduce from generalized geography, which is PSPACE-complete.[12](https://staff.itee.uq.edu.au/janetw/Computer%20Go/CS-TR-339.html) • [5](https://www.combinatorial-game-theory.com/essays/how-hard-is-it/)
## What makes a game solvable
Allis, van den Herik, and Herschberg argued that difficulty has two dimensions: space complexity, the number of positions in the search space, and decision complexity, the difficulty of making correct decisions.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) A large search space alone does not make a game hard to solve. A trivial variant of Go on a 19 × 19 board, in which the first player to place 181 stones wins, has a search complexity of about 10170 yet is trivial to solve, because the decision complexity is negligible.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) • [12](https://staff.itee.uq.edu.au/janetw/Computer%20Go/CS-TR-339.html)
The games solved so far fit the two-dimensional account. They have either low decision complexity, such as Qubic with 1030 positions and Go-Moku with 10105, or low space complexity, such as Nine Men's Morris with 1011 positions, or both, as with Connect Four at 1014.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf) Checkers was rated as having high decision complexity, on par with backgammon and 10 × 10 draughts and less complex than chess, together with moderate space complexity.[1](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf)
## Solving in practice
Most weak and strong solutions are produced by brute-force enumeration over all possible positions, working backward from terminal positions and propagating results, the method behind checkers proofs, chess endgame tablebases, and complete solutions of small games.[4](https://github.com/brianhliou/solved-games) Ultra-weak solutions, by contrast, usually come from mathematical proof.[8](https://www.combinatorial-game-theory.com/essays/what-solved-means/) The distinction matters to players as well as researchers: a solved status is a specific technical claim, and games such as chess and Go are not solved even though superhuman engines exist for both.[13](https://www.dotclash.com/zh-Hans/blog/is-dots-and-boxes-solved-small-boards)
## References
1. [Jonathan Schaeffer and Robert Lake. Solving the Game of Checkers.](https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/solving.pdf)
2. [Games solved: Now and in the future (slides)](https://homepage.iis.sinica.edu.tw/~tshsu/tcg/2011/slides/slide5.pdf)
3. [Connect-4 AI: A Comprehensive Taxonomy and Critical Review of Methods and Metrics, MDPI Symmetry](https://www.mdpi.com/2073-8994/18/2/293)
4. [brianhliou/solved-games: A structured record of solved games, GitHub](https://github.com/brianhliou/solved-games)
5. [How hard is it, Combinatorial Game Theory](https://www.combinatorial-game-theory.com/essays/how-hard-is-it/)
6. [Checkers Is Solved, Science 317(5844):1518-1522, ResearchGate](https://www.researchgate.net/publication/231216842_Checkers_Is_Solved)
7. [Game playing, MIT 6.034 course notes](https://classes.csail.mit.edu/6.034s/handouts/spring12/games.pdf)
8. [Three different claims are all called solved, Combinatorial Game Theory](https://www.combinatorial-game-theory.com/essays/what-solved-means/)
9. [Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay, arXiv:2411.01029](https://arxiv.org/abs/2411.01029)
10. [Is Checkers Solved? Yes, and Here Is What That Means, Checkers Online Blog](https://checkersonline.io/blog/is-checkers-solved/)
11. [Chess (and variations) Endgame Complexity, Board & Card Games Stack Exchange](https://boardgames.stackexchange.com/questions/5819/chess-and-variations-endgame-complexity)
12. [Jay Burmeister and Janet Wiles. CS-TR-339 Computer Go Tech Report, University of Queensland](https://staff.itee.uq.edu.au/janetw/Computer%20Go/CS-TR-339.html)
13. [Is Dots and Boxes a Solved Game? What We Actually Know, Dot Clash](https://www.dotclash.com/zh-Hans/blog/is-dots-and-boxes-solved-small-boards)
---
*Topic: Encyclopedia › Sports, games, and recreation › Board, card, and puzzle games › Board games*
*Initially written Sep 17, 2026 · Reviewed: Oct 21, 2026 · Edited: Oct 15, 2026; Oct 21, 2026 · Last review: Oct 21, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license