The case where two agents are competing, so that a positive reward for one is a negative reward for the other, is a two-agent zero-sum game. An agent that plays such a game well requires adversarial reasoning. The value of such a game can be characterized by a single number that one agent is trying to maximize and the other agent is trying to minimize, which leads to a minimax search space. Each node is either a MAX node, if it is controlled by the agent trying to maximize, or a MIN node, if it is controlled by the agent trying to minimize.

Figure 14.5 implements a minimax algorithm for zero-sum perfect information games, by the MAX agent choosing an action with the maximum value, and the MIN agent choosing an action with the maximum of the negation of the value.

The game-tree search of Figure 14.5 traverses the whole game tree. It is possible to prune part of the search tree for minimax games by showing that some part of the tree will never be part of an optimal play.

The previous example analyzed what can be pruned. Minimax with alpha–beta ($\alpha$–$\beta$) pruning is a depth-first search algorithm that prunes by passing pruning information down in terms of parameters $\alpha$ and $\beta$. In this depth-first search, a node has a score, which has been obtained from (some of) its descendants.

The parameter $\alpha$ is used to prune MIN nodes. Initially, it is the highest current value for all MAX ancestors of the current node. Any MIN node whose current value is less than or equal to its $\alpha$ value does not have to be explored further. This cutoff was used to prune the other descendants of nodes $l$, $m$, and $c$ in the previous example.

The $\beta$ parameter is used to prune MAX nodes in an analogous way.

The minimax algorithm with $\alpha$–$\beta$ pruning is given in Figure 14.7. It is called, initially, with $MinimaxAlphaBeta(R,-\mathrm{\infty },\mathrm{\infty })$, where $R$ is the root node. It returns a pair of the value for the node $n$ and a path of choices that lead to this value. (Note that this path does not include $n$.) Line 13 performs $\beta$ pruning; at this stage the algorithm knows that the current path will never be chosen, and so returns a current score. Similarly, line 22 performs $\alpha$-pruning. Line 17 and line 26 concatenate $c$ to the path, as it has found a best path for the agent. In this algorithm, the path “$None$” is sometimes returned for non-leaf nodes; this only occurs when the algorithm has determined this path will not be used.

The amount of pruning provided by this algorithm depends on the ordering of the children of each node. It works best if a highest-valued child of a MAX node is selected first and if a lowest-valued child of a MIN node is returned first. In implementations of real games, much of the effort is made to try to ensure this ordering.

Most real games are too big to carry out minimax search, even with $\alpha$–$\beta$ pruning. For these games, instead of only stopping at leaf nodes, it is possible to stop at any node. The value returned at the node where the algorithm stops is an estimate of the value for this node. The function used to estimate the value is an evaluation function. Much work goes into finding good evaluation functions. There is a trade-off between the amount of computation required to compute the evaluation function and the size of the search space that can be explored in any given time. It is an empirical question as to the best compromise between a complex evaluation function and a large search space.