Gamesolving

Gamesolving, or game solving, is the study of determining optimal play in formal games. It concerns whether the outcome of a game can be forced or avoided by perfect play from both players, starting from the initial position, and, for some games, for all positions reachable during play. The field distinguishes strong solving, in which every position has a known outcome under perfect play, from weak solving, where the outcome is known for the initial position or for a large class of positions. It is part of artificial intelligence, theoretical computer science, and mathematical game theory, and it is distinct from game playing, which emphasizes practical performance rather than guaranteed optimality, and from game design.

Methods used in gamesolving include exact search techniques such as retrograde analysis and endgame databases, as well as decision procedures like minimax with alpha-beta pruning and proof-number search. For larger or more complex games, researchers rely on approximate methods, including Monte Carlo tree search, reinforcement learning, and carefully crafted heuristic evaluations. Endgame databases encode every possible position for a reduced game, allowing unconditional proofs of the correct outcome for those positions.

Notable milestones include tic-tac-toe being trivially solvable, Connect Four having a forced first-player win (published in the late 1980s), and checkers being solved in the 2000s with the Chinook program proving a forced win for the first player. Chess and Go remain unsolved, although modern AI approaches have achieved superhuman performance without a formal solution. Today, gamesolving informs AI research, game verification, and the study of computational limits in search, planning, and learning.