Writing artificial intelligence is a lot like being a parent. It requires an unbelievable amount of work. There are utterly frustrating times where your children (or bots) do completely stupid things and you just can't figure out what they were thinking. And there are other times they act brilliantly, and all the effort feels satisfying and well spent.
Fascinatingly enough, people rarely ask the question of whether being a parent is worth the effort. There's an implicit belief that once you grow up and get married, you should have children. It's like the option of not having children doesn't exist. And of course once you do have children, you must do everything in your power to raise them as well as you can. Questions of whether becoming a parent is good idea, or how much time should be invested in children rather than your spouse are discouraged if they are even asked.
Now I'm not suggesting that parents shouldn't spend a lot of time parenting. Once you've committed the next 18 years of your life by having a child, it seems like you should live up to the responsibility you create for yourself. I'm just wary of people claiming there's only one answer when they aren't even asking the question. Doing the right thing for the wrong reason might cause you to do wrong thing later, as situations change. A good example from parenting would be an overt amount of hand-holding once your child goes off to college. If you always believe you should give 100% to help your kids no matter what, you might end up doing their laundry and cleaning their room when they turn 25. Certainly the purpose of parenting is to turn children into adults, and at some point good parenting involves letting your child being an adult. So the core question of, "Is it worth the trouble to have children?" is a real question, and the answer isn't always yes, although many people assume it is.
What seems strange to me is how people answer the related question, "Is it worth the trouble to program good AI?" And they almost universally say, "No". There are countless games where the AI overtly cheats to win-- pretty much every real time strategy game. Almost every first person shooter to date has had massive problems navigating around a level, Quake 3 included. Most squad-based AI is exploitable by any player who has encountered it a reasonable number of times. And the solution of heavier scripting might make AI seem more realistic when first encountered, but it's far less realistic every other time. Companies resoundingly see little financial benefit in creating genuinely good AI.
I find these answers very much at odds with each other. Writing good AI requires more intelligence than raising a child well, but certainly less time. Moreover, good scientific research results are never lost. They can built upon for centuries. They still teach Newtonian mechanics in colleges, even though we know Newton was technically incorrect (but close enough for most practical purposes). There is a lot of potential long term value in designing good AI, even if the short term profits aren't there. Similarly, the cost of raising a child these days is easily over $100,000. That's a huge short term investment that, quite frankly, never pays off for a lot of children in long term societal benefit.
The real conclusion is that economic and scientific valuation have almost nothing to do with the actual choices people make. When someone says, "Is it worth it to raise children?" or a company asks "Is it worth it to make good AI?" they are using different definitions of worth. The company wants to make money but the potential parent wants to enjoy life.
People don't do what makes them the most money. People do what they love!
Why are there over six billion people in this world? Because people are genetically programmed to love having children. The existence of hormones that encode these feelings of love doesn't make the love any less genuine. Children require effort, but the love for children overrides the dislike of effort (for most people, at least). Without the love of children coded into the DNA of humanity, good parents might become as rare as AI programmers. There's not a lot of people who love designing AI.
Of all the things I have learned designing AI, the most important is this:
Find what you love doing, then do it.
That said, there are surely people who would love life more if they didn't have children. And there are companies that make money by writing good AI. I would love to see more people enjoying life, even if that means going against societal trends and not having children. I would also love to see more companies making money by writing good AI. Not every company can or should do that, but I believe there's room for advancement in both areas.
Monday, March 31, 2008
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.
Monday, March 3, 2008
Good Enough For Government Work
This might be a surprise if you've read my post on pragmatism, The Attitude of the Knife, but I'm actually an idealist. I don't want things to be good enough; I want them to be perfect, or at least as perfect as pragmatically possible. I use the attitude of the knife to temper my idealism.
Of course, there is tension between idealism and pragmatism when encountering very difficult problems. I don't just mean, "you'll have to be really smart to solve this problem." I mean, "it's mathematically impossible to solve this problem using the computer you have access to." The idealist wants 100% and the pragmatist wants 99% or even just 90%.
The classic example of a mathematically difficult problem is the Traveling Salesman Problem. If you're not familiar with the problem, it works like this: Suppose you have a salesman who wants to visit every city in a certain area exactly once, and he knows the distance between each pair of cities. What's the minimum distance he'll have to travel to visit all the cities and how do you determine it?
Mathematicians have been studying this problem for almost 200 years now. It turns out that determining the perfect solution is really, really hard, but it's possible. Worst case you can just check every possible ordering of cities. That worst case is unbelievably bad, however. If the salesman had 30 cities to visit and a computer could test one trillion options per second (current no single computer exists that is this fast), testing all these options would take much longer than the current age of the universe. Most of the studying mathematicians have done on this problem revolves around ways to get a "pretty good" answer without spending billions of years to do so.
I say I'm an idealist, which means I want things to be perfect. But I'm also ruthlessly pragmatic. These contrasting ideals intersect on the definition of perfect. If it takes 1 trillion years to find the traveling salesman route that takes 38 days but 1 hour to find the route that takes 42 days, then the 38 day solution isn't perfect. It's really 1 trillion years plus 38 days, which is definitively worse than 42 days, 1 hour. A "perfect" solution must take into account the constraints surrounding the problem and not just the problem itself. The mathematically optimal solution is not the perfect solution expressly because it's not practical enough to use.
What does this have to do with Artificial Intelligence, and specifically item pickup? Deciding what items to pickup is very similar to solving the traveling salesman problem, and that's bad news for me as the AI designer! If there are 20 items on a level, a bot wants to pickup between 0 and 20 different items on the way to its final destination. That's similar to a traveling salesman wanting to visit exactly 20 different cities. And since BrainWorks bots can't spend several trillion years to decide what items they're going to pickup, their item pickup code cuts a lot of corners to get a pretty good solution in a reasonable amount of time. This isn't the mathematically optimal solution, but it is a better choice overall.
Here are some of the tricks BrainWorks uses to reduce the computation time:
It's rare that thinking 10 item pickups ahead would really help the bot more than the first two or three choices. And usually the bot doesn't want to travel halfway across the map to pickup some random item. Only the nearby items are worth considering. For the one or two items that really might be that good, the bot specifically notes these items and includes them in the list of possible pickups, no matter how far away they might be. And as it turns out, these results are still "very good". Often the theoretically best solution isn't the best for the problem at hand. If you idealize the results and not the method, being idealistic involves selecting the most pragmatic solution.
Of course, there is tension between idealism and pragmatism when encountering very difficult problems. I don't just mean, "you'll have to be really smart to solve this problem." I mean, "it's mathematically impossible to solve this problem using the computer you have access to." The idealist wants 100% and the pragmatist wants 99% or even just 90%.
The classic example of a mathematically difficult problem is the Traveling Salesman Problem. If you're not familiar with the problem, it works like this: Suppose you have a salesman who wants to visit every city in a certain area exactly once, and he knows the distance between each pair of cities. What's the minimum distance he'll have to travel to visit all the cities and how do you determine it?
Mathematicians have been studying this problem for almost 200 years now. It turns out that determining the perfect solution is really, really hard, but it's possible. Worst case you can just check every possible ordering of cities. That worst case is unbelievably bad, however. If the salesman had 30 cities to visit and a computer could test one trillion options per second (current no single computer exists that is this fast), testing all these options would take much longer than the current age of the universe. Most of the studying mathematicians have done on this problem revolves around ways to get a "pretty good" answer without spending billions of years to do so.
I say I'm an idealist, which means I want things to be perfect. But I'm also ruthlessly pragmatic. These contrasting ideals intersect on the definition of perfect. If it takes 1 trillion years to find the traveling salesman route that takes 38 days but 1 hour to find the route that takes 42 days, then the 38 day solution isn't perfect. It's really 1 trillion years plus 38 days, which is definitively worse than 42 days, 1 hour. A "perfect" solution must take into account the constraints surrounding the problem and not just the problem itself. The mathematically optimal solution is not the perfect solution expressly because it's not practical enough to use.
What does this have to do with Artificial Intelligence, and specifically item pickup? Deciding what items to pickup is very similar to solving the traveling salesman problem, and that's bad news for me as the AI designer! If there are 20 items on a level, a bot wants to pickup between 0 and 20 different items on the way to its final destination. That's similar to a traveling salesman wanting to visit exactly 20 different cities. And since BrainWorks bots can't spend several trillion years to decide what items they're going to pickup, their item pickup code cuts a lot of corners to get a pretty good solution in a reasonable amount of time. This isn't the mathematically optimal solution, but it is a better choice overall.
Here are some of the tricks BrainWorks uses to reduce the computation time:
- Nearby items are grouped into a single cluster. Bots consider picking up the entire cluster at once. This reduces the effective number of things to consider.
- Bots do not consider picking up more than four items at once before going to their final goal.
- Bots only consider picking up the dozen or so items that are relatively near their current position, or not far off the path to their destination.
- When the bot is very near an item (less than a second away), it automatically picks it up rather than doing a full computation.
It's rare that thinking 10 item pickups ahead would really help the bot more than the first two or three choices. And usually the bot doesn't want to travel halfway across the map to pickup some random item. Only the nearby items are worth considering. For the one or two items that really might be that good, the bot specifically notes these items and includes them in the list of possible pickups, no matter how far away they might be. And as it turns out, these results are still "very good". Often the theoretically best solution isn't the best for the problem at hand. If you idealize the results and not the method, being idealistic involves selecting the most pragmatic solution.
Subscribe to:
Posts (Atom)