Valdez Ameneyro, Fred (2024) Analysing the Impacts of Dynamically Evolving Selection Policies in Monte Carlo Tree Search Through Evolutionary Algorithms. PhD thesis, National University of Ireland Maynooth.

Download (4MB)

Abstract

This thesis presents an innovative exploration into the synergy between Monte Carlo Tree Search (MCTS) and Evolutionary Algorithms (EAs), focusing on the evolution of selection policies within MCTS. MCTS, a powerful and versatile algorithm, has seen widespread adoption in various domains, from strategic gaming to robotics, due to its ability to effectively navigate large and complex decision spaces. However, the adaptability of its selection policy, a critical factor in its performance, remains a challenging aspect that demands further research. The primary aim of this work is to investigate how evolutionary processes can be harnessed to adaptively evolve MCTS’s selection policies online, thus enhancing the algorithm’s efficiency and robustness in different problem landscapes, as well as in different stages of the search. By integrating EAs into MCTS, this thesis explores the dynamic and context-aware exploration of the search space, potentially surpassing the performance of traditional approaches. The thesis lays the groundwork for understanding the fundamentals of MCTS and EA embeddings for online decision-making. It offers a detailed survey on the integration of MCTS and EAs, particularly focusing on enhancing MCTS’s selection policy without prior exposure to the domain. A series of test problems, including the Function Optimisation Problem and proposed simplifications of the board game Carcassonne, provide a platform to evaluate the interaction between MCTS’s tree policy and game tree characteristics. Empirical analyses of evolved selection policies are presented, comparing them with traditional MCTS and Minimax approaches and assessing their performance. The thesis aims to contribute significantly to AI and decision-making algorithms by advancing the integration of evolutionary strategies within MCTS. It focuses on developing adaptable and effective selection policies, examining the role of every aspect of the evolutionary processes, and refining EA integration for enhanced decision-making efficiency in MCTS.

Item Type:	Thesis (PhD)
Keywords:	Impacts; Dynamically Evolving Selection Policies; Monte Carlo Tree Search; Evolutionary Algorithms;
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	18627
Depositing User:	IR eTheses
Date Deposited:	10 Jun 2024 13:37
URI:
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads