An AlphaZero-Inspired Approach to Solving Search Problems

• URL: http://arxiv.org/abs/2207.00919v1
• Date: Sat, 2 Jul 2022 23:39:45 GMT
• Title: An AlphaZero-Inspired Approach to Solving Search Problems
• Authors: Evgeny Dantsin, Vladik Kreinovich, and Alexander Wolpert
• Abstract summary: We adapt the methods and techniques used in AlphaZero for solving search problems. We describe possible representations in terms of easy-instance solvers and self-reductions. We also describe a version of Monte Carlo tree search adapted for search problems.
• Score: 63.24965775030674
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: AlphaZero and its extension MuZero are computer programs that use machine-learning techniques to play at a superhuman level in chess, go, and a few other games. They achieved this level of play solely with reinforcement learning from self-play, without any domain knowledge except the game rules. It is a natural idea to adapt the methods and techniques used in AlphaZero for solving search problems such as the Boolean satisfiability problem (in its search version). Given a search problem, how to represent it for an AlphaZero-inspired solver? What are the "rules of solving" for this search problem? We describe possible representations in terms of easy-instance solvers and self-reductions, and we give examples of such representations for the satisfiability problem. We also describe a version of Monte Carlo tree search adapted for search problems.

Related papers

• Semi-Strongly solved: a New Definition Leading Computer to Perfect Gameplay [0.0]
  Several definitions exist for solving the game,' but they are markedly different regarding computational cost and the detail of insights derived. We introduce a novel definition called semi-strongly solved' and propose an algorithm to achieve this type of solution efficiently.
  arXiv  Detail & Related papers  (2024-11-01T21:00:46Z)
• People use fast, goal-directed simulation to reason about novel games [75.25089384921557]
  We study how people reason about a range of simple but novel connect-n style board games. We ask people to judge how fair and how fun the games are from very little experience.
  arXiv  Detail & Related papers  (2024-07-19T07:59:04Z)
• Game Solving with Online Fine-Tuning [17.614045403579244]
  This paper investigates applying online fine-tuning while searching and proposes two methods to learn tailor-designed computations for game solving. Our experiments show that using online fine-tuning can solve a series of challenging 7x7 Killall-Go problems, using only 23.54% of time compared to the baseline.
  arXiv  Detail & Related papers  (2023-11-13T09:09:52Z)
• AlphaZero Gomoku [9.434566356382529]
  We broaden the use of AlphaZero to Gomoku, an age-old tactical board game also referred to as "Five in a Row" Our tests demonstrate AlphaZero's versatility in adapting to games other than Go.
  arXiv  Detail & Related papers  (2023-09-04T00:20:06Z)
• 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)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• A Novel Approach to Solving Goal-Achieving Problems for Board Games [8.882671058559016]
  This paper first proposes a novel RZ-based approach, called the RZ-Based Search (RZS) to solving L&D problems for Go. RZS tries moves before determining whether they are null moves post-hoc. We also propose a new training method called Faster to Life (FTL), which modifies AlphaZero to entice it to win more quickly.
  arXiv  Detail & Related papers  (2021-12-05T13:23:10Z)
• Solving QSAT problems with neural MCTS [0.0]
  Recent achievements from AlphaZero using self-play has shown remarkable performance on several board games. In this paper, we try to leverage the computational power of neural Monte Carlo Tree Search (neural MCTS), the core algorithm from AlphaZero. Knowing that every QSAT problem is equivalent to a QSAT game, the game outcome can be used to derive the solutions of the original QSAT problems.
  arXiv  Detail & Related papers  (2021-01-17T08:20:07Z)
• Monte-Carlo Tree Search as Regularized Policy Optimization [47.541849128047865]
  We show that AlphaZero's search algorithms are an approximation to the solution of a specific regularized policy optimization problem. We propose a variant of AlphaZero which uses the exact solution to this policy optimization problem, and show experimentally that it reliably outperforms the original algorithm in multiple domains.
  arXiv  Detail & Related papers  (2020-07-24T13:01:34Z)
• Provable Self-Play Algorithms for Competitive Reinforcement Learning [48.12602400021397]
  We study self-play in competitive reinforcement learning under the setting of Markov games. We show that a self-play algorithm achieves regret $tildemathcalO(sqrtT)$ after playing $T$ steps of the game. We also introduce an explore-then-exploit style algorithm, which achieves a slightly worse regret $tildemathcalO(T2/3)$, but is guaranteed to run in time even in the worst case.
  arXiv  Detail & Related papers  (2020-02-10T18:44:50Z)

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.