There's a class of questions that have no good answers to them. For example:
Have you stopped beating your wife?
The question presupposes something that is hopefully false, and giving either a yes or no answer implies the question is legitimate. The solution is to provide an answer that challenges the premise. In other words:
I never started.
First person shooter games like Quake 3 are really games of questions and answers. Every shot you take at an opponent asks the question, "How will you survive this hit?" And your opponent would prefer to respond, "You aren't going to hit me". Of course, he doesn't have much say for an instant hit bullet weapon like a machine gun or shotgun. Either you hit him or you don't. But these weapons are balanced to do less damage. For projectile weapons like a rocket launcher, it takes the missile some time to reach them, and they might move out of the way by the time it gets there. In return, they deal a lot of damage if the opponent fails at dodging. Whenever you shoot a rocket at an opponent, you are giving them the opportunity to make a mistake by not moving out of the way.
Tactically it seems like a poor choice to give your opponent the opportunity to not to take damage. All other things being equal, you'd rather they didn't have a say in the matter. Why ask a question ("Do you want to take 100 damage?") when you can make a statement ("Here, take 50 damage!")? But missile weapons provide a tactical advantage. They make large sections of the map dangerous, denying the opponent safe access to whatever items and safe cover locations are in that place. As a result, missile weapons give you control over where your opponent might go next.
I believe that no good player should take damage from the grenade launcher or plasma gun. These weapons exist solely for the purpose of controlling where your opponent can run. In particular, the plasma gun stream is so fast, constant, and deadly that it can literally herd the opponent into a position where another weapon can finish them off. If they don't want to be herded there, they are free to take 200 damage per second from the plasma shots. Missile weapons are more about controlling position than actually damaging the opponent.
Of course, none of that matters if the target can't dodge the incoming projectiles in the first place. The original Quake 3 bots were notoriously bad at this, obliviously walking directly into a path of fire. So I made sure to give BrainWorks bots a very effective missile dodging system. Just watching a BrainWorks bot play, you can shoot a straight stream of missiles at them and watch them sidestep out of the way. It's such a simple, obvious thing for a human that it might not even seem that special.
For the bot, it's not that simple. The bot needs to analyze the trajectory of all incoming missiles for possible impact and the bot needs to compute a safe direction to dodge from that. Sometimes there will be no safe areas, but some areas will be safer than others. And the final dodge direction needs to take into account the bot's intended final destination. If the bot only moves to the safest possible location, the attacker will simply herd the bot to a place that's even more dangerous. The bots selection of where to dodge also needs to eventually get them towards their goal location, albiet at a slower, safer pace.
Those are the requirements for the dodging system, and they are all challenging. Next post I'll explain in detail how BrainWorks solves this problem.
Showing posts with label weapons. Show all posts
Showing posts with label weapons. Show all posts
Monday, October 27, 2008
Monday, August 25, 2008
Sitting on the Fence
For roughly the past month, I've been interviewing at a few different places looking for a new job. I've felt overqualified at my current place of employment and really wanted some more challenging work. At the end of the process I had two offers to choose from, both of which were really similar and far superior to my current job. I suppose most people might decide based on some simple, simple heuristic like "highest salary", "most attractive coworkers", or "did I flip heads?"
But I'm a compulsive optimizer. Naturally I agonized for two weeks over which offer I should. I was hoping one offer would be clearly better than the other, but both the corporate cultures and salary packages were similar. I analyzed every angle I could think of, from the commute times to little things my interviewers had said. I called friends I knew and got as much inside information about the places. I made risk estimates for the companies based on their respective industries. Talk about overkill! My opinion changed on a daily basis, but after two weeks I finally made my final decision.
This is, of course, the exact opposite of what good AI should do.
In most systems where a computer must analyze some data and make a decision, there's a problem when two choices are very similar. Sometimes the system can get caught in an oscillation state where working on either choice makes the other one better. For example, a Quake 3 bot might decide to pick up armor, but the act of moving towards the armor makes it decide that picking up some health is a better choice. So the bot instead moves towards the health, and on the way decides the armor is better. The bot can end up in a situation of indecision where it picks up neither of the two items, and clearly this is the worst of the three choices.
Item pickup isn't the only situation where this occurs. Target selection and weapon selection can have the same problems. A bot can try to chase down one target but on the way decide it would rather aim at a different one and waste valuable time aiming at neither. Or in theory a bot can switch to one weapon and change its range based on the new choice, but by the time it gets in position it decides another weapon is useful. If you've never seen a BrainWorks bot do this, that's great! I've worked hard to remove these indecisions from the AI, but it's neigh impossible to make AI that works in all situations. There are two basic tactics you can use to solve indecision oscillations, each with their own costs.
Most of the time I give the scoring estimate a bonus of between 10% and 25% for keeping the same decision. In other words, the AI won't change its mind unless the new option is at least 25% better than the old. The higher this factor is, the fewer oscillations will occur. However, the risk is that an option that's genuinely 8% better will be missed, even if it wouldn't cause an indecision loop. Additionally, it's rare but still possible that even with a 25% factor, the bot can get stuck in indecision. This method is best used for situations where the estimated value of one option over another doesn't change that rapidly. This is how general item pickup oscillations are handled, as well as enemy selection.
When a small buffer isn't sufficient, the other option is to prevent the bot from changing its mind until it completes its selection, or at least for a reasonably long duration (such as half a minute). This is guaranteed to solve the problem. But there are two drawbacks. Not only will the bot be more likely to make suboptimal decisions, but it could get caught in a situation where it's very predictable. As such, it's best to apply this tactic only when absolutely necessary and ideally when the action can be completed quickly.
This method is used in item pickup for items the bot is very nearby. If a bot can pickup an item in less than one second, it immediately overrides all other item pickups and grabs it no matter how useful some other item may be. It turns out that even with a bonus factor for keeping the same item selection, bots could still get stuck in indecision loops when they were very close to an item of low value. That's because the estimated points per second is the ratio of two very small numbers, so the estimation has a large margin of error. No bonus factor could stop the bot from switching between the bad nearby item and the good item that was far away. The code forces the bot to spend half second to grab the nearby item, thereby preventing the loop from occurring.
Regarding my new job, I was leaning towards the place that offered slightly less money but seemed to have higher job satisfaction. In the end they decided to beat the salary offered by the other company, so it was a no-brainer to pick the job that has both higher pay and happier workers.
But I'm a compulsive optimizer. Naturally I agonized for two weeks over which offer I should. I was hoping one offer would be clearly better than the other, but both the corporate cultures and salary packages were similar. I analyzed every angle I could think of, from the commute times to little things my interviewers had said. I called friends I knew and got as much inside information about the places. I made risk estimates for the companies based on their respective industries. Talk about overkill! My opinion changed on a daily basis, but after two weeks I finally made my final decision.
This is, of course, the exact opposite of what good AI should do.
In most systems where a computer must analyze some data and make a decision, there's a problem when two choices are very similar. Sometimes the system can get caught in an oscillation state where working on either choice makes the other one better. For example, a Quake 3 bot might decide to pick up armor, but the act of moving towards the armor makes it decide that picking up some health is a better choice. So the bot instead moves towards the health, and on the way decides the armor is better. The bot can end up in a situation of indecision where it picks up neither of the two items, and clearly this is the worst of the three choices.
Item pickup isn't the only situation where this occurs. Target selection and weapon selection can have the same problems. A bot can try to chase down one target but on the way decide it would rather aim at a different one and waste valuable time aiming at neither. Or in theory a bot can switch to one weapon and change its range based on the new choice, but by the time it gets in position it decides another weapon is useful. If you've never seen a BrainWorks bot do this, that's great! I've worked hard to remove these indecisions from the AI, but it's neigh impossible to make AI that works in all situations. There are two basic tactics you can use to solve indecision oscillations, each with their own costs.
Most of the time I give the scoring estimate a bonus of between 10% and 25% for keeping the same decision. In other words, the AI won't change its mind unless the new option is at least 25% better than the old. The higher this factor is, the fewer oscillations will occur. However, the risk is that an option that's genuinely 8% better will be missed, even if it wouldn't cause an indecision loop. Additionally, it's rare but still possible that even with a 25% factor, the bot can get stuck in indecision. This method is best used for situations where the estimated value of one option over another doesn't change that rapidly. This is how general item pickup oscillations are handled, as well as enemy selection.
When a small buffer isn't sufficient, the other option is to prevent the bot from changing its mind until it completes its selection, or at least for a reasonably long duration (such as half a minute). This is guaranteed to solve the problem. But there are two drawbacks. Not only will the bot be more likely to make suboptimal decisions, but it could get caught in a situation where it's very predictable. As such, it's best to apply this tactic only when absolutely necessary and ideally when the action can be completed quickly.
This method is used in item pickup for items the bot is very nearby. If a bot can pickup an item in less than one second, it immediately overrides all other item pickups and grabs it no matter how useful some other item may be. It turns out that even with a bonus factor for keeping the same item selection, bots could still get stuck in indecision loops when they were very close to an item of low value. That's because the estimated points per second is the ratio of two very small numbers, so the estimation has a large margin of error. No bonus factor could stop the bot from switching between the bad nearby item and the good item that was far away. The code forces the bot to spend half second to grab the nearby item, thereby preventing the loop from occurring.
Regarding my new job, I was leaning towards the place that offered slightly less money but seemed to have higher job satisfaction. In the end they decided to beat the salary offered by the other company, so it was a no-brainer to pick the job that has both higher pay and happier workers.
Monday, August 11, 2008
Project Planning
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.
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.
Monday, July 21, 2008
Gaming The System
Typically, a game artificial intelligence developer views their job as creating an opponent that will entertain the player. There's nothing wrong with this view. After all, if the player isn't having fun, it doesn't matter what the AI does well. The most realistic play in the world doesn't mean a thing if the player doesn't enjoy playing against it. It's possible to make AI that plays like that, of course. If a human can play so well it frustrates their opponent, an AI can do that too. But is the problem the AI design or the game design? I'd argue the game design is at fault. In other words,
AI design is a counterpoint to game design.
Game design really has two parts to it: making the game fun and making the game challenging. Alternatively, you can think of this as making the game fun for the winners and making the game fun for the losers. If a game is too easy for you, then chances are your opponents are getting crushed and aren't having a good time. A good multiplayer game is one in which everyone enjoys it regardless of whether they win. And a good single player game is one where it's neither too hard nor to easy to win.
That means AI can be a valuable tool in the design feedback loop for a game. If the AI continually exploits a certain unsatisfying strategy, you can expect players will do the same, and the game should be changed. When the AI uses a variety of interesting strategies, that's a good sign your game design is solid.
In the design of BrainWorks, I came across a few instances of AI behavior that commented on the game design of Quake 3. For example, on any level with a reasonably accessible BFG, the bots will do everything in their power to grab and use the weapon. They might even camp BFG ammo just to make it harder for other people to use the gun. While it makes gameplay boring and predictable, they aren't necessarily doing the wrong thing. The AI determined that the BFG was 10 times better than the next best option and made it choices accordingly.
There's also the issue of the machinegun. You might notice that if there are a lot of players on a level, the bots will sometimes flat out skip weapon upgrades and just use the machinegun. This also isn't a mistake. When there are more players on the level, each player's life expectancy decreases. When the bot won't live that long anyway, there's no point in wasting time for a new weapon. The starting machinegun is only slightly worse damage and comes with a reasonable amount of ammunition.
In the case of the BFG, the weapon is obviously too powerful, but it's pretty clear that was the point. The machinegun is a different case though. Is it really too powerful or do players just start with too much ammo? Or maybe it's fine that this is a strategy when a level becomes overpopulated, and human players that waste too much time picking up weapons are just playing it the wrong way.
This is just opinion, but I believe the problem is the amount of damage the machinegun deals. The reason I think this is that there are actually has two damage values for machinegun bullets. Normally it's 7 damage per hit, but in teamplay mode it's only 5 damage. Apparently iD software determined that in a teamplayer game, the standard 7 damage was too much. And they're right, but the problem wasn't the weapon's use in team games. It's the weapon's initial power in games with lots of people, even large free-for-all games. What would be best is if the weapon just dealt 5 damage always. Then freshly respawned players had incentive to grab a new weapon as soon as possible. In game design, the simpler solution is usually the best choice.
On a related note, game design is also a hobby of mine. My wife and I have two upcoming board games that will hopefully be released end of this year or beginning of next. If people are interested in more columns explaining the thought process that goes into game design, I'm happy to write more on that subject. In my mind, designing a game is very similar to designing artificial intelligence.
AI design is a counterpoint to game design.
Game design really has two parts to it: making the game fun and making the game challenging. Alternatively, you can think of this as making the game fun for the winners and making the game fun for the losers. If a game is too easy for you, then chances are your opponents are getting crushed and aren't having a good time. A good multiplayer game is one in which everyone enjoys it regardless of whether they win. And a good single player game is one where it's neither too hard nor to easy to win.
That means AI can be a valuable tool in the design feedback loop for a game. If the AI continually exploits a certain unsatisfying strategy, you can expect players will do the same, and the game should be changed. When the AI uses a variety of interesting strategies, that's a good sign your game design is solid.
In the design of BrainWorks, I came across a few instances of AI behavior that commented on the game design of Quake 3. For example, on any level with a reasonably accessible BFG, the bots will do everything in their power to grab and use the weapon. They might even camp BFG ammo just to make it harder for other people to use the gun. While it makes gameplay boring and predictable, they aren't necessarily doing the wrong thing. The AI determined that the BFG was 10 times better than the next best option and made it choices accordingly.
There's also the issue of the machinegun. You might notice that if there are a lot of players on a level, the bots will sometimes flat out skip weapon upgrades and just use the machinegun. This also isn't a mistake. When there are more players on the level, each player's life expectancy decreases. When the bot won't live that long anyway, there's no point in wasting time for a new weapon. The starting machinegun is only slightly worse damage and comes with a reasonable amount of ammunition.
In the case of the BFG, the weapon is obviously too powerful, but it's pretty clear that was the point. The machinegun is a different case though. Is it really too powerful or do players just start with too much ammo? Or maybe it's fine that this is a strategy when a level becomes overpopulated, and human players that waste too much time picking up weapons are just playing it the wrong way.
This is just opinion, but I believe the problem is the amount of damage the machinegun deals. The reason I think this is that there are actually has two damage values for machinegun bullets. Normally it's 7 damage per hit, but in teamplay mode it's only 5 damage. Apparently iD software determined that in a teamplayer game, the standard 7 damage was too much. And they're right, but the problem wasn't the weapon's use in team games. It's the weapon's initial power in games with lots of people, even large free-for-all games. What would be best is if the weapon just dealt 5 damage always. Then freshly respawned players had incentive to grab a new weapon as soon as possible. In game design, the simpler solution is usually the best choice.
On a related note, game design is also a hobby of mine. My wife and I have two upcoming board games that will hopefully be released end of this year or beginning of next. If people are interested in more columns explaining the thought process that goes into game design, I'm happy to write more on that subject. In my mind, designing a game is very similar to designing artificial intelligence.
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, April 14, 2008
BrainWorks 1.0.1 Released
I've just released the latest update to BrainWorks implementing the fixes I talked about a few weeks ago. Basically there's a much more sophisticated algorithm for tracking and estimating how likely a bot is to shoot a weapon in a given situation. You can download them using the links on the right if you're interested in trying it out. Let me know what you think!
Related to this, I've been thinking about the question of when software is done. In some sense I still stand by my answer in The Attitude of the Knife, which is "when you say it is". The flip side is that as long as you still have ideas and commitment, there's always room for continual improvement. For a simple program meant to meet a specific purpose, such as reading your email, there comes a point where there isn't much more room for feature development. Artificial intelligence isn't like that though. To this day, researchers are still trying to figure out how different areas of the human brain work. And contrary to popular opinion, humans are not the end of evolution. The human brain itself continues to refine and advance itself through generations.
I believe the line dividing things that can be finished and things that cannot is the line of self reference. When the problem is best solved by something that can analyze and correct its own mistakes, a whole new field of issues apply. For an in depth explanation of why this is, I highly recommend the second of three books that influenced my mental framework for understanding the world. That book is Godel, Escher, Bach: The Eternal Golden Braid, and it is about the nature of intelligence. Very roughly paraphrased, the book talks about the mathematical theorem known as Godel's Incompleteness Theorem, which says that any system capable of describing itself can describe statements that are true but unprovable. Originally the theorem was discovered in attempts to work out some issues in Principia Mathematica, an attempt to derive all mathematical truths from first principles. However, the incompleteness theorem sheds unanticipated insights on the areas of philosophy and by extension the nature of thought and intelligence.
Viewed in the context of intelligence, you could conclude that there are things which an intelligent person would do, but there is no describable algorithm that could conclude what those things are. Perhaps this represents acts of creativity, intuition and insight. Or perhaps those things are describable, but other things are not.
Applied to Artificial Intelligence, it means that there are some aspects of AI that we cannot solve; we can only approximate. And there's always room for better approximations. This is the real that AI development can last forever. You're never really done. At least not until you say you are.
Related to this, I've been thinking about the question of when software is done. In some sense I still stand by my answer in The Attitude of the Knife, which is "when you say it is". The flip side is that as long as you still have ideas and commitment, there's always room for continual improvement. For a simple program meant to meet a specific purpose, such as reading your email, there comes a point where there isn't much more room for feature development. Artificial intelligence isn't like that though. To this day, researchers are still trying to figure out how different areas of the human brain work. And contrary to popular opinion, humans are not the end of evolution. The human brain itself continues to refine and advance itself through generations.
I believe the line dividing things that can be finished and things that cannot is the line of self reference. When the problem is best solved by something that can analyze and correct its own mistakes, a whole new field of issues apply. For an in depth explanation of why this is, I highly recommend the second of three books that influenced my mental framework for understanding the world. That book is Godel, Escher, Bach: The Eternal Golden Braid, and it is about the nature of intelligence. Very roughly paraphrased, the book talks about the mathematical theorem known as Godel's Incompleteness Theorem, which says that any system capable of describing itself can describe statements that are true but unprovable. Originally the theorem was discovered in attempts to work out some issues in Principia Mathematica, an attempt to derive all mathematical truths from first principles. However, the incompleteness theorem sheds unanticipated insights on the areas of philosophy and by extension the nature of thought and intelligence.
Viewed in the context of intelligence, you could conclude that there are things which an intelligent person would do, but there is no describable algorithm that could conclude what those things are. Perhaps this represents acts of creativity, intuition and insight. Or perhaps those things are describable, but other things are not.
Applied to Artificial Intelligence, it means that there are some aspects of AI that we cannot solve; we can only approximate. And there's always room for better approximations. This is the real that AI development can last forever. You're never really done. At least not until you say you are.
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.
Monday, February 25, 2008
At the Heart of it All
As I outlined last week, the item pickup problem in First Person Shooter games is very difficult to solve, and that goes for humans as well. How do the truly advanced players approach this problem? At the heart of it all is one central question:
How will this benefit me?
If you want to know whether to pickup item A or B, you first must know how much item A benefits you, and how much it costs (in additional time to get the item). BrainWorks solves this problem using a customized resource prediction model, handled by ai_resource.c. Be warned, this code is not for the feign of heart. It's gratuitously well commented and documented, but there are so many bits and pieces it's very hard to get your head around everything at once. Think of it like opening the hood of your car, removing the engine block, and taking everything down to the nuts and bolts. Very interesting, but good luck assembling it into a working vehicle.
First, the AI's resource engine must encode the player's current state. This is handled by the resource_state_t structure (defined in ai_main.h). In brief, that information is:
Determining how many points a given resource state is worth is significantly more complicated. Why is that? What other information does the bot need to estimate the points it would gain if it had this set of items? In short, it needs information about possible encounters with enemies:
The three damage values should be independent of any changes to the resource states. The amount of damage a weapon deals depends on the bot's accuracy-- getting more ammo will let the bot deal that damage longer, but it won't ever make one weapon deal more damage per second than another. As a result, the bot sorts every possible weapon it could use in a priority list at the very start of prediction. The list might read something like, "Use the plasma gun until out of ammo, then the rocket launcher, then the shotgun, then ..." Now that might not be what the bot actually does when it gets in combat, but it uses this as a rough estimate of what might happen.
Naturally the estimated damage each weapon will deal is computed from the bot's historical data of previous weapon use. If in the past the bot had 30% machinegun accuracy and fired 90% of the time the machinegun was loaded, the machinegun's effective damage rate is 27% of it's maximum possible damage rate.
So when the bot needs to predict 20 seconds of time, it might say, "Well I'll get this many points from firing my rocket launcher for 8 seconds, until it's out of ammo. Then the next weapon is a railgun, which I shoot for the remaining 12 seconds and get this many extra points." There would be 2 distinct calculations in that situation. The code uses a similar system for powerups wearing off. In that example, if the bot had a quad damage that wore off after 15 seconds, it would break the time into three segments (0 to 8, 8 to 15, 15 to 20).
Of course this is all well and good if the bot survives, but what happens if the bot predicts its own death? Surely there must be a penalty if the bot needs health but considers options other than getting it. When the bot thinks its health will reach zero, the resource prediction engine stops giving points, and the bot takes a (1 / opponents) point penalty, since getting killed gives one opponent a point.
All that work just to figure out how many points the bot will gain, not even to select the best item for pickup! Next week I'll explain how exactly the item pickup algorithm uses this resource prediction engine to determine the best item to pickup.
How will this benefit me?
If you want to know whether to pickup item A or B, you first must know how much item A benefits you, and how much it costs (in additional time to get the item). BrainWorks solves this problem using a customized resource prediction model, handled by ai_resource.c. Be warned, this code is not for the feign of heart. It's gratuitously well commented and documented, but there are so many bits and pieces it's very hard to get your head around everything at once. Think of it like opening the hood of your car, removing the engine block, and taking everything down to the nuts and bolts. Very interesting, but good luck assembling it into a working vehicle.
First, the AI's resource engine must encode the player's current state. This is handled by the resource_state_t structure (defined in ai_main.h). In brief, that information is:
- Health
- Armor
- Weapons
- Ammo per weapon
- Powerups (eg. Haste, Quad Damage)
- Activatable items (eg. Portable Teleporter)
Determining how many points a given resource state is worth is significantly more complicated. Why is that? What other information does the bot need to estimate the points it would gain if it had this set of items? In short, it needs information about possible encounters with enemies:
- Chance of encountering an enemy near the bot
- How much damage the bot will deal with each weapon
- How much damage is required to score a kill
- How much damage an attacking enemy will deal to the bot
The three damage values should be independent of any changes to the resource states. The amount of damage a weapon deals depends on the bot's accuracy-- getting more ammo will let the bot deal that damage longer, but it won't ever make one weapon deal more damage per second than another. As a result, the bot sorts every possible weapon it could use in a priority list at the very start of prediction. The list might read something like, "Use the plasma gun until out of ammo, then the rocket launcher, then the shotgun, then ..." Now that might not be what the bot actually does when it gets in combat, but it uses this as a rough estimate of what might happen.
Naturally the estimated damage each weapon will deal is computed from the bot's historical data of previous weapon use. If in the past the bot had 30% machinegun accuracy and fired 90% of the time the machinegun was loaded, the machinegun's effective damage rate is 27% of it's maximum possible damage rate.
So when the bot needs to predict 20 seconds of time, it might say, "Well I'll get this many points from firing my rocket launcher for 8 seconds, until it's out of ammo. Then the next weapon is a railgun, which I shoot for the remaining 12 seconds and get this many extra points." There would be 2 distinct calculations in that situation. The code uses a similar system for powerups wearing off. In that example, if the bot had a quad damage that wore off after 15 seconds, it would break the time into three segments (0 to 8, 8 to 15, 15 to 20).
Of course this is all well and good if the bot survives, but what happens if the bot predicts its own death? Surely there must be a penalty if the bot needs health but considers options other than getting it. When the bot thinks its health will reach zero, the resource prediction engine stops giving points, and the bot takes a (1 / opponents) point penalty, since getting killed gives one opponent a point.
All that work just to figure out how many points the bot will gain, not even to select the best item for pickup! Next week I'll explain how exactly the item pickup algorithm uses this resource prediction engine to determine the best item to pickup.
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.
Wednesday, February 6, 2008
The Attitude of the Knife
When I was 15, I read one of the three books that shaped my early attitudes, perceptions, and thought process. That book was Frank Herbert's Dune. The book is about an extremely gifted 15 year old who rises to political power because of his talent and training. But he has trouble finding people who relate to him as a person because of how special he is. As another gifted 15 year old, the entire story resonated with me, and many sections of the book left their mark on my memory. My favorite quote isn't the popular "Fear is the mind killer..." quote, however. It's about finishing things:
Arrakis teaches the attitude of the knife--chopping what's off what's incomplete and saying: "Now, it's complete because it's ended here."
The attitude of the knife is an attitude of firm boundaries. It is the decision of royal fiat, the parent's "because I said so". The attitude of the knife is the act of will that sacrifices short term opportunities for long term gain by ensuring that things never grow beyond the size of usefulness.
Once you've embraced the attitude of the knife, you have significantly more peace in life. If you stain your favorite shirt, you might be able to wash the stain out, but you'll be stressed until you know one way or the other. If you accidentally rip that shirt in half, there's nothing you can do-- that's the end of the shirt. Certainly you'd rather have the shirt intact (and unstained) than not, but that's no longer an option. The shirt has met its end and your only option is to throw it out. The attitude of the knife reduces many choices to just one, even if it's not the "best" one. It is the recognition of when a problem is not solvable, at least by you, despite being a real problem.
You might be wondering what this has to do with writing Artificial Intelligence. One of the bigger problems in software development is feature creep, the desire to add "just one more feature" or extend the usefulness of an existing feature. But things can easily grow out of control, beyond the ability of the project's developers. Often the features become so numerous that it's difficult for users to do what they want to do. All the features you don't care about get in the way. (Microsoft Office and Window's Vista, I'm looking at you.)
The attitude of the knife puts an end to feature creep. It says, "Sorry, that problem is out of my jurisdiction. I understand that's a real problem and you have to accept that it will continue to be a problem." Because Artificial Intelligence is so complicated, there's an awful lot of problems and it's very easy for a project to grow out of maintainability. You need to the attitude of the knife to write AI, or you'll never finish.
When I first started BrainWorks, I decided on two strict boundaries. First, every piece of source code has to be run on the game server alone, only running when the server requests AI processing. No changes to non-AI parts of the server were allowed. Second, no modifications to the core game engine were allowed either. The core engine that ships with Quake 3 runs the most complicated AI algorithms, such as navigation, motion prediction, and item pickup. If I found issues in the engine, I was allowed to write my own version but I could not modify the engine, even to fix bugs I found.
As fate would have it, all of the core engine algorithms for AI were dysfunctional. I did end up rewriting most of them-- weapon selection, item pickup, and motion prediction were all rewritten from scratch. But the one unsolvable problem was navigation. The core engine doesn't do a good job of navigating anything but a flat, two dimensional map. What's worse is the core engine doesn't even give the AI code enough map information for the AI to try a better job of making navigation decisions. The problem simply cannot be solved given the constraints of the system.
That's a real problem, but thankfully it wasn't my problem. There were enough other issues to tackle in writing BrainWorks. Many times it was a relief to find a bug that could immediately be ignored. Not because it wasn't a problem, but because nothing could be done about it anyway. And to be honest, most of the time the navigation decisions are actually correct. It only messes up in certain areas of certain levels. On the other hand, the core engine's item pickup and weapon selection decisions were universally wrong.
For those of you curious what two other books formed my life attitude, they are Godel, Escher, Bach: An Eternal Golden Braid and the Christian Bible. While I'm no longer a Christian, I've still taken to heart the positive humanitarian parts of the Bible. And I've not forgotten my promise to explain why I'm no longer a Christian and what part Artificial Intelligence played in that story.
Arrakis teaches the attitude of the knife--chopping what's off what's incomplete and saying: "Now, it's complete because it's ended here."
The attitude of the knife is an attitude of firm boundaries. It is the decision of royal fiat, the parent's "because I said so". The attitude of the knife is the act of will that sacrifices short term opportunities for long term gain by ensuring that things never grow beyond the size of usefulness.
Once you've embraced the attitude of the knife, you have significantly more peace in life. If you stain your favorite shirt, you might be able to wash the stain out, but you'll be stressed until you know one way or the other. If you accidentally rip that shirt in half, there's nothing you can do-- that's the end of the shirt. Certainly you'd rather have the shirt intact (and unstained) than not, but that's no longer an option. The shirt has met its end and your only option is to throw it out. The attitude of the knife reduces many choices to just one, even if it's not the "best" one. It is the recognition of when a problem is not solvable, at least by you, despite being a real problem.
You might be wondering what this has to do with writing Artificial Intelligence. One of the bigger problems in software development is feature creep, the desire to add "just one more feature" or extend the usefulness of an existing feature. But things can easily grow out of control, beyond the ability of the project's developers. Often the features become so numerous that it's difficult for users to do what they want to do. All the features you don't care about get in the way. (Microsoft Office and Window's Vista, I'm looking at you.)
The attitude of the knife puts an end to feature creep. It says, "Sorry, that problem is out of my jurisdiction. I understand that's a real problem and you have to accept that it will continue to be a problem." Because Artificial Intelligence is so complicated, there's an awful lot of problems and it's very easy for a project to grow out of maintainability. You need to the attitude of the knife to write AI, or you'll never finish.
When I first started BrainWorks, I decided on two strict boundaries. First, every piece of source code has to be run on the game server alone, only running when the server requests AI processing. No changes to non-AI parts of the server were allowed. Second, no modifications to the core game engine were allowed either. The core engine that ships with Quake 3 runs the most complicated AI algorithms, such as navigation, motion prediction, and item pickup. If I found issues in the engine, I was allowed to write my own version but I could not modify the engine, even to fix bugs I found.
As fate would have it, all of the core engine algorithms for AI were dysfunctional. I did end up rewriting most of them-- weapon selection, item pickup, and motion prediction were all rewritten from scratch. But the one unsolvable problem was navigation. The core engine doesn't do a good job of navigating anything but a flat, two dimensional map. What's worse is the core engine doesn't even give the AI code enough map information for the AI to try a better job of making navigation decisions. The problem simply cannot be solved given the constraints of the system.
That's a real problem, but thankfully it wasn't my problem. There were enough other issues to tackle in writing BrainWorks. Many times it was a relief to find a bug that could immediately be ignored. Not because it wasn't a problem, but because nothing could be done about it anyway. And to be honest, most of the time the navigation decisions are actually correct. It only messes up in certain areas of certain levels. On the other hand, the core engine's item pickup and weapon selection decisions were universally wrong.
For those of you curious what two other books formed my life attitude, they are Godel, Escher, Bach: An Eternal Golden Braid and the Christian Bible. While I'm no longer a Christian, I've still taken to heart the positive humanitarian parts of the Bible. And I've not forgotten my promise to explain why I'm no longer a Christian and what part Artificial Intelligence played in that story.
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)