A two player game can be "solved" on several levels ^{[1] [2]}: For other uses, see Game (disambiguation). ...

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. In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ... In combinatorial game theory, the Strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy. ... “Minmax” redirects here. ... In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. ...

As a very trivial 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. Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ... For other uses, see Nim (disambiguation). ... Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content, see external link) This article is on the theory of combinatorial games. ...

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. Maharajah and the Sepoys, originally called Shatranj Diwana Shah, is a popular chess variant with different armies for white and black. ... Chomp is a 2-player game played on a rectangular chocolate bar made up of smaller square blocks. ... Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as a 11x11 rhombus. ...

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. Game theory is a branch of applied mathematics that is often used in the context of economics. ... Black to move. ...

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/3rd) 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. Perfect information is a term used in economics and game theory to describe a state of complete knowledge about the actions of other players that is instantaneously updated as new information arises. ... In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... Rock, Paper, Scissors chart Listen to this article ( info/dl) This audio file was created from an article revision dated 2006-07-13, and may not reflect subsequent edits to the article. ...

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. EndGame is the name of a 1997 story arc of the Sonic the Hedgehog comic book published by published by Archie Comics. ... A typical interface for querying a tablebase. ... 1990s Pressure-sensory Chess Computer with LCD screen The idea of creating a chess-playing machine dates back to the eighteenth century. ...

Solved 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. Philip Brocoum has created a website where you can play Chomp against the computer. You can also download from Philip's site a list of all winning moves on boards up to 8 x 9. Philip used 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 (Hand game)

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)^[3]. First player can force a win.

Dakon

Weakly solved by humans, but proven by computers.^[4]

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.^[5] Checkers is the largest game that has been solved to date, with a search space of 5x10²⁰.^[6] The number of calculations involved were 10¹⁴ and were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.^[7]

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.

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.^[8]
• 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.^[9]

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 ^[10]

Pentominoes

Weakly solved by H. K. Orman.^[11] It is a win for the first player.

Quarto

Solved by Luc Goossens (1998). Two perfect players will always draw. ^[12]

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.^[13]

Teeko

Solved by Guy Steele (1998). Depending on the variant either a first-player win or a draw. ^[14]

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.

Oware is an abstract strategy game and the mancala game most widely considered suitable for serious adult competition. ... A foldable, wooden Mancala board Mancala (Arabic: , manqalä) is a family of board games played around the world, sometimes called sowing games or count and capture games, which comes from the general gameplay. ... Dr. Henri Elle Bal is a professor of Computer Science at the Vrije Universiteit, Amsterdam in the Netherlands. ... The Vrije Universiteit is a university in Amsterdam, The Netherlands. ... For other uses, see Amsterdam (disambiguation). ... Chomp is a 2-player game played on a rectangular chocolate bar made up of smaller square blocks. ... In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy (i. ... Chopsticks (also called Magic Fingers) is a commonly played two player traditional Japanese childrens hand game. ... Connect Four (also known as Plot Four) is a two-player board game in which the objective is to be the first to get four of ones own discs in a line. ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Congklak, also called Dakon, Congkak, or Sungka, is a mancala game played in Indonesia, Malaysia, and the Philippines. ... English draughts, also called American checkers or straight checkers, commonly called checkers in the U.S., but commonly called draughts in some other countries, is a form of the draughts board game played on an 8×8 board with 12 pieces on each side that may only move and capture... “Checkers” redirects here. ... Jonathan Schaeffer is a researcher and professor at the University of Alberta. ... Chinook is a computer program that plays English draughts, developed around 1989 at the University of Alberta, led by Jonathan Schaeffer. ... The term personal computer or PC has three meanings: IBMs range of PCs that led to the use of the term - see IBM PC. Any computer based on IBMs original specifications also known as IBM PC compatible. ... Fanorona is a board game indigenous to Madagascar and derived from Alquerque. ... Gomoku, go-moku, or gobang (Japanese: 五目並べ, Gomoku Narabe, five points), or in English Connect Five (also spelled Connect 5 or Connect5) is an abstract strategy board game. ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Hex is a board game played on a hexagonal grid, usually in the shape of a 10 by 10 or a 11 by 11 rhombus. ... In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy (i. ... John Forbes Nash, Jr. ... The pie rule, sometimes referred to as the swap rule, is a meta-rule commonly used in abstract strategy board games like Hex and Havannah. ... In complexity theory, PSPACE-complete is a complexity class. ... Kalah, also called Kalaha or Mancala, is a game in the mancala family introduced to the West by William Julius Champion Jr in the early 20th century. ... The L game was invented by Edward De Bono, intended to illustrate lateral thinking. ... Maharajah and the Sepoys, originally called Shatranj Diwana Shah, is a popular chess variant with different armies for white and black. ... For other uses, see Nim (disambiguation). ... Nine Mens Morris is an abstract strategy board game for two players that emerged from the Roman Empire. ... A pentomino is a polyomino composed of five (Greek πέντε / pente) congruent squares, connected orthogonally. ... Quarto Quarto is a board game for two players invented by Blaise Müller. ... a selfmade Qubic game Qubic is a four-in-a-row game played in a 4×4×4 matrix. ... Oren Patashnik (born 1954) is a computer scientist. ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Renju or Lianzhu (Chinese/Japanese: 連珠) is the professional variant of Gomoku, a board game originated from China. ... Teeko is an abstract strategy game invented by John Scarne in 1945 and rereleased in refined form in 1952 and again in the 1960s. ... Guy Lewis Steele, Jr. ... Three Mens Morris is played on a three-line by three-line board, and is a game of position. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

Partially solved games

Chess

Solved by retrograde computer analysis for all 3- to 6-piece, and some 7-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).^[15]

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.^[16]. Boards up to 6x7 have been solved.^[17] Humans usually play on a 19×19 board which is over 145 orders of magnitude more complex than 7x7.^[18]

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.

This article is about the Western board game. ... Black to move. ... EndGame is the name of a 1997 story arc of the Sonic the Hedgehog comic book published by published by Archie Comics. ... Staunton chess pieces, left to right: pawn, rook, knight, bishop, queen, and king. ... A typical interface for querying a tablebase. ... Minichess is a family of chess variants played with regular chess pieces and standard rules, but on a smaller board. ... Go is a strategic board game for two players. ... Komi points (komidashi is the more complete Japanese language term) are points given in the game of go to one player to add to his or her score. ... In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy (i. ... “Minmax” redirects here. ... Reversi and Othello are names for an abstract strategy board game which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. ... An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. ... In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many games, that the second player cannot have a winning strategy (i. ...

See also

• Game complexity

Combinatorial game theory has several ways of measuring game complexity. ...

References

Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era in the 21st century. ... is the 201st day of the year (202nd in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era in the 21st century. ... is the 200th day of the year (201st in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era in the 21st century. ... is the 201st day of the year (202nd in leap years) in the Gregorian calendar. ...

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 Puzzles by David Eppstein.
• GamesCrafters - on solving two-person games with perfect information and no chance