Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search
This work addresses the problem of developing AI for complex imperfect information games like social deduction games, but it is incremental as it applies an existing algorithm to a new game without surpassing baseline performance.
The authors tackled the challenge of applying an AI agent to Secret Hitler, a complex hidden role game with both hidden roles and card deck randomness, by using Single Observer Information Set Monte Carlo Tree Search (SO-ISMCTS). The result showed that SO-ISMCTS performed as well as simpler rule-based agents in 10,108 simulated games, demonstrating its potential in such domains.
Advances in intelligent game playing agents have led to successes in perfect information games like Go and imperfect information games like Poker. The Information Set Monte Carlo Tree Search (ISMCTS) family of algorithms outperforms previous algorithms using Monte Carlo methods in imperfect information games. In this paper, Single Observer Information Set Monte Carlo Tree Search (SO-ISMCTS) is applied to Secret Hitler, a popular social deduction board game that combines traditional hidden role mechanics with the randomness of a card deck. This combination leads to a more complex information model than the hidden role and card deck mechanics alone. It is shown in 10108 simulated games that SO-ISMCTS plays as well as simpler rule based agents, and demonstrates the potential of ISMCTS algorithms in complicated information set domains.