Back to Search
Start Over
Monte-Carlo Tree Search for the game of Scotland Yard
- Source :
- 2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, 158-165, STARTPAGE=158;ENDPAGE=165;TITLE=2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, CIG
- Publication Year :
- 2011
-
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.
- 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
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- 2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, 158-165, STARTPAGE=158;ENDPAGE=165;TITLE=2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, CIG
- Accession number :
- edsair.doi.dedup.....ee5afa825b19b55ecc940fc50c710b0b