Improving AlphaZero Using Monte-Carlo Graph Search

Authors

  • Johannes Czech TU Darmstadt
  • Patrick Korus TU Darmstadt
  • Kristian Kersting TU Darmstadt Hessian Center for Artificial Intelligence

DOI:

https://doi.org/10.1609/icaps.v31i1.15952

Keywords:

Classical Planning Techniques And Analysis, Applications And Case Studies Of Planning And Scheduling Techniques, Learning For Planning And Scheduling, Multi-agent And Distributed Planning

Abstract

The AlphaZero algorithm has been successfully applied in a range of discrete domains, most notably board games. It utilizes a neural network that learns a value and policy function to guide the exploration in a Monte-Carlo Tree Search. Although many search improvements such as graph search have been proposed for Monte-Carlo Tree Search in the past, most of them refer to an older variant of the Upper Confidence bounds for Trees algorithm that does not use a policy for planning. We improve the search algorithm for AlphaZero by generalizing the search tree to a directed acyclic graph. This enables information flow across different subtrees and greatly reduces memory consumption. Along with Monte-Carlo Graph Search, we propose a number of further extensions, such as the inclusion of Epsilon-Greedy exploration, a revised terminal solver and the integration of domain knowledge as constraints. In our empirical evaluations, we use the CrazyAra engine on chess and crazyhouse as examples to show that these changes bring significant improvements to AlphaZero.

Downloads

Published

2021-05-17

How to Cite

Czech, J., Korus, P., & Kersting, K. (2021). Improving AlphaZero Using Monte-Carlo Graph Search. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 103-111. https://doi.org/10.1609/icaps.v31i1.15952