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.
Showing posts with label Aiming. Show all posts
Showing posts with label Aiming. Show all posts
Monday, August 18, 2008
Monday, July 7, 2008
A Simple Solution
As the story ended last week, I had uncovered a very strange bug in BrainWorks. There was up to a 10% accuracy difference between the first bot added to the game and the last bot. No one guessed the correct cause, but this one from cyrri was the closest:
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
bots occupy client slots in the same order as they are added.This actually does happen, but it only accounts for a 1% to 2% accuracy change between the first and last bots. Also, this value increases as bot accuracy increases, since it's more likely that two bots will be lined up for a good shot at the same time.
in the very rare cases of two clients killing a third one simultaneously, it is allways the one with the lower slot id that gets the frag, becuase his usercommands are processed first. the other one gets a missed shot.
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
Monday, June 30, 2008
A Peculiar Bug
In my postmortem of BrainWorks, I mentioned one of the big things I did right was creating a powerful debugging infrastructure directly in the code base itself. In general, it's easiest to test and maintain software when as much of the testing is fully automated as possible. Now that's easy for a program like Excel, where you can create a battery of sheets with strange formulas that might cause errors, and then confirm that the numbers all match up. If the software creates something measurable, it can usually be automatically tested.
Naturally, this means automated testing is far harder for Artificial Intelligence than other areas of computer science. The goal of BrainWorks is "bots that appear to be human". How do you teach a computer to measure whether a player's decisions appear to be human? That's tantamount to writing a program that can judge a Turing test, which is as hard as passing one. Fully automated testing of the AI isn't an option, but there are certainly things that can assist testing. All you have to do is identify an measurable component and check if it meets the human expectations.
For aiming, BrainWorks already measures accuracies with each weapon in each combat situation. The bot knows that it scores perhaps 35% with the shotgun against an enemy a few feet away and 5% against an enemy a hundred feet away. But it doesn't know if those numbers are reasonable until I tell it what to expect. The vast majority of the testing I did with aiming involved forcing a bot to use a particular weapon, making it play for hours, and then checking if the numbers "looked good". Generally they didn't, and I had to figure out why they weren't matching my expectations. In this testing process, I uncovered a variety of interesting bugs. Large sections of the aiming algorithm were rewritten around a dozen times trying to get things right. I found several errors in how accuracy was even being measured. But the strangest error I encountered was something totally unexpected.
I was monitoring Railgun accuracy as way of testing the overall ability to aim. It's an instant hit weapon with no spread and infinite range, so it's a great initial test case. I loaded up eight bots on a wide open level and forced them all to have exactly the same skill, then ran them for several hours. Curiously when I checked the results, their accuracies weren't all the same. The best had an accuracy around 75% and the worst was around 65%. Moreover, their scores reflected this.
I activated some mechanics in the system to modify aiming behavior. First I turned off all errors, so the aiming should be flawless, like watching a human who doesn't make mistakes. Their accuracies were still stratified. Then I completely circumvented the entire aiming code, forcing the bots to aim directly where they wanted to. That gave the bots what most people think of as an aim hacking, so their aim should have been perfect. But even still, testing showed that some bots would get higher accuracies than others. Sure, there was one bot that would score 99.9% accuracy, but another bot would only score 97%. When a bot has perfect information and reflexes, it should not miss one in 30 shots.
Then one day I noticed that all eight bots were sorted in alphabetical order. The bot with the first name had the highest score (and accuracy) down to the bot with the last name having the lowest score. Since the odds of this are 1 in 8! = 40,320, I considered this curious but still possibly a coincidence. So I tested it again, and each time the bots were sorted alphabetically! That was the final clue I needed to isolate this bug.
The script I used to start testing adds the bots in alphabetical order, so I tried swapping the order different bots were added and their accuracies changed as a result. Each time, the most accurate bot was added to the game first and the least accurate bot was added last. For some reason, the internal numbering of bots was affecting their aim.
So why exactly was this the case? I'll let you puzzle over it for the week. Next week I'll explain why this happened and the extreme amount of work that went into solving it.
Naturally, this means automated testing is far harder for Artificial Intelligence than other areas of computer science. The goal of BrainWorks is "bots that appear to be human". How do you teach a computer to measure whether a player's decisions appear to be human? That's tantamount to writing a program that can judge a Turing test, which is as hard as passing one. Fully automated testing of the AI isn't an option, but there are certainly things that can assist testing. All you have to do is identify an measurable component and check if it meets the human expectations.
For aiming, BrainWorks already measures accuracies with each weapon in each combat situation. The bot knows that it scores perhaps 35% with the shotgun against an enemy a few feet away and 5% against an enemy a hundred feet away. But it doesn't know if those numbers are reasonable until I tell it what to expect. The vast majority of the testing I did with aiming involved forcing a bot to use a particular weapon, making it play for hours, and then checking if the numbers "looked good". Generally they didn't, and I had to figure out why they weren't matching my expectations. In this testing process, I uncovered a variety of interesting bugs. Large sections of the aiming algorithm were rewritten around a dozen times trying to get things right. I found several errors in how accuracy was even being measured. But the strangest error I encountered was something totally unexpected.
I was monitoring Railgun accuracy as way of testing the overall ability to aim. It's an instant hit weapon with no spread and infinite range, so it's a great initial test case. I loaded up eight bots on a wide open level and forced them all to have exactly the same skill, then ran them for several hours. Curiously when I checked the results, their accuracies weren't all the same. The best had an accuracy around 75% and the worst was around 65%. Moreover, their scores reflected this.
I activated some mechanics in the system to modify aiming behavior. First I turned off all errors, so the aiming should be flawless, like watching a human who doesn't make mistakes. Their accuracies were still stratified. Then I completely circumvented the entire aiming code, forcing the bots to aim directly where they wanted to. That gave the bots what most people think of as an aim hacking, so their aim should have been perfect. But even still, testing showed that some bots would get higher accuracies than others. Sure, there was one bot that would score 99.9% accuracy, but another bot would only score 97%. When a bot has perfect information and reflexes, it should not miss one in 30 shots.
Then one day I noticed that all eight bots were sorted in alphabetical order. The bot with the first name had the highest score (and accuracy) down to the bot with the last name having the lowest score. Since the odds of this are 1 in 8! = 40,320, I considered this curious but still possibly a coincidence. So I tested it again, and each time the bots were sorted alphabetically! That was the final clue I needed to isolate this bug.
The script I used to start testing adds the bots in alphabetical order, so I tried swapping the order different bots were added and their accuracies changed as a result. Each time, the most accurate bot was added to the game first and the least accurate bot was added last. For some reason, the internal numbering of bots was affecting their aim.
So why exactly was this the case? I'll let you puzzle over it for the week. Next week I'll explain why this happened and the extreme amount of work that went into solving it.
Monday, June 2, 2008
It's All In The Wrist
I consider the aiming algorithm used by the BrainWorks bots to be the biggest success of the project. More than one experienced Quake player has told me how amazed they were to spectate the bots and watch their aiming, since it appears so realistic. I went through close to a dozen different iterations of the basic aiming engine until I got results I was pleased with, and this is the research that took most of the six year development period. I estimate roughly 60% of the work was spent on aiming! (If you're curious, item pickup was about 30% of the time and everything else took 10% total.) To me, the objective was to create a bot whose aiming realistically matched a human player's aiming. There's a secret to how I did this:
It's all in the wrist.
Most games don't let you spectate their AI units because it would be immediately obvious how the AI is cheating. But if you could, you almost always see on of two things. The AI might look almost directly at the player and but moves their camera away from the ideal position by a random amount, so that they miss sometimes at random. Or the AI could turn at a fixed, slowish speed, but always (eventually) aims more or less perfectly, so that they only miss right after the target suddenly changes.
The problem is that these algorithms don't model how a human wrist would interact with a mouse. So the result is that the AI won't miss at sometimes the human would miss, and will hit when the human won't hit. For example, rapidly moving side to side will confuse the AI whose aiming moves at a fixed, slowish rate, making them constantly miss. With these traditional algorithms, no matter what parameters the bot has for speed and error frequency, its aiming will never look like a human. That means its accuracy with weapons will never match human accuracies either.
The solution to modeling the aiming problem is to stop thinking about the monitor (whether the crosshairs are lined up) and start thinking about the mouse (how human motion changes the crosshairs). Human motion of the mouse doesn't move at a fixed speed, and it doesn't "randomly" move to the wrong area. The motion involves acceleration and deceleration. The faster a human moves a muscle, the larger the potential error. Humans can increase the precision of their movements by moving slower, so typical human motion involves a rapid acceleration to a desired speed, some time moving at that speed, and then deceleration to a rest state.
Mathematically this means that if a human attempts to accelerate at rate X m/s^2, the actual acceleration is somewhere in the interval [X*(1-e), X*(1+e)] where e is the maximum allowed error (eg. 10%). So a small error in acceleration is magnified over time each time the acceleration is applied to the velocity, and the velocity error in turn magnifies position error each time the velocity changes the view position. This, combined with an extremely simple, elegant error correction algorithm, provides an excellent simulation of the view motion created by a human hand on a mouse.
That's basically the algorithm BrainWorks implements. The bot splits its view state into two distinct axies: Up and down on the simulated mousepad make the bot pitch its view up or down, and moving left or right on the mousepad make the bot rotate left and right. This reduces the view problem into two identical one-dimensional problems. For each axis, the bot decides how much to accelerate and decelerate the movement of its simulated mouse to get from its current view position to its selected view position as quickly as possible. The small acceleration error factor is all that's needed to generate the smooth overshooting mistakes that humans make when they try to turn quickly with a mouse.
The calculus to compute exactly how much time to spend accelerating and decelerating is a bit complicated: there's a 150 line comment explaining the derivation in ViewAxisModify() function in ai_view.c. But the resulting equations are fast and easy to compute. It's 30 lines of actual code, only one square root, four floating point divides, and a whole bunch of adds and multiplies.
As I said, it's all in the wrist.
It's all in the wrist.
Most games don't let you spectate their AI units because it would be immediately obvious how the AI is cheating. But if you could, you almost always see on of two things. The AI might look almost directly at the player and but moves their camera away from the ideal position by a random amount, so that they miss sometimes at random. Or the AI could turn at a fixed, slowish speed, but always (eventually) aims more or less perfectly, so that they only miss right after the target suddenly changes.
The problem is that these algorithms don't model how a human wrist would interact with a mouse. So the result is that the AI won't miss at sometimes the human would miss, and will hit when the human won't hit. For example, rapidly moving side to side will confuse the AI whose aiming moves at a fixed, slowish rate, making them constantly miss. With these traditional algorithms, no matter what parameters the bot has for speed and error frequency, its aiming will never look like a human. That means its accuracy with weapons will never match human accuracies either.
The solution to modeling the aiming problem is to stop thinking about the monitor (whether the crosshairs are lined up) and start thinking about the mouse (how human motion changes the crosshairs). Human motion of the mouse doesn't move at a fixed speed, and it doesn't "randomly" move to the wrong area. The motion involves acceleration and deceleration. The faster a human moves a muscle, the larger the potential error. Humans can increase the precision of their movements by moving slower, so typical human motion involves a rapid acceleration to a desired speed, some time moving at that speed, and then deceleration to a rest state.
Mathematically this means that if a human attempts to accelerate at rate X m/s^2, the actual acceleration is somewhere in the interval [X*(1-e), X*(1+e)] where e is the maximum allowed error (eg. 10%). So a small error in acceleration is magnified over time each time the acceleration is applied to the velocity, and the velocity error in turn magnifies position error each time the velocity changes the view position. This, combined with an extremely simple, elegant error correction algorithm, provides an excellent simulation of the view motion created by a human hand on a mouse.
That's basically the algorithm BrainWorks implements. The bot splits its view state into two distinct axies: Up and down on the simulated mousepad make the bot pitch its view up or down, and moving left or right on the mousepad make the bot rotate left and right. This reduces the view problem into two identical one-dimensional problems. For each axis, the bot decides how much to accelerate and decelerate the movement of its simulated mouse to get from its current view position to its selected view position as quickly as possible. The small acceleration error factor is all that's needed to generate the smooth overshooting mistakes that humans make when they try to turn quickly with a mouse.
The calculus to compute exactly how much time to spend accelerating and decelerating is a bit complicated: there's a 150 line comment explaining the derivation in ViewAxisModify() function in ai_view.c. But the resulting equations are fast and easy to compute. It's 30 lines of actual code, only one square root, four floating point divides, and a whole bunch of adds and multiplies.
As I said, it's all in the wrist.
Monday, April 7, 2008
Getting it "Just Right"
There's not much difference between driving 55 and 56. Unless of course the speed limit is 55, in which case that small amount of speed could make you get a speeding ticket. Standard outside temperatures average between 0 and 100 degrees Fahrenheit, but people easily notice the difference between 68 and 72 degrees. And yet for other measurements in our lives, small changes are completely unnoticed. A car with a full gas tank drives just as well as a car with a quarter tank left-- you only notice the problem when the last drop of gas is gone.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
Tuesday, February 12, 2008
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.
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.
Monday, January 28, 2008
You've Got My Attention
Everyone has had moments of deep concentration, only to be interrupted by someone's voice. Turning to see who spoke is the natural response. People naturally look at whatever thing has their attention, so a First Person Shooter bot should be no different. And because "looking" (aiming) is literally half of this AI problem, bots need a detailed mechanism for deciding what occupies their attention. Just figuring out what the bot wants to look at is complex enough.
Last post I described how bots become aware of different enemy targets and select one as the target to aim at. But just because the bot has an enemy to aim at doesn't mean there isn't something even more demanding of the bot's attention. And what happens when the bot can't find an enemy to look at? They have to look at something, presumably in the direction an enemy is most likely to appear.
The selection of where to look is handled by the aim engine (ai_aim.c). The selection algorithm uses a simple priority structure to arbitrate between conflicting things. For example, if the bot needs to jump over a pit while there is an enemy nearby, the bot will always look in the direction of the jump so it doesn't mess it up. While aiming at the enemy it might score the bot a kill, doing so makes the bot extremely likely to fall down the pit to its death. The bot can always aim at the enemy after landing the jump. Similarly if the bot hears a noise that might have been made by a player, the bot will only turn to inspect that area if the bot doesn't already have a known target. Aiming at enemies has a lower priority than getting air but a higher priority than finding additional targets.
Here is the list of typical aiming reasons, from most to least important, as taken from BotAimSelect():
The base of Maslow's pyramid is comprised of immediate pressing needs, just like the top of the aiming priorities. Bots look forward when jumping because they will die if they don't. Bots don't look at items when there's an enemy nearby who wants to kill them. In this regard, bots are like humans. We are all programmed for survival as the greatest need.
Last post I described how bots become aware of different enemy targets and select one as the target to aim at. But just because the bot has an enemy to aim at doesn't mean there isn't something even more demanding of the bot's attention. And what happens when the bot can't find an enemy to look at? They have to look at something, presumably in the direction an enemy is most likely to appear.
The selection of where to look is handled by the aim engine (ai_aim.c). The selection algorithm uses a simple priority structure to arbitrate between conflicting things. For example, if the bot needs to jump over a pit while there is an enemy nearby, the bot will always look in the direction of the jump so it doesn't mess it up. While aiming at the enemy it might score the bot a kill, doing so makes the bot extremely likely to fall down the pit to its death. The bot can always aim at the enemy after landing the jump. Similarly if the bot hears a noise that might have been made by a player, the bot will only turn to inspect that area if the bot doesn't already have a known target. Aiming at enemies has a lower priority than getting air but a higher priority than finding additional targets.
Here is the list of typical aiming reasons, from most to least important, as taken from BotAimSelect():
- Jumping over pits
- Aiming at enemies
- Shooting destructible objects like mines
- Looking forward when swimming
- Face a non-hostile target that has the bot's attention
- Look at the item the bot is going to pick up
- Look in an area enemies are likely to be
- Look at the same thing as last time
- Physiological Needs (being free from short term danger)
- Safety (being free from long term danger)
- Love (being accepted)
- Esteem (being appreciated)
- Self Actualization (just being who you are)
The base of Maslow's pyramid is comprised of immediate pressing needs, just like the top of the aiming priorities. Bots look forward when jumping because they will die if they don't. Bots don't look at items when there's an enemy nearby who wants to kill them. In this regard, bots are like humans. We are all programmed for survival as the greatest need.
Subscribe to:
Posts (Atom)