Solved game

A two player game can be "solved" on several levels: [V. Allis, "Searching for Solutions in Games and Artificial Intelligence." PhD thesis, Department of ComputerScience, University of Limburg, 1994. Online: [http://fragrieu.free.fr/SearchingForSolutions.pdf 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. Online: [http://www.fdaw.unimaas.nl/education/4.2ZT/Literature/GamesSolved.pdf pdf] ]

; Ultra-weak: In the weakest sense, solving a game means proving 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 may not actually help determine this perfect play.

; Weak: More typically, solving a game means 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.

; Strong: The strongest sense of solution requires an algorithm which can produce perfect play from any position, i.e. even if mistakes have already been made on one or both sides.

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

As an example, the game of tic-tac-toe is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim also admit of a rigorous analysis using combinatorial game theory.

Whether a game is solved does not necessarily correlate with whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if the 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 which leads to 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 backwards 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 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 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.

olved games

; Awari (a game of the Mancala family): The variant 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.

; Chomp: Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size. [http://www.philipbrocoum.com/ Philip Brocoum] has created a website where you can [http://www.philipbrocoum.com/munch/ play Chomp] against the computer. You can also download from Philip's site a list of [http://www.philipbrocoum.com/munch/winners8x9.txt all winning moves] on boards up to 8 x 9. Philip used [http://tryruby.hobix.com/ Ruby] to calculate the winning positions in about 10 seconds on an Apple iMac.

: For arbitrary board sizes, a strategy-stealing argument proves this is a 1st player win starting from a rectangle. However, this “ultra-weak” solution is merely a curiosity arising from the fact that, in effect, the first player has a “pass” move available (remove just one block) and hence can choose to become the second player if this is more advantageous. An actual winning strategy for the game is not known except in the simplest cases. If the “pass” move is forbidden as an opening then it is not even known in general which player wins.

; Chopsticks: The second player can always force a win.

; Connect Four: Solved first by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988) [http://www.cwi.nl/~tromp/c4/c4.html John's Connect Four Playground ] ] . First player can force a win. Strongly solved by John Tromp's 8-ply database [ftp://ftp.ics.uci.edu/pub/machine-learning-databases/connect-4/] [ [http://archive.ics.uci.edu/ml/machine-learning-databases/connect-4/ Index of /ml/machine-learning-databases/connect-4 ] ] (Feb 22, 1995). Weakly solved for all boardsizes where width+height is at most 15 (Feb 18, 2006).

; Dakon: Weakly solved by humans, but proven by computers. [ [http://www.cs.unimaas.nl/icga/journal/contents/content24-1.htm "ICGA Journal"] , Vol. 24, No. 1 - March 2001]

; Draughts, English (i.e. checkers): This 8x8 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. [cite web | url=http://www.sciencemag.org/cgi/content/abstract/1144079 | title=Checkers Is Solved | date=2007-07-19 | accessdate=2007-07-20 | publisher=Science | first=Jonathan | last=Schaeffer] Checkers is the largest game that has been solved to date, with a search space of 5x10²⁰. [cite web | url=http://www.cs.ualberta.ca/~chinook/project/ | title=Project - Chinook - World Man-Machine Checkers Champion | accessdate=2007-07-19] The number of calculations involved was 10¹⁴, and those were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50. [cite web | url=http://www.newscientisttech.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html | title=Checkers 'solved' after years of number crunching | date=2007-07-19 | accessdate=2007-07-20 | publisher=NewScientist.com news service | first=Justin | last=Mullins]

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

; Free Gomoku: Solved by Victor Allis (1993). First player can force a win without opening rules.

; Ghost: Solved by Alan Frank using the Official Scrabble Dictionary in 1987, and independently by Randall Munroe using the Ubuntu dictionary in 2007

; Hex:* 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. [ [http://www.ee.umanitoba.ca/~jingyang/ Jing Yang homepage] ] :* 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.

; Kalah: Most variants solved by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). Strong first-player advantage was proven in most cases. [ [http://graphics.stanford.edu/~irving/papers/irving2000_kalah.pdf Solving Kalah] by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.]

; 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: Completely solved for all starting configurations.

; Nine Men's Morris: Solved by Ralph Gasser (1993). Either player can force the game into a draw [ [http://www.ics.uci.edu/~eppstein/cgt/morris.html Nine Men's Morris is a Draw] by Ralph Gasser]

; Pentominoes: Weakly solved by H. K. Orman. [Hilarie K. Orman: "Pentominoes: A First Player Win" in " [http://www.msri.org/publications/books/Book29/contents.html Games of no chance] ", MSRI Publications – Volume 29, 1996, pages 339-344. Online: [http://www.msri.org/publications/books/Book29/files/orman.pdf pdf] .] It is a win for the first player.

; Quarto: Solved by Luc Goossens (1998). Two perfect players will always draw. [ [http://zoo.cs.yale.edu/classes/cs490/00-01b/kerner.matthew.mmk29/quarto/node9.html Solving Quarto] by Matthew Kerner]

; Qubic: Weakly solved by Oren Patashnik (1980) and Victor Allis. The first player wins.

; Free Renju: (Without opening rules) claimed to be solved by János Wagner and István Virág (2001). A first-player win. [ [http://www.cs.unimaas.nl/icga/journal/contents/content24-1.htm "ICGA Journal"] , Vol. 24, No. 1 - March 2001]

; Teeko: Solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw. [ [http://mathworld.wolfram.com/Teeko.html Teeko] , by E. Weisstein]

; Three Men's Morris: Trivially solvable. Either player can force the game into a draw.

; Tic-tac-toe: Trivially solvable. Either player can force the game into a draw.

; Tigers and Goats: Weakly solved by Yew Jin Lim (2007). The game is a draw. [Yew Jin Lim. [http://www.yewjin.com/papers/PhDThesisLimYewJin.pdf On Forward Pruning in Game-Tree Search] . Ph.D. Thesis, National University of Singapore, 2007.]

Partially solved games

; Chess: 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 3x3 board is strongly solved by Kirill Kryukov (2004). [ [http://kd.lab.nig.ac.jp/3x3-chess/ 3x3 Chess] by Kirill Kryukov.]

; International Draughts: All positions with 2 through 7 pieces were solved. Positions with 4x4 and 5x3 pieces where each side had 1 king or less. Positions with 5 men vs. 4 men, 5 men vs. 3 men and 1 king, and 4 men and 1 king vs. 4 men. Solved in 2007 by Ed Gilbert of the United States. [ [http://pages.prodigy.net/eyg/Checkers/Culemborg2007.htm Some of the 9 piece endgame tablebase] by Ed Gilbert]

; Go: If no compensation points ("komi") were given to the second player, then the fact that passing is a legal move in Go allows a strategy-stealing argument to show that the game would be at least a draw for the first player. Thus solving Go entails determining the difference in score at the end of the game with both sides trying to maximize their score. Go with komi set to this value would be a draw. Board sizes up to 4×4 are strongly solved. The 5×5 board is weakly solved for all opening moves. [ [http://www.cs.unimaas.nl/~vanderwerf/5x5/5x5solved.html 5x5 Go is solved] by Erik van der Werf] . Humans usually play on a 19×19 board which is over 145 orders of magnitude more complex than 7x7. [ [http://homepages.cwi.nl/~tromp/go/legal.html Counting legal positions in Go] , Tromp and Farnebäck, accessed 2007-08-24.]

; Reversi (alias Othello): Solved on a 4×4 and 6×6 board as a second player win. Far from solved on 8×8 board (the standard one), yet computer analysis shows a very likely draw: there are thousands of likely draw lines although not a single line has been fully proven. No strongly supposed estimates other than increased chances for the starting player (black) on 10×10 and greater boards exist.

; 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

* Game complexity

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

* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles] by David Eppstein.
* [http://gamescrafters.berkeley.edu/ GamesCrafters] - on solving two-person games with perfect information and no chance