A Change of Perspective

This past Thursday was the American holiday of Thanksgiving. President Abraham Lincoln instituted the holiday as an annual occurrence, although the story hearkens to a tale in 1621 of how the native American ("Indians") welcomed the British colonists ("Pilgrims") to American, and how the Pilgrims gave thanks to God for the safety of the Atlantic voyage. Over the centuries, the religious factor was de-emphasized and the holiday was rewritten as a story of the Indians greeting the Pilgrims with a feast, and the Pilgrims thanking the Indians for their hospitality.

It's a fabricated holiday in that the actual feast probably didn't occur, but instead captures the spirit of thankfulness the Pilgrims had. These days, Thanksgiving is a holiday to get together with family and (hopefully) be thankful for the good things in your life. So for most people that means travel, a big meal, and the stress of being with people you might not get along with. But you still have the opportunity for thankfulness if you want to take it.

There's a lot of value in thinking positively. I'm not talking about pretending bad things are good, or completely ignoring things that are obviously issues. Rather I'm referring to appreciating the good things, and not letting problems get in the way of that appreciation. When nine things go well and one thing goes wrong, it's easy to focus on the negative-- it's the part that needs your attention. Everyone sees their current set of problems as the biggest mountain in the world, even if it's really just a molehill in the grand scheme of things.

I've written a lot about the importance accepting that things can't be perfect, even though it's good to strive for it. But that's different from being happy. When you work hard on something and some parts work out while others don't, you can accept this fact with a depressed attitude or with a joyful one. The attitude you pick won't change the world at all, so you might as well pick what makes you happiest. Focusing on the positive things can be hard, but it's a simple thing that makes your entire life better.

So with that in mind, I'm taking this opportunity to remember the successful portions of BrainWorks:

• Highly realistic aiming
• Intelligent item pickup selection
• Context dependent weapon selection
• Awareness and scanning that lets players try to outsmart bots
• Dynamic feedback systems that let bots learn as they play

If you've read this blog for a while, you'll know there's a few things I'm not happy with. But to me at least, the project was overall a big success. I met or exceeded the objectives I set and I'm very happy with the results of the AI.

Last, working on this project provided an enormous amount of personal growth which I am also thankful for:

• Increased self-confidence
• More self-responsibility
• Freedom from the burdens of Christianity
• Less perfectionistic
  
• More optimistic
• Greater joy in life

Working on BrainWorks forced me to take an enormous amount of responsibility. I thought my God would come through for me, but things only came together when I took responsibility for myself. I'm sure the Christian readers will say that this was just God's way of building me up in strength. My perspective is that I finally realized there was no Christian God. But if what really happened was God gave me strength by teaching me not to believe or trust in him anymore, then praise God for that, and I'll continue following his instructions of relying on my own strength.

In short, I feel like I've won at life. This isn't the hardest project I'll ever work on, and not everything in my life is perfect. But working on BrainWorks gave me so much joy and freedom that I know I can handle whatever else life has in store for me. I'm still relatively young (barely into my thirtys) and I figured out the purpose of my life. I love making awesome things, and I plan on doing that as long as I'm alive.

Boot Camp

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.

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.

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.

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:

• Would hit a missile
• Would hit a wall
• Would fall down a pit

The bot might then dodge in any of the remaining dodge directions. There are two obvious and wrong ways the bot can choose which direction to move in.

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%
  

Once the bot knows where it wants to move, it keeps dodging in that direction for anywhere between three quarters of a second and a second and a half, at which point it chooses another direction (or possibly keeps going the same way). The result? A simple weighted probability function prevents the bot from running into missiles, being predictable, and being routed away from their goals.

Dodging The Question

There's a class of questions that have no good answers to them. For example:

Have you stopped beating your wife?

The question presupposes something that is hopefully false, and giving either a yes or no answer implies the question is legitimate. The solution is to provide an answer that challenges the premise. In other words:

I never started.

First person shooter games like Quake 3 are really games of questions and answers. Every shot you take at an opponent asks the question, "How will you survive this hit?" And your opponent would prefer to respond, "You aren't going to hit me". Of course, he doesn't have much say for an instant hit bullet weapon like a machine gun or shotgun. Either you hit him or you don't. But these weapons are balanced to do less damage. For projectile weapons like a rocket launcher, it takes the missile some time to reach them, and they might move out of the way by the time it gets there. In return, they deal a lot of damage if the opponent fails at dodging. Whenever you shoot a rocket at an opponent, you are giving them the opportunity to make a mistake by not moving out of the way.

Tactically it seems like a poor choice to give your opponent the opportunity to not to take damage. All other things being equal, you'd rather they didn't have a say in the matter. Why ask a question ("Do you want to take 100 damage?") when you can make a statement ("Here, take 50 damage!")? But missile weapons provide a tactical advantage. They make large sections of the map dangerous, denying the opponent safe access to whatever items and safe cover locations are in that place. As a result, missile weapons give you control over where your opponent might go next.

I believe that no good player should take damage from the grenade launcher or plasma gun. These weapons exist solely for the purpose of controlling where your opponent can run. In particular, the plasma gun stream is so fast, constant, and deadly that it can literally herd the opponent into a position where another weapon can finish them off. If they don't want to be herded there, they are free to take 200 damage per second from the plasma shots. Missile weapons are more about controlling position than actually damaging the opponent.

Of course, none of that matters if the target can't dodge the incoming projectiles in the first place. The original Quake 3 bots were notoriously bad at this, obliviously walking directly into a path of fire. So I made sure to give BrainWorks bots a very effective missile dodging system. Just watching a BrainWorks bot play, you can shoot a straight stream of missiles at them and watch them sidestep out of the way. It's such a simple, obvious thing for a human that it might not even seem that special.

For the bot, it's not that simple. The bot needs to analyze the trajectory of all incoming missiles for possible impact and the bot needs to compute a safe direction to dodge from that. Sometimes there will be no safe areas, but some areas will be safer than others. And the final dodge direction needs to take into account the bot's intended final destination. If the bot only moves to the safest possible location, the attacker will simply herd the bot to a place that's even more dangerous. The bots selection of where to dodge also needs to eventually get them towards their goal location, albiet at a slower, safer pace.

Those are the requirements for the dodging system, and they are all challenging. Next post I'll explain in detail how BrainWorks solves this problem.

Groupthink

There is a psychological concept known as groupthink, where members of a group discussing a topic gravitate towards a consensus based on a desire to minimize conflict rather than rationally discussing the subject. The play and film 12 Angry Men is a famous view of groupthink in action. A jury must decide whether a man is guilty or innocent, and the general group consensus is that he is guilty. But one juror refuses to ignore his intuition, even though it differs from the other jurors. The drama of the film is primarily based on how the other 11 jurors come to change their minds and eventually find the man innocent. Groupthink is a dangerous phenomenon because it can cause rational people to make irrational choices purely because it is the most common choice made by other group members. Just because a decision is right for everyone else in the group doesn't mean it's right for you.

Surprisingly, groupthink can be a problem in video game AI as well. This seems counterintuitive, as a bot must be programmed to follow logical rules. How can following logical rules produce illogical results? The issue is one of scope. In a teamplay game variant like capture the flag, each bot might be doing the best thing without knowing what the other players are doing, but not coordinating as a team. Suppose one bot does some logical deductions and concludes the optimal strategy is for him to guard the flag. Since all other bots have roughly the same understanding of the game state, some poorly designed AI code could cause all of them to defend the flag. It's optimal for more than zero players to defend, but having no players attack is clearly the wrong choice.

So bots that don't take into account the overall strategy of the team are likely to fall into a groupthink scenario. This results in a poor strategic choice even if each individual choice is "optimal" when consider without knowledge of the other choices. The solution is for bots to make teamplay decisions as, well, a team. Each bot's decision needs to take into account the likely decisions of other players, bots and humans alike.

The good news is that if bots are good at general combat tactics, the amount of additional logic to handle a teamplay scenario is minimal. It's not like players have better or worse aim when they're fighting in a team, or suddenly some weapons are sigificantly worse when you're playing capture the flag. None of that has to be rewritten to handle play in a group. Teamplay logic is just a question of priorities: when an enemy player has your flag, it's a lot more important to kill that player than any other opponent, and guarding your own base is a lot less important than attacking theirs. And in almost all situations, the choice is between defending and attacking. How the bot attacks and defends doesn't really change.

So BrainWorks can get away with some extremely simple logic to handle team games and still produces reasonable results. One bot becomes the defacto leader for choosing the strategy the bots will take-- exactly how offensive or defensive it is. Some number of players are slotted for defense and the rest for offense, but never 0% in either category. Then the bots are sorted based on how close they are to the two bases. If there are 5 bots on a team and the leader decides on a 2-3 split of defense to offense, then the two bots closest to the home base are assigned with "defense" and the three bots furthest from home are the "offense". Any human players in the game have no assignments, obviously.

It's worth noting that "offense" and "defense" depend on the context of the game. In capture the flag, for example, the defenders guard your team's flag when it's in the base, but they also track down the enemy flag carrier when it's been taken. Attackers try to take the opposing flag, but once someone has the other flag, the attackers need to escort their flag carrier. Once the concept of whether to defend is separated from how to defend, the actual algorithm to defeat groupthink is simple.