(Note that this meeting is on the second Wednesday of the month!)

The $25 billion commercial game industry is in the early stages of an artificial intelligence revolution. Game developers are starting to move away from finite-state machines and hand-written scripts and towards adaptive AI techniques like planning and learning. This presentation will discuss both academic and commercial perspectives on this revolution and give some specific examples of how planning and learning are being used in games today.

In 2001 Dr. van Lent joined the University of Southern California's Institute for Creative Technologies (ICT) as a research scientist. Dr. van Lent is the lead researcher for ICT's Commercial Platform Training Aids project which resulted in Full Spectrum Command, a PC-based company command training aid, and Full Spectrum Warrior, an Xbox-based squad leader training aid. Now a project leader at ICT, Dr. van Lent's areas of interest include advanced AI techniques for commercial computer games, the use of commercial game technology for training and education, and the integration of commercial game technology with military simulation technology. His current research focuses on explainable artificial intelligence and adaptive opponents for military training and computer games. Dr. van Lent is also active in the growing collaboration between academic researchers and commercial game developers as the former Editor-in-Chief of the Journal of Game Development and a frequent contributor to the Game Developer's Conference.
prepared by Paul Schmidt
 

The presentation was "Planning and Learning in Games" by Dr. Michael van Lent, Research Project leader, USC Institute for Creative Technologies (ICT). This was a regular meeting of the Los Angeles Chapter of ACM.

Dr. van Lent got into games by using artificial intelligence (AI) for large military simulations. Then a company was spun off to do artificial intelligence for real computer games. First he taught a computer course in artificial intelligence in design implementation and started to hook AI up to games. That led to his current job at ICT.

Games have become a big business. Dr van Lent observed that the audience was composed of both students and older professionals. In answer to his question all of the students played games and many of the others, also. Games are a huge industry, not a couple of guys in a garage turning out what will reach the market the next day. 60% of Americans play video games which includes Solitaire and Minesweeper, often played by people who don’t believe they play computer games. Computer games were a $25 billion dollar business worldwide in 2004 with $11 billion in the U.S. The U.S. total was up from $4.4 billion in 1997 to $5.5 billion in 1998 to $6.1 billion in 1999.

Some people have claimed that the game industry is bigger than the movie industry, but this is not technically true. It is true that the total sales of computer games are greater than the box office gross of the movie industry. If you count DVD sales and commercial tie in's the movie totals are still larger than the games market. For one day sales records games held the lead until Harry Potter (Half Blood Prince) took in $140 million in a single day pushing Halo 2 into second place with a single day sales total of $125 million. Games don’t get the same big press as the movies. The games industry has focused their attention at their usual younger group of players, although they are trying to broaden their appeal to older audiences.

Consoles dominate the industry with 90% of the sales with leading companies Microsoft, Sony and Nintendo. Piracy concerns limit the amount of effort put on PC games. Most developers find they get a higher return on investment if they make it a console product rather than a PC product.

The average age of game players is 29 but is steadily going up. Gamers don’t stop playing games when they are older, but new gamers keep coming in. The average age of game buyers is 36 as many parents buy games for their kids. Online games are huge. Currently it is a $1.1 billion market that is expected to rise to $3.6 million in 5 years. Online game players tend to be older and more women play them. Most game players are men. For all games, 59% are men and quite a few of the women are playing casual games such as solitaire that are not generally thought of as computer games. The Sims have a large group of women players and are one of the few game types that have demographics beyond the usual young male audience.

Dr. van Lent provided some context for Game AI. The early history of game AI has had lots of work on path planning, hand coded AI, finite state machines, scripted AI and embeds hints in the environment. Most games use 5-20% of the CPU cycles, use specialized scripted AI functions, and users can learn to "game the game."

Path planning is still a very important part of game development and you will find it actively discussed in presentations at gamer symposiums. A-star search is the basis of path planning and there are a lot of tweaks on it to try to optimize paths. Path planning is where one person in a game position wants to travel to another point and determines what directions to take to get there. It is basically a search problem. Games developers know the search world inside and out and are on the edges about how you can extend searches in various directions. Many gamers use finite state machines; they are simple, fast and they work. In the past gaming only took about 2% CPU time, with most of the rest used for graphics. Today there are special graphics CPUs and games take from 5-20% of their CPU time. The time you get is in very small slices. Scripted AI is heavily used today with a designer writing a set of specialized functions that are many times are repetitive so experienced game players can learn from past experience what they are going to have happen in their next games. It can be a lot of fun to learn how to “game the game”. Game designers try to deliberately put enough of this in the game to make it pleasurable and interesting for the player. Game designers will place embedded hints in the games about the environment like information on game maps and 3-D objects. They put meshes on the map and information about what things can and can’t do. This is information for the AI to take care of, not information for the player.

Things are starting to change. Game environments are getting more and more complex. One of the most impressive accomplishments is being able to do the same things that could be done in earlier games in the more complex environment. The world is becoming three dimensional with many more possible actions. Players don’t appreciate how much work is required to achieve this. Players are getting more sophisticated, and are starting to think more about the AI. There are higher expectations out there both for the AI and also graphics and physics depicted in the game. Development costs are skyrocketing. The gap between what a game costs to produce and the income received from it is narrowing. 10 to 15% of the games developed during a year return the cost to develop them. You need to get a publisher and the publisher must like your games. Publishers are looking for a safe bet. They focus on incremental improvements over existing games rather than dramatic new developments. The publishers are in the game to make money and are doing the things they need to do to make it, as well as producing some pretty good games along the way.

Game developers are and are having to adopt new techniques. Its no longer becoming the case that you can build an AI descriptive in your game, you are going to have to make your game AI more procedural and use adaptive techniques. New and approved techniques are required. Next Dr. van Lent provided an example of some Scripted AI code of a game where attacks were made at a set hour and then repeated at intervals if the conditions were suitable. He discussed Madden Football where the developers started out with random play selection. Later the developers went to a more thought out game strategy, but some of the players claimed the game wasn’t as good because it didn’t do the unexpected things it did before. Never under-estimate the players willingness to read intelligence into the game, whether it is there or not.

Extensive mod capabilities are necessary for games to keep them competitive. Give players the ability to change characteristics of the game to make it more enjoyable. This is true of most “First Person Shooter” games. One good way to have a successful interview at a game studio is to come in with an existing game for which you have supplied some unique mods that make it a more interesting experience. Dr. van Lent provided another scripted code example and discussed how it worked. There are many control numbers required in games and much testing is needed to get numbers right.

An example of procedural AI is The Sims game. This game is one of the most financially successful games. It was developed by Game Designer Will Wright – the Michael Jordan of game design. There are a number of different needs for Sims and if left alone they will play at a background state. Most of the knowledge is in the objects in the worlds and each Sim fills one need at a time. Some people believe the Sims programs can be used for real serious educational purposes, but the companies aren’t interested in that field.

One of two adaptive AI technologies is Deliberative Planning. Two new games are F.E.A.R. and Condemned. Deliberative planning is used to select the behavior patterns of the opponents. The second technology is Machine Learning. Both of these are big areas of AI research. Criteria are making use of first hand experience and supporting procedural and adaptive AI. Machine Learning is sometimes considered "scary voodoo" by developers. It uses decision tree induction and neural nets in Black & White. Drivatar in Forza Motorsport is an example where the game learns from the actions of the driver.

Why planning and learning? It is necessary to improving current games by making them more variable and replayable, more immersive and energizing, have them provide a more customized experience, and make them more robust and challenging. You want games to be challenging, but not always beat the player. For the game to be successful the player must have fun. The game should be more like professional wrestling that is mainly showmanship than boxing. For the game producer planning and learning is needed to provide improved profits, more sales, improved marketing and cheaper development costs. New elements of game play are necessary as games advance. A lot of these have not yet proven to have the desired advantages.

Why not planning and learning? It could possibly lead to costlier development and is the expense worth the result? There can be greater processor and memory loads. AI typically gets 10-20% of the CPU and this comes in frequent small slices. It is harder to control the player's experience. There are not a lot of AI licenses available so development must be done from the beginning. It is harder to do quality assurance and may double the cost of testing. It adds technical risk and programmers need to spin up on new technologies. Designers need to understand what’s possible and create AI designs the programmers can implement. There can be a marketing backlash against games that are too new and different and once a game is stable it is too late to make additions. It can be difficult to sell a new game to a publisher. Sometimes it is like giving instructions to a dog. You give the dog a set of complicated verbal instructions and the dog basically hears its name and that what you are saying has something to do with it. The publishers miss the significance of the technical details but do understand the term "Improved Profits."

Deliberative Planning uses a domain independent planning engine with an abstract problem description with a goal. An example would be a world state as a mission objective. There would be operators and would include options and plans. The object is to find a sequence of operators that change the initial world state into a goal world state. Dr. van Lent provided a detailed discussion of a strategic planning example that would accomplish the goal.

Machine Learning is learning by Behavior Capture. This is also called behavioral cloning, learning by observation, learning by imitation and is a form of knowledge capture. One way to learn is by watching an expert. Experts are good at performing tasks but aren’t always good teachers. You can learn believable, human-like behavior and mimic the styles of expert players by Behavior Capture. One example is Microsoft's Drivator. Drivator technology is the foundation of the human-like AI in Forza Motorsport.

The learning to fly program is where we develop a flight sim autopilot by observing human pilots. There were 30 mission observations each from 3 experts. There were 20 features (elevation, airspeed, twist, fuel, thrust, etc.) and 4 controls (elevators, rollers, thrust, flaps). The mission was to take off, level out, fly towards a mountain, return and land. The first key idea is that experts react to the same situation in different ways depending on their current goals. People do not always do the same thing. The flight sim task was divided into 7 phases and 4 decision trees were learned for each stage (one per control). The second key idea is don't combine data from multiple experts as it will result in something approaching a flight by committee and won’t provide optimum results. If you break the data out and learn separate models for each person then it works great. You want to learn the style of each individual.

Knomic (Knowledge Mimic) was used to learn air combat in a flight sim with a deathwatch bot in Quake II. The bot plays against you and tries to kill you. This demonstrates dynamic behavior against opponents and you can’t divide the task into fixed phases. The first key idea is that experts dynamically select which operator they are working on based on the opponent and environment. They also learn when to select operators (preconditions) and what these operators do (effects). The second key idea is that experts annotate observations with their operator selections and change their future actions.

Dr. van Lent showed a movie The Future. This showed a hospital setting with many characters and involved a scenario where the hospital had to be evacuated and an American officer had to deal with a local doctor who was antagonistic to the move. The officer had to deal effectively with his opposition. This was developed through an army contract to provide training films. Dr. van Lent believes that in the future there will be interactive simulations that will be used for training.

Where we can go to learn more:

• AI and Interactive Digital Entertainment Conference
          Marriott Marina del Rey, June 2006
• Journal of Game Development
          Charles River Media
• Game Developer Magazine
          August special issue on AI
• Game Developer’s Conference
• AI Game Programming Wisdom book series
• Historical:
  • 2005 IJCAI workshop on Reasoning, Representation and Learning in Computer Games
  • AAAI Spring Symposiums 1999 – 2003
  • 2004 AAAI Workshop

• The most challenging opponent isn’t the most fun.
• "Never stupid" is better than "sometimes brilliant."
• Never underestimate the player’s ability to see intelligence where there is none.
• Game companies aren’t a source of research funds.

• Maximize the ratio of internal complexity to perceived intelligence.
• The player will build an internal model of your system. If you don’t help them build it, they’ll probably build the wrong one.
• The flow of information about a system has a huge impact on the player’s perception of its intelligence.
• From the players point of view there is a fine line between complex behavior and random behavior.

At the end of the meeting there were some interesting discussions about AI uses in education and requirements for AI in games with large numbers of interactive members. The discussions were wide ranging, informative, and provided more questions than answers. Many of the ideas sounded like good topics for future research and development and perhaps for future meetings.

Dr van Lent gave an excellent presentation that included detailed explanations that could not be covered completely in this article. He presented a lot of information in a limited time. His talk was both entertaining and informative. The audience was very interested and interactive with him both during the talk and in the question and answer period after the meeting.