Minimax

Minimax represents a game as a tree of possibilities. Each branch is a move, and each level alternates between one side and the other. A chess engine, meaning a program that analyzes positions and selects moves, considers its choices and then the opponent's strongest replies. Its central assumption is cautious: it never relies on the opponent making a mistake.

At levels where the engine moves, the algorithm keeps the most favorable result. At the opponent's levels, it keeps the least favorable result for the engine, because the opponent is assumed to resist as well as possible. Those values are then carried backward from future positions to the current one. The starting moves can therefore be compared by what each can guarantee against best defense.

A practical search can rarely examine the whole game. At its depth limit it uses an evaluation function, a formula that estimates which side is better. A depth-limited minimax choice is therefore not an absolute proof: it depends on how far the search went and how accurate that estimate was. It can also suffer from the horizon effect, where an important consequence lies just beyond the cutoff.

Engines make this framework efficient with techniques such as move ordering, which examines promising choices first so irrelevant branches can be rejected sooner. Other systems, including Monte Carlo tree search, distribute their effort differently while pursuing the same practical goal: identifying the move that deserves the most confidence.