The DOI matches its DataCite record; 1 of the 1 references it cites were found in a registry or an index.
Monte-Carlo Graph Search for AlphaZero
Open accessAbstract
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 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 introduce a new, improved search algorithm for AlphaZero which generalizes 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 evaluations, we use the CrazyAra engine on chess and crazyhouse as examples to show that these changes bring significant improvements to AlphaZero.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Neuroscience-Inspired Artificial Intelligence
Hassabis, D., Kumaran, D., Summerfield, C., & Botvinick, M. (2017) · Neuron · doi:10.1016/j.neuron.2017.06.011 · Cited by 1,557 · cited 1×
“The planning process of most humans for discrete domains resembles the AlphaZero Monte-Carlo Tree Search (MCTS) variant (Silver et al., 2017) which uses a guidance policy as its prior and an evaluation function to distinguish between good and bad positions (Hassabis et al., 2017).”
Method
Research works printed but not linked: 13
- [1][1] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 'Finite-time analysis of the multiarmed bandit problem'. In: Machine learning 47.2-3 (2002), pp. 235256. -
- [2][2] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. 'A Survey of Monte Carlo Tree Search Methods'. In: IEEE Transactions on Computational Intelligence and AI in Games 4.1 (2012), pp. 1-43. DOI: 10.1109/TCIAIG. 2012.2186810. - · DOI
- [3][3] Yen-Chi Chen, Chih-Hung Chen, and Shun-Shii Lin. 'Exact-win strategy for overcoming AlphaZero'. In: Proceedings of the 2018 International Conference on Computational Intelligence and Intelligent Systems . 2018, pp. 26-31. -
- [5][5] Johannes Czech, Moritz Willig, Alena Beyer, Kristian Kersting, and Johannes F¨ urnkranz. 'Learning to Play the Chess Variant Crazyhouse Above World Champion Level With Deep Neural Networks and Human Data'. In: Frontiers in Artificial Intelligence 3 (2020), p. 24. ISSN: 2624-8212. DOI: 10 . 3389 / frai.2020.00024. URL: https://www.frontiersin.org/ article/10.3389/frai.2020.00024. - · DOI
- [7][7] Sylvain Gelly and David Silver. 'Monte-Carlo tree search and rapid action value estimation in computer Go'. In: Artificial Intelligence 175.11 (2011), pp. 1856-1875. -
- [10][10] Christopher D Rosin. 'Multi-armed bandits with episode context'. In: Annals of Mathematics and Artificial Intelligence 61.3 (2011), pp. 203-230. -
- [11][11] Abdallah Saffidine, Tristan Cazenave, and Jean M´ ehat. 'UCD: Upper Confidence bound for rooted Directed acyclic graphs'. In: Knowledge-Based Systems 34 (2012), pp. 26-33. -
- [12][12] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 'Mastering the game of go without human knowledge'. In: nature 550.7676 (2017), pp. 354-359. -
- [13][13] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 'Dropout: a simple way to prevent neural networks from overfitting'. In: The journal of machine learning research 15.1 (2014), pp. 19291958. -
- [14][14] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction . MIT press, 2018. -
- [15][15] Christopher JCH Watkins and Peter Dayan. 'Qlearning'. In: Machine learning 8.3-4 (1992), pp. 279-292. -
- [16][16] Mark HM Winands, Yngvi Bj¨ ornsson, and JahnTakeshi Saito. 'Monte-Carlo tree search solver'. In: International Conference on Computers and Games . Springer. 2008, pp. 25-36. -
- [18][18] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. 'Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity'. In: International Conference on Learning Representations . 2020. URL: https://openreview.net/forum? id=BJgnXpVYwS.
Cited by
Sorted by citations
MLEvolve: A Self-Evolving Framework for Automated Machine Learning Algorithm Discovery
Du, S., Yan, X., Shi, J., Cao, Z., Feng, S., Liang, Z., Sun, B., Guo, X., Peng, T., Zhou, Y., et al. (2026) · arXiv · doi:10.48550/arxiv.2606.06473 · Cited by 31
Metadata
- Authors
- Czech, J., Korus, P., & Kersting, K.
- Affiliations
- Technische Universität Darmstadt (DE)
- ORCID
- Czech, Johannes
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2020
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2012.11045
- OpenAlex
- W3117497722
- Cited by
- 3
- References
- 1
- Citations by year
- 2024: 1 · 2023: 1 · 2021: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Keywords
- AlphaZero, Monte Carlo tree search, directed acyclic graphs, search tree exploration, epsilon-greedy exploration, domain knowledge constraints, chess, memory reduction
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
