Elamur Research
☰
home / papers / 2017 / Mastering chess and shogi by self-play with a general reinforcement learning algorithm

Mastering chess and shogi by self-play with a general reinforcement learning algorithm

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1712.01815

Summary

The paper asks whether a single learning method, given only the rules of a game, can reach top strength in several board games. The strongest chess and shogi engines rely on decades of expert-designed evaluation features and alpha-beta search tuned for each game. The authors present AlphaZero, a generalized form of AlphaGo Zero. It uses no human game records and no game-specific tuning. One deep neural network outputs move probabilities and an expected-outcome value, and the outcome can be a draw as well as a win or loss. These outputs guide a Monte-Carlo tree search (MCTS). The network starts from random weights and improves only by playing against itself, with continuous updates instead of AlphaGo Zero's best-player gating. The same hyper-parameters are used for chess, shogi and Go, and no symmetry augmentation is applied. Within hours of training, AlphaZero beat the champion programs Stockfish, Elmo and AlphaGo Zero. This suggests that general self-taught search can replace handcrafted domain engineering, even though it examines far fewer positions.

Key points

  • Training setup: each game was trained for 700,000 steps with mini-batches of 4,096. Self-play ran on 5,000 first-generation TPUs, and network training used 64 second-generation TPUs.

  • Speed of learning: AlphaZero surpassed Stockfish after about 4 hours (300k steps) and Elmo after under 2 hours (110k steps). It overtook AlphaGo Lee after about 8 hours (165k steps).

  • 100-game matches at 1 minute per move:

    OpponentWinsDrawsLosses
    Stockfish (chess)28720
    Elmo (shogi)9028
    AlphaGo Zero, 3-day version (Go)60–40

  • Search efficiency: AlphaZero evaluates about 80k positions per second in chess and 40k in shogi. Stockfish evaluates about 70M and Elmo about 35M. AlphaZero's MCTS also gained more from extra thinking time than the alpha-beta engines.

  • Chess openings: AlphaZero rediscovered the 12 most popular human openings during self-play. It beat Stockfish when starting from each of them.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Mathematics & statistics

Cited by

139 papers of our library cite it (of the 140673 whose bibliographies we read); 11 of them have a page here, 128 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. arXiv 1712.01815

@misc{anon2017mastering,
  title = {{Mastering chess and shogi by self-play with a general reinforcement learning algorithm}},
  year = {2017},
  eprint = {1712.01815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.01815}
}

References

32 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Online chess games database, 365chess, 2017. URL: https://www.365chess.com/. ↗
  2. Victor Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, University of Limburg, Netherlands, 1994. find
  3. Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 5366–5376, 2017. find
  4. Oleg Arenz. Monte Carlo chess. Master’s thesis, Technische Universitat Darmstadt, 2012. find
  5. Computer Shogi Association. Results of the 27th world computer shogi championship. http://www2.computer-shogi.org/wcsc27/index\_e.html. Retrieved November 29th, 2017. ↗
  6. J. Baxter, A. Tridgell, and L. Weaver. Learning to play chess using temporal differences. Machine Learning, 40(3):243–263, 2000. find
  7. Donald F. Beal and Martin C. Smith. Temporal difference learning for heuristic search and game playing. Inf. Sci., 122(1):3–21, 2000. find
  8. Donald F. Beal and Martin C. Smith. Temporal difference learning applied to game playing and the results of application to shogi. Theoretical Computer Science, 252(1–2):105–119, 2001. find
  9. M. Campbell, A. J. Hoane, and F. Hsu. Deep Blue. Artificial Intelligence, 134:57–83, 2002. find
  10. R. Coulom. Whole-history rating: A Bayesian rating system for players of time-varying strength. In International Conference on Computers and Games, pages 113–124, 2008. find
  11. Omid E David, Nathan S Netanyahu, and Lior Wolf. Deepchess: End-to-end deep neural network for automatic learning in chess. In International Conference on Artificial Neural Networks, pages 88–96. Springer, 2016. find
  12. Kunihito Hoki and Tomoyuki Kaneko. Large-scale optimization for evaluation functions with minimax search. Journal of Artificial Intelligence Research (JAIR), 49:527–568, 2014. find
  13. Feng-hsiung Hsu. Behind Deep Blue: Building the Computer that Defeated the World Chess Champion. Princeton University Press, 2002. find
  14. Hiroyuki Iida, Makoto Sakuta, and Jeff Rollason. Computer shogi. Artificial Intelligence, 134:121–144, 2002. find
  15. Norman P. Jouppi, Cliff Young, Nishant Patil, et al. In-datacenter performance analysis of a tensor processing unit. In Proceedings of the 44th Annual International Symposium on Computer Architecture, ISCA ’17, pages 1–12. ACM, 2017. find
  16. Tomoyuki Kaneko and Kunihito Hoki. Analysis of evaluation-function learning by comparison of sibling nodes. In Advances in Computer Games - 13th International Conference, ACG 2011, Tilburg, The Netherlands, November 20-22, 2011, Revised Selected Papers, pages 158–169, 2011. find
  17. John Knudsen. Essential Chess Quotations. iUniverse, 2000. find
  18. D. E. Knuth and R. W Moore. An analysis of alphabeta pruning. Artificial Intelligence, 6(4):293–326, 1975. find
  19. Matthew Lai. Giraffe: Using deep reinforcement learning to play chess. Master’s thesis, Imperial College London, 2015. find
  20. Emanuel Lasker. Common Sense in Chess. Dover Publications, 1965. find
  21. David N. L. Levy and Monty Newborn. How Computers Play Chess. Ishi Press, 2009. find
  22. Chris J. Maddison, Aja Huang, Ilya Sutskever, and David Silver. Move evaluation in Go using deep convolutional neural networks. In International Conference on Learning Representations, 2015. find
  23. Tony Marsland. Computer chess methods. In S. Shapiro, editor, Encyclopedia of Artificial Intelligence. John Wiley & sons, New York, 1987. find
  24. Raghuram Ramanujan, Ashish Sabharwal, and Bart Selman. Understanding sampling style adversarial search methods. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI), 2010. find
  25. Tord Romstad, Marco Costalba, Joona Kiiski, et al. Stockfish: A strong open source chess engine. https://stockfishchess.org/. Retrieved November 29th, 2017. ↗
  26. A. L. Samuel. Some studies in machine learning using the game of checkers II - recent progress. IBM Journal of Research and Development, 11(6):601–617, 1967. find
  27. Claude E Shannon. Xxii. programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314):256–275, 1950. find
  28. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukc… find
  29. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go withou… find
  30. Wilhelm Steinitz. The Modern Chess Instructor. Edition Olms AG, 1990. find
  31. Sebastian Thrun. Learning to play the game of chess. In Advances in neural information processing systems, pages 1069–1076, 1995. find
  32. J. Veness, D. Silver, A. Blair, and W. Uther. Bootstrapping from game tree search. In Advances in Neural Information Processing Systems, pages 1937–1945, 2009. Methods Anatomy of a Computer Chess Program find