Chris Moyer

First-person computer games have been around for well over a decade. Some old titles such as Doom and Wolfenstein still draw the attention of a few gamers. However, the limited nature of these games has helped forward a new breed of first-person game, one with more intelligent, customizable computer opponents. For the last five years, these new computer opponents, called bots, have undergone many changes, from the code that guides a bot’s navigation all the way to the underlying AI that makes these players appear to play as a human would play. It is making these bots appear human that will be discussed in this paper.

In the mid 1990s, a first-person game was released that allowed the players of the game to not only play through the game, but also customize the game themselves. This game, Quake, was also a milestone in that it was the first true three-dimensional game ever; in other words, the world that the game is played in is rendered in three dimensions in real-time. (Previously, "sprites", or two-dimensional graphics, were used to simulate a 3-D world.) New aspects of gameplay had to be taken into consideration with this game, such as aiming your weapon up and down as well as side-to-side. Unfortunately, Quake does not have the most intelligent enemies. For example, one enemy, the ogre, has two weapons, a grenade launcher and a chainsaw. To defeat it, one must dodge grenades and shoot it at a distance – not a challenging opponent. More advanced opponents did not have much better "skills". The creatures of Quake were all basically the same, but with different movement algorithms or improved speed and accuracy. Through a combination of the uninteresting intelligence found in the provided enemies and the availability for players to customize the game, people started creating new enemies with more intelligence. Any player could play against these "bots" which started to take on more human game-playing behavior.

A bot can be broken up into two distinct parts. The first is navigation and movement, and the second is combat. The first is much more complex to deal with if bot behavior is to emulate a human, although combat is not easy by any standard. Navigation can be performed in many ways, one of which is hard-coding. Hard-coding usually limits the portability of the bot to stages that have been coded beforehand for the bot, and so is not used much. For now, lets rather assume that the bots will be placed into a game level that they know nothing about, and so hard-coding actions will be impossible. (A third approach exists, a combination of these two extremes, but this will be explained later.)

In order for the bots to move at all, they need to be able to "learn" about their surroundings. This very basic concept is then broken down even further into being able to determine if they can move in a given direction, and then be able to find opponents and "goodies", or "power-ups", inside the level. The concepts may seem elementary, but they are really not. A bot must be able to deal with two basic obstructions: walls and gaps. Walls are defined as anything that cannot be passed through, such as a real wall, a fence, opponents, crates, stairs leading up, and so on. Gaps, on the other hand, are places where the floor stops or breaks, such as a hole, stairs leading down, etc.

In dealing with these two problems, a good technique is the utilization of the traceline function. This function, introduced with Quake, allows the bot to trace a line from one X-Y-Z coordinate to another, and receive in return information about where the line goes, what it intersects, and so on. Using several calls to traceline starting at the bot, it is possible to "see" if an obstruction is really a wall, an incline that can be walked upon, a stair, or whatever. The same technique is used to determine whether a break in the floor is a stair leading down, a small hole that can be walked across, a large hole which the bot will fall through, and so on. There are many more details involved, but this is not the intended direction of this paper. Similar techniques can be used to find and locate opponents and goodies.

Now that we have a bot that can determine where is safe to walk to, we can look at the ways that a bot can maneuver a level intelligently. There seem to be two schemes. The first of these, which saw the light of day in the early Quake bots, utilizes the idea of "nodes", while the other tends to use paths. In a node-based environment, nodes are placed around the level utilizing rules defined by the bot’s creator. The nodes act as vertices in a graph, and each node can give the bot information about that particular piece of the board. Some bot designers will cheat and have human players place nodes for the bot to use. Even though this introduces more complexity, the benefit is the ability to take advantage of the true intelligence found in a human player. More will be explained on the second scheme later.

So far, we have not seen any real artificial intelligence techniques utilized within a bot, but rather educated methods of determining its surroundings; at best we’ve seen bots cheat by stealing from human intelligence. However, there are many aspects of the combat side of a bot that have been look at from an AI point-of-view. Combat situations have many uses for some sort of search algorithm or decision-making process. In a battle, it is necessary to predict the opponent’s moves to determine the best course of action for the bot. Minimax has always been a possibility for this, for when given a good heuristic function, it will tend to find a good move. However, Minimax is slow, and so there have been no widely-accepted bots that have implemented it to date. Partial Minimax is an option that has been considered for these decision-making algorithms, but has still not gained acceptance. Researchers have stated, "Use partial Minimax when there is a clear choice (i.e., when the best available minimax value is substantially better than the second best). Otherwise, if all values are clustered around some intermediate range, use another strategy…" (Abramson) Unfortunately, in a real-time game with bots, there is usually no clear choice that minimax should pick. Each choice corresponds to a different strategy that the bot could adopt.

Many proponents of minimax may not realize at first how valuable speed is when examining the effectiveness of a real-time bot. The less time the bot needs to "think" about a decision, the more decisions it can make, increasing its responsiveness and skill level. Remember that for all practical purposes a bot is fighting against a human brain that can intuitively interpret the three-dimensional world in which the bot has been placed. For example, in a battle, a bot will need to aim at the opponent, predict their movements, predict its best movements dependant on how its opponent may react, and so on, all without really being able to understand the environment in which it has been placed into. To gain the most speed, most algorithms inside of bots tend to use the A* algorithm. This algorithm, though not advanced, has the benefit of being very fast; its complexity is O(log h(n)), where h(n) is the complexity of a heuristic function. A* is basically a depth-first search algorithm that is governed by a heuristic used to guess the next best branch. This way, at each depth, only the branch with the best heuristic value is expanded.

Next, lets examine some of the more current theories and practices surrounding bot AI today. First, we can get a brief look at how different researched AI approaches have impacted the bot field. Then, we’ll look at some of the questions that bot designers have asked when attempting to make a bot appear more human using these and other techniques. Finally, observations of the skills exhibited by bots in Unreal Tournament (UT) will be examined.

While most bots do not rely on standard AI techniques such as minimax or other highly researched algorithms, there are a few that do. However, most of these are not accepted in the gaming community. For instance, there is a bot that was created for Quake II, the successor to Quake, which relies on a neural net to learn its surroundings and skills. It also uses a genetic algorithm to train the bots. This bot, called the Neuralbot, has gained the attention of researchers.

While a great research avenue, the Neuralbot has been look down upon by the gaming community. Many believe it is not practical, doesn’t appear human, and just can’t understand the things that a normal bot can understand. Perhaps they do not want to know what an artificial intelligence that learns is capable of producing, but rather are interested in creating the most "human" bots possible. MrElusive, creator of several bots, most notably those found in id Software’s Quake III Arena, says about the Neuralbot, "Yes very cool project… but [it] will never really understand the 3D world or the specific map." Others have also argued that gamers are not interested in the ability of a bot to be truly intelligent, but rather put up a good fight:

To a the gaming community, true artificial intelligence is more of an illusion of human behavior in a way that makes the game more fun and challenging, not a simulation of true intelligence.

Now is a good time to mention the control structure for most bots today (not the Neuralbot). Many bots use what is called a schedule-driven state machine. This is similar to a deterministic finite automata, but it has several different behaviors, or schedules, defined for each bot. In each schedule, different aspects of the surrounding world are taken into consideration, and then algorithms such as A* are used to determine the next best behavior. Though not advanced, this seems to produce the most realistic behavior.

As it turns out, most game programmers do not interact with researchers of game AI. Instead, they build their bots to be the most "human" that they can, and then test their bots on humans. Though not a good research method, this has been the driving force behind almost all bots produced to date. MrElusive, for example, states that he creates his bots through testing, and has not read many AI books. Researchers, on the other hand, do not build bots that they believe will be the best bot, but rather are interested in the research returns possible. In these respects, researchers tend to act independent of the gaming community.

One of the areas in bot research that has just recently been looked at is making a bot that does not cheat in any way. So far, most bots have some functions that will pull data from other players (human or bot) in order to play as best as they can. Through research and trial-and-error, bots have been created that do not rely on what would be considered the private knowledge of other players. While these bots are still quite rare, they are not by any means easy to beat. In removing the ability to peek at the private data of their opponents, these bots have had their accuracy and speed levels raised to compensate. The result is a bot that appears a little more inhuman with its reflexes than other bots, but is still a challenge and a good opponent. Is it more satisfying to play against a bot that you know does not cheat? This is a question left to the gaming community.

The bots for Quake III Arena that MrElusive has created are bots of this type that do not cheat in any way. The concept of a non-cheating bot was most likely not invented, but rather first implemented on a large scale, by MrElusive. More than just non-cheating bots can be learned from this man. Previously, the notion of path-based navigation was mentioned. MrElusive, as well as the software engineers behind Unreal Tournament’s bots, have implemented pieces of this, as well as hard-coded rules, into their bots. In order to make the bots appear more human, they have created them in such a way that the bots require paths predefined in any level that the bots will play in. Then, rules are coded that tell the bot how to navigate the paths if there is no battle in progress. Some may think that this is cheating, because the bot will already know the stage. However, when a human has played a stage enough times, they will already know everything that there is to know about the stage as well. Why should the bot have to learn all this information every time it enters a stage it has already played? Rather, this allows the bots to have a human-like understanding of the level, with the benefit of being able to spend more CPU time on other tasks.

So far, I’ve mentioned only some of the techniques used to make bots act more like human opponents, which is what the gaming community believes is artificial intelligence. To finish, I decided to examine how the bots in Unreal Tournament react, and whether or not I would consider them to be good human players. UT was chosen for several reasons. Even though the Quake III Arena bots do not cheat, they appear to be more skilled than most humans, even on the easy levels. The UT bots do tend to behave more human-like in that they have a tendency to not have perfect aim all the time. I chose to play the bots on several of the eight skill levels, from the easiest to the hardest.

On the easiest level, when the bots saw me, they would stand and shoot their weapons at me. Once a weapon was chosen, they would rarely change it. Two skill levels up, the bots start chasing me, and select a better weapon from time to time. They still don’t dodge very well, but at least try. When I put the skill level up three more levels, I noticed that the bots are getting very precise about which weapons they will and will not use. They start to prefer close combat to long-range combat. Their accuracy is definitely better in close quarters. Also, when they attack, they don’t go straight towards me. They tend to move side-to-side a bit and dodge as they approach me. Finally, at the highest skill level, they tend to hide behind cover as best they can, have better accuracy (but still prefer close-combat), move faster, and will always select the best weapon for the current situation.

In an effort to compare my findings against some trusted source, I chose to test the UT bots against the rules of combat described in "The Art of War". This work was written by Sun Tzu, a Chinese general who lived 2400 years ago. This work is still regarded as a great strategic reference, and is still utilized by generals today. I intend only to compare the high-level UT bots, as the low-skill bots are too primitive to compare. Sun Tzu states that the keys to successful battle are knowledge, concealment, and position. The bots are always on the lookout for opponents, and once one is spotted, they will start shooting and moving erratically. They know the levels as good as any human opponent could; they know where all the weapons and goodies are located on a stage, and they know the best path from one point in the board to another. They can perceive that if you go one direction, you will most likely come out at some other specific place on the stage, and they will try to cut you off at that place. They aren’t always accurate, but can guess correctly most of the time. Also, whenever the bot is making an advancement, it will not take the most direct route to its opponent. Instead, it will take the route with the most cover. The bots are not perfect, though. They are good at predicting how to dodge weapons, but they don’t dodge in the same way that a human would dodge. They are less jumpy than a human opponent, and are still somewhat predictable.

Over the past few years, first-person game bots have made incredible progress. They act more and more like a human. In these games, artificial intelligence is viewed differently from traditional artificial intelligence. The AI is designed to act human. A bot does not learn, but rather attempts to play and convince its opponents that it is a human opponent. Though researchers have frowned upon the game industry because many basic techniques that are utilized, and advanced techniques are pushed aside, there is still something to be learned from the AI found in bots. These bots can operate in real time, and are very close to acting just like a human would, inside the game. It shouldn’t matter as much how the goals of intelligent-looking behavior are achieved, but that the goal is actually achieved. This is what the game developers have been working with and perfecting for the past few years.

References

Abramson, Bruce, "Control Strategies for Two-Player Games", ACM Computing Surveys, Vol. 21, No. 2, June 1989.

Bettinson, Mat, "Game Artificial Intelligence", GameSpot Inc., www.gamespot.co.uk/pc.gamespot/features/artintel, 1999.

Crickett, John, "Explaining Common Search Algorithms, Bot A.I.D.", www.botepidemic.com/aid/Search/BFS.html, 1998.

Falise, Sander, "Interview with Mi. Elusive", Project 414n, www.botepidemic.com/414n/index.php3?go=articles,2, August 2000.

Thompson, Scott, "AI Uncertainty", GameDev.net, www.gamedev.net/reference/articles/article197.asp, 1995.

Wright, Jonathan, "Artificial Deathmatch: The story of the Bot", PlanetQuake, www.planetquake.com/design/bots.html.