An AlphaZero-Inspired Approach to Solving Search Problems
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.