Abstract
Perfect Information Monte Carlo (PIMC) sampling is a widely used technique for imperfect information games, yet it is fundamentally limited by "strategy fusion"—the unrealistic assumption that opponents possess perfect knowledge of hidden information. This paper introduces Presumed Value PIMC (PVP), a variant that explicitly models the opponent's limited knowledge and potential for error. Evaluated on the complex trick-taking game Schnapsen, the PVP agent demonstrates super-human performance, outperforming human experts and standard PIMC baselines while maintaining computational efficiency. Unlike equilibrium-based approaches, PVP calculates moves on the fly, making it scalable to games with massive state spaces.
Introduction
In games with hidden information, such as Bridge or Poker, AI agents must make decisions without knowing the opponent's cards. A common approach is Perfect Information Monte Carlo (PIMC) sampling, which averages the results of multiple "worlds" where hidden cards are randomly assigned. However, PIMC often fails due to strategy fusion: it solves each world independently, implicitly assuming both players will know exactly which world they are in during future turns. This leads to "paranoid" play, where the agent assumes the opponent will always find the perfect counter-move that only a clairvoyant could know.
Methodology
To address these limitations, the authors propose three key algorithmic improvements:
- Error Allowing Minimax (EAM): Instead of binary win/loss values, EAM uses a triple-value system to account for the probability of an opponent making a mistake when forced to guess.
- Presumed Payoff PIMC (PPP): This introduces a knowledge estimate parameter ($k$). While standard PIMC ($k=1$) assumes a clairvoyant opponent, PPP allows for modeling an opponent with limited knowledge ($k < 1$), finding a balance between caution and realism.
- Presumed Value PIMC (PVP): Extending PPP to full matches, PVP evaluates moves based on the overall probability of winning the match rather than just the immediate point payoff.
These methods are designed for efficiency, adding only approximately 30% computational overhead compared to the 600% increase seen in previous attempts like Vector Minimax.
Experimental Results
The agent was rigorously tested on Kinderschnapsen (a simplified variant) and the full game of Schnapsen, which has a state-space of $10^{20}$.
Performance in Kinderschnapsen
In controlled tests, PVP variants significantly outperformed standard PIMC and other baselines. As shown in Figure 5, the PVP agent achieved a win rate of approximately 53.6% against standard PIMC, demonstrating the effectiveness of modeling limited opponent knowledge.
Super-Human Performance in Schnapsen
In the full game of Schnapsen, the PVP agent reached even higher levels of performance. Against human experts, the agent won 58.9% of its games. Furthermore, in a test against 110 complex scenarios analyzed by a human expert, the agent agreed with the expert in 101 cases (92%) and even identified errors in the expert's original analysis in the remaining instances.
Conclusion
The success of PVP suggests that in imperfect information games, assuming a "best defense" from a clairvoyant opponent is sub-optimal. By using coarse heuristics to estimate opponent knowledge and calculating moves on the fly, PVP provides a scalable, expert-level solution for games with massive state spaces that cannot be pre-solved. Future work will explore dynamic estimation of opponent skill levels and more sophisticated card distribution modeling.
Summary updated