# Learning Self-Game-Play Agents for Combinatorial Optimization Problems

arXiv: https://arxiv.org/abs/1903.03674 · HTML: https://mlsanity.com/paper/1903.03674/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2019.

## Built on by (most cited first, 7 of 7)

- [Beyond Games: A Systematic Review of Neural Monte Carlo Tree Search Applications](https://mlsanity.com/paper/2303.08060/) (2023)
- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Self-play Learning Strategies for Resource Assignment in Open-RAN Networks](https://mlsanity.com/paper/2103.02649/) (2021)
- [First-Order Problem Solving through Neural MCTS based Reinforcement Learning](https://mlsanity.com/paper/2101.04167/) (2021)
- [Solving QSAT problems with neural MCTS](https://mlsanity.com/paper/2101.06619/) (2021)
- [Dual Monte Carlo Tree Search](https://mlsanity.com/paper/2103.11517/) (2021)
- [Learning to Play: Reinforcement Learning and Games](https://mlsanity.com/paper/2610.17391/) (2026)

## Abstract (arXiv)

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 consider that RL, starting from zero knowledge, might be able to gradually approximate a winning strategy after a certain amount of training. In this paper, we explore neural Monte-Carlo-Tree-Search (neural MCTS), an RL algorithm which has been applied successfully by DeepMind to play Go and Chess at a super-human level. We try to leverage the computational power of neural MCTS to solve a class of combinatorial optimization problems. Following the idea of Hintikka's Game-Theoretical Semantics, we propose the Zermelo Gamification (ZG) to transform specific combinatorial optimization problems into Zermelo games whose winning strategies correspond to the solutions of the original optimization problem. The ZG also provides a specially designed neural MCTS. We use a combinatorial planning problem for which the ground-truth policy is efficiently computable to demonstrate that ZG is promising.