Artificial Intelligence in games

by Anders Petersson

May 2001

Copyright (c) 2001 Anders Petersson.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts and no Back-Cover Texts. A copy of the license can be obtained from http://www.gnu.org/copyleft/fdl.html

Abstract:

There are two main types of AI: event driven and goal driven. In a good game they hardly ever come alone. Which your AI engine will emphasize mostly depends on the type of game. And be wary of intensive searches.


Contents

1 Introduction

What does it mean to simulate thinking? AI1 can be described as ``Representing intelligent behavior in an algorithmic way,'' but what does that mean practically?

When you are designing AI for a game you generally don't want to make a true simulation because of limited resources. However you often want to make a simplified version of the true simulation to ensure that it doesn't get predictable and boring. Plans are good, code is better.

2 Purpose

The purpose of this document is to give an introduction on how to use AI in games and give inspiration to approach problems from new directions.

3 Method

I have gathered some of the basic ideas of AI and compiled a little introduction.

4 Types of AI

4.1 Event driven

An event driven AI engine works on the basic principle that all actions are taken based on specific events that happened. This is the most common type and it can be varied almost infinitely. The events can be anything from happenings in the world to the user's commands to an NPC2.

4.2 Goal driven

The goal driven approach is inherently different from the event driven although an event driven engine can be used to feed goals to a goal driven engine.

It works by taking the highest ranked goal and processing it, breaking it into smaller subgoals as needed, and processing them until the goal has been fulfilled.

4.3 Leaking buckets

The leaking buckets approach is a mix between the event driven and the goal driven approaches. The theory is simple, you have a couple of buckets; let's say flee, fight, and restock. The buckets leak some of their contents over time. You run the script associated with the most filled bucket. Things that happened fill the buckets to a different extent. For example:

seen enemy
Add 5% to flee and 10% to fight.
low ammo
Add 20% to restock.
low hitpoints
Add 20% to flee and 10% to restock.
much ammo and hitpoints
Add 50% to fight, remove 20% from flee and restock.
lost 50% hitpoints in one hit
Add 50% to flee, add 20% restock and remove 50% from fight.
You can also add personalities to this. For example:

normal
No action.
coward
Double points to flee and restock.
berserk
Add no points to flee.

4.4 Searching

Although searching might seem to have nothing to with the high level decision making it is in most cases essential to both the choice of action and the execution of the choice.

4.4.1 Heuristics

Heuristics3 make many searches feasible as well as improving speed and accuracy.

Consider chess as an example, it is not a viable solution to search through all possible moves for one that leads to victory. Instead you could use a simple heuristic to evaluate board positions. Lets say we give one point for each pawn and two points for the rest of the pieces except for the queen which gives four. Deduct half of that for each of those threatened by the other side and deduct ten if the king is threatened. Now you have a simple way to search for the board position within you time limit that gives the highest score.

To improve the results even more you can search more along the paths that give higher score than those which give a lower score.

5 Implementations in games

5.1 First Person Shooter

An ordinary FPS usually uses an event driven engine where the events might look like this:

enemy seen
Attack with best weapon.
hurt badly
Run away and find health.
no ammo
Find ammo.
It might be good to use a leaking bucket approach to make it more flexible.

If you look at an old game such as doom it probably only had one event which was ``if player seen -> attack''.

One interesting approach would be to add a goal based engine but then the question is, are you moving towards an RPG?

5.2 Real-Time Strategy

An RTS is a good example of a mixture of an event based engine and a goal based one. While the AI players themselves are using a goal based engine that deals with decisions such as what to build and where to build it and moving units, the units themselves are controlled by an event based engine (which of course tells the goal based engine about attacks etc).

An example of the interaction could be as follows: a building becomes blown up by an air strike which makes the event based engine give a new goal to the goal based engine to increase air defenses. The goal based engine posts a move event to some units capable of air defense which in response move into place.

5.3 Role Playing Games

RPGs have historically had very little or no AI and have rather depended on either random encounters or scripted behavior (often a combination of both).

Random encounters are more common in hack'n'slash type games where the fighting and gaining levels is more important.

Scripted behavior (often coupled with some minor AI) is common in games depending more on their story line than other things; they are not uncommonly like adventure games with some fighting and character generation attached.

There are some games which are exceptions to this:

Lure of the Temptress
This game was a "virtual theater" where every person had goals and dreams and as time progressed the smith might start smithing, go to the inn to eat, or go to the store and barter. Although it was rather poorly implemented it was an interesting endeavor.
Daggerfall
Although it basically was a hack'n'slash with a story line (plus a practically infinite world with infinite quests) what was really interesting was the fact that people remembered previous encounters with you. Such 'faked' AI can be a good was to make games seem better than they are.
Ultima VII
This could be said, to some extent, to be a much better version of the ideas from Lure of the Temptress since it didn't have the limits that LotT had. Consider the smith: in LotT the smith was 'smithing,' while in U7 the smith was heating the fire, smithing the iron, getting water to fill the water basin, and so on. It was a very detailed world where both the player and the NPCs could do anything from harvesting to baking bread to fighting monsters even though it had a rather linear plot (with many sub plots).
Cyphesis
This is the AI server being developed by WorldForge[2] . It is really interesting since the NPCs are controlled by a complete goal engine with goals ranging from baking bread and chopping wood to reproduction and gossip. This is developed as free software so go and check it out.
Arianne[3]
Here is another free RPG effort that uses another approach to AI; namely, using a 'master mind'. This is a less CPU intensive approach compared to the Cyphesis agent based solution. When it recognizes something suspicious such as a band of known robbers approaching a village it will tell the village guards to move out and 'greet' them.

6 Conclusion

When deciding on what type of AI you need for a game it is important to know what kind of world interaction the player will have. You probably need some kind of event based engine at the bottom and if you can afford it a true goal based engine can really add to the game play. The most important thing is of course to experiment and actually get the code done. Also consider how much spare processing power you will have available for the AI. Generally, searches will hog the most CPU.

Bibliography

1
The Free On-line Dictionary of Computing

2
WorldForge http://www.worldforge.org/

3
Arianne http://www.arianne.cx/

About this document ...

Artificial Intelligence in games

This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)

Copyright 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -no_subdir -split 0 -show_section_numbers /home/demitar/skola/psychology_ai.tex

The translation was initiated by Anders Petersson on 2001-07-14


Footnotes

...AI1
AI = Artificial Intelligence

... NPC2
NPC = Non-Player Character

...Heuristics3
From foldoc[1]: heuristic 1. A rule of thumb, simplification or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood. Unlike algorithms, heuristics do not guarantee optimal, or even feasible, solutions and are often used with no theoretical guarantee. 2. approximation algorithm.