Optimizations over neural MCTS for solving combinatorial problems
Prashank Kadam · 2020
AlphaZero, using a combination of Deep Neural Networks and Monte Carlo Tree Search (MCTS), has successfully trained reinforcement learning agents in a tabula-rasa way. The neural MCTS algorithm has been successful in finding near-optimal strategies for games through self-play. However, the AlphaZero algorithm has a significant drawback; it takes a long time to converge due to a large number of policy updates before reaching the optimal strategy and requires high computational power due to complex neural networks for solving games like Chess, Go, Shogi, etc. Owing to this, it is very difficult to pursue neural MCTS research without cutting-edge hardware, which is a roadblock for many aspiring neural MCTS researchers. As a part of this thesis, we propose multiple techniques to accelerate the training. Along with this we also propose two new neural MCTS algorithms, called Meta MPV-MCTS and Dual MCTS, which help overcome these drawbacks. Both these algorithms use two different search trees instead of a single one in AlphaZero for the purpose of providing lookahead, along with a novel technique to reduce the number of updates made to the tree and can be extended to any MCTS based algorithms. We evaluate these enhancements along without newly proposed algorithms over different types of symmetric as well as asymmetric games. We show various strategies through which asymmetric games can be trained more efficiently. Finally, we have developed a grammar which we call Persophone-S which can be used for defining two-player first order logic-based games. This grammar can be used for defining real-world problems in games and then evaluating these definitions with our algorithms.--Author's abstract