Difference between revisions of "Solved game"
(New page: A '''solved game''' is a two-player game in which it is known what the theoretical result of the game. For example, checkers is considered to be a solved game since a computer called C...) |
|||
| Line 1: | Line 1: | ||
| − | A '''solved game''' is a two-player game in which it is known what the theoretical result of the game. For example, [[checkers]] is considered to be a solved game since a computer called Chinook determined in 2007 that the game is a draw with best play from both sides. <ref>http://www.msnbc.msn.com/id/19839044/</ref> | + | A '''solved game''' is a two-player game in which it is known what the theoretical result of the game should be. For example, [[checkers]] is considered to be a solved game since a computer called Chinook determined in 2007 that the game is a draw with best play from both sides. <ref>http://www.msnbc.msn.com/id/19839044/</ref> |
A game can be solved on several levels. A game can be "ultra-weakly solved", which means that the theoretical result of the game from the first position, given best play (win, lose, or draw for the first player) is known, but there is no specific [[algorithm]] known for bringing about this result. Right now, checkers is ultra-weakly solved, but computers are working on weakly solving it. <ref> http://www.cs.ualberta.ca/~mmueller/ps/ijcai05checkers.pdf</ref> | A game can be solved on several levels. A game can be "ultra-weakly solved", which means that the theoretical result of the game from the first position, given best play (win, lose, or draw for the first player) is known, but there is no specific [[algorithm]] known for bringing about this result. Right now, checkers is ultra-weakly solved, but computers are working on weakly solving it. <ref> http://www.cs.ualberta.ca/~mmueller/ps/ijcai05checkers.pdf</ref> | ||
Revision as of 04:25, October 17, 2007
A solved game is a two-player game in which it is known what the theoretical result of the game should be. For example, checkers is considered to be a solved game since a computer called Chinook determined in 2007 that the game is a draw with best play from both sides. [1]
A game can be solved on several levels. A game can be "ultra-weakly solved", which means that the theoretical result of the game from the first position, given best play (win, lose, or draw for the first player) is known, but there is no specific algorithm known for bringing about this result. Right now, checkers is ultra-weakly solved, but computers are working on weakly solving it. [2]
If a game is "weakly solved", the theoretical result of the game from the beginning is known, and an algorithm for bringing about this result is known. In other words, it is known exactly what moves need to be made to bring about this result. An example of a weakly solved game is Connect Four.
In a "strongly solved game", an algorithm for bringing about the theoretical result of the game can be produced from any position in the game, not just the opening position. An example of a strongly solved game is tic-tac-toe.
Games that have not been solved include go and chess.