Exploring Explainable Multi-agent MCTS-minimax Hybrids in Board Game Using Process Mining

Yiyu Qian Tim Miller Zheng Qian Liyuan Zhao · 2025

Read Exploring Explainable Multi-agent MCTS-minimax Hybrids in Board Game Using Process Mining by Yiyu Qian Tim Miller Zheng Qian Liyuan Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23326.txt.

Introduction

Yiyu Qian, Tim Miller, Zheng Qian, and Liyuan Zhao make game-playing search agents explain themselves by mining logs of their own behavior, in a paper from twenty twenty-five. Monte Carlo tree search drives many planning breakthroughs, but its giant trees of simulated futures are hard for people to read. A known weakness is tunnel vision: the selective tree can miss crucial moves and walk into traps.

The team weaves shallow full-width minimax search into the rollout phase of a multi-agent version, patching the blind spot. Process mining then reconstructs readable strategies from the agents' play in three-versus-three checkers. The work is ongoing, aimed at agents whose plans humans can audit.

Catalog record

CREATORYiyu Qian Tim Miller Zheng Qian Liyuan Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-23326

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exploring Explainable Multi-agent MCTS-minimax Hybrids in Board Game Using Process Mining Yiyu Qian Tim Miller Zheng Qian Liyuan Zhao Abstract Monte-Carlo Tree Search (MCTS) is a family of sampling-based search algorithms widely used for online planning in sequential decision-making domains and at the heart of many recent advances in artificial intelligence. Understanding the behavior of MCTS agents is difficult for developers and users due to the frequently large and complex search trees that result from the simulation of many possible futures, their evaluations, and their relationships. This paper presents our ongoing investigation into potential explanations for the decision-making and behavior of MCTS. A weakness of MCTS is that it constructs a highly selective tree and, as a result, can miss crucial moves and fall into tactical traps. Full-width minimax search constitutes the solution. We integrate shallow minimax search into the rollout phase of multi-agent MCTS and use process mining technique to explain agents’ strategies in 3v3 checkers. 1 [email protected] 2 [email protected] 3 [email protected] * 4 [email protected] Introduction Today’s artificial intelligence systems have widely spread to applications in our everyday lives. They are powerful enough to outperform humans’ efficiency on complex tasks, such as the decision-making process in recruitment organizations. Many companies rely on automated algorithms to reduce the effort of human sources in evaluating candidates’ capacity and potential, but it often results in a typical scenario where candidates are rejected on resume selection without any reasons. These algorithms are usually called black-box machine learning models predicting a person’s likelihood of being hired ( Miller 2019b ) . The black-box means that we only know a series of features will be fed into the model to generate output, but we will not know how the inner mechanism performs this decision-making process. In other words, the implementation of the algorithm is not transparent to users and those affected. To address this issue, researchers have started to explore the field of explainable artificial intelligence (XAI) since mid-1980s ( Buchanan and Shortliffe 1984 ) . The purpose of explainable AI is to show details of models’ inner workings through providing reasons and evidence on how the output is generated ( Miller 2019a ) . These models include commonly used machine learning models, such as support vector machine (SVM), deep learning (DL), and reinforcement learning (RL) ( Gunning et al. 2019 ) . In this paper, we explore the explainable RL, specifically focusing on explaining decision-making of MCTS-minimax hybrids in 3v3 checkers game. RL is an area of machine learning that creates optimal policies through agents learning from interactions with the environment ( Sutton and Barto 2018 ) . Agents are planners who execute actions in problems of decision-making. RL makes decisions for agents in two ways: model-based and model-free. Agents in model-based RL rely on Markov Decision Process (MDP) to learn policies from the environment, and agents in model-free RL can directly learn policies from the environment ( Puterman 1990 ) . In terms of understanding behaviors of model-based RL agents and model-free RL agents, Wells points out that there are two major challenges in providing human-readable explanations ( Wells and Bednarz 2021 ) . One involves dealing with a large number of sequential decisions generated in a short period of time. Another is the fact that model-free RL agents are trained without training data. It is difficult to provide valid explanations without training data linking actions and observations in the environment. Recent work in model-free RL focuses on learning Intrinsically Interpretable policies ( Milani et al. 2022 ) . Topin proposes the argumented MDP method to train agents to directly learn decision tree policies from the environment ( Topin et al. 2021 ) . In terms of XRL, previous researchers attempted to generate explanations using natural language and saliency maps. Ehsan and Wang rationalize agents’ behaviors by leveraging action-explanation pairs provided by humans ( Ehsan et al. 2018 ) ( Wang et al. 2019 ) . Greydanus constructs saliency maps to measure changes in the policy and highlight regions that are critical to agents’ decisions ( Greydanus et al. 2018 ) . In prior research conducted by Baier and Winands, MCTS-minimax hybrids are developed by incorporating shallow minimax searches into the MCTS framework ( Baier and Winands 2014 ) . This is the initial step in combining the strategic strength of MCTS with the tactical strength of minimax. MCTS is a simulation-based search algorithm that builds a tree of possible moves and outcomes iteratively and selects the optimal move based on statistics gathered during the search. It is especially useful in games with uncertain outcomes and intricate decision spaces ( Browne et al. 2012 ) . Minimax is a deterministic search algorithm that exhaustively explores all possible moves and outcomes, assuming that the opponent will play optimally. It is highly effective in games with perfect information and deterministic outcomes, but may be impractical in games with large decision spaces ( Strong 2011 ) . In terms of explainable MCTS, Baier and Kaisers highlight the use of post-hoc models to explain MCTS decisions ( Baier and Kaisers 2020 ) . They identify three fundamental types of post-hoc questions that occur naturally in numerous explanation contexts: 1. Why do you recommend this action? 2. What do you recommend in these possible futures? 3. Why don’t you recommend this alternative action? However, they fail to explain three crucial questions of future research on explainable MCTS: 1. How should feature engineering work be applied on decision data collected from MCTS model? 2. What are recommended post-hoc models to employ? 3. How to specifically apply post-hoc model to process data obtained from MCTS model? These three inquiries are addressed in our research. To the best of our knowledge, no one has applied post-hoc interpretability to explain MCTS-minimax hybrids before. The process mining model is utilised as a post-hoc model. Process mining is a technique to discover processes observed in the real world using event logs ( Buijs, van Dongen, and van der Aalst 2014 ) . We believe studying policy processes of agents in 3v3 checkers may bring humans ideas about how MCTS-minimax hybrids execute decisions, so we propose an approach to explain agents’ behaviors using process mining techniques. We believe our process mining-based post-hoc model will provide explanations on three fundamental types of post-hoc questions. Preliminaries This section discusses preliminaries in process mining, process models’ quality dimensions, MCTS and Minimax. Figure 1: Four quality dimensions in process mining ( Buijs, van Dongen, and van der Aalst 2014 ) Process Mining The purpose of process mining is to generate process models from records of an organization’s operational processes ( Buijs, van Dongen, and van der Aalst 2014 ) . Such records, known as event logs, consist of cases and events. Considering the sample event log in figure 2 from Van’s research in process discovery, we can observe that there are five cases (1, 2, 3, 4, and 5) and four types of tasks (A, B, C, and D) ( Van der Aalst, Weijters, and Maruster 2004 ) . For case 1, events ABCD are executed. For case 2, events ACBD are executed. For case 3, events ABCD are executed. For case 4, events ACBD are executed. For case

Read the complete text