Monte Carlo tree search

In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.

MCTS was combined with neural networks in 2016^[1] and has been used in multiple board games like Chess, Shogi,^[2] Checkers, Backgammon, Contract Bridge, Go, Scrabble, and Clobber^[3] as well as in turn-based-strategy video games (such as Total War: Rome II's implementation in the high level campaign AI^[4]) and applications outside of games.^[5]

^ Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.
^ Silver, David (2017). "Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm". arXiv:1712.01815v1 [cs.AI].
^ Rajkumar, Prahalad. "A Survey of Monte-Carlo Techniques in Games" (PDF). cs.umd.edu. Archived (PDF) from the original on 2023-04-07.
^ "Monte-Carlo Tree Search in TOTAL WAR: ROME II's Campaign AI". AI Game Dev. Archived from the original on 13 March 2017. Retrieved 25 February 2017.
^ Kemmerling, Marco; Lütticke, Daniel; Schmitt, Robert H. (1 January 2024). "Beyond games: a systematic review of neural Monte Carlo tree search applications". Applied Intelligence. 54 (1): 1020–1046. arXiv:2303.08060. doi:10.1007/s10489-023-05240-w. ISSN 1573-7497.

Monte Carlo tree search

Class	Search algorithm