Introduction
In the realm of artificial intelligence and game theory, perfect-information games like Chess and Go have long been dominated by the minimax algorithm. Minimax operates on the assumption of a rational opponent who always makes the optimal move. However, real-world scenarios and many complex games involve imperfect information, where the exact state of the world is hidden. In such environments, players must navigate "information sets"—collections of possible game states consistent with their observations. This paper explores whether a "paranoid" minimax-style approach or an "overconfident" model assuming random opponent behavior is more effective in these challenging domains.
The Information-Set Search Challenge
Imperfect-information games like Kriegspiel (a blindfold variant of chess) present a computational nightmare. The decision problem is complete in double-exponential time, making exact solutions impossible for non-trivial games. To address this, the authors propose an Information-Set Search algorithm.
The core of the method involves a recursive utility formula that calculates the expected utility (EU) of an information set by aggregating the probabilities of all constituent game histories. Due to the massive size of these sets—often exceeding $10^{13}$ states—the algorithm employs statistical sampling and a heuristic evaluation function to maintain tractability within fixed search depths.
Opponent Modeling: Paranoia vs. Overconfidence
The study compares two fundamental backup rules for the search:
- Paranoid Model: An analog to minimax that assumes the opponent knows the player's exact state and will always choose the move minimizing the player's expected utility.
- Overconfident Model: A simpler model that assumes the opponent chooses moves uniformly at random.
While the paranoid model seems more robust, it often falls into the "Paranoia Trap." In imperfect-information settings, a paranoid player might avoid a move that wins in the vast majority of scenarios just because a single, unlikely history leads to a loss—assuming the opponent will perfectly exploit that one weakness, even if the opponent lacks the information to identify it.
Experimental Results
The models were tested in Kriegspiel against random baselines, existing high-performance algorithms, and each other. The results consistently favored the overconfident approach. Against a random opponent at depth 2, the Overconfident model achieved a 50% win rate, significantly outperforming the Paranoid model's 29%.
In direct head-to-head matches, the Overconfident player maintained a clear advantage. As shown in the experimental data, at depth 2, the Overconfident player won 22% of games while losing only 4% against the Paranoid model. This suggests that the overconfident model's assumption of randomness is a better fit for the inherent uncertainty of Kriegspiel than the paranoid assumption of perfection.
Conclusion
The superiority of the overconfident model suggests that in games with high uncertainty, assuming a perfect opponent is often less effective than assuming a fallible one. The "More is Less" depth paradox further highlights the risks of deep search with flawed opponent models: deeper recursion can compound modeling errors and reduce the accuracy of statistical sampling. Future research will focus on more nuanced opponent models that bridge the gap between randomness and perfection.
Summary updated