50 results on '"Mark H. M. Winands"'
Search Results
2. Analysis of the Impact of Randomization of Search-Control Parameters in Monte-Carlo Tree Search
- Author
-
Mark H. M. Winands, Chiara F. Sironi, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
Randomization ,Artificial Intelligence ,Computer science ,Monte Carlo tree search ,Control parameters ,Algorithm - Abstract
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.
- Published
- 2021
3. Enhancing Playout Policy Adaptation for General Game Playing
- Author
-
Mark H. M. Winands, Chiara F. Sironi, Tristan Cazenave, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
0209 industrial biotechnology ,Discounting ,Mathematical optimization ,Computer science ,Monte Carlo tree search ,Control (management) ,02 engineering and technology ,computer.software_genre ,General game playing ,Tree (data structure) ,020901 industrial engineering & automation ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Adaptation (computer science) ,Set (psychology) ,computer ,Selection (genetic algorithm) - Abstract
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.
- Published
- 2021
4. Monte Carlo Tree Search as an intelligent search tool in structural design problems
- Author
-
L. Rossi, Mark H. M. Winands, Christoph Butenweg, RS: FSE DACS, and Dept. of Advanced Computing Sciences
- Subjects
Artificial intelligence ,Reinforced concrete buildings ,Computer science ,Monte Carlo tree search ,GAME ,020101 civil engineering ,02 engineering and technology ,Machine learning ,computer.software_genre ,0201 civil engineering ,Set (abstract data type) ,03 medical and health sciences ,structural design ,Genetic algorithm ,Civil engineering ,030304 developmental biology ,Structure (mathematical logic) ,0303 health sciences ,monte carlo tree search ,business.industry ,Design tool ,General Engineering ,Computer Science Applications ,Term (time) ,ARTIFICIAL NEURAL-NETWORKS ,GO ,Software agent ,Modeling and Simulation ,Applications of artificial intelligence ,ddc:620 ,business ,computer ,Software - Abstract
Engineering with computers (2021). doi:10.1007/s00366-021-01338-2, Published by Springer, London
- Published
- 2021
5. Adaptive General Search Framework for Games and Beyond
- Author
-
Chiara F. Sironi, Mark H. M. Winands, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
adaptive search ,ALGORITHM SELECTION ,General Game Playing ,search algorithm generation ,Artificial General Intelligence - Abstract
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.
- Published
- 2021
6. Comparing Randomization Strategies for Search-Control Parameters in Monte-Carlo Tree Search
- Author
-
Mark H. M. Winands, Chiara F. Sironi, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Randomization ,Theoretical computer science ,Monte-Carlo tree search ,Computer science ,Monte Carlo tree search ,A domain ,search-control parameter ,Diversification (marketing strategy) ,randomization ,computer.software_genre ,General game playing ,Tree (data structure) ,General Game Playing ,Control parameters ,computer - Abstract
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.
- Published
- 2019
7. Self-Adaptive Rolling Horizon Evolutionary Algorithms for General Video Game Playing
- Author
-
Raluca D. Gaina, Simon M. Lucas, Diego Perez-Liebana, Mark H. M. Winands, Chiara F. Sironi, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
Computer science ,Process (engineering) ,business.industry ,Key (cryptography) ,Evolutionary algorithm ,State (computer science) ,Artificial intelligence ,Rolling horizon ,Adaptation (computer science) ,business ,General video game playing ,Variety (cybernetics) - Abstract
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.
- Published
- 2020
8. Self-Adaptive Monte Carlo Tree Search in General Game Playing
- Author
-
Chiara F. Sironi, Mark H. M. Winands, Jialin Liu, DKE Scientific staff, and RS: FSE DACS
- Subjects
Optimization ,Mathematical optimization ,Offline optimization ,on-line parameter tuning ,Computer science ,Monte Carlo method ,Monte Carlo tree search ,Evolutionary algorithm ,Self adaptive ,Evolutionary computation ,computer.software_genre ,general game playing (GGP) ,General game playing ,N-tuple systems ,Artificial Intelligence ,Resource management ,Combinatorial multi-armed bandit (CMAB) ,STRATEGY ,Electrical and Electronic Engineering ,evolutionary algorithms ,Monte Carlo methods ,Tuners ,Control and Systems Engineering ,Games ,computer ,Software - Abstract
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.
- Published
- 2020
9. Editorial: Many games, many authors
- Author
-
Mark H. M. Winands, Dept. of Advanced Computing Sciences, RS: FSE DACS, and DKE Scientific staff
- Subjects
Human-Computer Interaction ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2020
10. The 2016 Two-Player GVGAI Competition
- Author
-
Simon M. Lucas, Raluca D. Gaina, Dennis J. N. J. Soemers, Diego Perez-Liebana, Tom Vodopivec, Adrien Couëtoux, Florian Kirchgesner, Mark H. M. Winands, Jialin Liu, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Sequential game ,Computer science ,Combinatorial game theory ,GAME ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,General video game playing ,Strategy ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,Video game ,TREE-SEARCH ,Game mechanics ,business.industry ,Competitions ,real-time games ,ComputingMilieux_PERSONALCOMPUTING ,Screening game ,Monte Carlo tree search (MCTS) ,010201 computation theory & mathematics ,Control and Systems Engineering ,general video game playing (GVGP) ,Repeated game ,020201 artificial intelligence & image processing ,Artificial intelligence ,rolling horizon evolutionary algorithms (RHEAs) ,business ,multiplayer games ,Software - Abstract
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.
- Published
- 2018
11. Optimising Level Generators for General Video Game AI
- Author
-
Diego Perez-Liebana, Olve Drageset, Mark H. M. Winands, Raluca D. Gaina, RS: FSE DACS NSO, and DKE Scientific staff
- Subjects
level generation ,Fitness function ,Generator (computer programming) ,Computer science ,business.industry ,Parameterized complexity ,GVGAI ,Context (language use) ,Machine learning ,computer.software_genre ,Evaluation function ,Constructive ,Genetic algorithm ,genetic algorithm ,Artificial intelligence ,business ,computer ,Video game - Abstract
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.
- Published
- 2019
12. Implementing Propositional Networks on FPGA
- Author
-
Chiara F. Sironi, Mark H. M. Winands, Jakub Kowalski, Cezary Siwek, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Computer science ,Monte Carlo tree search ,Process (computing) ,ComputingMilieux_PERSONALCOMPUTING ,020206 networking & telecommunications ,02 engineering and technology ,computer.software_genre ,Software implementation ,General game playing ,Computer engineering ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Field-programmable gate array ,Representation (mathematics) ,computer - Abstract
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.
- Published
- 2018
13. Editorial: Commemorating computer chess
- Author
-
Mark H. M. Winands, Dept. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
Human-Computer Interaction ,Engineering ,business.industry ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer chess ,business ,Computer Graphics and Computer-Aided Design ,Visual arts - Published
- 2020
14. Algorithms for computing strategies in two-player simultaneous move games
- Author
-
Marc Lanctot, Viliam Lisý, Branislav Bošanský, Jiří Čermák, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Computer Science::Computer Science and Game Theory ,Linguistics and Language ,Mathematical optimization ,Sequential game ,Monte Carlo Tree Search ,Monte Carlo tree search ,02 engineering and technology ,010501 environmental sciences ,computer.software_genre ,01 natural sciences ,Nash equilibrium ,Language and Linguistics ,General game playing ,symbols.namesake ,Markov games ,Artificial Intelligence ,Online search ,Game playing ,0202 electrical engineering, electronic engineering, information engineering ,Simultaneous move games ,Alpha-beta pruning ,0105 earth and related environmental sciences ,Mathematics ,Counterfactual regret minimization ,Regret matching ,Double-oracle algorithm ,Alpha–beta pruning ,Backward induction ,symbols ,020201 artificial intelligence & image processing ,Algorithm ,computer ,Gibbs sampling - Abstract
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.
- Published
- 2016
15. Editorial: Back to the roots
- Author
-
Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS
- Subjects
Human-Computer Interaction ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2019
16. Analysis of Self-Adaptive Monte Carlo Tree Search in General Video Game Playing
- Author
-
Mark H. M. Winands, Chiara F. Sironi, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Monte-Carlo tree search ,on-line parameter tuning ,business.industry ,Computer science ,Monte Carlo method ,Monte Carlo tree search ,Evolutionary algorithm ,02 engineering and technology ,021001 nanoscience & nanotechnology ,General video game playing ,Evolutionary computation ,Domain (software engineering) ,Tree (data structure) ,general video game playing ,0202 electrical engineering, electronic engineering, information engineering ,self-adaptive search ,020201 artificial intelligence & image processing ,Artificial intelligence ,0210 nano-technology ,business ,Video game - Abstract
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.
- Published
- 2018
17. CIG 2018 Preface
- Author
-
Cameron Browne, Jialin Liu, Mark H. M. Winands, Mike Preuss, DKE Scientific staff, RS: FSE DACS NSO, and RS: FSE DACS
- Published
- 2018
18. Editorial: Get serious
- Author
-
Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Human-Computer Interaction ,Computer science ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2019
19. MCTS-Minimax Hybrids with State Evaluations
- Author
-
Mark H. M. Winands, Hendrik Baier, DKE Scientific staff, RS: FSE DACS NSO, RS: FSE DACS, and Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
- Subjects
Mathematical optimization ,Statistics::Theory ,GAME ,02 engineering and technology ,State (functional analysis) ,Minimax ,Highly selective ,CARLO TREE-SEARCH ,Tree (data structure) ,MONTE-CARLO ,Artificial Intelligence ,GO ,0202 electrical engineering, electronic engineering, information engineering ,PROGRAM ,020201 artificial intelligence & image processing ,KNOWLEDGE ,Mathematics - Abstract
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.
- Published
- 2018
20. Special Issue on Computer Aided Game and Puzzle Design
- Author
-
Mark H. M. Winands, Cameron Browne, and Antonios Liapis
- Subjects
Human-Computer Interaction ,Engineering drawing ,Computer science ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer-aided ,Computer Graphics and Computer-Aided Design - Published
- 2019
21. Resource-gathering algorithms in the game of starcraft
- Author
-
Martin L. M. Rooijackers, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Intelligent agent ,Computer science ,ComputingMilieux_PERSONALCOMPUTING ,Computational intelligence ,Adversary ,computer.software_genre ,Algorithm ,computer ,Scheduling (computing) - Abstract
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.
- Published
- 2017
22. Optimizing Propositional Networks
- Author
-
Chiara F. Sironi, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Structure (mathematical logic) ,Speedup ,business.industry ,Process (engineering) ,Computer science ,media_common.quotation_subject ,ComputingMilieux_PERSONALCOMPUTING ,0102 computer and information sciences ,Semantic reasoner ,computer.software_genre ,01 natural sciences ,General game playing ,Prolog ,010201 computation theory & mathematics ,Quality (business) ,Artificial intelligence ,business ,Representation (mathematics) ,computer ,computer.programming_language ,media_common - Abstract
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.
- Published
- 2017
23. Editorial
- Author
-
Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Human-Computer Interaction ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2019
24. Advances in Computer and Games Conference (ACG2019)
- Author
-
Mark H. M. Winands
- Subjects
Human-Computer Interaction ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2019
25. Monte Carlo Tree Search for the Hide-and-Seek Game Scotland Yard
- Author
-
P. Nijssen, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Computer science ,business.industry ,Monte Carlo method ,Monte Carlo tree search ,ComputingMilieux_PERSONALCOMPUTING ,Perfect information ,Cooperation in games ,imperfect information ,Minimax ,Yard ,Seekers ,Monte Carlo tree search (MCTS) ,Categorization ,Artificial Intelligence ,Control and Systems Engineering ,Domain knowledge ,Artificial intelligence ,Electrical and Electronic Engineering ,business ,Scotland Yard ,Software - Abstract
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.
- Published
- 2012
26. Enhancements for Real-Time Monte-Carlo Tree Search in General Video Game Playing
- Author
-
Torsten Schuster, Mark H. M. Winands, Chiara F. Sironi, Dennis J. N. J. Soemers, RS: FSE DACS, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Computer science ,business.industry ,Monte Carlo tree search ,Initialization ,Context (language use) ,0102 computer and information sciences ,02 engineering and technology ,Machine learning ,computer.software_genre ,01 natural sciences ,General video game playing ,Knowledge-based systems ,Tree (data structure) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Pruning (decision trees) ,Artificial intelligence ,Heuristics ,business ,computer - Abstract
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.
- Published
- 2016
27. Sequential halving for partially observable games
- Author
-
Tristan Cazenave, Mark H. M. Winands, Tom Pepels, Dept. of Advanced Computing Sciences, RS: FSE DACS, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Mathematical optimization ,Domineering ,%22">Fish ,Observable ,Algorithm ,Search tree ,Selection (genetic algorithm) ,Imaging phantom ,Mathematics - Abstract
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.
- Published
- 2016
28. IJCAI Computer Games Workshop 2015
- Author
-
Tristan Cazenave, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Human-Computer Interaction ,Computational Mechanics ,Computer Science (miscellaneous) ,Computer Graphics and Computer-Aided Design - Published
- 2017
29. Monte Carlo Tree Search in Lines of Action
- Author
-
Yngvi Björnsson, Mark H. M. Winands, Jahn-Takeshi Saito, DKE Scientific staff, RS: FSE DACS NSO, and Promovendi NTM
- Subjects
Theoretical computer science ,Computer science ,business.industry ,Monte Carlo method ,Monte Carlo tree search ,Branching factor ,Game-tree solver ,Search tree ,Game tree search ,Lines of Action (LOA) ,Monte Carlo tree search (MCTS) ,Action (philosophy) ,Artificial Intelligence ,Control and Systems Engineering ,Domain knowledge ,Artificial intelligence ,Electrical and Electronic Engineering ,business ,Game theory ,Software - Abstract
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.
- Published
- 2010
30. ENHANCED REALIZATION PROBABILITY SEARCH
- Author
-
Mark H. M. Winands, Yngvi Björnsson, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Scheme (programming language) ,Computer program ,Computer science ,Applied Mathematics ,Search, heuristics, games ,Computer Science Applications ,Domain (software engineering) ,Human-Computer Interaction ,Computational Mathematics ,Computational Theory and Mathematics ,Overhead (computing) ,Heuristics ,Algorithm ,computer ,computer.programming_language - Abstract
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.
- Published
- 2008
31. Best Play in Fanorona Leads to Draw
- Author
-
Maurice H. J. Bergsma, Jos W. H. M. Uiterwijk, Maarten P. D. Schadd, H. Jaap van den Jerik, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Engineering ,Exploit ,Computer science ,business.industry ,Applied Mathematics ,Endgame tablebase ,ComputingMilieux_PERSONALCOMPUTING ,Information and Computer Science ,Fanorona, proof-number search, endgame databases ,Data science ,Information science ,Computer Science Applications ,Human-Computer Interaction ,Computational Mathematics ,Computational Theory and Mathematics ,Position (vector) ,Artificial intelligence ,Proof-number search ,business ,Chess endgame ,Value (mathematics) - Abstract
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.
- Published
- 2008
32. Learning to Predict Life and Death from Go Game Records
- Author
-
Erik C. D. van der Werf, H. Jaap van den Herik, Mark H. M. Winands, Jos W. H. M. Uiterwijk, Informatica, and RS: FSE DACS NSO
- Subjects
Information Systems and Management ,learning ,Artificial neural network ,Computer science ,business.industry ,neural net ,life and death ,Perceptron ,Evaluation function ,Machine learning ,computer.software_genre ,Computer Science Applications ,Theoretical Computer Science ,Artificial Intelligence ,Control and Systems Engineering ,Go ,game records ,Artificial intelligence ,business ,Classifier (UML) ,computer ,Software - Abstract
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.
- Published
- 2005
33. Enhanced forward pruning
- Author
-
Jos W. H. M. Uiterwijk, Erik C. D. van der Werf, H. Jaap van den Herik, Mark H. M. Winands, RS: FSE DACS, RS: FHS MICC, and Dept. of Advanced Computing Sciences
- Subjects
Reduction (complexity) ,Variable (computer science) ,Information Systems and Management ,Artificial Intelligence ,Control and Systems Engineering ,Principal variation search ,Null (mathematics) ,Pruning (decision trees) ,Algorithm ,Software ,Computer Science Applications ,Theoretical Computer Science ,Mathematics - Abstract
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.
- Published
- 2005
34. Monte carlo tree search with heuristic evaluations using implicit minimax backups
- Author
-
Marc Lanctot, Nathan R. Sturtevant, Tom Pepels, Mark H. M. Winands, DKE Scientific staff, RS: FSE DACS NSO, Dep. of Advanced Computing Sciences, and RS: FSE DACS
- Subjects
FOS: Computer and information sciences ,Mathematical optimization ,Negamax ,Computer Science - Artificial Intelligence ,Monte Carlo tree search ,Minimax ,computer.software_genre ,Expectiminimax tree ,General game playing ,Artificial Intelligence (cs.AI) ,Heuristic evaluation ,Minimax search ,computer ,Mathematics ,Killer heuristic - Abstract
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
- Published
- 2014
35. Monte Carlo Tree Search variants for simultaneous move games
- Author
-
Mandy J. W. Tak, Mark H. M. Winands, Marc Lanctot, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Set (abstract data type) ,Mathematical optimization ,Class (set theory) ,Computer Science::Computer Science and Game Theory ,Theoretical computer science ,Matching (graph theory) ,Computer science ,Monte Carlo tree search ,ComputingMilieux_PERSONALCOMPUTING ,Regret ,Extension (predicate logic) ,Selection (genetic algorithm) - Abstract
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.
- Published
- 2014
36. Improving Best-Reply Search
- Author
-
Mark H. M. Winands, Marc Lanctot, Maarten P. D. Schadd, Markus Esser, Michael Gras, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Discrete mathematics ,Computer science ,ComputingMilieux_PERSONALCOMPUTING ,Order (ring theory) ,Best reply ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) - Abstract
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.
- Published
- 2014
37. Minimizing Simple and Cumulative Regret in Monte-Carlo Tree Search
- Author
-
Mark H. M. Winands, Tristan Cazenave, Marc Lanctot, and Tom Pepels
- Subjects
Tree (data structure) ,Mathematical optimization ,Regret minimization ,Computer science ,Simple (abstract algebra) ,Monte Carlo tree search ,Regret ,Selection (genetic algorithm) ,Computational budget - Abstract
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.
- Published
- 2014
38. Monte Carlo Tree Search in Simultaneous Move Games with Applications to Goofspiel
- Author
-
Viliam Lisý, Mark H. M. Winands, Marc Lanctot, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Matching (graph theory) ,Computer science ,business.industry ,Monte Carlo tree search ,Perfect information ,Sampling (statistics) ,Regret ,Machine learning ,computer.software_genre ,Outcome (game theory) ,symbols.namesake ,Nash equilibrium ,Search algorithm ,symbols ,Artificial intelligence ,business ,computer - Abstract
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.
- Published
- 2014
39. Game-Tree Search Using Proof Numbers: The First Twenty Years
- Author
-
Martin Müller, Jahn-Takeshi Saito, Mark H. M. Winands, Akihiro Kishimoto, DKE Scientific staff, RS: FSE DACS NSO, and Bioinformatica
- Subjects
Human-Computer Interaction ,Theoretical computer science ,Computer science ,Computational Mechanics ,Computer Science (miscellaneous) ,Checkmate ,Take over ,Computer Graphics and Computer-Aided Design ,Domain (software engineering) ,Game tree search ,Task (project management) - Abstract
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.
- Published
- 2012
40. Time management for Monte-Carlo tree search in Go
- Author
-
Hendrik Baier, Mark H. M. Winands, DKE Scientific staff, RS: FSE DACS NSO, and RS: FSE DACS
- Subjects
Tree (data structure) ,Mathematical optimization ,Time control ,Computer science ,Monte Carlo tree search ,Time allocation ,Time management ,Tournament ,State (computer science) ,Duration (project management) - Abstract
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.
- Published
- 2012
41. Enhancements for Monte-Carlo Tree Search in Ms Pac-Man
- Author
-
Mark H. M. Winands, Tom Pepels, Dep. of Advanced Computing Sciences, RS: FSE DACS, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Tree (data structure) ,Variable (computer science) ,Theoretical computer science ,business.industry ,Software agent ,Computer science ,Monte Carlo method ,Path (graph theory) ,Monte Carlo tree search ,Computational intelligence ,Artificial intelligence ,business ,Chess endgame - Abstract
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.
- Published
- 2012
42. Monte-Carlo tree search enhancements for Havannah
- Author
-
Jan A. Stankiewicz, Mark H. M. Winands, Jos W. H. M. Uiterwijk, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Tree (data structure) ,business.industry ,Computer science ,Monte Carlo tree search ,Initialization ,Artificial intelligence ,Enhanced Data Rates for GSM Evolution ,business ,Machine learning ,computer.software_genre ,computer ,Selection (genetic algorithm) - Abstract
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.
- Published
- 2012
43. Playout search for Monte-Carlo tree search in multi-player games
- Author
-
Mark H. M. Winands, J. (Pim) A. M. Nijssen, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Tree (data structure) ,Theoretical computer science ,Computer science ,Reliability (computer networking) ,InformationSystems_INFORMATIONSYSTEMSAPPLICATIONS ,Monte Carlo tree search ,Real-time computing ,ComputingMilieux_PERSONALCOMPUTING ,Order (ring theory) ,ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS ,Data_CODINGANDINFORMATIONTHEORY ,Focus (optics) - Abstract
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.
- Published
- 2012
44. Best Reply Search for Multiplayer Games
- Author
-
Maarten P. D. Schadd, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Chinese Checkers ,Root (linguistics) ,paranoid ,Multiplayer games ,Max(n) ,business.industry ,Computer science ,ComputingMilieux_PERSONALCOMPUTING ,Perfect information ,Best reply ,best reply search (BRS) ,Focus ,Artificial Intelligence ,Control and Systems Engineering ,Rolit ,Artificial intelligence ,Electrical and Electronic Engineering ,business ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,Game theory ,Software - Abstract
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.
- Published
- 2011
45. Monte-Carlo Tree Search for the game of Scotland Yard
- Author
-
J. (Pim) A. M. Nijssen, Mark H. M. Winands, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
Operations research ,Computer science ,business.industry ,Monte Carlo tree search ,ComputingMilieux_PERSONALCOMPUTING ,GeneralLiterature_MISCELLANEOUS ,Yard ,Reduction (complexity) ,Tree (data structure) ,Seekers ,Categorization ,Domain knowledge ,Graph (abstract data type) ,Artificial intelligence ,business - Abstract
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.
- Published
- 2011
46. Randomized Parallel Proof-Number Search
- Author
-
H. Jaap van den Herik, Jahn-Takeshi Saito, Mark H. M. Winands, DKE Scientific staff, RS: FSE DACS NSO, and Informatica
- Subjects
Set (abstract data type) ,Theoretical computer science ,Shared memory ,Computer science ,Parallel computing ,Proof-number search ,Chess endgame ,Selection (genetic algorithm) ,Search tree - Abstract
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.
- Published
- 2010
47. Proof-Number Search and Its Variants
- Author
-
Mark H. M. Winands, H. Jaap van den Herik, Informatica, and RS: FSE DACS NSO
- Subjects
Incremental heuristic search ,Fringe search ,Search algorithm ,Computer science ,Beam search ,Best-first search ,Proof-number search ,Game tree ,Algorithm ,Tabu search - Abstract
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.
- Published
- 2008
48. Preface for the special issue on Games and AI
- Author
-
Mark H. M. Winands, Yngvi Björnsson, Karl Tuyls, DKE Scientific staff, RS: FSE DACS NSO, and RS: FSE DACS RAI
- Subjects
Value (ethics) ,Civilization ,Computer performance ,Human intelligence ,business.industry ,Computer science ,media_common.quotation_subject ,ComputingMilieux_PERSONALCOMPUTING ,Computational intelligence ,Domain (software engineering) ,Human-Computer Interaction ,Entertainment ,Mathematics education ,Artificial intelligence ,business ,Turing ,computer ,Software ,computer.programming_language ,media_common - Abstract
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
- Published
- 2012
49. THE 11TH COMPUTER OLYMPIAD (CONTINUED)
- Author
-
J.W. Hellemons, H.J. van den Herik, and Mark H. M. Winands
- Subjects
Human-Computer Interaction ,Engineering ,business.industry ,Computational Mechanics ,Computer Science (miscellaneous) ,Mathematics education ,Olympiad ,business ,Computer Graphics and Computer-Aided Design - Published
- 2006
50. An effective two-level proof-number search algorithm
- Author
-
H. Jaap van den Herik, Mark H. M. Winands, Jos W. H. M. Uiterwijk, Dept. of Advanced Computing Sciences, RS: FSE DACS, and RS: FHS MICC
- Subjects
General Computer Science ,Two-level search ,Best-first search ,Proof-number search ,Iterative deepening depth-first search ,Lines of Action ,Theoretical Computer Science ,PDS ,Jump search ,Search algorithm ,Beam stack search ,Beam search ,Interpolation search ,Algorithm ,Mathematics ,Computer Science(all) - Abstract
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.
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.