UCT for Games and Beyond

Lead Research Organisation: University of Essex
Department Name: Computer Sci and Electronic Engineering

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
publication icon
Browne C (2012) A Survey of Monte Carlo Tree Search Methods in IEEE Transactions on Computational Intelligence and AI in Games

publication icon
Perez D (2014) Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions in IEEE Transactions on Computational Intelligence and AI in Games

publication icon
Perez D (2014) Automated Map Generation for the Physical Traveling Salesman Problem in IEEE Transactions on Evolutionary Computation

publication icon
Perez D (2015) Multiobjective Monte Carlo Tree Search for Real-Time Games in IEEE Transactions on Computational Intelligence and AI in Games

publication icon
Perez-Liebana D (2016) The 2014 General Video Game Playing Competition in IEEE Transactions on Computational Intelligence and AI in Games

 
Title Griddle Plus Word Game 
Description The research undertaken on the grant led to a new game being developed to showcase the Monte Carlo Tree Search AI in providing an elegant and powerful AI opponent for players of the game. (extract from Google Play Store entry) Griddle: This simple but addictive word game strikes a fine balance between skill and luck. 25 cards will be dealt to you, from a specially designed 74 letter-card deck, which you have to strategically place onto your grid. Score as many points as you can, but be careful: once a letter is placed, it cannot be moved. Only vertical and horizontal words are allowed, but sub-words (within words) count, so try to make 5-letter words that have lots of shorter words within them. Words are checked against the integrated scrabble-style dictionary. You may be surprised at how many unusual words exist! (see URL below for full description; the game is currently only available on Android) 
Type Of Art Artefact (including digital) 
Year Produced 2014 
Impact The game showcased our ability as a group to develop robust applications for mobile platforms and helped a TSB Integrated Transport Feasibility Study be funded, which is now being considered for full funding. 
URL https://play.google.com/store/apps/details?id=com.lucapps.gstate&hl=en
 
Description That the game AI methods we developed are very general and can be applied directly to a range of problems with a minimum of domain-specific programming.
Exploitation Route The Games industry is crying out for better AI, and for more creative games. Our form of general video game AI is beginning to be adopted by some UK Games Studios such as Creative Assembly and Lionhead, but there is much more scope to adopt these methods and also use them to evaluate new video games.

We have submitted a new EPSRC proposal in order to follow this up.
Sectors Creative Economy,Digital/Communication/Information Technologies (including Software),Education,Leisure Activities, including Sports, Recreation and Tourism

URL http://gvgai.net
 
Description Our competitions framework has been used outside of academia. Members of the public have participated in our AI competitions such as Ms Pac-Man versus Ghost Team competition, the Physical Travelling Salesman Competition, and the General Video Game AI Competition. Various universities around the world have also used our competition server software to run their own competitions fore their bachelors, masters and PhD programmes.
First Year Of Impact 2011
Sector Creative Economy,Education,Leisure Activities, including Sports, Recreation and Tourism
Impact Types Cultural,Societal,Policy & public services

 
Description EPSRC CDT Call
Amount £5,589,906 (GBP)
Funding ID e:EP/L015846/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Academic/University
Country United Kingdom
Start 04/2014 
End 09/2022
 
Description IGGI Centre for Doctoral Training 
Organisation Goldsmiths, University of London
Country United Kingdom 
Sector Academic/University 
PI Contribution Professor Lucas is the PI at Essex
Collaborator Contribution Co-authored the application.
Impact Too early: the doctoral training programme had its first intake of students in September 2014.
Start Year 2014
 
Description IGGI Centre for Doctoral Training 
Organisation University of York
Country United Kingdom 
Sector Academic/University 
PI Contribution Professor Lucas is the PI at Essex
Collaborator Contribution Co-authored the application.
Impact Too early: the doctoral training programme had its first intake of students in September 2014.
Start Year 2014
 
Title General Video Game AI Server (GVGAI) 
Description The GVGAI server is used to run competitions and on-going leagues testing the ability of AI controllers to play any game without knowing the set of games in advance. This is designed to provide a tool for developing and testing game AI, and also testing the quality of games submitted to the system by measuring the experience of a range of bots while playing those games. This will also enable progress towards general intelligence. 
Type Of Technology Webtool/Application 
Year Produced 2014 
Impact This is having a significant impact on video game research, and is currently being adopted by many researchers as a way to develop and test their game AI algorithms, as well as being used in various computer science masters programmes. 
URL http://gvgai.net/
 
Description University of Essex 2012 Christmas Lectures 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Regional
Primary Audience Schools
Results and Impact Visiting students played a competitive multi-arm bandit game which sparked a good deal of audience interest and discussion afterwards on the trade-off between exploitation and exploration in life in general.

Since doing the Christmas lectures our UG admissions have increased significantly. While it is not possible to prove cause and effect in cases like this, anecdotal evidence suggests that this and other activities have been important.
Year(s) Of Engagement Activity 2012