Injecting Combinatorial Optimization into MCTS: Application to the Board Game boop
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.
Code (1)
Tasks
Board GamesCombinatorial OptimizationSimilar Papers 제목 키워드 기반
Learning Self-Game-Play Agents for Combinatorial Optimization Problems
Recent progress in reinforcement learning (RL) using self-game-play has shown remarkable performance on several board games (e.g., Chess and Go) as well as video games (e.g., Atari games and Dota2). It is plausible to co…
Atari GamesBoard GamesCombinatorial OptimizationReinforcement Learning+1Practical Massively Parallel Monte-Carlo Tree Search Applied to Molecular Design
It is common practice to use large computational resources to train neural networks, as is known from many examples, such as reinforcement learning applications. However, while massively parallel computing is often used …
Combinatorial OptimizationCPUAdaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem
The Flexible Job-Shop Scheduling Problem (FJSSP) is an NP-hard combinatorial optimization problem, with several application domains, especially for manufacturing purposes. The objective is to efficiently schedule multipl…
Combinatorial OptimizationJob Shop SchedulingSchedulingAlphaMapleSAT: An MCTS-based Cube-and-Conquer SAT Solver for Hard Combinatorial Problems
This paper introduces AlphaMapleSAT, a novel Monte Carlo Tree Search (MCTS) based Cube-and-Conquer (CnC) SAT solving method aimed at efficiently solving challenging combinatorial problems. Despite the tremendous success …
Heuristic SearchSurrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization
Industries frequently adjust their facilities network by opening new branches in promising areas and closing branches in areas where they expect low profits. In this paper, we examine a particular class of facility locat…
Combinatorial Optimization