Algorithmes de recherche basés sur l'échantillonnage dans les jeux
Jérôme Arjonilla · theses.fr (ABES) · 2024
Algorithm research in the context of games is a highly active field. Games are a prime application domain for search algorithms because they allow for the modeling and efficient resolution of complex problems. Many algorithms were first developed for games before being extended to other domains. In this thesis, we focus on heuristic search algorithms in the context of games, particularly heuristic search algorithms based on sampling, such as Monte Carlo Tree Search (MCTS) in perfect information, and based on determinization in imperfect information. We also explore the integration of search algorithms with other types of algorithms, especially reinforcement learning algorithms. We present existing methods as well as several original contributions in this field. The first part of the thesis is dedicated to the study of domain-independent heuristic search algorithms, making them easily testable and applicable in various contexts. Specifically, we focus on games with imperfect information, where players do not know all the details about the game state. In these types of algorithms and games, certain problems arise with existing methods, particularly issues related to strategy fusion and the impact of information revelation. We will discuss these problems in detail and present two original methods to address them. The second part of the thesis explores domain-dependent heuristic search algorithms. Domain-dependent algorithms are often more efficient than domain-independent ones because they can learn, generalize, and adapt to a specific domain. Throughout this part, we investigate the integration of heuristic search algorithms with other types of algorithms, particularly reinforcement learning algorithms. We present an original contribution in this area and another contribution that is currently under development. The first method proposes to enhance search algorithms by integrating reinforcement learning algorithms based on the guiding principle. The second method aims to incorporate model-based methods into searches in imperfect information settings.