UCT for Games and Beyond

Lead Research Organisation: University of Bradford
Department Name: School of Computing, Informatics & Media

Abstract

Artificial Intelligence (AI) research and the development of the multi-billion dollar video games industry have gone hand in hand for many years. Video games are by far the most prevalent way that the public encounter AI techniques on a day to day basis, and the desire for better video games has driven AI research in areas such as move/path planning, decision making, non-player character (NPC) behaviour and the automated generation of game content. A recent development of Monte Carlo methods called the Upper Confidence Bounds for Trees (UCT) method promises to have a profound impact on AI for games. Applications of UCT are not limited to games and have potential benefits for almost any domain where simulation and statistical modelling can be used to forecast outcomes, such as planning, decision support, economic modelling, behavioural analysis, and so on.Since it appeared in 2006/7, UCT has revolutionised the demanding problem of move planning for computer Go to produce artificial players able to beat professional players for the first time this year, a feat previously thought infeasible. UCT has also been successfully applied to the less specialised domain of General Game Playing (GGP) to produce the 2008 and 2009 world champion GGP programs. This success in Go, where substantial problem-specific knowledge is used, and in GGP, where it is impossible to use problem-specific knowledge, points to the tantalising possibility of the broad use of UCT between these two extremes. Game AI researchers are now starting to take such a great interest in UCT that we are seeing the birth of a new research field of Monte Carlo Tree Search (MCTS). However, there has been to date no unified effort to fully understand and exploit the UCT algorithm and related MCTS methods, a state of affairs that we plan to redress.The proposed research will develop and evaluate novel extensions of the UCT method to increase its applicability to a broad range of game-related domains including: its use for move planning and decision making in infinite, continuous real-time environments; its application to situations involving uncertainty and incomplete information; and its application to multi-objective and ensemble planning approaches. We will also investigate its use for more general game-related problems including the detection and optimisation or correction of suboptimal game designs and game content, and the automated generation of new high quality games and game content. Further, we will demonstrate how the techniques we develop can be applied to broader non-game domains by demonstrating their application to robotic control and automated music generation, in particular the creatively challenging task of jazz improvisation.The potential impact of UCT and MCTS cannot be overstated. Landmark events that have driven AI research include the introduction of tree search methods which have been the backstay of AI decision making since the inception of this field in the 1950s, and the formalisation of Monte Carlo methods in the 1970s for simulation-based decision making in a broader range of more general and less well-defined problems. UCT/MCTS promises to be the next major breakthrough in AI methods that combines the power of tree search with the generality of simulation-based search.

Publications

10 25 50

Related Projects

Project Reference Relationship Related To Start End Award Value
EP/H049061/1 01/10/2010 31/08/2012 £397,316
EP/H049061/2 Transfer EP/H049061/1 01/09/2012 28/02/2014 £166,170
 
Description These have all been reported in "UCT for Games and Beyond" EP/H049061/2
Exploitation Route These have all been reported in "UCT for Games and Beyond" EP/H049061/2
Sectors Creative Economy,Digital/Communication/Information Technologies (including Software)

 
Description These have all been reported in "UCT for Games and Beyond" EP/H049061/2.
First Year Of Impact 2014
Sector Creative Economy,Digital/Communication/Information Technologies (including Software)
 
Description AI Factory Collaboration 
Organisation AI Factory
Country United Kingdom 
Sector Private 
PI Contribution Our decision-making AI technology has been used directly in AI factory's mobile games - and has been downloaded over 5 million times, propelling their implementation of the card game "Spades" to number 1 in the Android charts.
Collaborator Contribution AI Factory provided access to the game's source code, integrated the AI and deployed it in their Spades game. Since deployment they have collected and shared with us a large amount of gameplay data that has been of great use in future research.
Impact The AI we developed helped their implementation of the card game "Spades" reach number 1 in the Google Play Store (Android) charts. Peter Cowling and Jeff Rollason gave a joint Keynote at the world's leading Game Developers Conference in 2014 - and a number of papers were co-published with Jeff Rollason.
Start Year 2011
 
Title mcts.ai 
Description Library for Monte Carlo Tree Search 
Type Of Technology Software 
Year Produced 2013 
Open Source License? Yes  
Impact Work with AI Factory and used in 
 
Description Google's Go triumph is a milestone for artificial intelligence research - Article for the Conversation 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Article written for The Conversation by Peter Cowling and Sam Devlin, explaining the impact of Google Deep Mind's success in developing AI to beat the European Go Champion - with strong links to their own research in AI.
The article has been republished many times and shared with more than 200 social media shares.
Year(s) Of Engagement Activity 2016
URL https://theconversation.com/googles-go-triumph-is-a-milestone-for-artificial-intelligence-research-5...
 
Description Let us Play: Artificial and Human Intelligence in Games 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Public/other audiences
Results and Impact Public engagement talk on AI and HCI research in Games
Year(s) Of Engagement Activity 2015
 
Description Monte Carlo Tree Search Tutorial 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact An invited tutorial at the IEEE Computational Intelligence in Games conference (IEEE CIG 2012) on the algorithms researched as part of the project
Year(s) Of Engagement Activity 2012
 
Description Monte Carlo Tree Search for Card and Board Games 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Industry/Business
Results and Impact An invited talk at the Vienna Game AI Conference held by AIGameDev.com
Year(s) Of Engagement Activity 2012
 
Description Peter Cowling attended UKIE Westminster reception (with Matt Hancock MP and others) 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Policymakers/politicians
Results and Impact I was invited to a UKIE-hosted reception at Westminster - providing an opportunity to talk about our research to people at Westminster including Noirin Carmody (chair of UKIE), Lynne Kilpatrick (civil servant - Head of Video Games and Creative Industries Skills) and many from the games industry.
Year(s) Of Engagement Activity 2017
URL https://ukie.org.uk/event/2017/10/16/westminster-games-industry-day
 
Description Peter Cowling contributed to Dagstuhl Seminar with leading international experts on "AI-Driven Games Design" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Industry/Business
Results and Impact A workshop bringing together 30 of the world's leading researchers in AI-Driven game design - to set the agenda for research in this area for the coming decade. I polled 100 industry partners and took along the best research questions coming from that poll.
Year(s) Of Engagement Activity 2017,2018
URL https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=17471
 
Description Rolling the Dice: Leveraging Monte Carlo Tree Search in Game AI 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Industry/Business
Results and Impact An invited talk on the research outputs of the project at the largest industry conference in the area
Year(s) Of Engagement Activity 2014
URL http://schedule2014.gdconf.com/session-id/828005