MCSIG:Main
From Grand Forum
MCSIG Mailing List
Project Name: Monte-Carlo Search in Games
Project Leader
Project Co-Leader
Researchers
- Jonathan Schaeffer (Alberta)
- Holger Hoos (UBC)
- Michael Buro (Alberta)
- Ryan Hayward (Alberta)
- Martin Mueller (Alberta)
- Nathan Sturtevant (Alberta)
- Csaba Szepesvari (Alberta)
Theme Distribution
Project Description
Achieving intelligent behavior of artificial characters and opponents is a key challenge of interactive entertainment. Traditional methods for building high performance systems that exhibit such behaviour, in real time, have been limited by the knowledge acquisition bottleneck. Monte-Carlo Tree Search (MCTS) is a relatively recent and very succesful new approach that sidesteps this bottleneck. It uses statistical methods based on sampling and building a selective search tree. It has been shown to work much better than previous approaches in challenging domains such as Go and General Game Playing, while requiring comparatively very little domain-specific knowledge.
This project aims to advance the state of the art in MCTS methods, generalize them to new application domains, and push the performance of existing applied systems (Kocsis & Szepesvari, 2006; Enzenberger & Mueller, 2006). . Key to this approach are combining the automated algorithm design techniques contributed by the UBC-based group of Prof. Hoos with the experience in building game-playing systems at University of Alberta. Our applications are in varied games domains to demonstrate the generality of the methods. Games provide the advantage of virtual worlds with clear rules and boundaries, and controllable complexity. Improving the decision-making ability of programs in such domains can serve as a stepping stone to tackling less well-defined real-world applications. One important question to be addressed in this research is how to integrate the best existing approaches such as inference and domain knowledge into an MCTS framework. Another goal of the project is to harness massively parallel AI aims to exploit the demonstrated scalability of MCTS with increased computing power,
Excellence of the Research
Development of Highly Qualified Personnel (HQP)
Students participating in this project will be trained in state-of-the-art technology with high expected impact on building future high-performance AI systems. They will acquire hands-on knowledge of state-of-the-art approaches in computer-aided algorithm design and parallel AI systems, and they will have a chance to showcase their work through participation in the development of world-class, competitive game-playing systems.
Networking and Partnerships
Both groups at the Universities of Alberta and British Columbia have established extensive industry contacts and partnerships with companies, including IBM and Actenum Corporation (a Canadian company), and researchers from internationally leading institutions, including IRIDIA at Universite Libre de Bruxelles (Belgium), Sandia Labs (USA) and the Tokyo Institute of Technology (Japan).
Knowledge and Technology Exchange and Exploitation
The Alberta group has an ongoing partnership with IBM, who has committed two full-time researchers and signed a joint study agreement with the University of Alberta that gives access to IBM source code and research results resulting from this project.
We expect this project to produce fundamental improvements that provide an excellent basis for commercial applications in computer games and other domains in which Monte Carlo search techniques are used.
References to the Literature
M. Enzenberger and M. Mueller (2009). A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm, accepted for Advances in Computer Games 12, 2009. http://www.cs.ualberta.ca/~mmueller/ps/enzenberger-mueller-acg12.pdf
L. Kocsis and C. Szepesvari (2006). Bandit Based Monte-Carlo Planning. Proceedings of the 17th European Conference on Machine Learning, Springer-Verlag, Berlin, LNCS/LNAI 4212, September 18-22, pp. 282-293, 2006. http://zaphod.aml.sztaki.hu/papers/ecml06.pdf
Publications
Presentations
|  |