Video Games and Artificial Intelligence

Established: June 10, 2009

The tutorial will give an introduction to the area of applying AI techniques, such as learning, search and planning, to video games. It will focus on past and recent applications, open problems and promising avenues for future research, and on resources available to people who would like to work in this space.
  • AI research and video games are a mutually beneficial combination. On the one hand, AI technology can provide solutions to an increasing demand to add realistic, intelligent behaviour to the virtual creatures that populate a game world. On the other hand, as game environments become more complex and realistic, they offer a range of excellent testbeds for fundamental AI research.

    This tutorial will give an introduction to the area of applying AI techniques, such as learning, search and planning, to video games. The tutorial will focus on past and recent applications, open problems and promising avenues for future research, and on resources available to people who would like to work in this space. We will present concrete AI techniques used in games and give references to relevant work. We hope that the topic is relevant to both game developers looking for ways to improve their products, and researchers looking for realistic benchmarks to test new algorithms and ideas.

  • We target our tutorial to researchers and practitioners with an interest in one or more fields such as video games, learning, planning and search. No deep prior knowledge is required in either of the covered topics.

  • Let us begin with a provocative question: In which area of human life is artificial intelligence (AI) currently applied the most? The answer, by a large margin, is Computer Games. This is essentially the only big area in which people deal with behaviour generated by AI on a regular basis. And the market for video games is growing, with sales in 2007 of $17.94 billion marking a 43% increase over 2006. However, growth is not only in sales but also in the diversity of content offered, ranging from educational games to first-person shooters. In addition, a fascinating convergence of media is taking place with video games often having movie quality cut-scenes and narrative.

    So, where does artificial intelligence come into play? We argue that both games and AI research can greatly benefit from each other. From a research point of view, video games offer fascinating toy examples that capture the complexity of real-world situations while maintaining the controllability and traceability of computer simulations. As an example, consider the problem of driving a racing car under realistic race conditions. While the full problem is too complex to be tackled right now because it involves problems around limited actuators and noisy sensors in addition to the AI problem, important aspects can be tackled working inside a state-of-the-art racing game simulation. As game designers work hard to create more realistic worlds for their customers, AI researchers can benefit from access to benchmarks that accurately reflect real-life problems. Games exhibit many combinations of features that are important in current AI research. For example, a game environment can be either static or dynamic, there can be either single-agent or two-player or multi-agent problems, transitions can be either deterministic or non-deterministic, and game worlds can be either fully known or partially observable.

    From a games perspective, one key problem is the creation of AI driven agents that can interact with the player and be adaptive so as to create a great interactive gaming experience. These agents can take a variety of roles such as player’s opponents, teammates or other non-player characters. Online planning and reinforcement learning have the ability to create adaptive behaviour, which might become a key feature in future games. This is useful to respond to changes in the human player strategy, the environment, the current problem instance, etc. Games like Creatures and Black & White have attempted to build entire games around the concept of teaching behaviour to adaptive AI agents.

    A few concrete examples of AI challenges in games, which we plan to cover in this tutorial, include driving a car in a racing game, path finding on a map, planning the behaviour of non-player characters in a role-playing game, resource gathering in a real-time strategy game, and planning the strategy of a combat team in a first-person shooting game. We anticipate that people from the AI community will have a lot to contribute to the field of computer games once the wealth of opportunities in this space has been understood.

    However, computer games offer a great variety of other challenges including problems in graphics, sound, networking, player rating and matchmaking, interface design, narrative generation, game world design, scripting etc. All of these areas would benefit from various learning and planning paradigms.

    1. Introduction
      • Why AI in Games?
      • Partially Observed Markov Decision Processes
      • Game Industry
    2. Machine Learning and Artificial Intelligence in Commercial Games
      • History of Machine Learning & AI in Games
      • Forza Motorsport (Demo)
      • Halo 3 (Demo)
    3. Supervised Learning
      • Bayesian Programming
      • Drivatars™
      • TrueSkill™
    4. Reinforcement Learning
      • Q-Learning & SARSA (Tao Feng Demo)
      • Adaptive Modelling and Planning System (PGR 3 Demo)
      • Learning to Walk
    5. Unsupervised Learning
      • Learning from Motion Capture Data
    6. Pathfinding
      • Introduction
      • Heuristics
      • Hierarchical Abstraction
      • Multi-Agent Pathfinding
    7. Planning
      • Global Picture
      • Planning for NPC’s in First-Person Shooter Games
      • Planning for NPC’s in Role-Playing Games
    8. Testbeds for Artificial Intelligence
    9. Future Challenges [17:10]
  • The tutorial will take place on the 13 July from 13:30 – 17:30. We will aim at showing many videos and demos to illustrate our points as well as to make the tutorial an entertaining experience. The presenters will take turns presenting different parts of the tutorial and will work together when more complex demos require it.

    • Thore Graepel and Ralf Herbrich are jointly heading the Applied Games (APG) group at Microsoft Research Cambridge. They have been working on the intersection of machine learning and games for over five years, and have close ties both into the machine learning and the computer games communities. Their group is responsible for the game AI of the Xbox title Forza Motorsport which features a driving style cloning feature called Drivatars™ based on machine learning. More recently, they developed the Bayesian skill rating system TrueSkill™, which is used to rate millions of players every day on the Xbox Live online gaming service. Their general research agenda is to apply machine learning to all aspects of computer games including game AI, online play and animation.
    • Adi Botea has performed his PhD research as a member of the GAMES Group at the University of Alberta, Canada. He currently holds a research and lecturing position at NICTA and the Australian National University. His research interests are in the areas of planning and search, computer games being a main application area. Recent and current games-related research includes hierarchical path finding, multi-agent path finding, planning with hierarchical task networks in video games, and automated generation of crosswords grids.