An old friend of mine was a former army drill sergeant. I was surprised to learn this, as he didn't fit the stereotypical personality at all. Thoughtful and friendly are not the first words that come to mind when you hear the phrase, "Drill Instructor". This former job came up when someone mentioned they were leaving for basic training (aka. "Boot Camp") in six weeks, and my friend immediately told the guy, "Start doing push-ups now." Apparently you do so many push-ups in boot camp that it's never to early to get in shape, and the better physical shape you are in, the easier it goes. Not that boot camp is ever easy.
Intrigued by learning that my friend had been a drill sergeant, I asked him about basic training from the sergeant's perspective. According to him, the most important thing you can do to survive boot camp is to be practically invisible. You need to blend into the crowd and never even be noticed by the drill instructors. The instructor's job is to spot recruits that don't fix the mix and make them fit in.
"The instructors don't hate you," he said. "It's just that nothing you've learned in civilian life is of any use in the army, and they need to beat that crap out of you."
The typical civilian doesn't take order very well. Generally orders are considered "loose guidelines". They're likely to ignore orders outright, only do the parts they want, or do things differently based on their preferences. That kind of attitude is acceptable (although not optimal) in real world business settings. In the army though, the lives of thousands if not millions of people are at stake, and defying orders can have large consequences that the enlisted units can't possibly be aware of.
If your army company controls a bridge, but your officer tells you to march one mile down a river and swim across at midnight, then that's exactly what you do. The option of taking the bridge across and walking down the other shore shouldn't even enter your mind, even though your officer never told you why he gave you your orders. Soldiers who disobey orders either get killed or get other people killed. That's why the number one objective of a drill instructor is to teach privates to follow orders.
There's a similar issue for AI in team play video games. If your team contains some bots or possibly "side kicks", the game designers generally give you some way to give them orders. No game designer considers making your minions sometimes ignore orders, of course. Rather, the problem is this: Just as most people aren't used to following order precisely, they also aren't used to giving them precisely. There's a whole set of problems determining what the player even intends when they say something as simple as, "go back through the door". Which door? How far back? So much of language depends on context and it's just hard to determining meaning from a small snippet of words.
The second issue is that no matter what order a player gives, they almost never want the bot to perform that task indefinitely and precisely. When you say "go guard the red armor", it's just until they spot an enemy. When the bot spots an enemy, you don't want it to let them get away if that enemy leaves the red armor spot. The bot should stop guarding and start attacking in that case. Similarly, if no one goes by the red armor for a while, the bot should stop guarding and find something useful to do. When the player says, "Guard the red armor", the bot needs to understand that as "Guard the red armor until you see an enemy or until you've been there for three minutes".
This is the basic strategy BrainWorks uses for its message processing, which is largely unchanged from the original Quake 3 message code. It does the best job to determine what the player means and treats that instruction as a relatively important high level task. But it's still just a guideline. Stuff like combat takes precedence, and the bot will forget about the order after a few minutes. Ironically the bots need to function like civilians rather than soldiers, or the person playing the game wouldn't be happy with how the bots would follow orders.
Monday, November 24, 2008
Monday, November 17, 2008
Ignorance Is Bliss
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.
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.
Monday, November 10, 2008
Social Mentality
I cannot help but comment on the results of the recent American presidential election, in which Barack Obama became the first non-white to be elected president. As a jaded American, I recognize that America has its share of both wonders and problems. But I have never been more proud of America than I was on this past election night. To me, the election of Barack Obama is symbolically a major victory in America's war against racism. And were Obama the Republican candidate and McCain the Democratic one, I would be no less overjoyed. Some things in life are more important than what percent of a candidate's positions we agree with.
I want to stress that this election is a victory over racism, not slavery. Most cultures in pre-modern times practiced slavery, but it was enslavement of people from the same ethnic background. Slavery in America and the Caribbean isles differed from other forms in slavery in that the belief was also coupled with a sentiment of racial superiority. So even after the abolition of slavery in 1863, the underlying tone of racism permeated much of American life. In contrast, the Britain empire outlawed slavery in 1833, but their enslavement wasn't particularly racially biased, so their past two centuries haven't been filled with racial tension. Abraham Lincoln won the war on slavery in 1865, but completely decimating the southern American states couldn't change the racist opinions that much of the country still retained. The election of Barack Obama to the office of President is proof that a large percent of America is now racially blind-- the ethnic background of a candidate is not a reason to select against them.
Of course, not all of America feels that way. That's why this election is a sign of major progress on the issue of racial discrimination, but it doesn't represent the end of it. Looking at the final electoral vote distribution, this election was heavily slanted towards Barack Obama but unanimous. For example, Alabama and Mississippi again voted for the conservative candidate as they've done for decades. But Virginia and North Carolina both voted for Barack Obama, two states that split away from America during the American Civil War because they wanted the right to keep slavery legal (among other things).
This might seem like a trite point, but each major population center in America has its own local way of thinking. People in Los Angeles are more liberal than people in Salt Lake City, for example. The southern states tend to be more conservative than New England states. And the way they vote is a reflection of their local societal beliefs. If this were not the case, every city and state would vote exactly the same way. There's nothing magical about the geography that makes people think in certain ways. The social mentality is a purely contained in the minds of all people in that local society, and if you think about it, that is an incredible thing.
For North Carolina to vote for a black man 147 years after it tried to secede from the United States, the entire cultural mentality had to change. It does not change quickly either. It wasn't until all the adults of that generation died, along their children and grandchildren, that the majority of the state decided that maybe blacks and whites were equals. That should be a sign of how easy it is to believe the first thing you're told and how hard it is to consider outside opinions.
More often than not, people belong to the political party and religion of their parents, quite apart from the actual merits of those positions. Over 90% of America is Christian and well under 10% of India is Christian, despite extensive missionary work. Even if there were strong, logical reasons to believe in the Christian religion, it's clear that those reasons are not why America is a Christian nation. If those reasons were so logically compelling, then India would be a Christian nation too.
Like it or not, if your political and religious views closely match your family's and city's views, the odds are high that you haven't thought very hard about them. That doesn't mean your beliefs are wrong, but if they are right, you probably don't know why they are. It means you accept the basic beliefs of society's "hive mind", and you've ceded some of your thinking.
While this can be dangerous, accepting society's beliefs without too many questions can be really helpful. I'm not advocating, "question everything", but, "question everything important". You might be wondering why that is, and what this has to do with Artificial Intelligence. Next week I'll explain what I mean.
I want to stress that this election is a victory over racism, not slavery. Most cultures in pre-modern times practiced slavery, but it was enslavement of people from the same ethnic background. Slavery in America and the Caribbean isles differed from other forms in slavery in that the belief was also coupled with a sentiment of racial superiority. So even after the abolition of slavery in 1863, the underlying tone of racism permeated much of American life. In contrast, the Britain empire outlawed slavery in 1833, but their enslavement wasn't particularly racially biased, so their past two centuries haven't been filled with racial tension. Abraham Lincoln won the war on slavery in 1865, but completely decimating the southern American states couldn't change the racist opinions that much of the country still retained. The election of Barack Obama to the office of President is proof that a large percent of America is now racially blind-- the ethnic background of a candidate is not a reason to select against them.
Of course, not all of America feels that way. That's why this election is a sign of major progress on the issue of racial discrimination, but it doesn't represent the end of it. Looking at the final electoral vote distribution, this election was heavily slanted towards Barack Obama but unanimous. For example, Alabama and Mississippi again voted for the conservative candidate as they've done for decades. But Virginia and North Carolina both voted for Barack Obama, two states that split away from America during the American Civil War because they wanted the right to keep slavery legal (among other things).
This might seem like a trite point, but each major population center in America has its own local way of thinking. People in Los Angeles are more liberal than people in Salt Lake City, for example. The southern states tend to be more conservative than New England states. And the way they vote is a reflection of their local societal beliefs. If this were not the case, every city and state would vote exactly the same way. There's nothing magical about the geography that makes people think in certain ways. The social mentality is a purely contained in the minds of all people in that local society, and if you think about it, that is an incredible thing.
For North Carolina to vote for a black man 147 years after it tried to secede from the United States, the entire cultural mentality had to change. It does not change quickly either. It wasn't until all the adults of that generation died, along their children and grandchildren, that the majority of the state decided that maybe blacks and whites were equals. That should be a sign of how easy it is to believe the first thing you're told and how hard it is to consider outside opinions.
More often than not, people belong to the political party and religion of their parents, quite apart from the actual merits of those positions. Over 90% of America is Christian and well under 10% of India is Christian, despite extensive missionary work. Even if there were strong, logical reasons to believe in the Christian religion, it's clear that those reasons are not why America is a Christian nation. If those reasons were so logically compelling, then India would be a Christian nation too.
Like it or not, if your political and religious views closely match your family's and city's views, the odds are high that you haven't thought very hard about them. That doesn't mean your beliefs are wrong, but if they are right, you probably don't know why they are. It means you accept the basic beliefs of society's "hive mind", and you've ceded some of your thinking.
While this can be dangerous, accepting society's beliefs without too many questions can be really helpful. I'm not advocating, "question everything", but, "question everything important". You might be wondering why that is, and what this has to do with Artificial Intelligence. Next week I'll explain what I mean.
Monday, November 3, 2008
Do Not Want!
I promised an in-depth explanation of how bots in BrainWorks perform dodging. But sometimes a picture provides the perfect overview:
That's the core of the algorithm. For whatever reason, this dog has decided he absolutely does not want to catch the ball someone threw at him, and the only thing his mind is thinking about is how he can safely get away.
When a bot needs to dodge a missile, the bot considers the eight possible directions it can move in (forward, backward, left, right, and each diagonal), plus the "dodge" of standing still. Any movement direction that collides with an incoming missile is considered completely off limits. Yes, it's bad to get "herded" where the enemy wants you to go, but that's a situation the bot can deal with later. There's no sense in eating a rocket now so that the bot might not take other damage later. Priority number one is always avoiding incoming damage.
So for each of the nine total dodge options, the bot computes what would happen if it moved in that direction for around a second. If a missile would hit the bot, it flat out ignores the option. It also has to check for some other problems. Obviously "dodging" into a wall isn't much of a dodge at all, so bots only dodge in directions with enough open space to move. And if the dodge is off a ledge, into a pit, then the bot also ignores that option. Those are the three reasons a bot will automatically disqualify a potential dodge direction:
Option 1: Move in the direction that gets the bot closest to its intended destination
The problem here is that the bot is very predictable. If you know where the bot wants to go and what route a missile shot cuts off, you know exactly where it will head next That makes it trivial to hit the bot in your next shot, and being predictable is not a luxury the bot has.
Option 2: Choose one of the remaining directions at random
This solves the predictability problem. But when you pick the remaining directions at random with equal probability, the bot's natural movement will be away from the missiles, without any regard for where the bot wants to end up. This random selection lets the attacker control the general direction the bot will move on, possibly keeping the bot from its destination indefinitely. In this situation, it's easy for the attacker to route the bot into a corner and finish it off.
The solution is to combine these two strategies:
Solution: Select at random, preferring directions that move towards the intended destination
Rather than assigned an equal chance of dodging in any direction, the bot analyzes all options and rates how well they help the bot reach its goal. The more helpful an option is, the higher the probability it will take it. However, any option could be taken. Over time, there is a high probability the bot will reach its goal, but its actual dodge direction is not predictable.
For example, suppose there is an incoming missile on the bot's east side, so it's unsafe to dodge east, northeast, or southeast. And suppose the bot would prefer to move northeast were the missile not in the way. The bot's dodge probability table might look like this:
That's the core of the algorithm. For whatever reason, this dog has decided he absolutely does not want to catch the ball someone threw at him, and the only thing his mind is thinking about is how he can safely get away.
When a bot needs to dodge a missile, the bot considers the eight possible directions it can move in (forward, backward, left, right, and each diagonal), plus the "dodge" of standing still. Any movement direction that collides with an incoming missile is considered completely off limits. Yes, it's bad to get "herded" where the enemy wants you to go, but that's a situation the bot can deal with later. There's no sense in eating a rocket now so that the bot might not take other damage later. Priority number one is always avoiding incoming damage.
So for each of the nine total dodge options, the bot computes what would happen if it moved in that direction for around a second. If a missile would hit the bot, it flat out ignores the option. It also has to check for some other problems. Obviously "dodging" into a wall isn't much of a dodge at all, so bots only dodge in directions with enough open space to move. And if the dodge is off a ledge, into a pit, then the bot also ignores that option. Those are the three reasons a bot will automatically disqualify a potential dodge direction:
- Would hit a missile
- Would hit a wall
- Would fall down a pit
Option 1: Move in the direction that gets the bot closest to its intended destination
The problem here is that the bot is very predictable. If you know where the bot wants to go and what route a missile shot cuts off, you know exactly where it will head next That makes it trivial to hit the bot in your next shot, and being predictable is not a luxury the bot has.
Option 2: Choose one of the remaining directions at random
This solves the predictability problem. But when you pick the remaining directions at random with equal probability, the bot's natural movement will be away from the missiles, without any regard for where the bot wants to end up. This random selection lets the attacker control the general direction the bot will move on, possibly keeping the bot from its destination indefinitely. In this situation, it's easy for the attacker to route the bot into a corner and finish it off.
The solution is to combine these two strategies:
Solution: Select at random, preferring directions that move towards the intended destination
Rather than assigned an equal chance of dodging in any direction, the bot analyzes all options and rates how well they help the bot reach its goal. The more helpful an option is, the higher the probability it will take it. However, any option could be taken. Over time, there is a high probability the bot will reach its goal, but its actual dodge direction is not predictable.
For example, suppose there is an incoming missile on the bot's east side, so it's unsafe to dodge east, northeast, or southeast. And suppose the bot would prefer to move northeast were the missile not in the way. The bot's dodge probability table might look like this:
- North: 40%
- Northeast: 0% (Ideal)
- East: 0%
- Southeast: 0%
- South: 15%
- Southwest: 5%
- West: 15%
- Northwest: 20%
- Stationary: 5%
Subscribe to:
Posts (Atom)