Search

Monte-Carlo Tree Search (MCTS) has been applied successfully in many domains, including games. However, its performance is not uniform on all domains, and it also depends on how parameters that control the search are set. Parameter values that are optimal for a task might be sub-optimal for another. In a domain that tackles many games with different characteristics, like general game playing (GGP), selecting appropriate parameter settings is not a trivial task. Games are unknown to the player, thus, finding optimal parameters for a given game in advance is not feasible. Previous work has looked into tuning parameter values online, while the game is being played, showing some promising results. This tuning approach looks for optimal parameter values, balancing exploitation of values that performed well so far in the search and exploration of less sampled values. Continuously changing parameter values while performing the search, combined also with exploration of multiple values, introduces some randomization in the process. In addition, previous research indicates that adding randomization to certain components of MCTS might increase the diversification of the search and improve the performance. Therefore, this article investigates the effect of randomly selecting values for MCTS search-control parameters online among predefined sets of reasonable values. For the GGP domain, this article evaluates four different online parameter randomization strategies by comparing them with other methods to set parameter values: online parameter tuning, offline parameter tuning and sub-optimal parameter choices. Results on a set of 14 heterogeneous abstract games show that randomizing parameter values before each simulation has a positive effect on the search in some of the tested games, with respect to using fixed offline-tuned parameters. Moreover, results show a clear distinction between games for which online parameter tuning works best and games for which online randomization works best. In addition, the overall performance of online parameter randomization is closer to the one of online parameter turning than the one of sub-optimal parameter values, showing that online randomization is a reasonable parameter selection strategy. When analyzing the structure of the search trees generated by agents that use the different parameters selection strategies, it is clear that randomization causes MCTS to become more explorative, which is helpful for alignment games that present many winning paths in their trees. Online parameter tuning, instead, seems more suitable for games that present narrow winning paths and many losing paths.

Playout policy adaptation (ppa) is a state-of-the-art strategy that has been proposed to control the playouts in monte-carlo tree search (mcts). Ppa has been successfully applied to many two-player, sequential-move games. This paper further evaluates this strategy in general game playing (ggp) by first reformulating it for simultaneous-move games. Next, it presents five enhancements for the strategy, four of which have been previously successfully applied to a related mcts playout strategy, the move-average sampling technique (mast). Experiments on a heterogeneous set of games show three enhancements to have a positive effect on ppa: (i) updating the policy for all players proportionally to their payoffs instead of updating only the policy of the winner, (ii) collecting statistics for n-grams of moves instead of single moves only, and (iii) discounting the backpropagated payoffs depending on the depth of the playout. Results also show enhanced ppa variants to be competitive with mast for small search budgets, and better for larger search budgets. The use of an \(\epsilon \)-greedy selection of moves and of after-move decay of statistics, instead, seem to have a detrimental effect on ppa.keywordsmonte-carlo tree searchplayout policy adaptationgeneral game playing.

Engineering with computers (2021). doi:10.1007/s00366-021-01338-2, Published by Springer, London

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 AGI research field, but also on the game industry and on real-world problems.

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.

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.

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 $\boldsymbol {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.

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.

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.

The speed of game rules processing plays an essential role in the performance of a General Game Playing (GGP) agent. Propositional Networks (propnets) are an example of a highly efficient representation of game rules. So far, in GGP, only software implementations of propnets have been proposed and investigated. In this paper, we present the first implementation of propnets on Field-Programmable Gate Arrays (FPGAs), showing that they perform between 25 and 58 times faster than a software-propnet for most of the tested games. We also integrate the FPGA-propnet within an MCTS agent, discussing the challenges of the process, and possible solutions for the identified shortcomings.

Simultaneous move games model discrete, multistage interactions where at each stage players simultaneously choose their actions. At each stage, a player does not know what action the other player will take, but otherwise knows the full state of the game. This formalism has been used to express games in general game playing and can also model many discrete approximations of real-world scenarios. In this paper, we describe both novel and existing algorithms that compute strategies for the class of two-player zero-sum simultaneous move games. The algorithms include exact backward induction methods with efficient pruning, as well as Monte Carlo sampling algorithms. We evaluate the algorithms in two different settings: the offline case, where computational resources are abundant and closely approximating the optimal strategy is a priority, and the online search case, where computational resources are limited and acting quickly is necessary. We perform a thorough experimental evaluation on six substantially different games for both settings. For the exact algorithms, the results show that our pruning techniques for backward induction dramatically improve the computation time required by the previous exact algorithms. For the sampling algorithms, the results provide unique insights into their performance and identify favorable settings and domains for different sampling algorithms.

A purpose of General Video Game Playing (GVGP) is to create agents capable of playing many different real-time video games. Instead of using a fixed general strategy, a challenging aspect is devising strategies that adapt the search to each video game being played. Recent work showed that on-line parameter tuning can be used to adapt Monte-Carlo Tree Search (MCTS) in real-time. This paper extends prior work on Self-adaptive Monte-Carlo Tree Search (SA-MCTS) by further testing one of the previously proposed on-line parameter tuning strategies, based on the N-Tuple Bandit Evolutionary Algorithm (NTBEA). Results show that, both for a simple and a more advanced MCTS agent, on-line parameter tuning has impact on performance only for a few GVGP games. Moreover, an informed strategy as NTBEA shows a significant performance increase only in one case. In a real-time domain as GVGP, advanced parameter tuning does not seem very promising. Randomizing pre-selected parameters for each simulation appears to be a robust approach.

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.

StarCraft is a real-time strategy game, which has a large state space, and commonly features two opposing players, capable of acting simultaneously. One of the aspects of the game is resource gathering. Each agent playing StarCraft has to gather minerals from nearby mineral field in order to produce more units. The more resources can be gathered, the larger the army is to attack the opponent and win the game. We present five algorithms that can be used for resource gathering for an intelligent agent playing the game of StarCraft: Brood War. The results reveal that improving the scheduling or the path finding improve the resource gathering considerably.

General game playing (ggp) programs need a game description language (gdl) reasoner to be able to interpret the game rules and search for the best actions to play in the game. One method for interpreting the game rules consists of translating the gdl game description into an alternative representation that the player can use to reason more efficiently on the game. The propositional network (propnet) is an example of such method. The use of propnets in ggp has become popular due to the fact that propnets can speed up the reasoning process by several orders of magnitude compared to custom-made or prolog-based gdl reasoners, improving the quality of the search for the best actions. This paper analyzes the performance of a propnet-based reasoner and evaluates four different optimizations for the propnet structure that can help further increase its reasoning speed in terms of visited game states per second.

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 epsilon-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.

General Video Game Playing (GVGP) is a field of Artificial Intelligence where agents play a variety of real-time video games that are unknown in advance. This limits the use of domain-specific heuristics. Monte-Carlo Tree Search (MCTS) is a search technique for game playing that does not rely on domain-specific knowledge. This paper discusses eight enhancements for MCTS in GVGP; Progressive History, N-Gram Selection Technique, Tree Reuse, Breadth-First Tree Initialization, Loss Avoidance, Novelty-Based Pruning, Knowledge-Based Evaluations, and Deterministic Game Detection. Some of these are known from existing literature, and are either extended or introduced in the context of GVGP, and some are novel enhancements for MCTS. Most enhancements are shown to provide statistically significant increases in win percentages when applied individually. When combined, they increase the average win percentage over sixty different games from 31.0% to 48.4% in comparison to a vanilla MCTS implementation, approaching a level that is competitive with the best agents of the GVG-AI competition in 2015.

This paper investigates Sequential Halving as a selection policy in the following four partially observable games: Go Fish, Lost Cities, Phantom Domineering, and Phantom Go. Additionally, H-MCTS is studied, which uses Sequential Halving at the root of the search tree, and UCB elsewhere. Experimental results reveal that H-MCTS performs the best in Go Fish, whereas its performance is on par in Lost Cities and Phantom Domineering. Sequential Halving as a flat Monte-Carlo Search appears to be the stronger technique in Phantom Go.

The success of Monte Carlo tree search (MCTS) in many games, where alpha beta-based search has failed, naturally raises the question whether Monte Carlo simulations will eventually also outperform traditional game-tree search in game domains where alpha beta-based search is now successful. The forte of alpha beta-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 alpha beta-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.

In this paper, we show that Realization Probability Search (RPS) significantly improves the playing strength of a world-class Lines-of-Action (LOA) computer program, even when used in combination with existing state-of-the-art αβ search enhancements. In a 600-game match, a RPS-based version of the program defeats the original one with a winning score of 62.5%. The main contribution of the paper, however, is the introduction of a much improved variant of RPS, called Enhanced Realization Probability Search (ERPS). The new algorithm addresses two weaknesses of RPS and overcomes them by using a better focussed re-searching scheme, resulting in both more robust tactical play and reduced search overhead. Our experiments in the domain of LOA show that ERPS offers just as a significant improvement over regular RPS, as the latter improves upon regular search. More specifically, the ERPS-based variant scores 62.1% against the RPS variant, and an impressive 72.2% score against the original program. This represents an improvement of over 100 ELO points over the original state-of-the-art player.

Fanorona is the national board game of Madagascar. The game's complexity is approximately the same as that of checkers. In this article, we present a search-based approach for weakly solving this game. It is a well-chosen combination of Proof-Number search and endgame databases. Retrograde analysis is used to generate the endgame databases in which every position with 7 or fewer pieces on the board has been solved. Then, a Proof-Number search variant, PN2, exploits the databases to prove that the game-theoretical value of the initial position is a draw. Future research should develop techniques for strongly solving the game.

This article presents a new learning system for predicting life and death in the game of go. It is called gone. The system uses a multi-layer perceptron classifier which is trained on learning examples extracted from game records. Blocks of stones are represented by a large amount of features which enable a rather precise prediction of life and death. On average, gone correctly predicts life and death for 88% of all the blocks that are relevant for scoring. Towards the end of a game the performance increases up to 99%. A straightforward extension for full-board evaluation is discussed. Experiments indicate that the predictor is an important component for building a strong full-board evaluation function.

In this paper forward-pruning methods, such as multi-cut and null move, are tested at so-called ALL nodes. We improved the principal variation search by four small but essential additions. The new PVS algorithm guarantees that forward pruning is safe at ALL nodes. Experiments show that multi-cut at ALL nodes (MC-A) when combined with other forward-pruning mechanisms give a significant reduction of the number of nodes searched. In comparison, a (more) aggressive version of the null move (variable null-move bound) gives less reduction at expected ALL nodes. Finally, it is demonstrated that the playing strength of the lines of action program MIA is significantly (scoring 21% more winning points than the opponent) increased by MC-A.

Monte Carlo Tree Search (MCTS) has improved the performance of game engines in domains such as Go, Hex, and general game playing. MCTS has been shown to outperform classic alpha-beta search in games where good heuristic evaluations are difficult to obtain. In recent years, combining ideas from traditional minimax search in MCTS has been shown to be advantageous in some domains, such as Lines of Action, Amazons, and Breakthrough. In this paper, we propose a new way to use heuristic evaluations to guide the MCTS search by storing the two sources of information, estimated win rates and heuristic evaluations, separately. Rather than using the heuristic evaluations to replace the playouts, our technique backs them up implicitly during the MCTS simulations. These minimax values are then used to guide future simulations. We show that using implicit minimax backups leads to stronger play performance in Kalah, Breakthrough, and Lines of Action., 24 pages, 7 figures, 9 tables, expanded version of paper presented at IEEE Conference on Computational Intelligence and Games (CIG) 2014 conference

Monte Carlo Tree Search (MCTS) is a widely-used technique for game-tree search in sequential turn-based games. The extension to simultaneous move games, where all players choose moves simultaneously each turn, is non-trivial due to the complexity of this class of games. In this paper, we describe simultaneous move MCTS and analyze its application in a set of nine disparate simultaneous move games. We use several possible variants, Decoupled UCT, Sequential UCT, Exp3, and Regret Matching. These variants include both deterministic and stochastic selection strategies and we characterize the game-play performance of each one. The results indicate that the relative performance of each variant depends strongly on the game and the opponent, and that parameter tuning can also not be as straightforward as the purely sequential case. Overall, Decoupled UCT performs best despite its theoretical shortcomings.

Best-Reply Search (BRS) is a new search technique for game-tree search in multi-player games. In BRS, the exponentially many possibilities that can be considered by opponent players is flattened so that only a single move, the best one among all opponents, is chosen. BRS has been shown to outperform the classic search techniques in several domains. However, BRS may consider invalid game states. In this paper, we improve the BRS search technique such that it preserves the proper turn order during the search and does not lead to invalid states. The new technique, BRS\(^+\), uses the move ordering to select moves at opponent nodes that are not searched. Empirically, we show that BRS\(^+\) significantly improves the performance of BRS in Four-Player Chess, leading to winning 8.3 %–11.1 % more games against the classic techniques max\(^n\) and Paranoid, respectively. When BRS\(^+\) plays against max\(^n\), Paranoid, and BRS at once, it wins the most games as well.

Regret minimization is important in both the Multi-Armed Bandit problem and Monte-Carlo Tree Search (MCTS). Recently, simple regret, i.e., the regret of not recommending the best action, has been proposed as an alternative to cumulative regret in MCTS, i.e., regret accumulated over time. Each type of regret is appropriate in different contexts. Although the majority of MCTS research applies the UCT selection policy for minimizing cumulative regret in the tree, this paper introduces a new MCTS variant, Hybrid MCTS (H-MCTS), which minimizes both types of regret in different parts of the tree. H-MCTS uses SHOT, a recursive version of Sequential Halving, to minimize simple regret near the root, and UCT to minimize cumulative regret when descending further down the tree. We discuss the motivation for this new search technique, and show the performance of H-MCTS in six distinct two-player games: Amazons, AtariGo, Ataxx, Breakthrough, NoGo, and Pentalath.

Monte carlo tree search (mcts) has become a widely popular sampled-based search algorithm for two-player games with perfect information. When actions are chosen simultaneously, players may need to mix between their strategies. In this paper, we discuss the adaptation of mcts to simultaneous move games. We introduce a new algorithm, online outcome sampling (oos), that approaches a nash equilibrium strategy over time. We compare both head-to-head performance and exploitability of several mcts variants in goofspiel. We show that regret matching and oos perform best and that all variants produce less exploitable strategies than uct.

Solving games is a challenging and attractive task in the domain of Artificial Intelligence. Despite enormous progress, solving increasingly difficult games or game positions continues to pose hard technical challenges. Over the last twenty years, algorithms based on the concept of proof and disproof numbers have become dominating techniques for game solving. Prominent examples include solving the game of checkers to be a draw, and developing checkmate solvers for shogi, which can find mates that take over a thousand moves. This article provides an overview of the research on Proof-Number Search and its many variants and enhancements.

The dominant approach for programs playing the game of Go is nowadays Monte-Carlo Tree Search (MCTS). While MCTS allows for fine-grained time control, little has been published on time management for MCTS programs under tournament conditions. This paper investigates the effects that various time-management strategies have on the playing strength in Go. We consider strategies taken from the literature as well as newly proposed and improved ones. We investigate 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. In our experiments, two domain-independent enhanced strategies, EARLY-C and CLOSE-N, are tested; each of them provides a significant improvement over the state of the art. 2012 Springer-Verlag.

In this paper enhancements for the Monte-Carlo Tree Search (MCTS) framework are investigated to play Ms Pac-Man. MCTS is used to find an optimal path for an agent at each turn, determining the move to make based on randomised simulations. Ms Pac-Man is a real-time arcade game, in which the protagonist has several independent goals but no conclusive terminal state. Unlike games such as Chess or Go there is no state in which the player wins the game. Furthermore, the Pac-Man agent has to compete with a range of different ghost agents, hence limited assumptions can be made about the opponent's behaviour. In order to expand the capabilities of existing MCTS agents, five enhancements are discussed: 1) a variable depth tree, 2) playout strategies for the ghost-team and Pac-Man, 3) including long-term goals in scoring, 4) endgame tactics, and 5) a Last-Good-Reply policy for memorising rewarding moves during playouts. An average performance gain of 40,962 points, compared to the average score of the top scoring Pac-Man agent during the CIG'11, is achieved by employing these methods.

This article shows how the performance of a Monte-Carlo Tree Search (MCTS) player for Havannah can be improved by guiding the search in the playout and selection steps of MCTS. To improve the playout step of the MCTS algorithm, we used two techniques to direct the simulations, Last-Good-Reply (LGR) and N-grams. Experiments reveal that LGR gives a significant improvement, although it depends on which LGR variant is used. Using N-grams to guide the playouts also achieves a significant increase in the winning percentage. Combining N-grams with LGR leads to a small additional improvement. To enhance the selection step of the MCTS algorithm, we initialize the visit and win counts of the new nodes based on pattern knowledge. By biasing the selection towards joint/neighbor moves, local connections, and edge/corner connections, a significant improvement in the performance is obtained. Experiments show that the best overall performance is obtained when combining the visit-and-win-count initialization with LGR and N-grams. In the best case, a winning percentage of 77.5% can be achieved against the default MCTS program. © 2012 Springer-Verlag.

Over the past few years, Monte-Carlo Tree Search (MCTS) has become a popular search technique for playing multi-player games. In this paper we propose a technique called Playout Search. This enhancement allows the use of small searches in the playout phase of MCTS in order to improve the reliability of the playouts. We investigate max\(^{\textrm{\scriptsize{n}}}\), Paranoid, and BRS for Playout Search and analyze their performance in two deterministic perfect-information multi-player games: Focus and Chinese Checkers. The experimental results show that Playout Search significantly increases the quality of the playouts in both games. However, it slows down the speed of the playouts, which outweighs the benefit of better playouts if the thinking time for the players is small. When the players are given a sufficient amount of thinking time, Playout Search employing Paranoid search is a significant improvement in the 4-player variant of Focus and the 3-player variant of Chinese Checkers.

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 maxn algorithm. 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.

This paper describes how Monte-Carlo Tree Search (MCTS) can be applied to play the hide-and-seek game Scotland Yard. It is essentially a two-player game in which the players are moving on a graph-based map. We show how limiting the number of possible locations of the hider by using information about the hider's moves increases the performance of the seekers considerably. We also propose a new technique, called Location Categorization, that biases the possible locations of the hider. The experimental results show that Location Categorization is a robust technique which significantly increases the performance of the seekers in Scotland Yard. Next, we show how to handle the coalition of the seekers in Scotland Yard by using Coalition Reduction. This technique balances each seeker's participation in the coalition by letting them seek the hider more greedily. Coalition Reduction improves the performance of the seekers significantly. Furthermore, we explain how domain knowledge is incorporated by applying e-greedy playouts for the hider and the seekers and move filtering to improve the performance of the hider. Finally, we test the performance of our MCTS program against a commercial Scotland Yard program on the Nintendo DS. The results show that the MCTS-based program plays stronger than this program.

Proof-number search (pns) is a powerful method for solving games and game positions. Over the years, the research on pns has steadily produced new insights and techniques. With multi-core processors becoming established in the recent past, the question of parallelizing pns has gained new urgency. This article presents a new technique called randomized parallel proof-number search (rppns) for parallelizing pns on multi-core systems with shared memory. The parallelization is based on randomizing the move selection of multiple threads, which operate on the same search tree. Rppns is tested on a set of complex lines-of-action endgame positions. Experiments show that rppns scales well. Four directions for future research are given.

Proof-number (pn) search is a best-first adversarial search algorithm especially suited for finding the game-theoretical value in game trees. The strategy of the algorithm may be described as developing the tree into the direction where the opposition characterised by value and branching factor is to expect to be the weakest. In this chapter we start by providing a short description of the original pn-search method, and two main successors of the original pn search, i.e., pn2 search and the depth-first variant proof-number and disproof-number search (pds). A comparison of the performance between pn, pn2, pds, and aß is given. It is shown that pn-search algorithms clearly outperform aß in solving endgame positions in the game of lines of action (loa). However, memory problems make the plain pn search a weaker solver for harder problems. Pds and pn2 are able to solve significantly more problems than pn and aß. But pn2 is restricted by its working memory, and pds is considerably slower than pn2. Next, we present a new proof-number search algorithm, called pds-pn. It is a two-level search (like pn2), which performs at the first level a depth-first pds, and at the second level a best-first pn search. Hence, pds-pn selectively exploits the power of both pn2 and pds. Experiments show that within an acceptable time frame pds-pn is more effective for really hard endgame positions. Finally, we discuss the depth-first variant df-pn. As a follow up of the comparison of the four pn variants, we compare the algorithms pds and df-pn. However, the hardware conditions of the comparison were different. Yet, experimental results provide promising prospects for df-pn. We conclude the article by seven observations, three conclusions, and four suggestions for future research.

kEver since humans achieved some degree of civilization, they have played games. The two most important reasons for games to be played are their intellectual challenge and their entertainment value. For the rst reason games are used as a testing ground for computational intelligence. Since the 1950s the AI community compares the computer performance with the human performance (Schaeer, 2001), or otherwise stated: since the birth of AI computational intelligence is measured with respect to human intelligence. Shannon (1950) and Turing (1953) were the rst to describe a chess-playing program, while Samuel (1959) wrote the rst game-playing program in the domain of Checkers. In the beginning most AI research in games concentrated on

The paper presents a new proof-number (PN) search algorithm, called PDS-PN. It is a two-level search (like PN2), which performs at the first level a depth-first proof-number and disproof-number search (PDS), and at the second level a best-first FIN search. Hence, PDS-PN selectively exploits the power of both PN2 and PDS. Experiments in the domain of Lines of Action are performed. They show that within an acceptable time frame PDS-PN is more effective for really hard endgame positions than alphabeta and any other PN-search algorithm.