Dynamic Learning of ai in Gaming

Michael Hercenberg

Computing Research

November 04, 2008

 AI in video games has been neglected for years as graphics, storylines and other aspects have advanced significantly. Gamers are now seeking greater challenges and demand more ‘human’ opponents to test their skills and make a game more believable. The AI needs to be able to assess a situation and make the best choice, but not a static choice, a dynamic one that takes into account the type of human the user is. The enemies need to learn how the user acts in given situations and then be able to formulate plans and carry them out. This is the heart of dynamic learning.

Dynamic Learning is where one takes the current situation and compares it to previous situations to find the most viable option. This paper talks about the methods used to make dynamic learning a common in video games. Section 2 describes the history of gaming AI and its advancements. Section 3 explains the various proposed methods for achieving dynamic learning and section 4 details continuing research areas.

 The earliest game AI’s were very simple and some enemies had one motive: move left. This is apparent in the early Mario games, where the small mushroom enemies, called Goombas, simply entered the screen from the right and walked left, even if they passed Mario or walked into an instant death area, such as a bottomless pit. While other enemies had more advanced programming, such as mimicking Mario’s moves, they were all very basic.

Scripts (which are built-in commands for the AI, chosen by condition) were introduced, which allowed the AI to have an assortment of commands that made for more realistic gameplay. Now, while the scripts allowed the enemies to attack, defend, retreat, take cover, etc. and take on a more human-like appearance, the ‘trigger’ that activated these scripts would become apparent to an observant gamer and then could be used to ‘force’ the enemy to use a certain script. Even if the user did not abuse this loophole, many scenarios would repeat themselves if two areas in the game were similar (which happens often).

As of today, AI does not have any official standards. Game companies simply do their best (or what the budget and time allow) in making the AI realistic or at least reasonable. Most focus is elsewhere, such as Valve’s physics engine or Ubisoft’s CryEngine (simply a graphics engine), which are the selling point of their games. In the past few years, the AI has substantially improved in many games, but is still far behind the other game aspects.

Dynamic learning can be implemented in a few ways. Firstly is Data Mining, which can be used for the generation of future levels in the game. Difficulty Scaling automatically changes the ‘difficulty level’ of the game. Finally, the FLORA3 can be used for explicit context tracking.

Data Mining is the collection of data that is used to determine the AI’s next action. There is a log made of a user’s previous actions in a game, for example, a labyrinth. So, the time it took compared to the expected, the number of dead-ends reached among other things are stored for each level. Then, the next level/maze will be generated based on these parameters: if the user finished really quickly and hit every dead-end and there were only a few, the next level will put more dead-ends in. This new level’s log, along with the previous level will be used to generate the next level.

Data Mining can produce sound results which keep a game fun and challenging for a player. The only drawback is due to the need of data. The user must ‘input’ enough data for the method to work, which can cause various effects to gameplay until the data mining is working properly. While playing the game for a short time, the difficulty curve can drastically change due to limited information. This causes the programmers to setup the beginning of the games to use scripts or default settings.

3.2 Difficulty Scaling

Difficulty Scaling is more active than Data Mining. During a single round/level/battle, the AI can determine how well the user is doing and change parameters as needed. It is basically Data Mining, but in smaller, less noticeable chunks. If a player does really terrible on level 1, level 2 would have fewer/weaker enemies if using Data Mining. Level 1 would still be really hard and if level 2 was too easy/hard, the player would have to get to level 3 before it changed.

With Difficulty Scaling, the player might be having a really hard time defeating a large group of enemies, but this would be seen and a few enemies might back off for a bit or the second wave wouldn’t spawn this time.

3.3 Explicit Context Tracking

Explicit context tracking is best described as Data Mining with a windowed view. The FLORA3 is a descendant of the FLORA and FLORA2, and is currently the pinnacle of explicit context tracking systems. The FLORA3 is a simple yet effective system that has three main characteristics. A list of examples is generated based on the interaction between the system and the environment and are stored in what is basically an array. The system has a ‘window’ that can only see a portion of these examples and it determines the next action based on these. As time passes and examples become less effective, the window shifts, including new examples and leaving behind the less effective examples. The problem is how the better/worse examples are determined. There are three description sets (DES): Accepted (ADES), Possible (PDES) and Negative (NDES). They each contain Description Items (DIs) that are a part of their particular category. Whenever a new example is added, by looking at the current examples, it determines which category it goes in, but since everything is dynamic, adding an Accepted DI can make others shift into Possible or even Negative. By making the window larger (more examples) each example has less impact on the rest, but there may be a lot of negative/unused examples still cluttering the window. Making it smaller can make the dynamic ‘weighing’ system very strict and possibly useless. There are ways for automatic window adjustment, where the more accepted DI’s there are, the larger the window should be (within a maximum), and vise-versa.

The FLORA3 and explicit context tracking seem to be a very sound method that extends Data Mining, but has yet to see much use. This is mostly due to the complexity of the FLORA3 and games aren’t being seen as good candidates for it yet.

4. Future Research Directions

There is much that can be advanced in dynamic learning. The methods here are ideas and first attempts. There may also be new methods to be discovered.

As with all programming, the faster and more durable code is, the better the algorithm. The examples given here are basic and need fine-tuning in order to see real use. Games today have many more parameters than a labyrinth game, one being that extra dimension. How does the AI know what to compare your completion time to when you have a choice to defeat certain enemies, explore the area, talk with the locals, buy equipment and so on. The sheer size and complexity of today’s games makes this a daunting task, especially since most AI used in games today is outdated by a few years or even a decade.

When compared advancements in gaming technology, gaming AI has received the least attention. Graphics have seen possibly the best improvement since the creation of HD televisions. But, with these certain aspects reaching heights unheard of, the AI is beginning to show just how lacking it is. What good is a unique, real-time battle system if the enemy gets stuck on a rock? Once large companies decide to start advancing the AI, the sooner the rest will follow.

Difficulty Scaling will be seeing use in Valve’s new upcoming game Left for Dead, so maybe advancements will see some improvement in the near future.

References

 Kitty S. Y. Chiu, Keith C. C. Chan. “Using Data Mining for Dynamic Level Design in Games” Lecture Notes in Computer Science, Volume 4994, 2008, 628-637.

Pieter Spronck, Ida Sprinkhuizen-Kuyper and Eric Postma. “Difficulty Scaling of Game AI” Universiteit Maastricht / IKAT, 2004, 1-5.

Pieter Spronck, Marc Ponsen, Ida Sprinkhuizen-Kuyper, Eric Postma. “Adaptive Game AI with Dynamic Scripting” Machine Learning, Volume 63, Number, June 2006.

Pieter Spronck, Ida Sprinkhuizen-Kuyper and Eric Postma. “Online Adaptation of Game Opponent AI in Simulation and in Practice” Universiteit Maastricht / IKAT, 2004, 1-8.

Gerhard Widmer, Miroslav Kubat. “Effective learning in dynamic environments by explicit context tracking” Springer Berlin / Heidelberg, Volume 667, 1993, 227-243.

Santiago Ontañón, Kinshuk Mishra, Neha Sugandh, Ashwin Ram. “Learning from Demonstration and Case-Based Planning for Real-Time Strategy Games” Studies in Fuzziness and Soft Computing, Volume 226, 2008.

Andrew G. Barto, Steven J. Bradtke, Satinder P. Singh."Learning to act using real-time dynamic programming" Artificial Intelligence Volume 72, Issues 1-2, January 1995, Pages 81-138.