A solved game is a
game
A game is a structured type of play usually undertaken for entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator sports or video games) or art ...
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 game
An abstract strategy game is a type of strategy game that has minimal or no narrative theme, an outcome determined only by player choice (with minimal or no randomness), and in which each player has perfect information about the game. For example ...
s, and especially to games with full information and no element of chance; solving such a game may use
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
or computer assistance.
Overview
A
two-player game
A two-player game is a multiplayer game that is played by precisely two players. This is distinct from a solitaire game, which is played by only one player.
Examples
The following are some examples of two-player games. This list is not intended ...
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
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existe ...
(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
In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe.
A game tree can be us ...
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
Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
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
Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
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
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
.
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
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
, 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.
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
Perfect information is a concept in game theory and economics that describes a situation where all players in a game or all participants in a market have knowledge of all relevant information in the system. This is different than complete informat ...
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
Rock, Paper, Scissors (also known by #Names, several other names and word orders) is an Intransitive game, intransitive hand game, usually played between two people, in which each player simultaneously forms one of three shapes with an outstret ...
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 tablebase
In chess, the endgame tablebase, or simply the tablebase, is a computerised database containing precalculated evaluations of chess endgame, endgame positions. Tablebases are used to analyse finished games, as well as by chess engines to evaluate ...
s), which will allow it to play perfectly after some point in the game.
Computer chess
Computer chess includes both hardware (dedicated computers) 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 analysi ...
programs are well known for doing this.
Solved games
;
Awari (a game of the
Mancala
Mancala ( ''manqalah'') is a family of two-player Turns, rounds and time-keeping systems in games, turn-based Strategy game, strategy board games played with small stones, beans, marbles or seeds and rows of holes or pits in the earth, a board ...
family)
: The variant of
Oware
Oware is an abstract strategy game among the mancala family of board games (pit and pebble games) played worldwide with slight variations as to the layout of the game, number of players and strategy of play. Its origin is uncertain but it is wide ...
allowing game ending "grand slams" was strongly solved by
Henri Bal
Henri Elle Bal (born 16 April 1958) is a professor of computer science at the Vrije Universiteit, Amsterdam in the Netherlands. He is a well-known researcher in computer systems with a specialization in parallel computer systems, languages, and ap ...
and John Romein at the
Vrije Universiteit
The (abbreviated as ''VU Amsterdam'' or simply ''VU'' when in context) is a public research university in Amsterdam, Netherlands, founded in 1880. The VU Amsterdam is one of two large, publicly funded research universities in the city, the othe ...
in
Amsterdam
Amsterdam ( , ; ; ) is the capital of the Netherlands, capital and Municipalities of the Netherlands, largest city of the Kingdom of the Netherlands. It has a population of 933,680 in June 2024 within the city proper, 1,457,018 in the City Re ...
, 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.
;
Connect Four
Connect Four (also known as Connect 4, Four Up, Plot Four, Find Four, Captain's Mistress, Four in a Row, Drop Four, and in the Soviet Union, Gravitrips) is a game in which the players choose a color and then take turns dropping colored tokens int ...
:

Solved first by James D. Allen on October 1, 1988, and independently by
Victor Allis
Louis Victor Allis (born 19 May 1965) is a Dutch computer scientist and co-founder of the election information technology firm Activote. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introd ...
on October 16, 1988.
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)
(Feb 18, 2006). Solved for all boardsizes where width+height equals 16 on May 22, 2024.
; Free
gomoku
''Gomoku'', also called ''five in a row'', is an Abstract strategy game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...
: Solved by
Victor Allis
Louis Victor Allis (born 19 May 1965) is a Dutch computer scientist and co-founder of the election information technology firm Activote. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introd ...
(1993). The first player can force a win without opening rules.
;
Ghost
In folklore, a ghost is the soul or Spirit (supernatural entity), spirit of a dead Human, person or non-human animal that is believed by some people to be able to appear to the living. In ghostlore, descriptions of ghosts vary widely, from a ...
: Solved by Alan Frank using the ''
Official Scrabble Players Dictionary'' in 1987.
;
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
Nine men's morris is a strategy board game for two players, dating back to at least the Roman Empire. The game is also known as nine-man morris, mill, mills, the mill game, merels, merrills, merelles, marelles, morelles, and ninepenny marl in Eng ...
: 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
Quarto (abbreviated Qto, 4to or 4º) is the format of a book or pamphlet produced from full sheets printed with eight pages of text, four to a side, then folded twice to produce four leaves. The leaves are then trimmed along the folds to produc ...
: Solved by Luc Goossens (1998). Two perfect players will always draw.
;
Renju
''Renju'' () is a professional variant of the abstract strategy board game gomoku. It was named renju by Japanese journalist Ruikou Kuroiwa (黒岩涙香) on December 6, 1899, in a Japanese newspaper ''Yorozu chouhou'' (萬朝報). The name "r ...
-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
Teeko is an abstract strategy game invented by John Scarne in 1937 and rereleased in refined form in 1952 and again in the 1960s. Teeko was marketed by Scarne's company, John Scarne Games Inc.; its quirky name, he said, borrowed letters from the g ...
: Solved by
Guy Steele
Guy Lewis Steele Jr. (; born October 2, 1954) is an American computer scientist who has played an important role in designing and documenting several computer programming languages and technical standards.
Biography
Steele was born in Missouri ...
(1998). Depending on the variant either a first-player win or a draw.
;
Three men's morris
Three men's morris is an abstract strategy game played on a three by three board (counting lines)
that is similar to tic-tac-toe. It is also related to six men's morris and nine men's morris. A player wins by forming a mill, that is, three of the ...
: 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
Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
: 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
Draughts (British English) or checkers (American English), also called straight checkers or simply draughts, is a form of the strategy board game checkers (or draughts). It is played on an 8×8 checkerboard with 12 pieces per side. The pieces m ...
(checkers)
: This 8×8 variant of
draughts
Checkers (American English), also known as draughts (; Commonwealth English), 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. ...
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×10
20 possible game positions. The number of calculations involved was 10
14, which were done over a period of 18 years. The process involved from 200
desktop computer
A desktop computer, often abbreviated as desktop, is a personal computer designed for regular use at a stationary location on or near a desk (as opposed to a portable computer) due to its size and power requirements. The most common configuratio ...
s at its peak down to around 50.
;
Fanorona
Fanorona () is a Abstract strategy game, strategy board game for two players. The game is indigenous to Madagascar.
Rules
Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimy, and Fanoron-Sivy. The difference between these variants i ...
: 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
''The Tragedy of Othello, the Moor of Venice'', often shortened to ''Othello'' (), is a tragedy written by William Shakespeare around 1603. Set in Venice and Cyprus, the play depicts the Moorish military commander Othello as he is manipulat ...
(Reversi)
:Weakly solved in 2023 by Hiroki Takizawa, a researcher at
Preferred Networks. 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
28 possible game positions.
;
Pentomino
A pentomino (or 5-omino) is a polyomino of order 5; that is, a polygon in the Plane (geometry), plane made of 5 equal-sized squares connected edge to edge. The term is derived from the Greek word for '5' and "domino". When rotation symmetry, rota ...
es
: Weakly solved by H. K. Orman.
[Hilarie K. Orman: ''Pentominoes: A First Player Win'' in ]
Games of no chance
', MSRI Publications – Volume 29, 1996, pages 339-344. Online
pdf
It is a win for the first player.
;
Qubic
: Weakly solved by
Oren Patashnik (1980) and
Victor Allis
Louis Victor Allis (born 19 May 1965) is a Dutch computer scientist and co-founder of the election information technology firm Activote. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introd ...
. 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.
[Yew Jin Lim]
On Forward Pruning in Game-Tree Search
. Ph.D. Thesis, National University of Singapore
The National University of Singapore (NUS) is a national university, national Public university, public research university in Singapore. It was officially established in 1980 by the merging of the University of Singapore and Nanyang University ...
, 2007.
Partially solved games
;
Chess
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
:
: 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 tablebase
In chess, the endgame tablebase, or simply the tablebase, is a computerised database containing precalculated evaluations of chess endgame, endgame positions. Tablebases are used to analyse finished games, as well as by chess engines to evaluate ...
s, 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.
[5×5 Go is solved](_blank)
by Erik van der Werf The 7×7 board was weakly solved in 2015.
[ (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)] Humans usually play on a 19×19 board, which is over 145
orders of magnitude
In a ratio scale based on powers of ten, the order of magnitude is a measure of the nearness of two figures. Two numbers are "within an order of magnitude" of each other if their ratio is between 1/10 and 10. In other words, the two numbers are wi ...
more complex than 7×7.
[Counting legal positions in Go](_blank)
, Tromp and Farnebäck, accessed 2007-08-24.
;
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
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...
. 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
International draughts (also called international checkers or Polish draughts) is a Abstract strategy, strategy board game for two players, one of the variants of draughts. The gameboard comprises 10×10 squares in alternating dark and light co ...
: 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.
See also
*
Computer chess
Computer chess includes both hardware (dedicated computers) 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 analysi ...
*
Computer Go
Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, the programs of the era were weak. The best ...
*
Computer Othello
Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It was notably included in Microsoft Windows from 1.0 to XP, where it is simply known as Reversi.
Av ...
*
Game complexity
Combinatorial game theory measures game complexity in several ways:
#State-space complexity (the number of legal game positions from the initial position)
#Game tree size (total number of possible games)
#Decision complexity (number of leaf nod ...
*
God's algorithm
God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fe ...
*
Zermelo's theorem (game theory)
In game theory, Zermelo's theorem is a theorem about finite two-person games of perfect information in which the players move alternately and in which chance does not affect the decision making process. It says that if the game cannot end in a dr ...
References
Further reading
* Allis, ''Beating the World Champion? The state-of-the-art in computer game playing.'' in New Approaches to Board Games Research.
External links
Computational Complexity of Games and Puzzlesby David Eppstein.
GamesCrafterssolving two-person games with perfect information and no chance
{{DEFAULTSORT:Solved Game
Mathematical games
Abstract strategy games
Combinatorial game theory