This paper presents Generalized Proof-Number Monte-Carlo Tree Search: a generalization of recently proposed combinations of Proof-Number Search (PNS) with Monte-Carlo Tree Search (MCTS), which use (dis)proof numbers to bias UCB1-based Selection strategies towards parts of the search that are expected to be easily (dis)proven. We propose three core modifications of prior combinations of PNS with MCTS. First, we track proof numbers per player. This reduces code complexity in the sense that we no longer need disproof numbers, and generalizes the technique to be applicable to games with more than two players. Second, we propose and extensively evaluate different methods of using proof numbers to bias the selection strategy, achieving strong performance with strategies that are simpler to implement and compute. Third, we merge our technique with Score Bounded MCTS, enabling the algorithm to prove and leverage upper and lower bounds on scores—as opposed to only proving wins or not-wins. Experiments demonstrate substantial performance increases, reaching the range of 80% for 8 out of the 11 tested board games.

The majority of current reinforcement learning (RL) research involves training and deploying agents in environments that are implemented by engineers in general-purpose programming languages and more advanced frameworks such as CUDA or JAX. This makes the application of RL to novel problems of interest inaccessible to small organisations or private individuals with insufficient engineering expertise. This position paper argues that, to enable more widespread adoption of RL, it is important for the research community to shift focus towards methodologies where environments are described in user-friendly domain-specific or natural languages. Aside from improving the usability of RL, such language-based environment descriptions may also provide valuable context and boost the ability of trained agents to generalise to unseen environments within the set of all environments that can be described in any language of choice.

Abstract Time-series forecasts underpin decision-making processes in a wide range of application domains. Recently it has been shown that these processes can be strengthened by conformal prediction, a framework that allows adding prediction intervals to point forecasts. The prediction intervals quantify the uncertainty of a predictive model with mathematical coverage guarantees, giving the user a range of scenarios to consider. However, applying conformal prediction to time-series tasks is not trivial. This is either because the exchangeability condition the framework places on the data is violated, or because the framework only allows for one-step-ahead univariate forecasts. In this article we combine two existing methods derived from conformal prediction, one built for multi-target regression and one designed to handle non-exchangeable data. The resulting method, called non-exchangeable multi-target conformal prediction (nmtCP) produces provably robust prediction regions for multi-step ahead multidimensional time-series forecasts, meaning that the miscoverage rate is bound. Additionally, nmtCP is computationally efficient and easy to implement. Due to its model-agnostic nature, nmtCP can be used on top of any time-series model that produces point forecasts. A theoretical analysis proves the method’s robustness while experiments on real-world data sets give insights into its practical behavior and performance.

This paper proposes a new game-search algorithm, PN-MCTS, which combines Monte-Carlo Tree Search (MCTS) and Proof-Number Search (PNS). These two algorithms have been successfully applied for decision making in a range of domains. We define three areas where the additional knowledge provided by the proof and disproof numbers gathered in MCTS trees might be used: final move selection, solving subtrees, and the UCB1 selection mechanism. We test all possible combinations on different time settings, playing against vanilla UCT on several games: Lines of Action (7×7 and 8×8 board sizes), MiniShogi, Knightthrough, and Awari. Furthermore, we extend this new algorithm to properly address games with draws, like Awari, by adding an additional layer of PNS on top of the MCTS tree. The experiments show that PN-MCTS is able to outperform MCTS in all tested game domains, achieving win rates up to 96.2% for Lines of Action.

Upper Confidence bounds applied to Trees (UCT) is the default selection policy in Monte-Carlo Tree Search (MCTS), yet it overlooks the strategic use of ancestral node information. Consequently, UCT approaches each decision level as an independent Multi-Armed Bandit problem, disregarding the results achieved along the path that led to the current state. Consequently, it treats decisions as separate in the tree, without integrating the historical context of previous choices. This paper introduces an enhancement to UCT for two-player, deterministic zero-sum games by integrating insights from $\alpha-\beta$ pruning-a method that increases minimax search efficiency through selective pruning. We propose a revised selection policy that leverages ancestor node data, mirroring $\alpha-\beta$ pruning’s principle, to refine sample-based search. Our experiments with this enhanced method reveal performance gains in Breakthrough, Mini Shogi, and GoMoku, highlighting the effectiveness of incorporating ancestor search results into the MCTS selection processes.

Many enhancements to Monte-Carlo Tree Search (MCTS) have been proposed over almost two decades of general game playing and other artificial intelligence research. However, our ability to characterise and understand which variants work well or poorly in which games is still lacking. This paper describes work on an initial dataset that we have built to make progress towards such an understanding: 268,386 plays among 61 different agents across 1494 distinct games. We describe a preliminary analysis and work on training predictive models on this dataset, as well as lessons learned and future plans for a new and improved version of the dataset.

We consider a flow-shop with m stations (machines) and n identical jobs that need to be processed on each station. The processing time of every job on station i is pi. After a job is processed on a station i, it needs to be transported by an automated guided vehicle (AGV) to the next station i + 1. There is only one AGV. We assume no buffers, i.e., when the AGV transports a job to a station, the station needs to be empty. Furthermore, an AGV can transport at most one job at a time, non-preemptively, i.e., it cannot leave the job in the middle of transportation. The transportation times between the stations are given and are independent of whether the AGV carries a job or not. We study the problem of scheduling the single AGV such that all jobs are processed and the makespan is minimized. We provide a characterization of feasible schedules, and use it to derive an integer linear program (ILP) for the problem. We observe that solving the ILP requires a rather large amount of computation time even for very small instances. We use the ILP-formulation to design a rolling-window based heuristic that scales up and provides close-to-optimum schedules, as demonstrated by experimental evaluation that also involves comparison to two natural greedy algorithms.

The field of Explainable Artificial Intelligence has gained popularity in recent years, due to the need for users to understand AI-made decisions, in order to increase their trust in the AI system. However, not much work has been performed on explaining recommendations made by search algorithms, which do not focus on single decisions, but on complex plans of action. This paper investigates promising directions for research in Explainable Search (XS), by evaluating with a user study different types of explanations for a search-based algorithm. Preliminary results suggest that users prefer explanations generated using context-based features, which are not only based on the current state of the problem, but are extracted from different parts of the tree generated by the search algorithm.

In many games, moves consist of several decisions made by the player. These decisions can be viewed as separate moves, which is already a common practice in multi-action games for efficiency reasons. Such division of a player move into a sequence of simpler / lower level moves is called splitting. So far, split moves have been applied only in forementioned straightforward cases, and furthermore, there was almost no study revealing its impact on agents' playing strength. Taking the knowledge-free perspective, we aim to answer how to effectively use split moves within Monte-Carlo Tree Search (MCTS) and what is the practical impact of split design on agents' strength. This paper proposes a generalization of MCTS that works with arbitrarily split moves. We design several variations of the algorithm and try to measure the impact of split moves separately on efficiency, quality of MCTS, simulations, and action-based heuristics. The tests are carried out on a set of board games and performed using the Regular Boardgames General Game Playing formalism, where split strategies of different granularity can be automatically derived based on an abstract description of the game. The results give an overview of the behavior of agents using split design in different ways. We conclude that split design can be greatly beneficial for single- as well as multi-action games.

Proof-Number Search (PNS) and Monte-Carlo Tree Search (MCTS) have been successfully applied for decision making in a range of games. This paper proposes a new approach called PN-MCTS that combines these two tree-search methods by incorporating the concept of proof and disproof numbers into the UCT formula of MCTS. Experimental results demonstrate that PN-MCTS outperforms basic MCTS in several games including Lines of Action, MiniShogi, Knightthrough, and Awari, achieving win rates up to 94.0%.

Monte Carlo Tree Search (MCTS) is a heuristic search algorithm that can play a wide range of games without requiring any domain-specific knowledge. However, MCTS tends to struggle in very complicated games due to an exponentially increasing branching factor. A promising solution for this problem is to focus the search only on a small fraction of states. Subgoal Monte Carlo Tree Search (S-MCTS) achieves this by using a predefined subgoal-predicate that detects promising states called subgoals. However, not only does this make S-MCTS domain-dependent, but also it is often difficult to define a good predicate. In this paper, we propose using quality diversity (QD) algorithms to detect subgoals in real-time. Furthermore, we show how integrating QD-algorithms into S-MCTS significantly improves its performance in the Physical Travelling Salesmen Problem without requiring any domain-specific knowledge.

The research field of Artificial General Intelligence (AGI) is concerned with the creation of adaptive programs that can autonomously address tasks of a different nature. Search and planning have been identified as core capabilities of AGI, and have been successful in many scenarios that require sequential decision-making. However, many search algorithms are developed for specific problems and exploit domain-specific knowledge, which makes them not applicable to perform different tasks autonomously. Although some domain-independent search algorithms have been proposed, a programmer still has to make decisions on their design, setup and enhancements. Thus, the performance is limited by the programmer's decisions, which are usually biased. This paper proposes to develop a framework that, in line with the goals of AGI, autonomously addresses a wide variety of search tasks, adapting automatically to each new, unknown task. To achieve this, we propose to encode search algorithms in a formal language and combine algorithm portfolios with automatic algorithm generation. In addition, we see games as the ideal test bed for the framework, because they can model a wide variety of complex problems. Finally, we believe that this research will have an impact not only on the AG I research field, but also on the game industry and on real-world problems.

For general video game playing agents, the biggest challenge is adapting to the wide variety of situations they encounter and responding appropriately. Some success was recently achieved by modifying search-control parameters in agents on-line, during one play-through of a game. We propose adapting such methods for Rolling Horizon Evolutionary Algorithms, which have shown high performance in many different environments, and test the effect of on-line adaptation on the agent's win rate. On-line tuned agents are able to achieve results comparable to the state of the art, including first win rates in hard problems, while employing a more general and highly adaptive approach. We additionally include further insight into the algorithm itself, given by statistics gathered during the tuning process and highlight key parameter choices.

Accepted at ECAI 2020

Many enhancements for Monte Carlo tree search (MCTS) have been applied successfully in general game playing (GGP). MCTS and its enhancements are controlled by multiple parameters that require extensive and time-consuming offline optimization. Moreover, as the played games are unknown in advance, offline optimization cannot tune parameters specifically for single games. This paper proposes a self-adaptive MCTS strategy (SA-MCTS) that integrates within the search a method to automatically tune search-control parameters online per game. It presents five different allocation strategies that decide how to allocate available samples to evaluate parameter values. Experiments with 1 s play-clock on multiplayer games show that for all the allocation strategies the performance of SA-MCTS that tunes two parameters is at least equal to or better than the performance of MCTS tuned offline and not optimized per-game. The allocation strategy that performs the best is N-Tuple Bandit Evolutionary Algorithm (NTBEA). This strategy also achieves a good performance when tuning four parameters. SA-MCTS can be considered as a successful strategy for domains that require parameter tuning for every single problem, and it is also a valid alternative for domains where offline parameter tuning is costly or infeasible.

Procedural Content Generation is an active area of research, with more interest being given recently to methods able to produce interesting content in a general context (without task-specific knowledge). To this extent, we focus on procedural level generators within the General Video Game AI framework (GVGAI). This paper proposes several topics of interest. First, a comparison baseline for GVGAI level generators, which is more flexible and robust than the existing alternatives. Second, a composite fitness evaluation function for levels based on AI play-testing. Third, a new parameterized generator, and a Meta Generator for performing parameter search on such generators are introduced. We compare the Meta Generator against random and constructive generator baselines, using the new fitness function, on 3 GVGAI games: Butterflies, Freeway and The Snowman. The Meta Generator is suggested to perform on par with or better than the baselines, depending on the game. Encouraged by these results, the Meta Generator will be submitted to the 2019 GVGAI Level Generation competition.

Monte-Carlo Tree Search (MCTS) has been applied successfully in many domains. Previous research has shown that adding randomization to certain components of MCTS might increase the diversification of the search and improve the performance. In a domain that tackles many games with different characteristics, like General Game Playing (GGP), trying to diversify the search might be a good strategy. This paper investigates the effect of randomizing search-control parameters for MCTS in GGP. Four different randomization strategies are compared and results show that randomizing parameter values before each simulation has a positive effect on the search in some of the tested games. Moreover, parameter randomization is compared with on-line parameter tuning.

Credit card transactions predicted to be fraudulent by automated detection systems are typically handed over to human experts for verification. To limit costs, it is standard practice to select only the most suspicious transactions for investigation. We claim that a trade-off between exploration and exploitation is imperative to enable adaptation to changes in behavior (concept drift). Exploration consists of the selection and investigation of transactions with the purpose of improving predictive models, and exploitation consists of investigating transactions detected to be suspicious. Modeling the detection of fraudulent transactions as rewarding, we use an incremental Regression Tree learner to create clusters of transactions with similar expected rewards. This enables the use of a Contextual Multi-Armed Bandit (CMAB) algorithm to provide the exploration/exploitation trade-off. We introduce a novel variant of a CMAB algorithm that makes use of the structure of this tree, and use Semi-Supervised Learning to grow the tree using unlabeled data. The approach is evaluated on a real dataset and data generated by a simulator that adds concept drift by adapting the behavior of fraudsters to avoid detection. It outperforms frequently used offline models in terms of cumulative rewards, in particular in the presence of concept drift.

Monte-Carlo Tree Search (MCTS) has been found to show weaker play than minimax-based search in some tactical game domains. In order to combine the tactical strength of minimax and the strategic strength of MCTS, MCTS-minimax hybrids have been proposed in prior work. This article continues this line of research for the case where heuristic state evaluation functions are available. Three different approaches are considered, employing minimax in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. Results show that the use of enhanced minimax for computing node priors results in the strongest MCTS-minimax hybrid in the three test domains of Othello, Breakthrough, and Catch the Lion. This hybrid also outperforms enhanced minimax as a standalone player in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts.

Monte-Carlo Tree Search (MCTS) has been found to show weaker play than minimax-based search in some tactical game domains. This is partly due to its highly selective search and averaging value backups, which make it susceptible to traps. In order to combine the strategic strength of MCTS and the tactical strength of minimax, MCTS-minimax hybrids have been introduced, embedding shallow minimax searches into the MCTS framework. Their results have been promising even without making use of domain knowledge such as heuristic evaluation functions. This article continues this line of research for the case where evaluation functions are available. Three different approaches are considered, employing minimax with an evaluation function in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. Furthermore, all three hybrids are enhanced with the help of move ordering and k-best pruning for minimax. Results show that the use of enhanced minimax for computing node priors results in the strongest MCTS-minimax hybrid investigated in the three test domains of Othello, Breakthrough, and Catch the Lion. This hybrid, called MCTS-IP-M-k, also outperforms enhanced minimax as a standalone player in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts. Using enhanced minimax for computing node priors is therefore a promising new technique for integrating domain knowledge into an MCTS framework.

This paper showcases the setting and results of the first Two-Player General Video Game AI Competition, which ran in 2016 at the IEEE World Congress on Computational Intelligence and the IEEE Conference on Computational Intelligence and Games. The challenges for the general game AI agents are expanded in this track from the single-player version, looking at direct player interaction in both competitive and cooperative environments of various types and degrees of difficulty. The focus is on the agents not only handling multiple problems, but also having to account for another intelligent entity in the game, who is expected to work toward their own goals (winning the game). This other player will possibly interact with first agent in a more engaging way than the environment or any nonplaying character may do. The top competition entries are analyzed in detail and the performance of all agents is compared across the four sets of games. The results validate the competition system in assessing generality, as well as showing Monte Carlo tree search continuing to dominate by winning the overall championship. However, this approach is closely followed by rolling horizon evolutionary algorithms, employed by the winner of the second leg of the contest.

Monte Carlo Tree Search (MCTS) is a popular approach for tree search in a variety of games. While MCTS allows for fine-grained time control, not much has been published on time management for MCTS programs under tournament conditions. This paper first investigates the effects of various time-management strategies on playing strength in the challenging game of Go. A number of domain-independent strategies are then tested in the domains Connect-4, Breakthrough, Othello, and Catch the Lion. We consider strategies taken from the literature as well as newly proposed and improved ones. Strategies include both semi-dynamic strategies that decide about time allocation for each search before it is started, and dynamic strategies that influence the duration of each move search while it is already running. Furthermore, we analyze the effects of time management strategies on the distribution of time over the moves of an average game, allowing us to partly explain their performance. In the experiments, the domain-independent strategy STOP provides a significant improvement over the state of the art in Go, and is the most effective time management strategy tested in all five domains.

The nine papers in this special section focus on the development of physics-based simulation video games (PBSG). The focus is on artificial intelligence for specific PBSGs competitions such as Angry Birds and computational pool, as well as on further developments of physics simulators in order to launch the next generation of PBSGs.

Monte Carlo tree search (MCTS) is a sampling-based search algorithm that is state of the art in a variety of games. In many domains, its Monte Carlo rollouts of entire games give it a strategic advantage over traditional depth-limited minimax search with αβ pruning. These rollouts can often detect long-term consequences of moves, freeing the programmer from having to capture these consequences in a heuristic evaluation function. But due to its highly selective tree, MCTS runs a higher risk than full-width minimax search of missing individual moves and falling into traps in tactical situations. This paper proposes MCTS-minimax hybrids that integrate shallow minimax searches into the MCTS framework. Three approaches are outlined, using minimax in the selection/expansion phase, the rollout phase, and the backpropagation phase of MCTS. Without assuming domain knowledge in the form of evaluation functions, these hybrid algorithms are a first step towards combining the strategic strength of MCTS and the tactical strength of minimax. We investigate their effectiveness in the test domains of Connect-4, Breakthrough, Othello, and Catch the Lion, and relate this performance to the tacticality of the domains.

Monte-Carlo Tree Search is a best-first search technique based on simulations to sample the state space of a decision-making problem. In games, positions are evaluated based on estimates obtained from rewards of numerous randomized play-outs. Generally, rewards from play-outs are discrete values representing the outcome of the game (loss, draw, or win), e.g., r∈{−1,0,1}, which are backpropagated from expanded leaf nodes to the root node. However, a play-out may provide additional information. In this paper, we introduce new measures for assessing the a posteriori quality of a simulation. We show that altering the rewards of play-outs based on their assessed quality improves results in six distinct two-player games and in the General Game Playing agent CADIAPLAYER. We propose two specific enhancements, the Relative Bonus and Qualitative Bonus. Both are used as control variates, a variance reduction method for statistical simulation. Relative Bonus is based on the number of moves made during a simulation and Qualitative Bonus relies on a domain-dependent assessment of the game's terminal state. We show that the proposed enhancements, both separate and combined, lead to significant performance increases in the domains discussed.

In this paper, Monte Carlo tree search (MCTS) is introduced for controlling the Pac-Man character in the real-time game Ms Pac-Man. MCTS is used to find an optimal path for an agent at each turn, determining the move to make based on the results of numerous randomized simulations. Several enhancements are introduced in order to adapt MCTS to the real-time domain. Ms Pac-Man is an arcade game, in which the protagonist has several goals but no conclusive terminal state. Unlike games such as Chess or Go there is no state in which the player wins the game. Instead, the game has two subgoals, 1) surviving and 2) scoring as many points as possible. Decisions must be made in a strict time constraint of 40 ms. The Pac-Man agent has to compete with a range of different ghost teams, hence limited assumptions can be made about their behavior. In order to expand the capabilities of existing MCTS agents, four enhancements are discussed: 1) a variable-depth tree; 2) simulation strategies for the ghost team and Pac-Man; 3) including long-term goals in scoring; and 4) reusing the search tree for several moves with a decay factor γ. The agent described in this paper was entered in both the 2012 World Congress on Computational Intelligence (WCCI'12, Brisbane, Qld., Australia) and the 2012 IEEE Conference on Computational Intelligence and Games (CIG'12, Granada, Spain) Pac-Man Versus Ghost Team competitions, where it achieved second and first places, respectively. In the experiments, we show that using MCTS is a viable technique for the Pac-Man agent. Moreover, the enhancements improve overall performance against four different ghost teams.

The aim of general game playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo tree search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper, we investigate the application of a decay factor for two domain-independent simulation strategies: the N-gram selection technique (NST) and the move-average sampling technique (MAST). Three decay factor methods, called move decay, batch decay, and simulation decay, are applied. Furthermore, a combination of move decay and simulation decay is also tested. The decay variants are implemented in the GGP program CadiaPlayer. Four types of games are used: turn taking, simultaneous move, one player, and multiplayer. Except for one-player games, experiments show that decaying can significantly improve the performance of both NST and MAST simulation strategies.

This paper describes how Monte Carlo tree search (MCTS) can be applied to the hide-and-seek game Scotland Yard. This game is essentially a two-player game in which the players are moving on a graph-based map. First, we discuss how determinization is applied to handle the imperfect information in the game. We show how using determinization in a single tree performs better than using separate trees for each determinization. We also propose a new technique, called location categorization, that biases the possible locations of the hider. The experimental results reveal that location categorization is a robust technique, and significantly increases the performance of the seekers. Next, we describe how to handle the coalition of the seekers by using coalition reduction. This technique balances each seeker's participation in the coalition. Coalition reduction improves the performance of the seekers significantly. Furthermore, we explain how domain knowledge is incorporated by applying ε-greedy playouts and move filtering. Finally, we compare the MCTS players to minimax-based players, and we test the performance of our MCTS player against a commercial Scotland Yard program on the Nintendo DS. Based on the results, we may conclude that the MCTS-based hider and seekers play at a strong level.

The aim of general game playing (GGP) is to create programs capable of playing a wide range of different games at an expert level, given only the rules of the game. The most successful GGP programs currently employ simulation-based Monte Carlo tree search (MCTS). The performance of MCTS depends heavily on the simulation strategy used. In this paper, we introduce improved simulation strategies for GGP that we implement and test in the GGP agent CADIAPLAYER, which won the International GGP competition in both 2007 and 2008. There are two aspects to the improvements: first, we show that a simple ϵ-greedy exploration strategy works better in the simulation play-outs than the softmax-based Gibbs measure currently used in CADIAPLAYER and, second, we introduce a general framework based on N-grams for learning promising move sequences. Collectively, these enhancements result in a much improved performance of CADIAPLAYER. For example, in our test suite consisting of five different two-player turn-based games, they led to an impressive average win rate of approximately 70%. The enhancements are also shown to be effective in multiplayer and simultaneous-move games. We additionally perform experiments with the last-good-reply policy (LGRP). The LGRP combined with N-grams is also tested. The LGRP has already been shown to be successful in Go programs and we demonstrate that it also has promise in GGP.

This paper proposes a new algorithm, called best reply search (BRS), for deterministic multiplayer games with perfect information. In BRS, only the opponent with the strongest counter move is allowed to make a move. More turns of the root player can be searched resulting in long-term planning. We test BRS in the games of Chinese Checkers, Focus, and Rolit™. In all games, BRS is superior to the maxnalgorithm. We show that BRS also outperforms paranoid in Chinese Checkers and Focus. In Rolit, BRS is on equal footing with paranoid. We conclude that BRS is a promising search method for deterministic multiplayer games with perfect information.

The success of Monte Carlo tree search (MCTS) in many games, where αβ-based search has failed, naturally raises the question whether Monte Carlo simulations will eventually also outperform traditional game-tree search in game domains where αβ -based search is now successful. The forte of αβ-based search are highly tactical deterministic game domains with a small to moderate branching factor, where efficient yet knowledge-rich evaluation functions can be applied effectively. In this paper, we describe an MCTS-based program for playing the game Lines of Action (LOA), which is a highly tactical slow-progression game exhibiting many of the properties difficult for MCTS. The program uses an improved MCTS variant that allows it to both prove the game-theoretical value of nodes in a search tree and to focus its simulations better using domain knowledge. This results in simulations superior in both handling tactics and ensuring game progression. Using the improved MCTS variant, our program is able to outperform even the world's strongest αβ-based LOA program. This is an important milestone for MCTS because the traditional game-tree search approach has been considered to be the better suited for playing LOA.