Editing Solved game (section)

==Overview==
A [[two-player game]] can be solved on several levels:<ref name="Allis">{{Cite thesis |last=Allis |first=Louis Victor |title=Searching for Solutions in Games and Artificial Intelligence |date=1994-09-23 |degree=PhD |publisher=Rijksuniversiteit Limburg |isbn=90-9007488-0 |place=Maastricht}}</ref><ref>[[H. Jaap van den Herik]], Jos W.H.M. Uiterwijk, Jack van Rijswijck, ''[https://web.archive.org/web/20170912011410/https://pdfs.semanticscholar.org/8296/bc0ab855841088b31190c9f2923951853d7b.pdf Games solved: Now and in the future]'', ''Artificial Intelligence'' 134 (2002) 277–311.</ref>

===Ultra-weak solution===
: Prove whether the first player will win, lose or draw from the initial position, given perfect play on both sides {{See below|{{slink||Perfect play}}, below}}. This can be a [[non-constructive proof]] (possibly involving a [[strategy-stealing argument]]) that need not actually determine any details of the perfect play.

===Weak solution===
: Provide one algorithm for each of the two players, such that the player using it can achieve at least the optimal outcome, regardless of the opponent's moves, from the start of the game, using reasonable computational resources.

===Strong solution===
: Provide an algorithm that uses reasonable computational resources and finds optimal plays for both players from all legal positions.

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.{{Citation needed|date=December 2014}}

By contrast, "strong" proofs often proceed by [[Brute force method|brute force]]—[[Computer-assisted proof|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]] 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.

As a simple example of a strong solution, the game of [[tic-tac-toe]] is easily solvable as a draw for both players with perfect play (a result manually determinable). Games like [[nim]] also admit 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 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]]). An ultra-weak solution (e.g., [[Chomp]] or [[Hex (board game)|Hex]] on a sufficiently large board) generally does not affect playability.