Introduction
In the mid-1980s, artificial intelligence research in game playing was largely synonymous with two-player, zero-sum games. The minimax algorithm, coupled with alpha-beta pruning, provided a robust framework for games like Chess and Checkers where one player's gain is exactly the other's loss. However, these methods faltered when applied to multi-player scenarios where payoffs are not zero-sum and players may have divergent or even partially overlapping interests. This 1986 paper introduces $max^n$, a generalization of minimax designed for $n$-person, non-cooperative games of perfect information.
The $max^n$ Algorithm
The fundamental shift in $max^n$ is the transition from scalar values to payoff vectors. In a two-player zero-sum game, a single number suffices to represent the state. In an $n$-person game, the state is represented by a vector $(v_1, v_2, \dots, v_n)$, where each entry $v_i$ represents the utility for player $i$.
The $max^n$ procedure operates by traversing the game tree. At any node where it is Player $i$'s turn to move, the algorithm evaluates all possible successor nodes and selects the one that maximizes the $i$-th component of the payoff vector. This entire vector is then "backed up" to the parent node.
Pruning Strategies: Shallow and Deep
A major challenge in multi-player search is the exponential growth of the state space. While alpha-beta pruning is highly effective for two players, $n$-person games present more complex bounding problems because you cannot easily bound the interests of multiple rational agents simultaneously. The authors introduce two primary optimizations:
- Shallow Pruning: This technique reduces computation by only fully evaluating the "best" child found so far. For subsequent siblings, the algorithm initially evaluates only the specific payoff entry relevant to the current player. If this entry cannot possibly exceed the current maximum, the rest of the vector evaluation for that branch is skipped.
- Deep Pruning: A more sophisticated method that utilizes bounds from "grandparent" nodes to prune entire subtrees. This is analogous to the $\alpha$ and $\beta$ bounds in two-player search but requires more complex bookkeeping across multiple player interests.
Theoretical Foundations and Results
The authors provide a critical theoretical guarantee: for any finite, $n$-person, non-cooperative game with perfect information, the $max^n$ algorithm is guaranteed to identify a Nash equilibrium point. This ensures that the strategies found are stable—no player can improve their outcome by unilaterally changing their move, assuming others remain rational.
In practical tests using a 3-person variant of Nim (2-2-2 Nim), shallow pruning demonstrated significant efficiency gains, reducing the number of node evaluations by approximately 38% compared to an exhaustive search. Under optimal move ordering, deep pruning can further reduce complexity to $b^m + n - 1$ (where $b$ is the branching factor and $m$ is the depth), which is significantly more efficient than the exhaustive $n \cdot b^m$.
Limitations and Future Work
Despite its theoretical elegance, $max^n$ has limitations. It assumes perfect rationality and does not account for "sub-optimal" or spiteful play. Furthermore, while it can model coalitions by treating them as a single "meta-player" whose payoff is the sum of its members' individual payoffs, the process of how players should decide to form those coalitions remains an open research problem. Future work is suggested to extend $max^n$ to games with imperfect information or chance elements.
Summary updated