Having written twice about the dangers of believing everything you are told, I'd like to give some face time to the opposing argument:
Ignorance is bliss.
It's all well and good to say, "You should understand things, not just follow blindly." But to be pragmatic, there is only one time this is a serious improvement: when the blind belief is wrong. What about the times that blind belief is right? Humans survived for centuries without understanding how gravity truly worked and that didn't stop them from creating some awesome things. They were even able to use the fact that "things fall towards the ground" to great effect, such as building water clocks, without ever learning Kepler's laws of motion.
Even if someone did want to totally understand the world today, it wouldn't be possible. There is such a vast corpus of information that learning even 1% of it is literally impossible in the span of a human life. Mathematicians who are experts in their field rarely have the chance to keep up on other branches of mathematics, to say nothing of physics, chemistry, or medicine.
The fact of the matter is that most of the information we've been told is correct. If I get a bus that says "Downtown" as its destination, it really is going there. The driver could take it anywhere but I'm very certain that the destination is downtown. When I order a meal at a restaurant, I take it for granted that the cook can actually make the things on the menu and that I'll be served food that's reasonable close to the description provided. The waitress serves me food assuming that I will pay the price listed. I suspect that less than 1 in 10,000 people really understands what a computer does when you turn it on, but hundreds of millions of people use a computer every day. Understanding is a luxury, not a necessity.
Like it or not, our lives as humans are anchored in faith, not reason and understanding, and this is the cornerstone of the religion well all share: Causality. If we do something ten times in a row and got the same result, we expect that the eleventh time will produce the same result. And it does, even though we rarely know why. Understanding everything is impossible, and the whole purpose of culture is to provide structure so that everyone can use the discoveries other people made.
If that's the case, why bother thinking about anything at all? Why not let someone else do your thinking for you? The primary purpose of education isn't to give people information, but to teach them how to think. And most importantly, to teach them when to think. Thinking is really important in uncharted waters. In any situation that doesn't match your typical life experience, thinking will give you a much better idea of what to do than trying something at random.
Unsurprisingly, the same problem comes up in artificial intelligence. There's only so much processor time to go around. So if seven bots all need the same piece of information and they will all come to roughly the same conclusion, it's much faster to do a rough computation once and let them all use those results. This leads to an information dichotomy, where there's general "AI Information" and "Bot specific information". Each bot has its own specific information, but shares from the same pool of general information. In BrainWorks, all bots share things like physics predictions and the basic estimation of an item's value. If a player has jumped off a ledge, there's no reason for every bot to figure out when that player will hit the bottom. It's much faster to work it out once (the first time a bot needs to know) and if another bot needs to know, it can share the result.
These are the kinds of optimizations that can create massive speed improvements, making an otherwise difficult computation fast. If you think about it, it's not that different from one person researching the effects of some new medicine and then sharing the results with the entire world.
Showing posts with label historical data. Show all posts
Showing posts with label historical data. Show all posts
Monday, November 17, 2008
Monday, July 7, 2008
A Simple Solution
As the story ended last week, I had uncovered a very strange bug in BrainWorks. There was up to a 10% accuracy difference between the first bot added to the game and the last bot. No one guessed the correct cause, but this one from cyrri was the closest:
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
bots occupy client slots in the same order as they are added.This actually does happen, but it only accounts for a 1% to 2% accuracy change between the first and last bots. Also, this value increases as bot accuracy increases, since it's more likely that two bots will be lined up for a good shot at the same time.
in the very rare cases of two clients killing a third one simultaneously, it is allways the one with the lower slot id that gets the frag, becuase his usercommands are processed first. the other one gets a missed shot.
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
Monday, April 7, 2008
Getting it "Just Right"
There's not much difference between driving 55 and 56. Unless of course the speed limit is 55, in which case that small amount of speed could make you get a speeding ticket. Standard outside temperatures average between 0 and 100 degrees Fahrenheit, but people easily notice the difference between 68 and 72 degrees. And yet for other measurements in our lives, small changes are completely unnoticed. A car with a full gas tank drives just as well as a car with a quarter tank left-- you only notice the problem when the last drop of gas is gone.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.
Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.
A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.
And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.
Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).
All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.
For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.
At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.
Monday, March 24, 2008
My Biggest Programming Fear
I have encountered some very strange bugs in my programming career. And most of them have been in BrainWorks, being by far the most complicated piece of software I've ever written. One of the worst involved a build that only crashed when run on someone else's system. On my system it was fine, but it would crash on my friend's system. It wouldn't crash right away, mind you. Sometimes it would take up to two minutes, so even testing to see if the bug was fixed took time. Oh, and his computer was in London while mine was in Los Angeles. Not exactly the easiest problem to solve.
I solved it by compiling in debug flags that would turn on or off entire sections of code and then had him run it. "Okay, load bots but turn off all movement, scanning, and aiming. Does it crash now? What about when Item Pickup is turned off?" Through the course of four builds that gradually narrowed in on particular blocks of code, we eventually found the offending bug.
(If you're curious what caused it, an uninitialized value was improperly being treated as an address, crashing the program whenever it was accessed. Because his machine's memory layout was different from mine, it would occasionally access invalid memory and the operating system would kill the program. For whatever reason, the uninitialized values that showed up on my system always happened to refer to memory BrainWorks was allowed to access, so it never crashed for me.)
It took about eight hours to do, but once you've solved a bug like that, you feel cabable of tackling any bug. Bugs bother me, but they don't frighten me. Know what my biggest programming fear is?
0 total errors
Any time I've spent over two hours working on a particular feature and attempt to rebuild the code base, I expect to see at least one error. I'm a good programmer, but that doesn't mean I'm perfect. I'm a good programmer because I know I'm not perfect. Good programmers assume they will make mistakes-- that's why they add all those safety error checks. If some other piece of code does the wrong thing, their error checks will contain it.
Last week I spent four hours tracking down the issues with bots overvaluing the shotgun. The problem was that the estimation of fire frequency wasn't precise enough. I spent another three hours analyzing the similarities between estimating the chance of hitting with a weapon (hits divided by attacks) and the chance of firing a weapon (attacks divided by potential attacks) and designing functionality that merged the two concepts. Actually writing the code took another 2 hours. Nine hours total including changes that could totally break the AI's ability to even attack, and here I am looking at the results from my very first recompile:
0 total errors
I haven't run it yet, but I'm terrified. Zero errors on the first try? That never happens. That's not even supposed to happen. Odds are the code I wrote has an error somewhere; I just don't know where.
At any rate, I plan to test it this upcoming week and get a new release out this weekend. Hope you enjoy it.
I solved it by compiling in debug flags that would turn on or off entire sections of code and then had him run it. "Okay, load bots but turn off all movement, scanning, and aiming. Does it crash now? What about when Item Pickup is turned off?" Through the course of four builds that gradually narrowed in on particular blocks of code, we eventually found the offending bug.
(If you're curious what caused it, an uninitialized value was improperly being treated as an address, crashing the program whenever it was accessed. Because his machine's memory layout was different from mine, it would occasionally access invalid memory and the operating system would kill the program. For whatever reason, the uninitialized values that showed up on my system always happened to refer to memory BrainWorks was allowed to access, so it never crashed for me.)
It took about eight hours to do, but once you've solved a bug like that, you feel cabable of tackling any bug. Bugs bother me, but they don't frighten me. Know what my biggest programming fear is?
0 total errors
Any time I've spent over two hours working on a particular feature and attempt to rebuild the code base, I expect to see at least one error. I'm a good programmer, but that doesn't mean I'm perfect. I'm a good programmer because I know I'm not perfect. Good programmers assume they will make mistakes-- that's why they add all those safety error checks. If some other piece of code does the wrong thing, their error checks will contain it.
Last week I spent four hours tracking down the issues with bots overvaluing the shotgun. The problem was that the estimation of fire frequency wasn't precise enough. I spent another three hours analyzing the similarities between estimating the chance of hitting with a weapon (hits divided by attacks) and the chance of firing a weapon (attacks divided by potential attacks) and designing functionality that merged the two concepts. Actually writing the code took another 2 hours. Nine hours total including changes that could totally break the AI's ability to even attack, and here I am looking at the results from my very first recompile:
0 total errors
I haven't run it yet, but I'm terrified. Zero errors on the first try? That never happens. That's not even supposed to happen. Odds are the code I wrote has an error somewhere; I just don't know where.
At any rate, I plan to test it this upcoming week and get a new release out this weekend. Hope you enjoy it.
Monday, March 17, 2008
Release Retrospective
While people have been overall pleased and impressed with the BrainWorks release, I've received one common bit of negative feedback. Many people have said the bots use the shotgun too often, especially in situations where it's flat out the wrong weapon to use. Now I don't have the luxury other people have of saying, "that's not a bug, that's a feature!" Or more commonly, "that's working as intended." BrainWorks is intended to feel realistic. If many people say a portion of it doesn't feel realistic, they are right. I have no grounds on which to disagree. There really is a bug in the code because you say there is.
Of course, if you've ever been told quite literally, "this thing doesn't feel right, so go fix it," you know how challenging of a request that is. One downside of fundamentally basing the BrainWorks AI on causality is that debugging is extremely difficult. There's no magic number that tells the bot how often to use the shotgun. Instead, the bot analyzes its situation and incorrectly decides the shotgun is the right weapon to use. To solve this problem, I need to walk through the entire analysis and see how it reaches that conclusion. To make matters worse, the bots don't always choose to use the shotgun. And there are surely situations where the bot correctly chooses the shotgun. It's very hard to isolate the situations where the mistake as made and then narrow down why that mistake occurred.
My solution was to write some debug code that outputted all the data the bot used at each step of weapon selection analysis, starting from accuracy and fire rate data and ending with its final valuation of how quickly a given weapon would score a kill. I had it output this data for all weapons available and just stared at the numbers, checking if each data point was an accurate value of the concept representing it. I found three key contributing issues, two of which are solvable.
#1) The estimation of weapon fire rate was incorrectly bounded
Knowing how frequently the bot will fire a weapon is crucial to determining the actual damage rate of the weapon. If a bot spends 3 seconds aiming at a target and only fires for 1 of those seconds, it will do one third the damage as a bot that spends all 3 seconds aiming-- provided it's always lined up for a good shot. The bot tracks how often it actually fires the weapon, but I gave this value a lower bound of 50%. In other words, the bot assumes it will spend at least 50% of its time firing with the weapon, possibly more.
I added this assumption to deal with another problem. Bots would switch to a weapon they had never fired before, not have a perfectly lined up shot, and think... "I've spent 0 seconds firing and 100 milliseconds aiming, so I spend 0% of my time attacking. This weapon is terrible. I'm going to use something else." And they would never try out the weapon to see that they could in fact make shots with it. One problem with relying on historical data is wide variance in the initial data sets. I ran some tests with most of the weapons and found the fire rates were in the 60% to 80% range, so 50% seemed like a good bound.
The problem was that the shotgun only had a fire rate of between 30% and 50%, meaning it's hard to line up good shots with the weapon. There were situations where the bot would think it fired 50% of the time when in reality it had only attacked 30% of the time, which inflated the estimated value of the shotgun by a solid 60%. (160% of 30 is 50.) So it's no wonder they thought the weapon was good. Lowering the minimum bound to 30% had other problems though. When that happened, sometimes bots would stop using genuinely good weapons like the rocket launcher. That's a sign that a lower bound is not the correct way to solve this problem.
Related to this is the second issue:
#2) The estimation of weapon fire rate doesn't take location into account
If you're wondering why the shotgun is generally a bad weapon, it's because it's so situational. At point blank range, it can do more damage than the railgun in two thirds the time. But the spread on the weapon makes its value decrease rapidly at medium and long range. There are situations where the shotgun is good, but not many of them. In contrast, weapons like the railgun are consistently good in a wider variety of situations.
This means that a bot might shoot more often with the shotgun at point blank range than at long range because the shots are easier to line up. If the bot had a 40% fire rate with the shotgun, that might be a 50% rate when close to the enemy but only 30% when far away. Similarly, it's easy to line up shots with the rocket launcher when the target is below you, since you can just shoot at the floor. If the target is above you, you need a direct hit, and that's very hard.
If the bot knew how the firing rate could change depending on the combat situation, it would have a much better understanding of whether a weapon is a good choice against the current target. Unfortunately, the code only tracks a single firing rate for each weapon. The concept of where the enemy was located doesn't factor into the data, and that's a real issue.
The drawback of tracking fire rate data across each of the bot's 12 combat zones is that it will take much longer to get good estimates on actual fire rates. If there were problems before with bots accumulating fire rate data into one data "bucket", now that there are 12 "buckets", it will take 12 times longer before the data stabilizes. In other words, the issue that the 50% minimum fire rate was trying to address has now gotten 12 times worse.
I'm still thinking about the best way to solve this problem, but I'm leaning towards seeding the data with some reasonable estimates of how often the weapons really should be firing. If there's enough seed data, it should encourage the bot to act reasonably until it has enough of it's own data to make conclusions. That just leaves one more issue:
#3) Bots do not take into account how a good choice now could be bad later
The major drawback a situational weapon like the shotgun has is that when you use it, you give your opponent some control. They have the power to make your weapon worse just by backing up. While this is a concern for all weapons, the more situational a weapon is, the worse it is when your opponent exploits your weapon's weakness. In other words, the shotgun isn't just bad because it's only useful at close range. It's bad because your opponent can choose to be at medium or far range after you spend the time to pull out the weapon.
This is unfortunately a much harder problem to solve, since it has to do with the local level geometry. If your opponent has no escape routes, the shotgun is still excellent in close quarters. I haven't thought about this problem very much, but my intuition says that solving it in BrainWorks is well beyond the scope of the project. You might be able to analyze past reactions opponents had to your weapon choices, but it's not clear how good this data would be, how it would affect the bot's choices, and if this problem is even large enough that it needs such a sophisticated solution.
At any rate, I apologize if this post is a bit more technical than normal, but that's the nature of the work. I'm very interested to hear your ideas for how to tackle these problems. I plan on thinking through possible solutions over this upcoming week and writing the fixes next weekend. If you have thoughts on this, I'd love to hear them.
Of course, if you've ever been told quite literally, "this thing doesn't feel right, so go fix it," you know how challenging of a request that is. One downside of fundamentally basing the BrainWorks AI on causality is that debugging is extremely difficult. There's no magic number that tells the bot how often to use the shotgun. Instead, the bot analyzes its situation and incorrectly decides the shotgun is the right weapon to use. To solve this problem, I need to walk through the entire analysis and see how it reaches that conclusion. To make matters worse, the bots don't always choose to use the shotgun. And there are surely situations where the bot correctly chooses the shotgun. It's very hard to isolate the situations where the mistake as made and then narrow down why that mistake occurred.
My solution was to write some debug code that outputted all the data the bot used at each step of weapon selection analysis, starting from accuracy and fire rate data and ending with its final valuation of how quickly a given weapon would score a kill. I had it output this data for all weapons available and just stared at the numbers, checking if each data point was an accurate value of the concept representing it. I found three key contributing issues, two of which are solvable.
#1) The estimation of weapon fire rate was incorrectly bounded
Knowing how frequently the bot will fire a weapon is crucial to determining the actual damage rate of the weapon. If a bot spends 3 seconds aiming at a target and only fires for 1 of those seconds, it will do one third the damage as a bot that spends all 3 seconds aiming-- provided it's always lined up for a good shot. The bot tracks how often it actually fires the weapon, but I gave this value a lower bound of 50%. In other words, the bot assumes it will spend at least 50% of its time firing with the weapon, possibly more.
I added this assumption to deal with another problem. Bots would switch to a weapon they had never fired before, not have a perfectly lined up shot, and think... "I've spent 0 seconds firing and 100 milliseconds aiming, so I spend 0% of my time attacking. This weapon is terrible. I'm going to use something else." And they would never try out the weapon to see that they could in fact make shots with it. One problem with relying on historical data is wide variance in the initial data sets. I ran some tests with most of the weapons and found the fire rates were in the 60% to 80% range, so 50% seemed like a good bound.
The problem was that the shotgun only had a fire rate of between 30% and 50%, meaning it's hard to line up good shots with the weapon. There were situations where the bot would think it fired 50% of the time when in reality it had only attacked 30% of the time, which inflated the estimated value of the shotgun by a solid 60%. (160% of 30 is 50.) So it's no wonder they thought the weapon was good. Lowering the minimum bound to 30% had other problems though. When that happened, sometimes bots would stop using genuinely good weapons like the rocket launcher. That's a sign that a lower bound is not the correct way to solve this problem.
Related to this is the second issue:
#2) The estimation of weapon fire rate doesn't take location into account
If you're wondering why the shotgun is generally a bad weapon, it's because it's so situational. At point blank range, it can do more damage than the railgun in two thirds the time. But the spread on the weapon makes its value decrease rapidly at medium and long range. There are situations where the shotgun is good, but not many of them. In contrast, weapons like the railgun are consistently good in a wider variety of situations.
This means that a bot might shoot more often with the shotgun at point blank range than at long range because the shots are easier to line up. If the bot had a 40% fire rate with the shotgun, that might be a 50% rate when close to the enemy but only 30% when far away. Similarly, it's easy to line up shots with the rocket launcher when the target is below you, since you can just shoot at the floor. If the target is above you, you need a direct hit, and that's very hard.
If the bot knew how the firing rate could change depending on the combat situation, it would have a much better understanding of whether a weapon is a good choice against the current target. Unfortunately, the code only tracks a single firing rate for each weapon. The concept of where the enemy was located doesn't factor into the data, and that's a real issue.
The drawback of tracking fire rate data across each of the bot's 12 combat zones is that it will take much longer to get good estimates on actual fire rates. If there were problems before with bots accumulating fire rate data into one data "bucket", now that there are 12 "buckets", it will take 12 times longer before the data stabilizes. In other words, the issue that the 50% minimum fire rate was trying to address has now gotten 12 times worse.
I'm still thinking about the best way to solve this problem, but I'm leaning towards seeding the data with some reasonable estimates of how often the weapons really should be firing. If there's enough seed data, it should encourage the bot to act reasonably until it has enough of it's own data to make conclusions. That just leaves one more issue:
#3) Bots do not take into account how a good choice now could be bad later
The major drawback a situational weapon like the shotgun has is that when you use it, you give your opponent some control. They have the power to make your weapon worse just by backing up. While this is a concern for all weapons, the more situational a weapon is, the worse it is when your opponent exploits your weapon's weakness. In other words, the shotgun isn't just bad because it's only useful at close range. It's bad because your opponent can choose to be at medium or far range after you spend the time to pull out the weapon.
This is unfortunately a much harder problem to solve, since it has to do with the local level geometry. If your opponent has no escape routes, the shotgun is still excellent in close quarters. I haven't thought about this problem very much, but my intuition says that solving it in BrainWorks is well beyond the scope of the project. You might be able to analyze past reactions opponents had to your weapon choices, but it's not clear how good this data would be, how it would affect the bot's choices, and if this problem is even large enough that it needs such a sophisticated solution.
At any rate, I apologize if this post is a bit more technical than normal, but that's the nature of the work. I'm very interested to hear your ideas for how to tackle these problems. I plan on thinking through possible solutions over this upcoming week and writing the fixes next weekend. If you have thoughts on this, I'd love to hear them.
Monday, March 10, 2008
Turn Left at the Quad Damage
Have you ever gotten directions that included phrases like, "When you see the giant viking statue, go straight and curve left" or "If you pass a third Starbucks, you've gone too far"? People don't always give directions based on street names; sometimes the street names are largely irrelevant. Here in New England, if the street sign is even posted at all, it might not be readable until too late. Directions like "turn left at the Rite-Way Mart" are often easier to follow than "turn left at old route 293".
Believe it or not, bots have the same problem. We might conceptualize a level as rooms, hallways, and open areas, but these places have no names. Humans generally name these areas after a recognizable landmark. In Quake 3, that usually means items. You'd never tell a teammate, "I'm at (540, -973, 108)", which is how the computer records your position. But you would say, "I'm near the rocket launcher".
One requirement of item pickup that I glossed over in a previous post was this: Bots need to know how likely they are to encounter an enemy in a general area. That implies bots need a concept of what an area is. They need to think of enemies being "near the rocket launcher" not "at (540, -973, 108)".
Bots need to think of enemy location in human terms, not computer terms.
The obvious method of approaching this problem is to divide the level into regions, with each region being defined by one item. Technically each region is "the area of space that is closer to this item than any other item". Once you have the level conceptually divided into "near the red armor" and "near the plasma gun", whenever the bot sees an enemy it can say, "Ah, that player is near the red armor, not the plasma gun. I'm more likely to find enemies if I head for the red armor as well." Now whether or not it wants to enemies is a different question, one answered by item pickup. But at least it can track meaningful data about what other players on the level are likely to do.
However, just because it's possible to find out what item a player is nearest doesn't mean it's particularly fast or easy for the computer to determine that. The AI obviously can't spend half a second to calculate data it needs to save 10 times a second. It's okay to spend a bunch of time when the level loads to calculate the best set of regions, but once these calculations are done, bots need to do the location to region calculation very quickly.
I researched a number of different options, but eventually settled on the octree, briefly mentioned in a previous post. Conceptually an octree is a way to layout some number of points in 3-space. In BrainWorks, the item region octree contains the location of all items on the level. Rather than rewrite what has already been written on the subject, I recommend reading the wikipedia article on quadtrees (the two dimensional equivalent of octrees).
For the 99% of readers who don't care how to implement an octree, I'll just say that a well balanced octree will generally let you find which item is closest to any input location very quickly. The run time is O(log8 N) time, where N is the number of items on the level. That means that finding the nearest item on a level with 64 items will take twice as long as a level with 8 items, and a level with 512 items will take 3 times as long as a level with 8 items. Since even the largest levels rarely have more than 100 items, this calculation is really fast, and that in turn frees up more processor time to think about different AI problems. The bot makes a richer impression to the human playing the game and hopefully the player has more fun too. Sometimes making a game fun to play involves implementing mind-numbingly boring data structures, but the fun just wouldn't be there if they were missing.
Believe it or not, bots have the same problem. We might conceptualize a level as rooms, hallways, and open areas, but these places have no names. Humans generally name these areas after a recognizable landmark. In Quake 3, that usually means items. You'd never tell a teammate, "I'm at (540, -973, 108)", which is how the computer records your position. But you would say, "I'm near the rocket launcher".
One requirement of item pickup that I glossed over in a previous post was this: Bots need to know how likely they are to encounter an enemy in a general area. That implies bots need a concept of what an area is. They need to think of enemies being "near the rocket launcher" not "at (540, -973, 108)".
Bots need to think of enemy location in human terms, not computer terms.
The obvious method of approaching this problem is to divide the level into regions, with each region being defined by one item. Technically each region is "the area of space that is closer to this item than any other item". Once you have the level conceptually divided into "near the red armor" and "near the plasma gun", whenever the bot sees an enemy it can say, "Ah, that player is near the red armor, not the plasma gun. I'm more likely to find enemies if I head for the red armor as well." Now whether or not it wants to enemies is a different question, one answered by item pickup. But at least it can track meaningful data about what other players on the level are likely to do.
However, just because it's possible to find out what item a player is nearest doesn't mean it's particularly fast or easy for the computer to determine that. The AI obviously can't spend half a second to calculate data it needs to save 10 times a second. It's okay to spend a bunch of time when the level loads to calculate the best set of regions, but once these calculations are done, bots need to do the location to region calculation very quickly.
I researched a number of different options, but eventually settled on the octree, briefly mentioned in a previous post. Conceptually an octree is a way to layout some number of points in 3-space. In BrainWorks, the item region octree contains the location of all items on the level. Rather than rewrite what has already been written on the subject, I recommend reading the wikipedia article on quadtrees (the two dimensional equivalent of octrees).
For the 99% of readers who don't care how to implement an octree, I'll just say that a well balanced octree will generally let you find which item is closest to any input location very quickly. The run time is O(log8 N) time, where N is the number of items on the level. That means that finding the nearest item on a level with 64 items will take twice as long as a level with 8 items, and a level with 512 items will take 3 times as long as a level with 8 items. Since even the largest levels rarely have more than 100 items, this calculation is really fast, and that in turn frees up more processor time to think about different AI problems. The bot makes a richer impression to the human playing the game and hopefully the player has more fun too. Sometimes making a game fun to play involves implementing mind-numbingly boring data structures, but the fun just wouldn't be there if they were missing.
Wednesday, January 23, 2008
Two Kinds of AI
There are two kinds of artificial intelligence problems. In both situations, the AI has data describing its world, but the two kinds of problems require vastly different solutions. In a video game, the AI can have perfect information about, well, everything. You can find out the exact location of anything, how fast it's moving, and pinpoint sound effects. The server can even give the AI perfect information about its enemies, like their current health and weapons.
Contrast this with AI in a real world setting, like creating an AI that drives cars:
Now the AI has a whole different set of problems. Your car might have a lot of sensors, but there still can be measurement errors. The data might not be in the ideal format-- in a game, the coordinates of all nearby objects are encoded in three dimensions. But an AI to drive a car would have to extract those coordinates from two dimensional camera images. And if game AI takes too long to think, the worst that happens is a slower server. If your car's AI thinks too long while driving on the freeway, it could get into an accident!
Of course, while writing AI for simulated environments like games is much easier than real world applications, it has a different set of challenges. A bot that always knows where you are and aims perfectly isn't much fun to play against. To make a fun bot, the AI should only use data a real player would have access to.
The challenge of real world AI is computing accurate data.
The challenge of simulated world AI is determining which pieces of data to use.
So when I tackled the problem of selecting which enemy a bot wants to attack, you can imagine the kind of challenge I faced. The simple and obvious solution-- considering each player in the game-- was simply incorrect because it used data the bot absolutely should not have access to. To solve this problem, I wrote an environment scanning engine for BrainWorks (ai_scan.c). Ironically, the purpose of this module is completely different from the scanning a car's AI would do. The BrainWorks scanning engine "fuzzes up" the data so it's less accurate, or simply ignores things the bot shouldn't know about. While it would be nice for bots to perform this task the same way humans do, in this case the bot approaches the problem in the exact opposite manner.
The bot starts by checking everything in the game and testing if it can see it, by testing that no walls are in the way, the bot is facing the thing, and the thing isn't too far away. The bot records all targets it sees in its awareness list (ai_aware.c). If the bot hasn't seen a target yet, there is a short delay before the target is "active" in the list, meaning the bot has officially spotted the target. This is analogous to time it takes humans to react to sudden changes. Furthermore, the bot will remain aware of this target for a few seconds even if they hide behind a corner. Just like a bot can't know about a target behind a corner it hasn't seen, the bot must know about that target if they have seen them. That enables the bot to chase after the enemy, should they run away.
And of course, there are other things the bot scans for. If it sees incoming missiles, it notes them as well so it can dodge out of the way. Sound effects help the bot identify enemies that can be heard but not seen, and so on. Once the bot has a list of enemies, it analyzes them to decide which it should attack. (Generally this is whichever enemy the bot has the easiest time shooting.)
All that work just to figure out who the bot wants to shoot at! The bot might have thought about the problem differently from humans, but it came to the same results. Sometimes good AI means making the AI play worse instead of better.
Contrast this with AI in a real world setting, like creating an AI that drives cars:
Now the AI has a whole different set of problems. Your car might have a lot of sensors, but there still can be measurement errors. The data might not be in the ideal format-- in a game, the coordinates of all nearby objects are encoded in three dimensions. But an AI to drive a car would have to extract those coordinates from two dimensional camera images. And if game AI takes too long to think, the worst that happens is a slower server. If your car's AI thinks too long while driving on the freeway, it could get into an accident!
Of course, while writing AI for simulated environments like games is much easier than real world applications, it has a different set of challenges. A bot that always knows where you are and aims perfectly isn't much fun to play against. To make a fun bot, the AI should only use data a real player would have access to.
The challenge of real world AI is computing accurate data.
The challenge of simulated world AI is determining which pieces of data to use.
So when I tackled the problem of selecting which enemy a bot wants to attack, you can imagine the kind of challenge I faced. The simple and obvious solution-- considering each player in the game-- was simply incorrect because it used data the bot absolutely should not have access to. To solve this problem, I wrote an environment scanning engine for BrainWorks (ai_scan.c). Ironically, the purpose of this module is completely different from the scanning a car's AI would do. The BrainWorks scanning engine "fuzzes up" the data so it's less accurate, or simply ignores things the bot shouldn't know about. While it would be nice for bots to perform this task the same way humans do, in this case the bot approaches the problem in the exact opposite manner.
The bot starts by checking everything in the game and testing if it can see it, by testing that no walls are in the way, the bot is facing the thing, and the thing isn't too far away. The bot records all targets it sees in its awareness list (ai_aware.c). If the bot hasn't seen a target yet, there is a short delay before the target is "active" in the list, meaning the bot has officially spotted the target. This is analogous to time it takes humans to react to sudden changes. Furthermore, the bot will remain aware of this target for a few seconds even if they hide behind a corner. Just like a bot can't know about a target behind a corner it hasn't seen, the bot must know about that target if they have seen them. That enables the bot to chase after the enemy, should they run away.
And of course, there are other things the bot scans for. If it sees incoming missiles, it notes them as well so it can dodge out of the way. Sound effects help the bot identify enemies that can be heard but not seen, and so on. Once the bot has a list of enemies, it analyzes them to decide which it should attack. (Generally this is whichever enemy the bot has the easiest time shooting.)
All that work just to figure out who the bot wants to shoot at! The bot might have thought about the problem differently from humans, but it came to the same results. Sometimes good AI means making the AI play worse instead of better.
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.
Subscribe to:
Posts (Atom)