A solved game is a

game A game is a structured form of play (activity), play, usually undertaken for enjoyment, entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator s ...

whose outcome (win, lose or

draw Draw, drawing, draws, or drawn may refer to: Common uses * Draw (terrain), a terrain feature formed by two parallel ridges or spurs with low ground in between them * Drawing (manufacturing), a process where metal, glass, or plastic or anything ...

) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to

abstract strategy game Abstract strategy games admit a number of definitions which distinguish these from strategy games in general, mostly involving no or minimal narrative theme, outcomes determined only by player choice (with no randomness), and perfect information. ...

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. Study has been largely confined to two-player games that have a ''position'' that the player ...

and/or computer assistance.

Overview

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 : Prove whether the first player will win, lose or draw from the initial position, given

perfect play 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 informa ...

on both sides. This can be a

non-constructive In mathematics, a constructive proof is a method of mathematical proof, 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 ...

proof (possibly involving a

strategy-stealing argument In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game ...

) that need not actually determine any moves of the perfect play. ;Weak : Provide 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. ;Strong : Provide an algorithm that can produce perfect moves from any position, even if mistakes have already been made on one or both sides. 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 Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...

algorithm that would exhaustively traverse the

game tree In the context of Combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, ch ...

. 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 an example of a strong solution, the game of

tic-tac-toe Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. ...

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

. 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 Maharajah and the Sepoys, originally called Shatranj Diwana Shah and also known as the Mad King's Game and Maharajah chess, is a popular chess variant with different armies for White and Black. It was first played in the 19th century in India. It i ...

). An ultra-weak solution (e.g.,

Chomp Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it" (remove from the board), tog ...

or Hex on a sufficiently large board) generally does not affect playability.

Perfect play

game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

, 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 Backward chaining (or backward reasoning) is an inference method described colloquially as working backward from the goal. It is used in automated theorem provers, inference engines, proof assistants, and other artificial intelligence applicat ...

, 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 In economics, perfect information (sometimes referred to as "no hidden information") is a feature of perfect competition. With perfect information in a market, all consumers and producers have complete and instantaneous knowledge of all market pr ...

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 other orderings of the three items, with "rock" sometimes being called "stone," or as Rochambeau, roshambo, or ro-sham-bo) is a hand game originating in China, usually played between two people, in which each p ...

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 Endgame, Endgames, End Game, End Games, or similar variations may refer to: Film * ''The End of the Game'' (1919 film) * ''The End of the Game'' (1975 film), short documentary U.S. film * ''Endgame'' (1983 film), 1983 Italian post-apocalyptic f ...

positions (in the form of

endgame tablebase An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of chess endgame positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysin ...

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 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 ...

(a game of the

Mancala The mancala games are a family of two-player turn-based strategy board games played with small stones, beans, or seeds and rows of holes or pits in the earth, a board or other playing surface. The objective is usually to capture all or some ...

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 a ...

and John Romein at the

Vrije Universiteit The Vrije Universiteit Amsterdam (abbreviated as ''VU Amsterdam'' or simply ''VU'' when in context) is a public research university in Amsterdam, Netherlands, being founded in 1880. The VU Amsterdam is one of two large, publicly funded research ...

Amsterdam Amsterdam ( , , , lit. ''The Dam on the River Amstel'') is the Capital of the Netherlands, capital and Municipalities of the Netherlands, most populous city of the Netherlands, with The Hague being the seat of government. It has a population ...

Netherlands ) , anthem = ( en, "William of Nassau") , image_map = , map_caption = , subdivision_type = Sovereign state , subdivision_name = Kingdom of the Netherlands , established_title = Before independence , established_date = Spanish Netherl ...

(2002). Either player can force the game into a draw. ;

Chopsticks Chopsticks ( or ; Pinyin: ''kuaizi'' or ''zhu'') are shaped pairs of equal-length sticks of Chinese origin that have been used as kitchen and eating utensils in most of East and Southeast Asia for over three millennia. They are held in the do ...

: Strongly solved. If 2 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 Gravitrips in the Soviet Union) is a two-player connection board game, in which the players choose a color and then take tur ...

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 working in the artificial intelligence (AI) field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game s ...

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). ;

English draughts English 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. Th ...

(checkers) : This 8×8 variant of

draughts Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...

was weakly solved on April 29, 2007, by the team of

Jonathan Schaeffer Jonathan Herbert Schaeffer (born 1957) is a Canadian researcher and professor at the University of Alberta and the former Canada Research Chair in Artificial Intelligence. He led the team that wrote Chinook, the world's strongest American c ...

. 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×10²⁰. The number of calculations involved was 10¹⁴, which were done over a period of 18 years. The process involved from 200

desktop computer A desktop computer (often abbreviated desktop) is a personal computer designed for regular use at a single location on or near a desk due to its size and power requirements. The most common configuration has a case that houses the power supply ...

s at its peak down to around 50. ;

Fanorona Fanorona () is a strategy board game for two players. The game is indigenous to Madagascar. Rules Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimy, and Fanoron-Tsivy. The difference between these variants is the size of board play ...

: Weakly solved by Maarten Schadd. The game is a draw. ; Free

gomoku ''Gomoku'', also called ''Five in a Row'', is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It is played using a 15×15 board while in the past a 19×19 board was standard. Be ...

: Solved by

(1993). The first player can force a win without opening rules. ;

Ghost A ghost is the soul or spirit of a dead person or animal that is believed to be able to appear to the living. In ghostlore, descriptions of ghosts vary widely from an invisible presence to translucent or barely visible wispy shapes, to rea ...

: Solved by Alan Frank using the ''

Official Scrabble Players Dictionary The ''Official Scrabble Players Dictionary'' or OSPD is a dictionary developed for use in the game Scrabble, by speakers of American and Canadian English. History Background and creation The ''Official Scrabble Players Dictionary'' was first ...

'' in 1987. ;

Hexapawn Hexapawn is a deterministic two-player game invented by Martin Gardner. It is played on a rectangular board of variable size, for example on a 3×3 board or on a regular chessboard. On a board of size ''n''×''m'', each player begins with ''m' ...

:3×3 variant solved as a win for black, several other larger variants also solved. ;

Kalah Kalah is a modern variation in the ancient Mancala family of games, the oldest known version having been found carved into a stone tablet in the 16th-century BCE pyramid of Cheops. The Kalah variation was developed in the United States by Willia ...

: 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. Mark Rawlings, of Gaithersburg, MD, has quantified the magnitude of the first player win in the (6/6) variant (2015). After creation of 39 GB of endgame databases, searches totaling 106 days of CPU time and over 55 trillion nodes, it was proven that, with perfect play, the first player wins by 2. Note that all these results refer to the Empty-pit Capture variant and therefore are of very limited interest for the standard game. Analysis of the standard rule game has now been posted for Kalah(6,4), which is a win by 8 for the first player, and Kalah(6,5), which is a win by 10 for the first player. Analysis of Kalah(6,6) with the standard rules is on-going, however, it has been proven that it is a win by at least 4 for the first player. ;

L game The L game is a simple abstract strategy board game invented by Edward de Bono. It was introduced in his book ''The Five-Day Course in Thinking'' (1967). Description The L game is a two-player game played on a board of 4×4 squares. Each playe ...

: Easily solvable. Either player can force the game into a draw. ; Losing chess : Weakly solved as a win for white beginning with 1. e3. ;

: 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 at least to 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 English. ...

: 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. ; Pentago : Strongly solved by Geoffrey Irving with use of a supercomputer at

NERSC The National Energy Research Scientific Computing Center (NERSC), is a high-performance computing (supercomputer) National User Facility operated by Lawrence Berkeley National Laboratory for the United States Department of Energy Office of Scien ...

. The first player wins. ;

Pentomino Derived from the Greek word for ' 5', and "domino", a pentomino (or 5-omino) is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to ...

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. ;

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. ;

Qubic 3D tic-tac-toe, also known by the trade name Qubic, is an abstract strategy board game, generally for two players. It is similar in concept to traditional tic-tac-toe but is played in a cubical array of cells, usually 4x4x4. Players take turns pla ...

: Weakly solved by

Oren Patashnik Oren Patashnik (born 1954) is an American computer scientist. He is notable for co-creating BibTeX, and co-writing '' Concrete Mathematics: A Foundation for Computer Science''. He is a researcher at the Center for Communications Research, La Jol ...

(1980) and

. The first player wins. ;

Renju ''Renju'' (Japanese: 連珠) is a professional variant of gomoku. It was named renju by Japanese journalist Ruikou Kuroiwa (黒岩涙香) on December 6, 1899 in a Japanese newspaper ''Yorozu chouhou'' (萬朝報). The name "renju" comes from th ...

-like game without opening rules involved : Claimed to be solved by János Wagner and István Virág (2001). A first-player win. ; Sim : Weakly solved: win for the second player. ;

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 Tic-t ...

: 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 thei ...

: Trivially solvable. Either player can force the game into a draw. ;

Three Musketeers 3 is a number, numeral, and glyph. 3, three, or III may also refer to: * AD 3, the third year of the AD era * 3 BC, the third year before the AD era * March, the third month Books * ''Three of Them'' (Russian: ', literally, "three"), a 1901 n ...

: 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 (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. ...

: 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. ; Tigers and Goats : 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 public research university in Singapore. Founded in 1905 as the Straits Settlements and Federated Malay States Government Medical School, NUS is the oldest autonomous university in the c ...

, 2007. ;

Wythoff's game Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile m ...

: Strongly solved by W. A. Wythoff in 1907.

Weak-solves

; Tigers and Goats :Weakly solved by Yew Jin Lim (2007). The game is a draw. ; Pentominoes :Weakly solved by H. K. Orman. It is a win for the first player.

Partially solved games

;

Chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...

: : Fully solving chess remains elusive, and it is speculated that the complexity of the game may preclude its ever being solved. Through retrograde computer analysis,

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

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
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 An order of magnitude is an approximation of the logarithm of a value relative to some contextually understood reference value, usually 10, interpreted as the base of the logarithm and the representative of values of magnitude one. Logarithmic dis ...

more complex than 7×7.Counting legal positions in Go
, Tromp and Farnebäck, accessed 2007-08-24. ; Hex : A

(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 (polynomial space) and if every other problem that can be solved in polynomial space can b ...

. 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. ; ''m'',''n'',''k''-game : It is trivial to show that the second player can never win; see

. Almost all cases have been solved weakly for ''k'' ≤ 4. Some results are known for ''k'' = 5. The games are drawn for ''k'' ≥ 8. ;

Reversi Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. It was invented in 1883. Othello, a variant with a fixed initial setup of the board, was patented in 1971. Basics There are sixty-four identical game pieces ...

(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.

References

External links

Computational Complexity of Games and Puzzles
by David Eppstein.
GamesCrafters
solving two-person games with perfect information and no chance {{DEFAULTSORT:Solved Game Mathematical games Abstract strategy games Combinatorial game theory