Injecting Combinatorial Optimization into MCTS: Application to the Board Game boop

• URL: http://arxiv.org/abs/2406.08766v1
• Date: Thu, 13 Jun 2024 02:55:08 GMT
• Title: Injecting Combinatorial Optimization into MCTS: Application to the Board Game boop
• Authors: Florian Richoux,
• Abstract summary: Combinatorial Optimization and Monte Carlo Tree Search can be combined efficiently. Our method beats 96% of the time the Monte Carlo Tree Search algorithm baseline. We opposed our AI method against human players on the Board Game Arena platform.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Games, including abstract board games, constitute a convenient ground to create, design, and improve new AI methods. In this field, Monte Carlo Tree Search is a popular algorithm family, aiming to build game trees and explore them efficiently. Combinatorial Optimization, on the other hand, aims to model and solve problems with an objective to optimize and constraints to satisfy, and is less common in Game AI. We believe however that both methods can be combined efficiently, by injecting Combinatorial Optimization into Monte Carlo Tree Search to help the tree search, leading to a novel combination of these two techniques. Tested on the board game boop., our method beats 96% of the time the Monte Carlo Tree Search algorithm baseline. We conducted an ablation study to isolate and analyze which injections and combinations of injections lead to such performances. Finally, we opposed our AI method against human players on the Board Game Arena platform, and reached a 373 ELO rating after 51 boop. games, with a 69% win rate and finishing ranked 56th worldwide on the platform over 5,316 boop. players.

Related papers

• Scattered Forest Search: Smarter Code Space Exploration with LLMs [55.71665969800222]
  We introduce Scattered Forest Search to enhance solution diversity while searching for solutions. Experiments on HumanEval, MBPP, APPS, CodeContests, and Leetcode reveal significant performance improvements.
  arXiv  Detail & Related papers  (2024-10-22T01:58:29Z)
• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  We formulate a new variant of multi-player multi-armed bandit (MAB) model, which captures arrival of requests to each arm and the policy of allocating requests to players. The challenge is how to design a distributed learning algorithm such that players select arms according to the optimal arm pulling profile. We design an iterative distributed algorithm, which guarantees that players can arrive at a consensus on the optimal arm pulling profile in only M rounds.
  arXiv  Detail & Related papers  (2024-08-20T13:57:00Z)
• Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
  We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
  arXiv  Detail & Related papers  (2023-07-25T12:33:53Z)
• Know your Enemy: Investigating Monte-Carlo Tree Search with Opponent Models in Pommerman [14.668309037894586]
  In combination with Reinforcement Learning, Monte-Carlo Tree Search has shown to outperform human grandmasters in games such as Chess, Shogi and Go. We investigate techniques that transform general-sum multiplayer games into single-player and two-player games.
  arXiv  Detail & Related papers  (2023-05-22T16:39:20Z)
• Proof Number Based Monte-Carlo Tree Search [1.93674821880689]
  This paper proposes a new game-search algorithm, PN-MCTS, which combines Monte-Carlo Tree Search (MCTS) and Proof-Number Search (PNS) We define three areas where the additional knowledge provided by the proof and disproof numbers gathered in MCTS trees might be used. Experiments show that PN-MCTS is able to outperform MCTS in all tested game domains, achieving win rates up to 96.2% for Lines of Action.
  arXiv  Detail & Related papers  (2023-03-16T16:27:07Z)
• MCTS Based Agents for Multistage Single-Player Card Game [0.0]
  The article presents the use of Monte Carlo Tree Search algorithms for the card game Lord of the Rings. The main challenge was the complexity of the game mechanics, in which each round consists of 5 decision stages and 2 random stages. To test various decision-making algorithms, a game simulator has been implemented.
  arXiv  Detail & Related papers  (2021-09-24T10:56:54Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Learning to Play Imperfect-Information Games by Imitating an Oracle Planner [77.67437357688316]
  We consider learning to play multiplayer imperfect-information games with simultaneous moves and large state-action spaces. Our approach is based on model-based planning. We show that the planner is able to discover efficient playing strategies in the games of Clash Royale and Pommerman.
  arXiv  Detail & Related papers  (2020-12-22T17:29:57Z)
• Monte Carlo Tree Search for a single target search game on a 2-D lattice [0.0]
  This project imagines a game in which an AI player searches for a stationary target within a 2-D lattice. We analyze its behavior with different target distributions and compare its efficiency to the Levy Flight Search, a model for animal foraging behavior.
  arXiv  Detail & Related papers  (2020-11-29T01:07:45Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• 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)

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.