UCT for Games and Beyond

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.

UCT has revolutionised the world of Computer Go, with computer players based on these techniques playing at a level that was inconceivable only a decade ago. We believe that a similar level of impact can be achieved in a far broader range of game and non-game domains to significantly benefit the multi-billion dollar video games industry and, more generally, AI research into search, optimisation and decision making. The vast majority of UCT research to date has been done outside the UK (largely in France, Canada, and the US). This state of affairs should not be allowed to continue; funding this research will make UCT research more accessible to UK industry. The public have already shown a great appetite for innovation in video games, with UK games studios well known internationally for their pioneering work in AI. UCT could provide a huge fillip to a new generation of video game designers. Better AI is seen by most game studios as being critical to the success of future titles, and there are now many well documented cases of smart AI being a major selling point of a game with titles such as F.E.A.R, Halo 3, Left4Dead and Crysis being prime examples. The best way to achieve effective AI is heavily debated and is dependent on many factors such as the complexity of the problem, the tools available, the skills base within a company, etc. However, for many games, good AI is extremely hard to achieve and is often one of the most disappointing aspects of even AAA game titles with budgets in the tens or hundreds of millions of dollars. UCT has the potential to revolutionise video game AI in the same way that it has revolutionised Computer Go and General Game Playing. It will lead to characters that behave in appropriate ways not because they have been explicitly programmed to do so, but because such behaviour emerges as the optimal response to a given situation through statistical simulation. This is a very general approach that can shape behaviour in all kinds of ways, in order to make it smarter, more stupid, more challenging, more supportive, and so on. Our work should provide tools that help deliver an optimised player experience with relatively little programming effort. In addition to the direct use of UCT to enhance the AI of the in-game characters, equally significant is the use of UCT as a game designer's tool to analyse the quality of the game mechanics. The proposed research has the potential for enormous impact in the UK and worldwide and we aim to fully exploit this.