At a certain level, adaptation is a requirement for AI. If a game doesn’t have it, you end up living inside a movie you can’t change! In practice, all the traditional techniques (e.g. finite state machines, scripts) help developers implement adaptive behaviors, but things get tricky when you want to adapt to many dynamic factors like player styles.

This week’s Thursday Theory post looks into the award-winning paper behind dynamic scripting, as proposed by Pieter Spronck from the Computer Science Department at Universiteit Maastricht. It presents some interesting ideas for dealing with the problem of creating behaviors automatically that can adapt to almost anything in the game.

Motivation

The process of creating entertaining AI for non-trivial games is becoming much harder because of two reasons:

1. Complexity — Large scripts are required to support games with many possible options, like role-playing games (RPG). Scripts are often long, static, poorly factored, hard to understand and maintain etc.

2. Adaptability — With better AI opponents, the entertainment value of the game goes up. So there’s a strong incentive to make the AI more competitive by adapting to the player’s tactics.

Developers typically create adaptable behaviors by manually scripting the different adaptations by hand, which of course increases the complexity of the solution.

Instead, this paper proposes the use of unsupervised learning to solve the problem and investigates the feasibility of this approach. Dynamic scripting aims to provide a fast implementation, effective behaviors that are competitive with hand-crafted AI, robust in being able to deal with uncertainty, and efficient at learning from few trials.

Screenshot 1: An encounter with AI opponents in Baldur’s Gate.

Contributions

There are two things that make this particular research project interesting:

• An architecture that combines reinforcement learning and scripting together.

• Its application to opponent AI in state-of-the-art RPGs like BioWare’s Baldur’s Gate.

The architecture itself is very reminiscent of Learning Classifier Systems (LCS) originally invented by John Holland. Here’s how it works:

1. There’s a database of rules, typically one for each opponent. These are made up of hand-crafted rules which perform actions in the game.

2. At the start of an encounter, a new script is generated randomly from the rules. Each rule is selected based on its weight value.

3. Once the encounter is over, the outcome (either positive or negative) is used to update the weights of each rule.

Over time, the rules with the most success are more likely to get picked for new scripts, thanks to the reinforcement they receive from each encounter.

Figure 2: The architecture of the dynamic scripting system (see paper).

Abstract & References

Here’s the abstract for the paper:

“Unsupervised online learning in commercial computer games allows computer-controlled opponents to adapt to the way the game is being played, thereby providing a mechanism to deal with weaknesses in the game AI and to respond to changes in human player tactics. For online learning to work in practice, it must be fast, effective, robust, and efficient.

This paper proposes a novel technique called “dynamic scripting” that meets these requirements. In dynamic scripting an adaptive rulebase is used for the generation of intelligent opponents on the fly. The performance of dynamic scripting is evaluated in an experiment in which the adaptive players are pitted against a collective of manually designed tactics in a simulated computer roleplaying game and in a module for the state-of-the-art commercial game NEVERWINTER NIGHTS.

The results indicate that dynamic scripting succeeds in endowing computer-controlled opponents with successful adaptive performance. We therefore conclude that dynamic scripting can be successfully applied to the online adaptation of computer game opponent AI.”

You can download the paper from the website (PDF, 614 Kb):

Online Adaptation of Game Opponent AI in Simulation and in Practice
Spronck, P., Sprinkhuizen-Kuyper I. and Postma E.
Proceedings of the 4th International Conference on Intelligent Games and Simulation (GAME-ON 2003)

If you’re interested in further academic background behind these ideas, look into Learning Classifier Systems, and particularly Wilson’s XCS (which will no doubt also feature on AiGameDev.com in the future).

Evaluation

Here’s how I think the technology in the paper ranks in practice:

Applicability to games: 8/10

The dynamic scripting technique is designed with very sound principles from a game development perspective. It’s efficient and doesn’t require much memory. Not all games would benefit from having this kind of adaptation, as it takes a certain amount of encounters with a specific opponent for the AI to be able to learn something!

Usefulness for character AI: 6/10

The paper shows how dynamic scripting can be applied to combat in an RPG, for things like selecting attacks. Luckily, this is the kind of situation that wouldn’t suffer too much from random behavior, so the learning process is not too obvious. (In fact, randomness can be fun here.) However, other problems in game AI are much more sensitive to randomness, which limits the applicability of this technique.

Simplicity to implement: 10/10

The major benefit of this technology is that it’s extremely simple to implement. Reinforcement learning is conceptually very simple, and when it’s hooked up to a simple rule-based representation it requires very little work to generate new scripts.

Screenshot 3: Combat in Neverwinter Nights 2.

Discussion

This paper, above all, shows the promise of unsupervised learning (which I think is very fertile ground) and demonstrates it in a game. There has been much more research on dynamic scripting since, and I expect many more research projects applying LCS-like technology into games…

For this paper in particular, what surprises me the most is the lack of references to Learning Classifier Systems. Pieter’s research is uncharacteristically well researched from the game development side, and that’s great to see! However, there’s a huge amount of knowledge and experience available in the field of LCS, particularly in how quickly a system learns and how it behaves when solving difficult problems.

As it turns out, the biggest problem with dynamic scripting is the very same that Learning Classifier Systems suffer from. While they are very good at learning to solve problems realistically, the process of them learning is not very realistic. Random exploration is a requirement, but it can appear uninformed and illogical. This would case problems in games where coherent behaviors are required (unlike combat).

Figure 4: Dynamic scripts get better over time, but do they learn realistically?

Basically, it’s the premise of generating these long “procedural” scripts from rules that causes the problem. The representation itself of these scripts makes it hard for designers in the first place, so simply hooking them up to an AI that uses random exploration and reinforcement learning will raise other problems!

Since game developers have been increasingly using planners to reduce complexity of their AI logic, it’d be interesting to see how these two approaches combine together. I raised the question in this article The Secret to Building Game AI that Learns Realistically; it’d be a fascinating research project.

What do you think about the technology behind dynamic scripting, and its applicability to games?