An AlphaZero-Inspired Approach to Solving Search Problems
This work addresses the challenge of applying game-playing AI techniques to general search problems, which could benefit researchers in AI and optimization, though it appears incremental as it builds on existing AlphaZero methods.
The paper tackles the problem of adapting AlphaZero's reinforcement learning methods to solve search problems like Boolean satisfiability, by proposing representations using easy-instance solvers and self-reductions, and developing a modified Monte Carlo tree search for this purpose.
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.