MAPLE: Multi-State Aggregated Policy Evaluation for AlphaZero in Imperfect-Information Games

• URL: http://arxiv.org/abs/2605.24139v1
• Date: Fri, 22 May 2026 18:59:01 GMT
• Title: MAPLE: Multi-State Aggregated Policy Evaluation for AlphaZero in Imperfect-Information Games
• Abstract summary: We propose a tree search method that aggregates policy and value evaluations from multiple sampled world states within a single search tree.<n>Experiments on Phantom Go and Dark Hex show that MAPLE significantly outperforms the PIMC-based AlphaZero baseline.<n>These results demonstrate that MAPLE is an effective approach for AlphaZero-style learning in imperfect-information games.
• Score: 11.496240939986507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Imperfect-information games (IIGs) are challenging, as players must make decisions without fully observing the true game state. While AlphaZero has achieved remarkable success in perfect-information games, extending it to IIGs remains difficult. Existing search-based approaches, such as Perfect Information Monte Carlo (PIMC), suffer from strategy fusion, while Information Set Monte Carlo Tree Search (IS-MCTS) incurs high computational cost when combined with neural networks. In this paper, we propose Multi-State Aggregated PoLicy Evaluation (MAPLE), a tree search method that aggregates policy and value evaluations from multiple sampled world states within a single search tree, combining the advantages of PIMC and IS-MCTS while maintaining a controllable computational cost. We further incorporate a Siamese-based sampling strategy to select informative world states from the information set. Experiments on Phantom Go and Dark Hex show that MAPLE significantly outperforms the PIMC-based AlphaZero baseline, achieving Elo improvements of 291 and 136, respectively. These results demonstrate that MAPLE is an effective approach for AlphaZero-style learning in imperfect-information games.

Related papers

• Holistically Guided Monte Carlo Tree Search for Intricate Information Seeking [118.3983437282541]
  We introduce an LLM-based search assistant that adopts a new information seeking paradigm with holistically guided Monte Carlo tree search (HG-MCTS)<n>We reformulate the task as a progressive information collection process with a knowledge memory and unite an adaptive checklist with multi-perspective reward modeling in MCTS.<n>Our multi-perspective reward modeling offers both exploration and retrieval rewards, along with progress feedback that tracks completed and remaining sub-goals.
  arXiv  Detail & Related papers  (2025-02-07T08:36:39Z)
• Improve Value Estimation of Q Function and Reshape Reward with Monte Carlo Tree Search [0.4450107621124637]
  Reinforcement learning has achieved remarkable success in perfect information games such as Go and Atari. Research in reinforcement learning for imperfect information games has been relatively limited due to the more complex game structures and randomness. In this paper, we focus on Uno, an imperfect information game, and aim to address these problems by reducing Q value overestimation and reshaping reward function.
  arXiv  Detail & Related papers  (2024-10-15T14:31:54Z)
• Perfect Information Monte Carlo with Postponing Reasoning [4.111084095218968]
  This research introduces Extended Perfect Information Monte Carlo' (EPIMC), an online algorithm inspired by the state-of-the-art determinization-based approach Perfect Information Monte Carlo (PIMC) EPIMC postpones the perfect information resolution, reducing alleviating issues related to strategy fusion. Our results demonstrate notable performance enhancements, particularly in games where strategy fusion significantly impacts gameplay.
  arXiv  Detail & Related papers  (2024-08-05T11:12:48Z)
• Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning [55.96599486604344]
  We introduce an approach aimed at enhancing the reasoning capabilities of Large Language Models (LLMs) through an iterative preference learning process. We use Monte Carlo Tree Search (MCTS) to iteratively collect preference data, utilizing its look-ahead ability to break down instance-level rewards into more granular step-level signals. The proposed algorithm employs Direct Preference Optimization (DPO) to update the LLM policy using this newly generated step-level preference data.
  arXiv  Detail & Related papers  (2024-05-01T11:10:24Z)
• How Far Are We on the Decision-Making of LLMs? Evaluating LLMs' Gaming Ability in Multi-Agent Environments [83.78240828340681]
  GAMA($gamma$)-Bench is a new framework for evaluating Large Language Models' Gaming Ability in Multi-Agent environments.<n>$gamma$-Bench includes eight classical game theory scenarios and a dynamic scoring scheme specially designed to assess LLMs' performance.<n>Our results indicate GPT-3.5 demonstrates strong robustness but limited generalizability, which can be enhanced using methods like Chain-of-Thought.
  arXiv  Detail & Related papers  (2024-03-18T14:04:47Z)
• Prompt Tuning for Zero-shot Compositional Learning [53.090335182962605]
  We propose a framework named Multi-Modal Prompt Tuning (MMPT) to inherit the "knowledgeable" property from the large pre-trained vision-language model. On the UT-Zappos dataset, MMPT pushes the AUC score to $29.8$, while the previous best score is $26.5$. On the more challenging MIT-States dataset, the AUC score of MMPT is 1.5 times better than the current state-of-the-art.
  arXiv  Detail & Related papers  (2023-12-02T07:32:24Z)
• LightZero: A Unified Benchmark for Monte Carlo Tree Search in General Sequential Decision Scenarios [32.83545787965431]
  Building agents based on tree-search planning capabilities with learned models has achieved remarkable success in classic decision-making problems, such as Go and Atari. It has been deemed challenging or even infeasible to extend Monte Carlo Tree Search (MCTS) based algorithms to diverse real-world applications. In this work, we introduce LightZero, the first unified benchmark for deploying MCTS/MuZero in general sequential decision scenarios.
  arXiv  Detail & Related papers  (2023-10-12T14:18:09Z)
• Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learning [65.36326734799587]
  We present a novel subgame curriculum learning framework for zero-sum games. It adopts an adaptive initial state distribution by resetting agents to some previously visited states. We derive a subgame selection metric that approximates the squared distance to NE values.
  arXiv  Detail & Related papers  (2023-10-07T13:09:37Z)
• Combining Off and On-Policy Training in Model-Based Reinforcement Learning [77.34726150561087]
  We propose a way to obtain off-policy targets using data from simulated games in MuZero. Our results show that these targets speed up the training process and lead to faster convergence and higher rewards.
  arXiv  Detail & Related papers  (2021-02-24T10:47:26Z)
• Learning to Stop: Dynamic Simulation Monte-Carlo Tree Search [66.34387649910046]
  Monte Carlo tree search (MCTS) has achieved state-of-the-art results in many domains such as Go and Atari games. We propose to achieve this goal by predicting the uncertainty of the current searching status and use the result to decide whether we should stop searching.
  arXiv  Detail & Related papers  (2020-12-14T19:49:25Z)
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search [8.22379888383833]
  Combination of Monte-Carlo Tree Search (MCTS) and deep reinforcement learning is state-of-the-art in two-player perfect-information games. We describe a search algorithm that uses a variant of MCTS which we enhanced by 1) a novel action value normalization mechanism for games with potentially unbounded rewards, 2) defining a virtual loss function that enables effective search parallelization, and 3) a policy network, trained by generations of self-play, to guide the search.
  arXiv  Detail & Related papers  (2020-05-22T18:02:36Z)
• Competing in a Complex Hidden Role Game with Information Set Monte Carlo Tree Search [0.0]
  The Information Set Monte Carlo Tree Search (ISMCTS) family of algorithms outperforms previous algorithms using Monte Carlo methods in imperfect information games. This paper is applied to Secret Hitler, a popular social deduction board game that combines traditional hidden role mechanics with the randomness of a card deck.
  arXiv  Detail & Related papers  (2020-05-14T17:21:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.