For roughly the past month, I've been interviewing at a few different places looking for a new job. I've felt overqualified at my current place of employment and really wanted some more challenging work. At the end of the process I had two offers to choose from, both of which were really similar and far superior to my current job. I suppose most people might decide based on some simple, simple heuristic like "highest salary", "most attractive coworkers", or "did I flip heads?"
But I'm a compulsive optimizer. Naturally I agonized for two weeks over which offer I should. I was hoping one offer would be clearly better than the other, but both the corporate cultures and salary packages were similar. I analyzed every angle I could think of, from the commute times to little things my interviewers had said. I called friends I knew and got as much inside information about the places. I made risk estimates for the companies based on their respective industries. Talk about overkill! My opinion changed on a daily basis, but after two weeks I finally made my final decision.
This is, of course, the exact opposite of what good AI should do.
In most systems where a computer must analyze some data and make a decision, there's a problem when two choices are very similar. Sometimes the system can get caught in an oscillation state where working on either choice makes the other one better. For example, a Quake 3 bot might decide to pick up armor, but the act of moving towards the armor makes it decide that picking up some health is a better choice. So the bot instead moves towards the health, and on the way decides the armor is better. The bot can end up in a situation of indecision where it picks up neither of the two items, and clearly this is the worst of the three choices.
Item pickup isn't the only situation where this occurs. Target selection and weapon selection can have the same problems. A bot can try to chase down one target but on the way decide it would rather aim at a different one and waste valuable time aiming at neither. Or in theory a bot can switch to one weapon and change its range based on the new choice, but by the time it gets in position it decides another weapon is useful. If you've never seen a BrainWorks bot do this, that's great! I've worked hard to remove these indecisions from the AI, but it's neigh impossible to make AI that works in all situations. There are two basic tactics you can use to solve indecision oscillations, each with their own costs.
Most of the time I give the scoring estimate a bonus of between 10% and 25% for keeping the same decision. In other words, the AI won't change its mind unless the new option is at least 25% better than the old. The higher this factor is, the fewer oscillations will occur. However, the risk is that an option that's genuinely 8% better will be missed, even if it wouldn't cause an indecision loop. Additionally, it's rare but still possible that even with a 25% factor, the bot can get stuck in indecision. This method is best used for situations where the estimated value of one option over another doesn't change that rapidly. This is how general item pickup oscillations are handled, as well as enemy selection.
When a small buffer isn't sufficient, the other option is to prevent the bot from changing its mind until it completes its selection, or at least for a reasonably long duration (such as half a minute). This is guaranteed to solve the problem. But there are two drawbacks. Not only will the bot be more likely to make suboptimal decisions, but it could get caught in a situation where it's very predictable. As such, it's best to apply this tactic only when absolutely necessary and ideally when the action can be completed quickly.
This method is used in item pickup for items the bot is very nearby. If a bot can pickup an item in less than one second, it immediately overrides all other item pickups and grabs it no matter how useful some other item may be. It turns out that even with a bonus factor for keeping the same item selection, bots could still get stuck in indecision loops when they were very close to an item of low value. That's because the estimated points per second is the ratio of two very small numbers, so the estimation has a large margin of error. No bonus factor could stop the bot from switching between the bad nearby item and the good item that was far away. The code forces the bot to spend half second to grab the nearby item, thereby preventing the loop from occurring.
Regarding my new job, I was leaning towards the place that offered slightly less money but seemed to have higher job satisfaction. In the end they decided to beat the salary offered by the other company, so it was a no-brainer to pick the job that has both higher pay and happier workers.
Monday, August 25, 2008
Monday, August 18, 2008
Scouting for Trouble
One of the funny things about designing artificial intelligence is that you run into all kinds of problems you never even considered. For example, I spent a lot of time designing algorithms to handle realistic aiming. But what does the bot do when it's not trying to line up a shot? It has to look at something, even if there's no one else in the area. That's because the bot must either hear or see an enemy to become aware of it and start shooting back. Scouting around for likely areas an enemy might be is the best thing the bot can do when, well, it has nothing else to do.
The issue is that a bot doesn't visualize the game the same way a human does. Technically stated, bots don't visualize anything at all. While we as humans see a brightly rendered three dimensional area, that's too much information for the artificial intelligence to process in a short amount of time. A Quake 3 bot actually uses something similar to sonar to "visualize" the world. It sends out a instantaneous pulse in a perfectly straight line and figures out where that pulse hits something. It can even tell what kind of thing the pulse hits, like a wall or some fleshy target. However, there isn't enough time to send pulses in all directions, so the bot needs to carefully spend its allotment. If it spends too much time figuring out what's nearby, it won't have enough time to think about other important things (such as where to run).
Getting back to the problem at hand, think about how a human player would decide where to look for new targets. In a hallway the solution is obvious-- look in both directions the hallway runs, but not towards the walls. In a large room you look towards the other side of the room, in doorways, and archways. As humans we quickly process the two dimensional rendering of the area and mentally create a three dimensional depth map. Then we look into the areas with the furthest line of sight, for the most part. That's because new targets come from far away.
While it's very hard for a bot to identify which areas are doors and hallways using its "sonar", it can at least determine which areas of the room are far away. To do this, the bot just sends out eight pulses around itself and finds the three that have furthest line-of-sight. It does some additional checking to find the ground below that point, so when the bot is on a ramp or staircase, it actually looks down the direction of the stairs. And then the bot randomly picks one of the three furthest directions. It's a pretty simple solution, and it does a great job of making sure the bot scouts in the areas where opponents will appear.
Now the interesting thing to note is that no human opponent ever actually sees the bot doing this for more than a fraction of a second. Once you're in the bot's field of view, it will start aiming at you rather than looking for more targets. But a human would notice the results of this code, in that the bots notice them and start responding in a realistic manner. An algorithm that no human actually sees is obviously less important than one they interact with all the time. But that's not the same thing as unimportant, and the relative simplicity of the scouting code reflects this.
The issue is that a bot doesn't visualize the game the same way a human does. Technically stated, bots don't visualize anything at all. While we as humans see a brightly rendered three dimensional area, that's too much information for the artificial intelligence to process in a short amount of time. A Quake 3 bot actually uses something similar to sonar to "visualize" the world. It sends out a instantaneous pulse in a perfectly straight line and figures out where that pulse hits something. It can even tell what kind of thing the pulse hits, like a wall or some fleshy target. However, there isn't enough time to send pulses in all directions, so the bot needs to carefully spend its allotment. If it spends too much time figuring out what's nearby, it won't have enough time to think about other important things (such as where to run).
Getting back to the problem at hand, think about how a human player would decide where to look for new targets. In a hallway the solution is obvious-- look in both directions the hallway runs, but not towards the walls. In a large room you look towards the other side of the room, in doorways, and archways. As humans we quickly process the two dimensional rendering of the area and mentally create a three dimensional depth map. Then we look into the areas with the furthest line of sight, for the most part. That's because new targets come from far away.
While it's very hard for a bot to identify which areas are doors and hallways using its "sonar", it can at least determine which areas of the room are far away. To do this, the bot just sends out eight pulses around itself and finds the three that have furthest line-of-sight. It does some additional checking to find the ground below that point, so when the bot is on a ramp or staircase, it actually looks down the direction of the stairs. And then the bot randomly picks one of the three furthest directions. It's a pretty simple solution, and it does a great job of making sure the bot scouts in the areas where opponents will appear.
Now the interesting thing to note is that no human opponent ever actually sees the bot doing this for more than a fraction of a second. Once you're in the bot's field of view, it will start aiming at you rather than looking for more targets. But a human would notice the results of this code, in that the bots notice them and start responding in a realistic manner. An algorithm that no human actually sees is obviously less important than one they interact with all the time. But that's not the same thing as unimportant, and the relative simplicity of the scouting code reflects this.
Monday, August 11, 2008
Project Planning
As BrainWorks is a complete rewrite of the Quake 3 AI code, it was a relatively daunting project that required a lot of effort in many areas. First person shooter AI requires aiming and firing decisions (not the same thing!), item pickup, weapon selection, movement, visual and auditory awareness, and high level strategy to give a non-exhaustive list. Simply put, there's a lot of things to write and they all have to work together. When the project is this large, it's hard to even know where to begin. How do you prioritize such a wide list of features when, quite frankly, everything is required?
For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.
So if Art of War is so great, why have you never heard of it before?
Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.
The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...
When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.
Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.
Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.
I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.
For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.
So if Art of War is so great, why have you never heard of it before?
Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.
The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...
When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.
Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.
Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.
I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.
Monday, August 4, 2008
Mind Candy
If you haven't worked in the game industry, you might think of a game designer job as a dream job. You get to create your own toys and then play with them! Well it certainly has its moments, but it's important to realize that the job is still a job. There will always be boring parts that need to be done. And more often than not, the job involves creating your own toys and then figuring out why the won't work or aren't fun. In fact, it's a lot like every other programming job except you get to make toys rather than spreadsheets, word processors, or websites. While it's fun to design toys for a living, there's a pretty high cost to it. And I don't mean the "there's boring stuff too" cost that comes with every job. Here is the cost:
The more time you spend designing a game, the harder it is to enjoy playing it.
The problem is that over time, you have to think of the game in terms of its individual core mechanics. But the wonder and enjoyment comes from how those mechanics are organized into something greater. No game has infinite replayability. There always comes a point where you think, "That was fun, but I won't ever want to play this game again." A game might have 10 hours of good fun, or even 100 or 1000. But no game is fun after 10,000 hours. Why is that? Why can't games be fun forever?
Games are mind candy.
They are a thought treat. Personally I approach games as puzzles to solve. The very act of thinking is fun, at least for my mind. The challenge is learning how the make the best move in each novel situation the game presents. As you play a game more, you learn it better. And eventually you simply recognize the situation and can play on autopilot. At that point the game ceases to be fun because it is no longer challenging. It can still be entertaining to execute the actions, and in playing I can encounter a few new challenges, but in general the candy of the game no longer tastes sweet to my mind.
Unfortunately, my job as a game designer isn't done until I've solved the game and determined there are no degenerate solutions. The harder it is to determine a game's optimal solution, the more replayability it has. (Note that replayability just defines how long it takes for the game to cease being fun. It has nothing to do with whether or not the game is fun in the first place, or to what extent.) If it's too easy to solve the game due to an obvious dominant strategy, no one will have fun playing the game once they figure it out and all my design work is for nothing.
While I'm not an author, composer, or movie producer, I suspect this problem extends to all jobs designing entertainment. A really satisfying book is one where all the plot pieces fit together nicely and there are no obvious plot holes. The characters need to feel genuine and you need to understand how their development as people natural extends from their personalities and experiences. No author can convincingly do that without really getting into the minds and lives of these fictional people. To build the depth of a good book, the author must understand that depth before the final editing pass is done and the book is sent to print. They will never have the enjoyment and wonder of watching how the lives of their characters unfold. They sacrifice that potential joy so that other people can experience it too. It's just part of the creative process.
For my part, I find I don't enjoy playing first person shooters as much as I did many years ago. Maybe after a few years break I'll enjoy them again, but that's just the personal price I paid so that other people get more enjoyment from the games they play.
The more time you spend designing a game, the harder it is to enjoy playing it.
The problem is that over time, you have to think of the game in terms of its individual core mechanics. But the wonder and enjoyment comes from how those mechanics are organized into something greater. No game has infinite replayability. There always comes a point where you think, "That was fun, but I won't ever want to play this game again." A game might have 10 hours of good fun, or even 100 or 1000. But no game is fun after 10,000 hours. Why is that? Why can't games be fun forever?
Games are mind candy.
They are a thought treat. Personally I approach games as puzzles to solve. The very act of thinking is fun, at least for my mind. The challenge is learning how the make the best move in each novel situation the game presents. As you play a game more, you learn it better. And eventually you simply recognize the situation and can play on autopilot. At that point the game ceases to be fun because it is no longer challenging. It can still be entertaining to execute the actions, and in playing I can encounter a few new challenges, but in general the candy of the game no longer tastes sweet to my mind.
Unfortunately, my job as a game designer isn't done until I've solved the game and determined there are no degenerate solutions. The harder it is to determine a game's optimal solution, the more replayability it has. (Note that replayability just defines how long it takes for the game to cease being fun. It has nothing to do with whether or not the game is fun in the first place, or to what extent.) If it's too easy to solve the game due to an obvious dominant strategy, no one will have fun playing the game once they figure it out and all my design work is for nothing.
While I'm not an author, composer, or movie producer, I suspect this problem extends to all jobs designing entertainment. A really satisfying book is one where all the plot pieces fit together nicely and there are no obvious plot holes. The characters need to feel genuine and you need to understand how their development as people natural extends from their personalities and experiences. No author can convincingly do that without really getting into the minds and lives of these fictional people. To build the depth of a good book, the author must understand that depth before the final editing pass is done and the book is sent to print. They will never have the enjoyment and wonder of watching how the lives of their characters unfold. They sacrifice that potential joy so that other people can experience it too. It's just part of the creative process.
For my part, I find I don't enjoy playing first person shooters as much as I did many years ago. Maybe after a few years break I'll enjoy them again, but that's just the personal price I paid so that other people get more enjoyment from the games they play.
Subscribe to:
Posts (Atom)