An Introduction to Game AI

Artificial Intelligence in games is slowly getting better. With the advent of games like HalfLife and Unreal, even the notoriously dumb AI-engines in first-person shooters are gradually getting more and more intelligent! Is it due to neglect that games have taken so long to get half-intelligent enemies? Perhaps, but it is also due to the incredible complexity of advanced AI engines that has put a lot of programming groups off putting in the effort and research to create one. This essay deals with the techniques often used in AI-engines in games, and possible uses for other paradigms in AI.

Finite State Machines

Glossary

• A* Pathing Algorithm
• Finite State Machines
• Minimax

Despite the rather technical-sounding term, finite state machines (FSM) are the simplest AI engines. They are often used in first-person shooters such as Doom, Quake and Q2. The enemies have about 8 states that they can be assigned, each state having its own behaviour, and its own trigger.

Quake2 is a good example to look at since most people have played it. Quake2 uses 9 different states: standing, walking, running, dodging, attacking, melee, seeing the enemy, idle and searching. For the programmers, here is a bit of code from Quake2 that shows how the monsters check whether they should change to their dodge state:

static void check_dodge (edict_t *self, vec3_t start, vec3_t dir, int speed) {
	vec3_t	end;
	vec3_t	v;
	trace_t	tr;
	float	eta;

	VectorMA (start, 6144, dir, end);	// JM: Lengthened vector.
	tr = gi.trace (start, NULL, NULL, end, self, MASK_SHOT);
	if ((tr.ent) && (tr.ent->svflags & SVF_MONSTER) && (tr.ent->health > 0)
	    && (tr.ent->monsterinfo.dodge) && infront(tr.ent, self)) {
		VectorSubtract (tr.endpos, start, v);
		eta = (VectorLength(v) - tr.ent->maxs[0]) / speed;
		tr.ent->monsterinfo.dodge (tr.ent, self, eta);
	}
}

Note that this comes from a Quake2 mod I created, so I've changed the code slightly. The states in a game might be connected together to form action, for example, to attack in Quake2, the states go from IDLE to RUN (to a point closer to the player), then once the point has been reached, the state switches to ATTACK. The states in a game can often be represented by a simple flow diagram. A typical FSM operation diagram might look like this:

Finite-state machines are a good way of create a quick, simple, and sufficient AI model for the games it is encorporated in. The "fun-factor" in first-person shooters comes from the sheer numbers of enemies, combined with (in modern ones) stunning 3D graphics. The new first-person shooters allow for add-ons, like bots. A lot of bots encorporate much more advanced AI algorithms, like A* pathing algorithms (generated from information they've dynamically learnt about the level), better dodging, jumping and general fighting code.

There is also a slight derivative to the state-based engine, but it used in more complicated games like flight simulators and games like MechWarrior. They use goal-based engines - each entity within the game is assigned a certain goal, be it 'protect base', 'attack bridge', 'fly in circles'. As the game world changes, so do the goals of the various entities.

Minimax Trees and Alpha-Beta Pruning

Moving on to another genre of games completely - board games. Board gaming AI has received a huge amount of publicity since the famous chess match between Deep Blue (IBM's master chess computer) and Kasparov - the first time a chess world champion has been beaten by a machine.

Games like chess, checker, Pente, and Go require a great deal of thinking ahead, predicting what moves the opponent might pick, and how to counter them. This is where minimax trees come in — the goal of a minimax tree is to minimize the opponents maximum move.

A board can be represented as a huge tree of moves, starting with a blank board as the root, then branching off with all the possible first moves, all of which in turn branch, until a winning state (or draw) is achieved. Yet, creating an entire tree of ALL moves would be impossible on current computer - even a simple game could require around a million nodes. So games like chess and Go are definitely impossible to represent as a complete tree. Therefore, the algorithms only generate trees 5-10 layers deep.

Looking ahead obviously uses the assumption that the computer and its opponent use the same set of heuristics (rules) to determine which move to make. This is obviously a rather tenuous assumption to make, especially when playing against humans (therefore, it is often these heuristics that make or break an AI engine). So, the computer generates all possible board positions from the current one and does this for about 5-10 moves ahead. After that, it sets about evaluating the nodes, and assigning values to them according to the "decency" of the move (again, the heuristic involved in this process can have a huge impact on the game). It then uses these values to determine which path to take so as to minimize its opponents best game.

Just as real trees can grow out of control and need to be pruned, so do minimax trees! Even when only evaluating a few moves ahead, in a complicated board game such as chess, these trees can be immense, and take a long time to generate and evaluate. Therefore, pruning is used to ensure time isn't wasted on evaluated pointless nodes.

Possible AI Applications

AI techniques such as genetic algorithms and neural networking can be applied to gaming, and are increasingly are making their ways into some AI engines. Generation5 has interviewed both Steve Grand (the lead programmer of Creatures, a program that utilizes both neural networks and genetic emulation) and Andre LaMothe (a famous computer programmer and author) about their AI programming methods.

Genetic Algorithms

Genetic Algorithms are excellent at searching very large problem spaces, and also for evolutionary developement. For example, an idea I was going to implement was create a large structure of possible traits for Quake II monsters (aggressiveness, probability of running away when low on health, probability of running away when few in numbers etc), then use a genetic algorithm to find the best combination of these structures to beat the player. So, the player would go through a small level, and at the end, the program would pick the monsters that faired the best against the player, and use those in the next generation. Slowly, after a lot of playing, some reasonable characteristics would be evolved.

Neural Networks

Neural networks can be used to evolve the gaming AI as the player progresses through the game. LaMothe suggests that a neural-network can be used to assess what fighting moves are to be made in the 3D fighting game (such as VirtuaFighter). The best thing with neural networks is that they will continually evolve to suit the player, so even if the player changes his tactics, before long, the network would pick up on it. The biggest problem with NN-programming is that no formal definitions of how to construct an architecture for a given problem have be discovered, so producing a network to perfectly suit your needs takes a lot of trial-and-error.

Conclusion

I'm very pleased with the direction that Artificial Intelligence is heading - it is slowly taking over more and more of the game loop as computers get quicker. Players who are getting used to network play are looking for intelligent opponents when playing offline too. As artificial intelligence techniques get formalized and become more mainstream, we can expect to see some excellent games emerging over the next 3 to 5 years.

Last Updated: 29/06/2000

Printed from: http://www.generation5.org/content/2000/app_game.asp