Scouting for Trouble

One of the funny things about designing artificial intelligence is that you run into all kinds of problems you never even considered. For example, I spent a lot of time designing algorithms to handle realistic aiming. But what does the bot do when it's not trying to line up a shot? It has to look at something, even if there's no one else in the area. That's because the bot must either hear or see an enemy to become aware of it and start shooting back. Scouting around for likely areas an enemy might be is the best thing the bot can do when, well, it has nothing else to do.

The issue is that a bot doesn't visualize the game the same way a human does. Technically stated, bots don't visualize anything at all. While we as humans see a brightly rendered three dimensional area, that's too much information for the artificial intelligence to process in a short amount of time. A Quake 3 bot actually uses something similar to sonar to "visualize" the world. It sends out a instantaneous pulse in a perfectly straight line and figures out where that pulse hits something. It can even tell what kind of thing the pulse hits, like a wall or some fleshy target. However, there isn't enough time to send pulses in all directions, so the bot needs to carefully spend its allotment. If it spends too much time figuring out what's nearby, it won't have enough time to think about other important things (such as where to run).

Getting back to the problem at hand, think about how a human player would decide where to look for new targets. In a hallway the solution is obvious-- look in both directions the hallway runs, but not towards the walls. In a large room you look towards the other side of the room, in doorways, and archways. As humans we quickly process the two dimensional rendering of the area and mentally create a three dimensional depth map. Then we look into the areas with the furthest line of sight, for the most part. That's because new targets come from far away.

While it's very hard for a bot to identify which areas are doors and hallways using its "sonar", it can at least determine which areas of the room are far away. To do this, the bot just sends out eight pulses around itself and finds the three that have furthest line-of-sight. It does some additional checking to find the ground below that point, so when the bot is on a ramp or staircase, it actually looks down the direction of the stairs. And then the bot randomly picks one of the three furthest directions. It's a pretty simple solution, and it does a great job of making sure the bot scouts in the areas where opponents will appear.

Now the interesting thing to note is that no human opponent ever actually sees the bot doing this for more than a fraction of a second. Once you're in the bot's field of view, it will start aiming at you rather than looking for more targets. But a human would notice the results of this code, in that the bots notice them and start responding in a realistic manner. An algorithm that no human actually sees is obviously less important than one they interact with all the time. But that's not the same thing as unimportant, and the relative simplicity of the scouting code reflects this.

Making Things Right

You do it thousands of times each day without even thinking about it. It happens when you put on your clothes, brush your teeth, eat your food, and open a door. Every time you walk down a hallway, drive down the street, or type at your computer, your brain is rapidly, subconsciously processing all kinds of data. Most of the information is uninteresting and gets discarded. But when the brain encounters little bits of unexpected data, for the most part it seamlessly reacts, performing minor adjustments to correct whatever mistakes were made in fine motor control. Someone might brush your shoulder as they pass you on the street, and without even thinking about it you step to the side. Or you see the car in front of you start breaking and you slow down as well. You don't swallow your food until the pieces feel sufficiently chewed in your mouth.

Somehow, the human brain performs thousands of minor error corrections while performing basic motor controls. Large motions are fast but they aren't precise. How exactly does this work? If you mean to move your hand 10 centimeters and actually move it 11, your brain compensates for the extra centimeter and has your hand move back. Well maybe it only moves 9 millimeters instead of 1 centimeter, but it gets close enough that it doesn't matter.

When I discussed how BrainWorks emulates human wrist motion, I explained this elegant mathematical model where errors accumulate based on muscle acceleration. But I brushed over the other half of this system, where the bot accounts for its error and readjusts. With error correction that's not good enough, a bot's aiming just looks erratic. And with error correction that's too accurate, the aiming looks robotic. There's a very fine balance to getting error correction that looks human, and to do that you need to understand how the human brain corrects muscle errors. There's just one problem with that...

I have no idea how it happens.

There have been numerous studies on this kind of thing, but I confess I haven't read them. Maybe they would have been useful; maybe they wouldn't. Instead, I tried a number of different methods for error correction (that number is 5), and only one of them produced realistic results. While I can't tell you how the human brain solves this problem, I can explain the one that worked.

From the bot's perspective, here's the problem. It thinks it's aiming at position X, but in reality it's aiming at X+e, where e is the error factor. As the bot corrects its error (ie. understands the mistake it has made), the error factor e approaches zero. An error factor of zero means the bot thinks it's aiming at X and is actually aiming at X+0 = X, meaning it perfectly understands where it is aiming. Most of my failed attempts used some form of exponential or linear decay. Ironically, the algorithm that worked is by far the simplest. It's just a canonical monte carlo algorithm:

1. Set the error value to a random number between -e and +e
2. There is no step 2

It's just that simple. You can read the full explanation behind this algorithm in the DataPerceiveCorrect() function in ai_view.c. It's a 100 line comment describing, quite literally, one line of actual code. Here's the body of the function:

float DataPerceiveCorrect(float estimate_offset)
{
 // Pick a new value in (0, +error) or (-error, 0)
 //
 // NOTE: It doesn't matter what the sign of error is; the random
 // function will preserve it.
 return random() * estimate_offset;
}

While I won't reproduce that entire 100 line description here, here's a portion of it that explains in more detail why this works:

Humans seem to use the following algorithm for refining estimates. For example, finding the dictionary page that contains a given word.

1) Make a reasonable estimate given the human's understanding of the situation. For example, even though W is the 23rd letter of the alphabet, humans don't look at the (23/26) * MAX_PAGES page of the dictionary when looking up W words, simply because they know the X-Y-Z sections are so short. This indexing is similar to the Interpolation Search algorithm. This result is compared to the actual value (ie. is the guess too high or too low?) and this value is fixed as either an upper or lower
bound. In other words, you mark this page with your finger.

2) Possibly make one or two more reasonable estimates to determine both an upper and lower bound that the data must reside in. At this point the human knows that lower < value < upper. He or she knows the precise values of "lower" and "upper" but NOT of "value".

3) Pick a random value in the interval (lower, upper) and compare it to "value". This selection replaces either the lower or upper bound as necessary. Repeat until the selection equals "value".

This might seem unintuitive, but humans don't actually use binary search to narrow down their errors when the range gets sufficiently small. Perhaps it takes too much time to roughly estimate the middle. In practice people will flip through maybe 10 pages at a time, or 1 page at a time, or just pick something and see. It will take more iterations to converge than binary search would but-- and this is crucial-- it takes less time overall than computing the midpoint at each iteration.

That is it say, a computer's most natural method of search is not the same as a human's. Computers usually operate best with binary search while humans "just try something". Only when I programmed the AI to do something counter-intuitive (for a computer) did the AI seem human.

Making Things Worse

One of the major challenges of game AI is creating AI that's plays at an appropriate skill level for a range a players. Most games need AI in easy, medium, and hard settings so that as players become better, they can face more appropriate challenges. There are three typical methods for solving this problem.

• More enemies appear on higher skill levels
• Higher skill enemies have more health and deal more damage
• Higher skill enemies act more intelligently

The first two are obviously far easier to implement than the last, but more intelligent enemies gives more satisfying results. While additional enemies works fine for a single player first person shooter like Half Life, it's not an option for Quake 3, since the player selects the number of enemies when they pick the level. The second option, adding more health and damage, was exactly what iD software used for the two lowest skill bots in the original AI. While skills 3-5 gained better accuracy, skills 1 and 2 simply dealt less damage and died faster than a skill 3 bot.

Of course it's the last option, coding additional levels of intelligence, that's "real AI". The other methods have their place, generally when deadlines must be met. But the reason good human players beat bad human players at a game isn't that the bad players accidentally had the "deal less damage" option checked. They just get outsmarted. High skill AI needs to outsmart people more often than low skill AI does, and you don't encounter that kind of AI very often in computer gaming.

When designing BrainWorks, I was determined that all skill gradations would be created by additional intelligence, at least where applicable. So, yes, bots will have more accurate aiming as their skill increases. But they also gain abilities. Here are some of the abilities BrainWorks bots gain and their minimum skill levels. (Skill 1 is the lowest, 5 is the highest.)

• Strafe jumping: Skill 4
• Blast shots: Skill 3
• Item Respawn Timing: Skill 3 (1 item), 4 (2 items), and 5 (3 items)
• Simultaneous movement and attacking: Skill 2

That's right, a skill 1 bot stops moving whenever it starts shooting. There are also other abilities that gradually increase in effect as skill increases:

• Aiming speed
• Aiming error correction
• Audio detection of enemies
• Memory of enemies no longer in view

And more that I'm sure I've missed. To make realistic low skill bots, it's best to start with realistic high skill bots and then take away intelligence until the result seems appropriate for the intended human's skill level. AI designed the other way, by taking bad AI and giving it more health and damage, never quite feels realistic.

Putting It All Together

I've received a number of requests from people who want to see the bots in action, but don't have Quake 3 installed. So I recorded a short demo of the bots in action, spectating from a bot's point of view. All the bots in this game are skill 4 out of 5, so they're intended to give an experienced player a run for their money. While there's a lot to be said about how each individual piece of code works, it's the entire package that matters. Weapon selection is meaningless without good aiming or item pickup, for example. Here's the video:



The biggest thing this demo shows is how realistic their aiming is. The bot's view changes as chaotically and accurately as a real person would, which is to say "generally pretty accurate, but fast enough to be a bit hard to follow". They quickly respond to changes in attention and their aim isn't instantly spot on, but they correct their aiming mistakes relatively rapidly. You can also see some good firing decisions. For example, early on Xaero fights Mynx in a narrow hallway. Xaero correctly chooses the rocket launcher and kills Mynx with two well placed blast hits.

You can also see how the bots do a pretty good job of picking up the crucial items. One of the first things they do when they respawn is grab a weapon, and they make sure to pickup health and armor when needed. It might not seem like a big deal that bots choose to pickup armor when they are near it, but it really is. The original Quake 3 bots were notorious for ignoring perfectly useful items.

This video also highlights areas where the bots could improve. Most notably, the navigation algorithm, which I could not change. Later in the demo, you can see Xaero dodge in place for maybe 10 seconds before Hunter arrives and Xaero kills her. In this situation, Xaero hears Hunter below him and wants to get to her, but he can't figure out how to jump down the ledge. So he dodges in place until she arrives. Once Xaero kills hunter, he goes on his way, picking up the megahealth and some armor.

So BrainWorks represents a lot of progress for First Person Shooter AI, but there's still a lot of room for improvement. As I said before, AI is hard! For those of you interested in more posts describing exactly how BrainWorks, uh, works, fear not! Next post we'll dive into one of the most complicated systems in the code, item pickup, and explain how the BrainWorks bots solve this difficult problem.

Two Kinds of AI

There are two kinds of artificial intelligence problems. In both situations, the AI has data describing its world, but the two kinds of problems require vastly different solutions. In a video game, the AI can have perfect information about, well, everything. You can find out the exact location of anything, how fast it's moving, and pinpoint sound effects. The server can even give the AI perfect information about its enemies, like their current health and weapons.

Contrast this with AI in a real world setting, like creating an AI that drives cars:



Now the AI has a whole different set of problems. Your car might have a lot of sensors, but there still can be measurement errors. The data might not be in the ideal format-- in a game, the coordinates of all nearby objects are encoded in three dimensions. But an AI to drive a car would have to extract those coordinates from two dimensional camera images. And if game AI takes too long to think, the worst that happens is a slower server. If your car's AI thinks too long while driving on the freeway, it could get into an accident!

Of course, while writing AI for simulated environments like games is much easier than real world applications, it has a different set of challenges. A bot that always knows where you are and aims perfectly isn't much fun to play against. To make a fun bot, the AI should only use data a real player would have access to.

The challenge of real world AI is computing accurate data.
The challenge of simulated world AI is determining which pieces of data to use.

So when I tackled the problem of selecting which enemy a bot wants to attack, you can imagine the kind of challenge I faced. The simple and obvious solution-- considering each player in the game-- was simply incorrect because it used data the bot absolutely should not have access to. To solve this problem, I wrote an environment scanning engine for BrainWorks (ai_scan.c). Ironically, the purpose of this module is completely different from the scanning a car's AI would do. The BrainWorks scanning engine "fuzzes up" the data so it's less accurate, or simply ignores things the bot shouldn't know about. While it would be nice for bots to perform this task the same way humans do, in this case the bot approaches the problem in the exact opposite manner.

The bot starts by checking everything in the game and testing if it can see it, by testing that no walls are in the way, the bot is facing the thing, and the thing isn't too far away. The bot records all targets it sees in its awareness list (ai_aware.c). If the bot hasn't seen a target yet, there is a short delay before the target is "active" in the list, meaning the bot has officially spotted the target. This is analogous to time it takes humans to react to sudden changes. Furthermore, the bot will remain aware of this target for a few seconds even if they hide behind a corner. Just like a bot can't know about a target behind a corner it hasn't seen, the bot must know about that target if they have seen them. That enables the bot to chase after the enemy, should they run away.

And of course, there are other things the bot scans for. If it sees incoming missiles, it notes them as well so it can dodge out of the way. Sound effects help the bot identify enemies that can be heard but not seen, and so on. Once the bot has a list of enemies, it analyzes them to decide which it should attack. (Generally this is whichever enemy the bot has the easiest time shooting.)

All that work just to figure out who the bot wants to shoot at! The bot might have thought about the problem differently from humans, but it came to the same results. Sometimes good AI means making the AI play worse instead of better.