Know your Enemy: Investigating Monte-Carlo Tree Search with Opponent Models in Pommerman
This work addresses computational scaling issues for multiplayer games like Pommerman, which is incremental as it adapts existing methods to new complexities.
The paper tackled the challenge of scaling Monte-Carlo Tree Search to multiplayer games with partial observability and long time horizons, specifically in Pommerman, by transforming them into single-player or two-player games using opponent models, and demonstrated effectiveness in supervised and reinforcement learning settings.
In combination with Reinforcement Learning, Monte-Carlo Tree Search has shown to outperform human grandmasters in games such as Chess, Shogi and Go with little to no prior domain knowledge. However, most classical use cases only feature up to two players. Scaling the search to an arbitrary number of players presents a computational challenge, especially if decisions have to be planned over a longer time horizon. In this work, we investigate techniques that transform general-sum multiplayer games into single-player and two-player games that consider other agents to act according to given opponent models. For our evaluation, we focus on the challenging Pommerman environment which involves partial observability, a long time horizon and sparse rewards. In combination with our search methods, we investigate the phenomena of opponent modeling using heuristics and self-play. Overall, we demonstrate the effectiveness of our multiplayer search variants both in a supervised learning and reinforcement learning setting.