2022/07/02 by Evgeny Dantsin, Dantsin, Evgeny, Владик Крейнович +3
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Artificial Intelligence in Games #FOS: Computer and information sciences #I.2 #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.2207.00919
openalex publication_date 2022/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.