# On the Evolution of the MCTS Upper Confidence Bounds for Trees by Means of Evolutionary Algorithms in the Game of Carcassonne

arXiv: https://arxiv.org/abs/2112.09697 · HTML: https://mlsanity.com/paper/2112.09697/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 17 Dec 2021.

## Builds on (most cited first, 8 of 8)

- [AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1903.11059/) (2019)
- [Neuroevolution in Deep Neural Networks: Current Trends and Future Challenges](https://mlsanity.com/paper/2006.05415/) (2020)
- [Semantics in Multi-objective Genetic Programming](https://mlsanity.com/paper/2105.02944/) (2021)
- [Semantic-based Distance Approaches in Multi-objective Genetic Programming](https://mlsanity.com/paper/2009.12401/) (2020)
- [Semantic Neighborhood Ordering in Multi-objective Genetic Programming based on Decomposition](https://mlsanity.com/paper/2103.00480/) (2021)
- [Playing Carcassonne with Monte Carlo Tree Search](https://mlsanity.com/paper/2009.12974/) (2020)
- [Statistical Tree-based Population Seeding for Rolling Horizon EAs in General Video Game Playing](https://mlsanity.com/paper/2008.13253/) (2020)
- [Promoting Semantics in Multi-objective Genetic Programming based on Decomposition](https://mlsanity.com/paper/2012.04717/) (2020)

## Built on by (most cited first, 2 of 2)

- [Broaden your SCOPE! Efficient Multi-turn Conversation Planning for LLMs with Semantic Space](https://mlsanity.com/paper/2503.11586/) (2025)
- [Towards Understanding the Effects of Evolving the MCTS UCT Selection Policy](https://mlsanity.com/paper/2302.03352/) (2023)

## Abstract (arXiv)

Monte Carlo Tree Search (MCTS) is a sampling best-first method to search for optimal decisions. The MCTS's popularity is based on its extraordinary results in the challenging two-player based game Go, a game considered much harder than Chess and that until very recently was considered infeasible for Artificial Intelligence methods. The success of MCTS depends heavily on how the tree is built and the selection process plays a fundamental role in this. One particular selection mechanism that has proved to be reliable is based on the Upper Confidence Bounds for Trees, commonly referred as UCT. The UCT attempts to nicely balance exploration and exploitation by considering the values stored in the statistical tree of the MCTS. However, some tuning of the MCTS UCT is necessary for this to work well. In this work, we use Evolutionary Algorithms (EAs) to evolve mathematical expressions with the goal to substitute the UCT mathematical expression. We compare our proposed approach, called Evolution Strategy in MCTS (ES-MCTS) against five variants of the MCTS UCT, three variants of the star-minimax family of algorithms as well as a random controller in the Game of Carcassonne. We also use a variant of our proposed EA-based controller, dubbed ES partially integrated in MCTS. We show how the ES-MCTS controller, is able to outperform all these 10 intelligent controllers, including robust MCTS UCT controllers.