As BrainWorks is a complete rewrite of the Quake 3 AI code, it was a relatively daunting project that required a lot of effort in many areas. First person shooter AI requires aiming and firing decisions (not the same thing!), item pickup, weapon selection, movement, visual and auditory awareness, and high level strategy to give a non-exhaustive list. Simply put, there's a lot of things to write and they all have to work together. When the project is this large, it's hard to even know where to begin. How do you prioritize such a wide list of features when, quite frankly, everything is required?
For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.
So if Art of War is so great, why have you never heard of it before?
Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.
The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...
When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.
Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.
Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.
I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.
Showing posts with label accuracy. Show all posts
Showing posts with label accuracy. Show all posts
Monday, August 11, 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.
Sunday, May 18, 2008
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.
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.)
- More enemies appear on higher skill levels
- Higher skill enemies have more health and deal more damage
- Higher skill enemies act more intelligently
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
- Aiming speed
- Aiming error correction
- Audio detection of enemies
- Memory of enemies no longer in view
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.
Monday, March 24, 2008
My Biggest Programming Fear
I have encountered some very strange bugs in my programming career. And most of them have been in BrainWorks, being by far the most complicated piece of software I've ever written. One of the worst involved a build that only crashed when run on someone else's system. On my system it was fine, but it would crash on my friend's system. It wouldn't crash right away, mind you. Sometimes it would take up to two minutes, so even testing to see if the bug was fixed took time. Oh, and his computer was in London while mine was in Los Angeles. Not exactly the easiest problem to solve.
I solved it by compiling in debug flags that would turn on or off entire sections of code and then had him run it. "Okay, load bots but turn off all movement, scanning, and aiming. Does it crash now? What about when Item Pickup is turned off?" Through the course of four builds that gradually narrowed in on particular blocks of code, we eventually found the offending bug.
(If you're curious what caused it, an uninitialized value was improperly being treated as an address, crashing the program whenever it was accessed. Because his machine's memory layout was different from mine, it would occasionally access invalid memory and the operating system would kill the program. For whatever reason, the uninitialized values that showed up on my system always happened to refer to memory BrainWorks was allowed to access, so it never crashed for me.)
It took about eight hours to do, but once you've solved a bug like that, you feel cabable of tackling any bug. Bugs bother me, but they don't frighten me. Know what my biggest programming fear is?
0 total errors
Any time I've spent over two hours working on a particular feature and attempt to rebuild the code base, I expect to see at least one error. I'm a good programmer, but that doesn't mean I'm perfect. I'm a good programmer because I know I'm not perfect. Good programmers assume they will make mistakes-- that's why they add all those safety error checks. If some other piece of code does the wrong thing, their error checks will contain it.
Last week I spent four hours tracking down the issues with bots overvaluing the shotgun. The problem was that the estimation of fire frequency wasn't precise enough. I spent another three hours analyzing the similarities between estimating the chance of hitting with a weapon (hits divided by attacks) and the chance of firing a weapon (attacks divided by potential attacks) and designing functionality that merged the two concepts. Actually writing the code took another 2 hours. Nine hours total including changes that could totally break the AI's ability to even attack, and here I am looking at the results from my very first recompile:
0 total errors
I haven't run it yet, but I'm terrified. Zero errors on the first try? That never happens. That's not even supposed to happen. Odds are the code I wrote has an error somewhere; I just don't know where.
At any rate, I plan to test it this upcoming week and get a new release out this weekend. Hope you enjoy it.
I solved it by compiling in debug flags that would turn on or off entire sections of code and then had him run it. "Okay, load bots but turn off all movement, scanning, and aiming. Does it crash now? What about when Item Pickup is turned off?" Through the course of four builds that gradually narrowed in on particular blocks of code, we eventually found the offending bug.
(If you're curious what caused it, an uninitialized value was improperly being treated as an address, crashing the program whenever it was accessed. Because his machine's memory layout was different from mine, it would occasionally access invalid memory and the operating system would kill the program. For whatever reason, the uninitialized values that showed up on my system always happened to refer to memory BrainWorks was allowed to access, so it never crashed for me.)
It took about eight hours to do, but once you've solved a bug like that, you feel cabable of tackling any bug. Bugs bother me, but they don't frighten me. Know what my biggest programming fear is?
0 total errors
Any time I've spent over two hours working on a particular feature and attempt to rebuild the code base, I expect to see at least one error. I'm a good programmer, but that doesn't mean I'm perfect. I'm a good programmer because I know I'm not perfect. Good programmers assume they will make mistakes-- that's why they add all those safety error checks. If some other piece of code does the wrong thing, their error checks will contain it.
Last week I spent four hours tracking down the issues with bots overvaluing the shotgun. The problem was that the estimation of fire frequency wasn't precise enough. I spent another three hours analyzing the similarities between estimating the chance of hitting with a weapon (hits divided by attacks) and the chance of firing a weapon (attacks divided by potential attacks) and designing functionality that merged the two concepts. Actually writing the code took another 2 hours. Nine hours total including changes that could totally break the AI's ability to even attack, and here I am looking at the results from my very first recompile:
0 total errors
I haven't run it yet, but I'm terrified. Zero errors on the first try? That never happens. That's not even supposed to happen. Odds are the code I wrote has an error somewhere; I just don't know where.
At any rate, I plan to test it this upcoming week and get a new release out this weekend. Hope you enjoy it.
Monday, March 17, 2008
Release Retrospective
While people have been overall pleased and impressed with the BrainWorks release, I've received one common bit of negative feedback. Many people have said the bots use the shotgun too often, especially in situations where it's flat out the wrong weapon to use. Now I don't have the luxury other people have of saying, "that's not a bug, that's a feature!" Or more commonly, "that's working as intended." BrainWorks is intended to feel realistic. If many people say a portion of it doesn't feel realistic, they are right. I have no grounds on which to disagree. There really is a bug in the code because you say there is.
Of course, if you've ever been told quite literally, "this thing doesn't feel right, so go fix it," you know how challenging of a request that is. One downside of fundamentally basing the BrainWorks AI on causality is that debugging is extremely difficult. There's no magic number that tells the bot how often to use the shotgun. Instead, the bot analyzes its situation and incorrectly decides the shotgun is the right weapon to use. To solve this problem, I need to walk through the entire analysis and see how it reaches that conclusion. To make matters worse, the bots don't always choose to use the shotgun. And there are surely situations where the bot correctly chooses the shotgun. It's very hard to isolate the situations where the mistake as made and then narrow down why that mistake occurred.
My solution was to write some debug code that outputted all the data the bot used at each step of weapon selection analysis, starting from accuracy and fire rate data and ending with its final valuation of how quickly a given weapon would score a kill. I had it output this data for all weapons available and just stared at the numbers, checking if each data point was an accurate value of the concept representing it. I found three key contributing issues, two of which are solvable.
#1) The estimation of weapon fire rate was incorrectly bounded
Knowing how frequently the bot will fire a weapon is crucial to determining the actual damage rate of the weapon. If a bot spends 3 seconds aiming at a target and only fires for 1 of those seconds, it will do one third the damage as a bot that spends all 3 seconds aiming-- provided it's always lined up for a good shot. The bot tracks how often it actually fires the weapon, but I gave this value a lower bound of 50%. In other words, the bot assumes it will spend at least 50% of its time firing with the weapon, possibly more.
I added this assumption to deal with another problem. Bots would switch to a weapon they had never fired before, not have a perfectly lined up shot, and think... "I've spent 0 seconds firing and 100 milliseconds aiming, so I spend 0% of my time attacking. This weapon is terrible. I'm going to use something else." And they would never try out the weapon to see that they could in fact make shots with it. One problem with relying on historical data is wide variance in the initial data sets. I ran some tests with most of the weapons and found the fire rates were in the 60% to 80% range, so 50% seemed like a good bound.
The problem was that the shotgun only had a fire rate of between 30% and 50%, meaning it's hard to line up good shots with the weapon. There were situations where the bot would think it fired 50% of the time when in reality it had only attacked 30% of the time, which inflated the estimated value of the shotgun by a solid 60%. (160% of 30 is 50.) So it's no wonder they thought the weapon was good. Lowering the minimum bound to 30% had other problems though. When that happened, sometimes bots would stop using genuinely good weapons like the rocket launcher. That's a sign that a lower bound is not the correct way to solve this problem.
Related to this is the second issue:
#2) The estimation of weapon fire rate doesn't take location into account
If you're wondering why the shotgun is generally a bad weapon, it's because it's so situational. At point blank range, it can do more damage than the railgun in two thirds the time. But the spread on the weapon makes its value decrease rapidly at medium and long range. There are situations where the shotgun is good, but not many of them. In contrast, weapons like the railgun are consistently good in a wider variety of situations.
This means that a bot might shoot more often with the shotgun at point blank range than at long range because the shots are easier to line up. If the bot had a 40% fire rate with the shotgun, that might be a 50% rate when close to the enemy but only 30% when far away. Similarly, it's easy to line up shots with the rocket launcher when the target is below you, since you can just shoot at the floor. If the target is above you, you need a direct hit, and that's very hard.
If the bot knew how the firing rate could change depending on the combat situation, it would have a much better understanding of whether a weapon is a good choice against the current target. Unfortunately, the code only tracks a single firing rate for each weapon. The concept of where the enemy was located doesn't factor into the data, and that's a real issue.
The drawback of tracking fire rate data across each of the bot's 12 combat zones is that it will take much longer to get good estimates on actual fire rates. If there were problems before with bots accumulating fire rate data into one data "bucket", now that there are 12 "buckets", it will take 12 times longer before the data stabilizes. In other words, the issue that the 50% minimum fire rate was trying to address has now gotten 12 times worse.
I'm still thinking about the best way to solve this problem, but I'm leaning towards seeding the data with some reasonable estimates of how often the weapons really should be firing. If there's enough seed data, it should encourage the bot to act reasonably until it has enough of it's own data to make conclusions. That just leaves one more issue:
#3) Bots do not take into account how a good choice now could be bad later
The major drawback a situational weapon like the shotgun has is that when you use it, you give your opponent some control. They have the power to make your weapon worse just by backing up. While this is a concern for all weapons, the more situational a weapon is, the worse it is when your opponent exploits your weapon's weakness. In other words, the shotgun isn't just bad because it's only useful at close range. It's bad because your opponent can choose to be at medium or far range after you spend the time to pull out the weapon.
This is unfortunately a much harder problem to solve, since it has to do with the local level geometry. If your opponent has no escape routes, the shotgun is still excellent in close quarters. I haven't thought about this problem very much, but my intuition says that solving it in BrainWorks is well beyond the scope of the project. You might be able to analyze past reactions opponents had to your weapon choices, but it's not clear how good this data would be, how it would affect the bot's choices, and if this problem is even large enough that it needs such a sophisticated solution.
At any rate, I apologize if this post is a bit more technical than normal, but that's the nature of the work. I'm very interested to hear your ideas for how to tackle these problems. I plan on thinking through possible solutions over this upcoming week and writing the fixes next weekend. If you have thoughts on this, I'd love to hear them.
Of course, if you've ever been told quite literally, "this thing doesn't feel right, so go fix it," you know how challenging of a request that is. One downside of fundamentally basing the BrainWorks AI on causality is that debugging is extremely difficult. There's no magic number that tells the bot how often to use the shotgun. Instead, the bot analyzes its situation and incorrectly decides the shotgun is the right weapon to use. To solve this problem, I need to walk through the entire analysis and see how it reaches that conclusion. To make matters worse, the bots don't always choose to use the shotgun. And there are surely situations where the bot correctly chooses the shotgun. It's very hard to isolate the situations where the mistake as made and then narrow down why that mistake occurred.
My solution was to write some debug code that outputted all the data the bot used at each step of weapon selection analysis, starting from accuracy and fire rate data and ending with its final valuation of how quickly a given weapon would score a kill. I had it output this data for all weapons available and just stared at the numbers, checking if each data point was an accurate value of the concept representing it. I found three key contributing issues, two of which are solvable.
#1) The estimation of weapon fire rate was incorrectly bounded
Knowing how frequently the bot will fire a weapon is crucial to determining the actual damage rate of the weapon. If a bot spends 3 seconds aiming at a target and only fires for 1 of those seconds, it will do one third the damage as a bot that spends all 3 seconds aiming-- provided it's always lined up for a good shot. The bot tracks how often it actually fires the weapon, but I gave this value a lower bound of 50%. In other words, the bot assumes it will spend at least 50% of its time firing with the weapon, possibly more.
I added this assumption to deal with another problem. Bots would switch to a weapon they had never fired before, not have a perfectly lined up shot, and think... "I've spent 0 seconds firing and 100 milliseconds aiming, so I spend 0% of my time attacking. This weapon is terrible. I'm going to use something else." And they would never try out the weapon to see that they could in fact make shots with it. One problem with relying on historical data is wide variance in the initial data sets. I ran some tests with most of the weapons and found the fire rates were in the 60% to 80% range, so 50% seemed like a good bound.
The problem was that the shotgun only had a fire rate of between 30% and 50%, meaning it's hard to line up good shots with the weapon. There were situations where the bot would think it fired 50% of the time when in reality it had only attacked 30% of the time, which inflated the estimated value of the shotgun by a solid 60%. (160% of 30 is 50.) So it's no wonder they thought the weapon was good. Lowering the minimum bound to 30% had other problems though. When that happened, sometimes bots would stop using genuinely good weapons like the rocket launcher. That's a sign that a lower bound is not the correct way to solve this problem.
Related to this is the second issue:
#2) The estimation of weapon fire rate doesn't take location into account
If you're wondering why the shotgun is generally a bad weapon, it's because it's so situational. At point blank range, it can do more damage than the railgun in two thirds the time. But the spread on the weapon makes its value decrease rapidly at medium and long range. There are situations where the shotgun is good, but not many of them. In contrast, weapons like the railgun are consistently good in a wider variety of situations.
This means that a bot might shoot more often with the shotgun at point blank range than at long range because the shots are easier to line up. If the bot had a 40% fire rate with the shotgun, that might be a 50% rate when close to the enemy but only 30% when far away. Similarly, it's easy to line up shots with the rocket launcher when the target is below you, since you can just shoot at the floor. If the target is above you, you need a direct hit, and that's very hard.
If the bot knew how the firing rate could change depending on the combat situation, it would have a much better understanding of whether a weapon is a good choice against the current target. Unfortunately, the code only tracks a single firing rate for each weapon. The concept of where the enemy was located doesn't factor into the data, and that's a real issue.
The drawback of tracking fire rate data across each of the bot's 12 combat zones is that it will take much longer to get good estimates on actual fire rates. If there were problems before with bots accumulating fire rate data into one data "bucket", now that there are 12 "buckets", it will take 12 times longer before the data stabilizes. In other words, the issue that the 50% minimum fire rate was trying to address has now gotten 12 times worse.
I'm still thinking about the best way to solve this problem, but I'm leaning towards seeding the data with some reasonable estimates of how often the weapons really should be firing. If there's enough seed data, it should encourage the bot to act reasonably until it has enough of it's own data to make conclusions. That just leaves one more issue:
#3) Bots do not take into account how a good choice now could be bad later
The major drawback a situational weapon like the shotgun has is that when you use it, you give your opponent some control. They have the power to make your weapon worse just by backing up. While this is a concern for all weapons, the more situational a weapon is, the worse it is when your opponent exploits your weapon's weakness. In other words, the shotgun isn't just bad because it's only useful at close range. It's bad because your opponent can choose to be at medium or far range after you spend the time to pull out the weapon.
This is unfortunately a much harder problem to solve, since it has to do with the local level geometry. If your opponent has no escape routes, the shotgun is still excellent in close quarters. I haven't thought about this problem very much, but my intuition says that solving it in BrainWorks is well beyond the scope of the project. You might be able to analyze past reactions opponents had to your weapon choices, but it's not clear how good this data would be, how it would affect the bot's choices, and if this problem is even large enough that it needs such a sophisticated solution.
At any rate, I apologize if this post is a bit more technical than normal, but that's the nature of the work. I'm very interested to hear your ideas for how to tackle these problems. I plan on thinking through possible solutions over this upcoming week and writing the fixes next weekend. If you have thoughts on this, I'd love to hear them.
Friday, January 11, 2008
It's a Hit!
In my last post, I explained how it's easy to decide what weapon a player wants to use given some simple data and one magic value: the player's accuracy with a weapon. It makes perfect sense-- if two weapons deal similar damage and you'll hit twice as often with one of them, then of course that's the weapon you want to use!
There's just two problems with writing AI for this. First, there's no innate concept of "weapon accuracy" like there is for weapon damage or weapon reload. A player's ability to use a weapon well is emergent behavior based on their reaction speed, mental estimation, and muscle precision. Bots don't magically know how accurate they are with a weapon-- they must be taught.
Second, even if bots knew their overall accuracy, that wouldn't be enough. Some weapons are much more effective in some situations than others. The shotgun is good at close range because the shot spread makes it ineffective at long ranges. Rockets are good when you are above your target because you can blast the rocket against the floor, making your target take blast damage even if they dodge the missile, and so on.
To get truly human-like weapon selection, bots need a relatively accurate answer to the following question:
How likely am I hit to hit my target from my current position?
The goal of the accuracy engine (ai_accuracy.c) is to answer this question. Bots solve this question by tracking the results of their attacks in game and modifying their behavior accordingly. If a bot starts scoring a lot of hits with one particular weapon in a certain situation, then it will naturally favor that weapon whenever it's in a that situation again.
Tracking accuracy against actual shots also lets the bots react to differences in player skill. Some weapons are particularly good against players who dodge poorly. If the bot encounters a player like this, their accuracy will increase and they'll know to use weapons that player has trouble with.
The accuracy data is reset every level to prevent bias. For example, if one level is wide open (favoring instant hit weapons) and the next level has many narrow hallways (favoring missile weapons), the bot will notice its higher accuracy on the second level and show a preference for missile weapons.
To differentiate the different combat situations a bot could be in, the bot analyzes both the distance to the target (whether it's near or far) and the bot's pitch view angle (whether the bot has to look up or down to aim at the target). These two values define a "Combat Zone". For example, 500 units away and 15 degrees down is one possible combat zone.
There are a total of 12 "reference" combat zones, forming a 4x3 grid of four distances (close, mid-range, far, very far) and three pitches (high, level, low). When the bot scores a hit (or miss) in a zone, the data is split between the four nearest combat zones. For example, one zone might split its data as:
The bot doesn't even need to know why rockets are better when it aims down at a target. Maybe it's the opponent, maybe it's the level, or maybe it's the bot's aiming algorithm. The reason really doesn't matter. The historical data will tell the bot that the rocket launcher is good in that situation, and that's enough for the bot to select that weapon.
There's just two problems with writing AI for this. First, there's no innate concept of "weapon accuracy" like there is for weapon damage or weapon reload. A player's ability to use a weapon well is emergent behavior based on their reaction speed, mental estimation, and muscle precision. Bots don't magically know how accurate they are with a weapon-- they must be taught.
Second, even if bots knew their overall accuracy, that wouldn't be enough. Some weapons are much more effective in some situations than others. The shotgun is good at close range because the shot spread makes it ineffective at long ranges. Rockets are good when you are above your target because you can blast the rocket against the floor, making your target take blast damage even if they dodge the missile, and so on.
To get truly human-like weapon selection, bots need a relatively accurate answer to the following question:
How likely am I hit to hit my target from my current position?
The goal of the accuracy engine (ai_accuracy.c) is to answer this question. Bots solve this question by tracking the results of their attacks in game and modifying their behavior accordingly. If a bot starts scoring a lot of hits with one particular weapon in a certain situation, then it will naturally favor that weapon whenever it's in a that situation again.
Tracking accuracy against actual shots also lets the bots react to differences in player skill. Some weapons are particularly good against players who dodge poorly. If the bot encounters a player like this, their accuracy will increase and they'll know to use weapons that player has trouble with.
The accuracy data is reset every level to prevent bias. For example, if one level is wide open (favoring instant hit weapons) and the next level has many narrow hallways (favoring missile weapons), the bot will notice its higher accuracy on the second level and show a preference for missile weapons.
To differentiate the different combat situations a bot could be in, the bot analyzes both the distance to the target (whether it's near or far) and the bot's pitch view angle (whether the bot has to look up or down to aim at the target). These two values define a "Combat Zone". For example, 500 units away and 15 degrees down is one possible combat zone.
There are a total of 12 "reference" combat zones, forming a 4x3 grid of four distances (close, mid-range, far, very far) and three pitches (high, level, low). When the bot scores a hit (or miss) in a zone, the data is split between the four nearest combat zones. For example, one zone might split its data as:
- 10% (close, low)
- 40% (close, level)
- 10% (mid, low)
- 40% (mid, level)
- 5% (close, low)
- 20% (close, level)
- 15% (mid, low)
- 60% (mid, level)
The bot doesn't even need to know why rockets are better when it aims down at a target. Maybe it's the opponent, maybe it's the level, or maybe it's the bot's aiming algorithm. The reason really doesn't matter. The historical data will tell the bot that the rocket launcher is good in that situation, and that's enough for the bot to select that weapon.
Monday, January 7, 2008
The Rambo Problem
So imagine you're armed like Rambo. With a machine gun, shotgun, enough grenades to blow up a tank, and a missile launcher, you're a one man army. (Forget for a moment how you're carrying all this stuff; that's why it's a game!) There's just one problem. You only have two hands. So what weapon do you use? If you were one of the original Quake 3 bots, you would use whatever you felt like, as described by some randomly assigned weapon preference values. Unfortunately, that doesn't produce very good results. Shooting a rocket at a moving target far in the distance is bound to miss. What good players do is choose the best weapon to attack the selected target, and that's what BrainWorks bots do as well.
Of course, the devil is in the details: what makes a weapon "best" for the current situation? Well why do players attack targets anyway? To kill them, of course, since each kill is worth one point. The best weapon is whichever weapon will kill the target fastest. Mathematically estimating "Time to Death" (TTD) is an easy enough problem, given the following input variables for each weapon:
The bot will average one hit every R*A/P = T seconds with whatever weapon it's considering, and it will kill the target in H/D = K hits, with a minimum of 1 hit. In other words, a weapon that deals 100 damage will require 1 hit against a target with 20 health, not .2 hits. This bounding ensures that the bot properly penalizes itself for "overkill" on the last hit. Against a target with 120 health, the bot might continue using the 100 damage/hit weapon until it scores a hit, and then switch to something else when the target is at 20 health.
This tiny little bit of code creates the crucial bit of emergent behavior known as "weapon combos". BrainWorks bots can and do attack bots with some high damage, slow reload weapons, and then switch to a spray-and-pray weapon like the machine gun or shotgun to finish off wounded opponents. It's something every good human player does and I never wrote a bit of code that says, "switch to the machine gun if the target has less than 30 health." This emergent behavior is the payoff from properly designing the algorithm, and it handles far more situations than the one described.
At any rate, if the bot averages one hit every T seconds and needs H hits to kill the target, the estimated time to death with a given weapon is T*K... Right? Well yes, but for reasons more complicated than they first appear. The real time to death is the sum of a geometric series defined as, "Chance to kill in 1 shot multiplied by time to fire 1 shot plus chance to kill in 2 shots multiplied by time to fire 2 shots plus ..." But this value turns out to be T*K.
There are a few other caveats well. No reload time is incurred for the last shot required to kill a target, so the code deducts R/P seconds from time to death for that. And if the weapon being considered isn't the currently equipped weapon, there's a reload penalty for switching which increases the time to death. The weapon switch reload penalty is automatically incurred (possibly a second time) if the considered weapon doesn't have ammo to kill the target, since the bot will be forced to change once it runs out. But that's the algorithm in a nutshell:
Search all weapons available, find the one that kills the target fastest, and use it.
If you've been reading closely, there are still two details I've glossed over: Estimating target health and estimating weapon accuracy. For health, bad players don't even think about it, good players estimate based on sounds (wounded players sound different), and great players keep a running total of the health value based on the hits the score and the items they see their target pickup. Attempting to model this, the average and low skill BrainWorks bots assume everyone has a fixed health total. The above average bots roughly know their target's health to the nearest 25 health points. And the best bots will flat out cheat and look up the exact health value. That last part is a bit unrealistic, but the information is used in a realistic manner. You don't have to use strict causality and emergent behavior for every problem to get good results.
Estimating accuracy is much harder, hard enough that there is an entire ai_accuracy.c file devoted to tracking it, so I will cover that topic at a later date.
Of course, the devil is in the details: what makes a weapon "best" for the current situation? Well why do players attack targets anyway? To kill them, of course, since each kill is worth one point. The best weapon is whichever weapon will kill the target fastest. Mathematically estimating "Time to Death" (TTD) is an easy enough problem, given the following input variables for each weapon:
- D = Damage per hit
- R = Reload between shots
- A = Bot's accuracy with this weapon
- P = Percent of time the bot attacks with this weapon
- H = Target's current health
The bot will average one hit every R*A/P = T seconds with whatever weapon it's considering, and it will kill the target in H/D = K hits, with a minimum of 1 hit. In other words, a weapon that deals 100 damage will require 1 hit against a target with 20 health, not .2 hits. This bounding ensures that the bot properly penalizes itself for "overkill" on the last hit. Against a target with 120 health, the bot might continue using the 100 damage/hit weapon until it scores a hit, and then switch to something else when the target is at 20 health.
This tiny little bit of code creates the crucial bit of emergent behavior known as "weapon combos". BrainWorks bots can and do attack bots with some high damage, slow reload weapons, and then switch to a spray-and-pray weapon like the machine gun or shotgun to finish off wounded opponents. It's something every good human player does and I never wrote a bit of code that says, "switch to the machine gun if the target has less than 30 health." This emergent behavior is the payoff from properly designing the algorithm, and it handles far more situations than the one described.
At any rate, if the bot averages one hit every T seconds and needs H hits to kill the target, the estimated time to death with a given weapon is T*K... Right? Well yes, but for reasons more complicated than they first appear. The real time to death is the sum of a geometric series defined as, "Chance to kill in 1 shot multiplied by time to fire 1 shot plus chance to kill in 2 shots multiplied by time to fire 2 shots plus ..." But this value turns out to be T*K.
There are a few other caveats well. No reload time is incurred for the last shot required to kill a target, so the code deducts R/P seconds from time to death for that. And if the weapon being considered isn't the currently equipped weapon, there's a reload penalty for switching which increases the time to death. The weapon switch reload penalty is automatically incurred (possibly a second time) if the considered weapon doesn't have ammo to kill the target, since the bot will be forced to change once it runs out. But that's the algorithm in a nutshell:
Search all weapons available, find the one that kills the target fastest, and use it.
If you've been reading closely, there are still two details I've glossed over: Estimating target health and estimating weapon accuracy. For health, bad players don't even think about it, good players estimate based on sounds (wounded players sound different), and great players keep a running total of the health value based on the hits the score and the items they see their target pickup. Attempting to model this, the average and low skill BrainWorks bots assume everyone has a fixed health total. The above average bots roughly know their target's health to the nearest 25 health points. And the best bots will flat out cheat and look up the exact health value. That last part is a bit unrealistic, but the information is used in a realistic manner. You don't have to use strict causality and emergent behavior for every problem to get good results.
Estimating accuracy is much harder, hard enough that there is an entire ai_accuracy.c file devoted to tracking it, so I will cover that topic at a later date.
Subscribe to:
Posts (Atom)