A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be "unsolved." Games for which only some positions have been solved are said to be "partially solved." This article focuses on two-player games that have been solved.
A two-player game can be "solved" on several levels:
- 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 need not actually determine any moves of the 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. That is, producing at least one complete ideal game (all moves start to end), with proof that each move is optimal for the player making it.
- Strong
- The strongest sense of solution requires an algorithm which can produce perfect play (moves) 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 is not necessarily the same as 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.
Read more about Solved Game: Perfect Play, Solved Games, Partially Solved Games
Famous quotes containing the words solved and/or game:
“Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan Press On, has solved and will always solve the problems of the human race.”
—Calvin Coolidge (18721933)
“Wild Bill was indulging in his favorite pastime of a friendly game of cards in the old No. 10 saloon. For the second time in his career, he was sitting with his back to an open door. Jack McCall walked in, shot him through the back of the head, and rushed from the place, only to be captured shortly afterward. Wild Bills dead hand held aces and eights, and from that time on this has been known in the West as the dead mans hand.”
—State of South Dakota, U.S. public relief program (1935-1943)