The Year In Review

Today marks one year since I publicly released the source code for BrainWorks, the artificial intelligence rewrite for Quake 3. I've written slightly more than once per week, giving roughly equal time to the technology behind BrainWorks and general philosophical topics related to AI. While I have more things to write about, I feel like I've covered the basics of BrainWorks in sufficient detail. If people want to hear more about a specific algorithmic part of the code, please let me know and I'll write about it. But for this next year I'm going to focus on more abstract topics likes philosophy, ethics, religion, and the meaning of intelligence. And of course there will be computer science related topics like programming style, structure, game design and so on.

I confess I'm been a bit disdainful of blogs. This is primarily because they are so many of them, and they always focus on the same thing: whatever the author finds interesting. The problem is that so few people have interesting thoughts. And now internet fads like Twitter have made it even easier to share information no one cares about. That's the reason I rarely link to other blogs: It's only when they have something profound to say. If I can only regurgitate someone else's ideas rather than writing new thoughts myself, those ideas had better be very meaningful. The only things worth writing are those things worth reading, and 99% of blogs break this rule.

With that in mind, I plan on doing posts once every two weeks rather than once a week. Quality is far more important than quantity, and good posts can take several days (or weeks) of thinking to best articulate. Here's a rundown of some topics I'd like to cover:

• Reading between the lines (extracting truth from lies)
• Living as a non-Christian who still has Christian ethics
• What does it mean to have feelings?
• Designing games that invoke emotional responses
• Intellectual consistency (why I'm not offended when people pray for me)
• Learning how to learn

If you want to hear my opinions on other topics, now is your chance to make your voice heard.

The Meaning of Truth

I recently had a conversation with my mother where she was bemoaning the current bias in media. She is very conservative, so hearing about the liberal media bias is something I've heard about from her for over a decade. But this time her point was different. For the first time in my memory, she called the conservative media sources untrustworthy as well. And if you can't trust Fox News, how do you find out what's really true? Everyone's message is tampered with their own personal biases.

I explained to her how facts ("truth") can and must be extracted from the biased information we receive from others. Nothing can be accepted at face value, even one's own first impressions. In other words, I believe there's no such thing as unbiased information. In contrast, my mother's contention is that people can and do recognize absolute truth, but immoral people twist it to suit their own purposes. I spent a good amount of time thinking about this dichotomy, and I believe what side you fall on depends on how you answer the following two questions:

1) Can absolute truth be perfectly understood?
2) Can absolute truth be communicated without distorting it?

My mother believes that the answer to both of these questions is yes for the vast majority of truths. My personal belief is that absolute truth cannot be perfectly understood, but you can get a really close approximation most of the time. And it's possible but extremely hard to communicate absolute truth without distortion. That's why learning to extract truth from imperfect information is such a crucial skill for a free thinker.

The problem is that statements must fit within the confines of language to be expressed to others, but not everyone has the same underlying definitions. Much of language depends on context. For example, consider this claim by Alcoholics Anonymous:

Alcoholism is a disease.

The majority of lay people believe this is true, while most medical professionals disagree. Whether you agree with this statement depends on how you define a disease. And that in turn depends on what conclusions you want to apply. The impression I get from Alcoholics Anonymous is that it's important to classify alcoholics as diseased so they can receive sympathy for their troubles in life. If alcoholism were caused by personal choices, then friends and family would be more inclined to chastise the alcoholic than rally around and support them in their addiction.

Meanwhile, medical professionals think about diseases differently. When someone has a disease, that means specific kinds of medication and treatment may be effective. From a medical perspective, diseases tend not to require psychotherapy to treat. So calling alcoholism a disease is misleading for the purposes of treatment. But it's a reasonable statement if you define a disease as, "a malady that requires outside assistance to treat."

The question is which definition of disease are people thinking of when you use the word, and I tend to think the medical professional definition is the more common usage. After all, if all ailments that required psychiatric help were considered diseases, that would include depression and schizophrenia, and no one is claiming that is the case. That's a sign the statement "alcoholism is a disease" lacks internal logical consistency. Nevertheless, that statement is still true within the context of a rather contrived set of definitions.

Perhaps its best to think about statements as belonging to one of two categories: scientific or sociological. A scientific statement is any statement that uses precise terms that are universally understood and agreed on. For example, "the sum of 0 and 1 is 1." Scientific statements, being the basis of science, must be both well defined and measurable.

A sociological statement is anything that's not scientific and therefore not well defined. For example, "Pablo Picasso was a great artist." Not all sociological statements are obviously opinions, however. The statement, "Rappers are musicians" depends on your definition of musician. I personally think of rap stars as poetry artists and not musicians, because their work lacks both melody and harmony.

Even statements that are thought of as facts can be disputed. Consider the following statement:

Senator Obama won a decisive victory over McCain in the past presidential election.

Most but not all people believe this statement is true. The disagreement centers around the definition of decisive. It's true that Obama had over double the electoral votes of McCain, but Obama only had 13% more votes than McCain had. Some people claim that a victory is not decisive when 46% of the country voted for the loser. (I disagree for a variety of reasons, but that's not really the matter at hand.)

The further statements get from scientific statements things like "0 + 1 = 1" and the closer they get to sociological statements like "Rappers are musicians", the harder they are to agree upon and therefore test. And as a result, their absolute truth becomes impossible to verify and bias works its way in. Unfortunately, it is sociological statements that interest most of humanity, not scientific ones. Almost every statement you've read in this post has been a sociological one-- its truth can only be approximated, not scientifically tested and verified. The vast majority of "facts" you interact with on a daily basis are untestable. That is why its so important to analyze whatever you hear rather than accepting it as fact. It's also why artificial intelligence is the most difficult area of computer science. AI is the area that deals with answering sociological questions like "what is best" or "what do you want".

First Causes

In recent years, I've come to realize the most formative event in my life occurred when I was three years old. My parents took us kids out on a walk, and for reasons that aren't clear to me, we didn't take the dog alone. My parents put him out on the deck so he could get fresh air, but kept him on a leash tied to the deck so he wouldn't run off and get lost. When we got back an hour later, I ran ahead to the house and discovered the body of our dog hanging from the deck. He had jumped over the railing to follow us and accidentally hung himself on his leash.

This would have been a traumatic experience for any child. I'm certain that if my parents had found the body first, they would have tidied things up a bit and told me a good lie to lessen the blow of what actually happened. But I found him first, and the memory is firmly etched in my mind. As my three year old mind tried to make sense of the situation, I was confronted by an overwhelming sense of loss and waste. I wasn't just sad that my dog had died. I was particularly hurt by how needless the death had been. If my parents had taken my dog along, left him in the house, or tied him to a low post on the deck staircase, none of this would have happened. I didn't blame my parents for not thinking of this. It was just an unlucky situation that could easily have been avoided.

I didn't recognize it until decades later, but that experience framed the rest of my life. It wasn't framed with an objective or a rationale, but with an emotion:

I despise waste.

I've lived my entire life in a constant struggle against inefficiencies and minimizing potential risks. I work hard to prevent problems before they occur. For example, when I get out of any car and shut the door, I always try the handle to make sure the door is locked. I always check that I bring my wallet with me when I take my keys and vice versa. If I have to be somewhere in an hour and it will take forty minutes to get there (including the margin of error), I find something to do for exactly twenty minutes.

I think this is why I was attracted to computer programming as a profession, and why I'm so good at it. Good programming means you can teach a computer to do menial tasks that would otherwise cost a human lots of time. I'm anal about error checking and commenting in my code because I absolutely do not want things to go wrong. Carefulness has become a way of life for me, so "clean" programming is second nature. Many programmers complain that writing good code takes a lot more time than sloppy code, but I don't agree. I've been writing good code so long that it's actually faster than writing "bad code".

As the story left off last week, I had finished writing the most impressive homing missiles ever. And for game balance reasons, I couldn't use the work the way I wanted to. Obviously this pushed my buttons about wasting time and effort, so I designed a Quake 3 game modification (aka "mod") using the homing missiles. Thus Seeker Quake was born. As this was released over eight years ago, it's a bit hard to find sites where you can download it, but I believe it's still available from this site.

The PlanetQuake article does a good job of summarizing the game, but here's the basic gist. Each player starts with a rocket launcher and gets one seeker shot active at any point in time. When you shoot, it selects a random person with higher score than you and mercilessly tracks them down. They can try to outrun it, but they absolutely cannot hide from the seeker. While your seeker is active, all other rocket shots act like normal rockets. And of course, you can use any other weapon available on the level too.

It's a pretty simple twist but it has a really interesting effect on game balance. I tried games with four to eight players on it of varying skills. On a typical level with a point limit of 20, the scores would probably range anywhere from -2 to 20. But in Seeker Quake, final scores were generally in the 13 to 20 range. The best player still pretty much always won and the worst player always lost, but the range was much tighter. Seekers act as handicapping mechanic, as the best player got targeted with a lot more seekers. He has to work harder to maintain his edge. Meanwhile, the worst players on the level have almost no seekers targeting them, so they have more time to catch up.

Here's the bottom line: When a bunch of players with widely varying skill play Seeker Quake, everyone has a good time and everyone is challenged relative to skill. The game is a total blast.

My life hasn't been all cupcakes and roses. But I've worked hard to turn bad situations into good ones. I'm glad I've taken the time to do so.

Building a Better Wizard

I write a lot about the artificial intelligence in BrainWorks, but that's not everything I program. Seven years ago I created a Quake 3 mod called Art of War. It's a class-based teamplay game, not so different from Team Fortress in that respect. Each class belongs to a faction with its own play style-- there was a faction with strong assault classes and weaker defenders, another with stronger defense and weaker assault classes, and so on. But even the heavily defensive faction needed one competitive assault unit. It just needed abilities that were "in theme" for the flavor of the faction. The resulting class, the Wizard, became a stealth attacker. When upgraded, it could blink through walls and turn invisible, making it ideal for hit-and-run guerilla warfare tactics but terrible for an all-out overrun of the enemy base.

Since each class had three upgrade levels, I was looking for a third ability for the Wizard that was in theme for the stealth assault play style. I decided to try homing missiles. The idea was that the wizard could shoot fireballs that would navigate through corridors and eventually home in on enemy structures. The wizard could assault the enemy base without even being inside it, forcing the defenders to track down the wizard and kill them. That's a very different gameplay situation from defending a swarm of attackers, and variety makes for good gameplay.

Given a choice between doing something the standard way and the excessive way, I usually choose excessive, and it was no different for these homing missiles. First let me explain the standard algorithm for homing projectiles.

• Repeat every 50 milliseconds:
• Check for possible targets in the missile's cone of view.
• If there are no targets, keep heading forward.
• Otherwise, turn a bit towards the target closest to the missile's forward direction.

That's about it. You can write that in 15 lines of code, and they are reasonably effective. The big problem with these missiles is their lack of memory. They can only latch onto a target that fits in their field of view. If the target can duck around a corner, the missile will forget about them and keep moving forward into a wall. There's no way you could lose track of a real opponent by stepping out of sight for an instant, but the homing missiles just don't know any better.

Not being content with the standard solution, I fortified homing missiles with some industrial strength awesome! These seeker missiles locked onto a target when it was fired and remembered that target's location (even if it went out of view). Obviously the seeker does a standard turn towards the target when it can get line of sight. When the seeker can't view the target, however, it employed the equivalent of sonar to get a navigational reading on its surroundings. The seeker would look in front of itself for walls, pillars, and other obstacles, trying to find large open hallways and rooms. It considered every direction that had sufficiently large space. From that list of possibilities, the seeker picked the direction that was most in line with the target's current position.

Now it's still possible for the seeker to get caught in a corner or alcove. Abstractly this is a local minima: something that appears to be an immediate improvement but is not useful for reaching the optimal goal. To combat this problem, the seeker kept track of how much free space it wanted. Remember, it only considers directions that have enough open space. By modifying thd definition of "enough", the seeker could control the tradeoff between getting to the target and getting to a wide-open area with lots of navigation options.

Whenever the seeker spent time turning, it increased the amount of space it wanted, making it favor open areas (and deprioritize finding the target). And whenever it went straight, it decreased how much space it needed (prioritizing finding the target). The result was that when a missile got stuck in a corner, it would start desparately searching for any hallway it could find, just to get somewhere else. When it found one, it would "relax" a bit and be a bit pickier in the next area. This is a form of simulated annealing.

This entire bit of code took about one week to write and was around 500 lines of code. I tested it for about an hour, tweaked some numbers, and it just worked. Watching it was incredible, as you could see the seekers do amazing things. They would seamlessly turn down narrow hallways with sharp turns, open doors, fly up and down ledges. Think "precise robotics control on a remote control missile" and you'll have the basic idea.

I was really excited to try this out in the next build of Art of War, because I wanted to see how this would affect the play style of the Wizard. To my dismay, it was a total disaster. The homing fireballs ended up being far too good. A wizard could shoot a fireball anywhere on the level and they would automatically find and kill enemy structures. In fact, a team of wizards could launch an assault by standing in their own home base, and there was just no way to defend against that. To balance the class, I had to remove all the cool homing missile code.

Of course, I wasn't willing to let good code go to waste...

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.

The Theory Of Fun

Last week I ended with a simple question: Does making a game more balanced make it more fun? And like so many other things in life, the answer is both simple and complicated:

It depends.

To put it briefly, it depends on the context of the game and the reasons people are playing it. While on the surface, the original Doom appears similar to Quake 3, they are polar opposite games from a game design perspective. Doom is all about mowing downs armies of generally stupid demons with your increasingly diverse stockpile of weapons. Quake 3 is about fighting a skilled opponent with access to the same weapons and powerups you can use. Doom is a visceral game while Quake 3 is tactical. Rather than saying Doom is fun, it's more accurate to say that visceral experiences are fun, and Doom happens to fill that role. But a game like Serious Sam is just as fun, and in the same way.

If games are candy for the mind, then whether or not you like a particular flavor of game is a question of personal preference. What does your mind enjoy? Each kind of thinking corresponds to a different style of game.

• Analysis
• Action
• Discovery
• Creativity
• Socialization
• Identity
  

As best I can tell, these are the six basic thought elements that make games fun. Allow me to explain them in more detail:

Analysis

Examples: Chess, Go
Requires: Discrete set of Options

People who like analytical games approach them as a puzzle to be solved. The game needs to provide decisions for the player to make, any of which could be helpful in the right situation. The fun is in selecting your decision and finding out if it was a good choice. Winning the game usually means you were right, or at least more right than your opponents. Analytical games can also be single player games, such as a Rubix Cube. They need not include perfect information to all players like Chess and Go do, of course. A game like Poker contains a lot of analysis. But the analysis is in large part about probabilities, risks, and rewards. You can win a game of poker by making the wrong play, or lose making the right play, but people who deduce the right plays more often will win more often, and that's what makes the game analytical.

Action

Examples: Golf, Football
Requires: Physical Interaction

An action game is anything that involves a physical component. If there is ever a game situation where you know what you need to do but your muscles might not be able to do it, it's an action game. The joy in an action game is seeing how well you can do what you tried to do. It's really satisfying to shoot a three point shot in basketball, score a goal in football, or hit a home run in baseball. Every physical sport is an action game by this definition. But other games have action components as well. All first person shooter games are "action games" because they require you to aim at your target and shoot them. You know what you want to do, but your muscles might fail at moving the mouse to the right place. Even a game like Jenga is an action game, because it depends on precise muscle control.

Discovery

Examples: Final Fantasy VII, World of Warcraft
Requires: Artistry

Discovery games are fun because the player experience new things. Their joy is the joy of appreciation. A common theme in these games is a story line. As a result, discovery games generally have lower replayability. They are highly engaging the first time through, however. What the player experiences doesn't have to be the story, of course. It could be enjoying the look and feel of a new World of Warcraft zone. What all discovery games have in common is artistically designed content that the player enjoys experiencing.

Creativity

Examples: Charades, Magic: The Gathering
Requires: Very large set of Options

Some people really enjoy thinking outside the box. To become a medium for expressing creativity, the rules of the game must be extremely flexible, allowing for a wide variety of possible options. The number of options is far larger than that of an analytical game: it needs to be so large that players cannot exhaustively try all of the alternatives. This gives creative people the option to express themselves by making choices other people might not even have considered. Creative games often have a verbal component to them, but this is not necessary. For example, deck design in Magic: The Gathering is a very creative endeavor. There are more legal Magic decks than atoms in the Universe! And a number of Magic players enjoy making decks more than playing with them.

Socialization

Examples: Mafia, Shadows over Camelot
Requires: Cooperation

While it's true that games are only as fun as the people you play them with, some people explicitly enjoy games because of the social interactions. In their opinion, a game's purpose is to generate social interactions, and whether you win or lose isn't as important as how you got there. These games categorically encourage players to work as a team towards a common goal. Victories and losses are shared. The fun is about being part of a group and, for some games, deducing who isn't really a member of the team from their actions.

Identity

Examples: Counterstrike, Team Fortress 2
Requires: Winners and Losers

There are some gamers who play games to win. Obviously the typical sore loser falls into this category, but that's not the only type of person who fits this description. This type of gamer considers winning an expression of who they are. The sore loser is someone who considers that expression to be a validation of identity-- they are distressed when they lose because the loss injures their ego. By definition, every game has winners and losers. But in almost all cases, gamers who want to win prefer games against human opponents, as it makes winning more meaningful. Note that these gamers need not be good players. Often bad players who want to win will gravitate towards teamplay games like Counterstrike. No matter how bad you are, you will win roughly half of your games if the teams are large enough. When a gamer wants to express themselves through winning, all they really need is a human opponent and the plausibility to claim they won through skill. Actual skill could have been involved, but it's not required.

Less Is More

Previously I wrote about a Quake 3 modification I made named Art of War, and how it was the inspiration for BrainWorks. But it wasn't the first Quake 3 mod I made. That honor belongs to an unreleased game variant simply titled Less. The concept of Less is simple: All items are less powerful, less health or ammo per pickup. It's the opposite of Excessive Quake. Excessive is fun because who wouldn't want to be uber powerful. Doesn't that mean Less is less fun to play?

I believe that when done correctly, less is more. The actual numbers on an item don't mean anything; only the relative values matter. For example, you could multiply all health, armor, and damage values in Quake by 1000 and the game play wouldn't change. Players would start with 125,000 health and each rocket would do up to 100,000 damage. Strategically nothing has changed. I call this "Pinball Inflation", as pinball games have been adding extra zeros for decades. Some tables now have scores that reach the trillions.

Online RPGs like World of Warcraft have a similar issue, where you can gain levels and deal extra damage, but you fight monsters that have more health. The difficulty of the fights don't change that much. At best you might gain a totally new kind of ability as you gain a level, which gives you another tool at your disposal, and that's the only way the difficulty increases. So for MMOs, the number inflation game is a method of unlocking more content. Players would be daunted if the first time they picked up a class of character, they had 30+ different abilities to choose from. It's better to start them with 3 to 5 and have them gradually learn more.

All that said, it's crucial to realize that gaining levels doesn't actually make your character more powerful, relative to the content you're doing. Sure you might kill goblins in 2 hits instead of 3, but you'll eventually move onto killing stronger goblins. The primary purpose of gaining levels is letting you experience more content in the game while maintaining the same difficulty.

I started the design of Less from a similar standpoint: I wanted Quake 3 to have more content. Reducing the benefit of each item might seem like a strange way to add content, but listen to the logic. A typical game of Quake 3 involves controlling the two to five best items on the map: red and yellow armor, megahealth, and powerups like quad damage and haste. But on the level there are dozens of items that rarely matter, things like boxes of ammo and weapons. You'd think weapons would matter more, but when they respawn every 5 seconds after pickup, pretty much everyone has any weapon they want. And the ammo a weapon provides makes that weapon's associated ammo box irrelevant. There may be 50 items on a level, but only 3 of them matter for a typical game.

The concept of Less was to make all items have a roughly equal play value on average. Then the best players would be those who knew which item was most important in the current situation, and what their opponent needed the most. You could end up with a game where the winner was the person who best controlled a box of rockets and a box of machinegun bullets. And that adds a deeper level of strategy and tactics, thereby adding more gameplay to the game.

You'd be suprised, but it's actually possible to tweak the numbers for each item to make this possible. The game plays like Bizzaro Quake 3, where you start timing the respawn of ammo boxes and small health balls in addition to armor and quad damage. It's definitely the same game on the surface, but the high level strategy of how you play the map is totally different.

While I don't have the source code in front of me, here are some of the changes made, to give you a sense of how dramatically the gameplay shifts.

• Railgun Weapon: Provides 2 slugs (3 seconds) instead of 10 (15 seconds)
• Railgun Slug Box: Provides 5 slugs (7.5 seconds) instead of 10 (15 seconds)
• Lightning Weapon: Provides 24 ammo (1.2 seconds) instead of 100 (5 seconds)
• Lightning Ammo: Provides 40 ammo (2 seconds) instead of 60 (3 seconds)
  
• Quad Damage: Lasts for 8 seconds instead of 30
• Red Armor: 50 armor instead of 100
• Yellow Armor: 25 armor instead of 50
• Orange Health: 25 health instead of 50
• Yellow Health: 15 health instead of 25

When playing Less, you have this constant sense of never having enough of anything, and that in turn creates a sense of fear and tension. The big question is, though, "Do these changes make a better game?" I'm curious what other people think, and next week I'll share my own thoughts on the difference (and connection) between making a game balanced and making a game fun.

Anatomy Of The Brain

Last week I wrote in brief about the differences between conscious and non-conscious thought, and how experiments show humans use both. Even the most primitive animal brain is an extremely complicated organ, and the human brain is obviously the most advanced brain we've encountered. Conceptually there are three main sections of the human brain, corresponding to the evolutionary processes that produced the brain.

Pardon the aside, but I wanted to say a word to the Christian readers who believe in Intelligent Design instead of evolution. Feel free to interpret "evolution" with "how God chose to create life". Your personal belief about how humans came to exist won't change your interpretation of what I have to say, so don't let my choice of language get in the way. Remember, I was a Christian for 30 years. I was taught creationism by my parents. In high school I believed the theory of evolution, and just said "God used evolution to create humans". Now I just think "humans were created through evolution". I still think people who believe in Intelligent Design are wrong given the data, but I see no reason to be condescending or judgmental about it.

As I was saying, there are three main sections of the brain. At the core is the so called "Reptilian Brain", or more formally the brain stem. This section handles basic reflexive responses such as "fight or flight", mating instincts, and the fear of other species. It also handles exactly one emotion: rage. Next is the Mammalian Brain, or Limbic system. This is the area of the brain that handles all other emotions, as well as concepts like family, culture, and attachments. Some aspects of conscious thought and self-identity are handled by the mammalian brain as well. Last is the Neo-cortex, which is responsible for higher level thought such as speech, reasoning, imagination, and speculation.

While there's a clear physical boundary between the reptilian and mammalian brains, the division between mammalian (limbic) and neo-cortex is not as clear, and there seems to be a stronger bleed between the functions. For example, some conscious thoughts are handled by the mammalian brain while others are handled by the neo-cortex.

Humans have all three brain sections, as do higher mammals such as other primates and larger mammals. Small primates such as rodents do not have a neo-cortex, although they do have the limbic system and reptilian brain. And as the name implies, all reptiles have the reptilian brain, but lack the mammalian brain and neo-cortex. So the brain sections correspond to different evolutionary forks. The primary feature that separates mammals from reptiles is not hair or internal gestation, but a more advanced brain.

If that's true, then reptiles don't actually have conscious thought. They simply respond to stimuli in the same fashion every time. But mammals, having a memory, can learn from past experiences and modify their behavior. Perhaps this is how mammals survived the dinosaurs after a natural disaster hit the earth. Dinosaur brains weren't programmed to handle the "meteor crashed into the earth and all your normal food dies" situation, whereas mammals could learn to find new food sources.

In computer science terms, the reptilian brain is analogous to a state machine, or a simple circuit board. It's pure hardware, and if you give it the same set of inputs, it produces the same set of outputs every time. It has no memory. The mammalian brain is more like a simple computer program, in that its responses are based both on sensory input and on past memories and experiences. Running the same computer program multiple times might produce different results. Mammals have the ability to learn throughout their life while reptiles do not. And since the neo-cortex handles imagination, reasoning, and "what if?" scenarios, it's closer in function to an operating system. An OS can run multiple programs in parallel, similar to the neo-cortex's ability to think about multiple thoughts at the same time, even conflicting thoughts.

This biological framework provides an interesting context from which to answer the questions "What are emotions?" and "Can a computer have emotions?" Some day I'll write on that, but there's a lot more to say than should be stuffed at the end of this column. In the meantime you'll just have to speculate.

Armchair Neuroscience

I'm really grateful for my undergraduate education at the University of Chicago. I believe it's the best liberal arts school in the country, in large part because it lacks the name recognition of Harvard or Yale while still placing academically in the top ten undergraduate institutions in America. No one goes to the University of Chicago for the fame or connections they might get at Harvard, and as a result the school attracts only those students who really want to learn. At the University of Chicago, they teach you how to think and analyze everything.

The joke in college was that a University of Chicago student didn't need to know anything about a subject to have an opinion on it. This is pretty much true. I distinctly remember getting an A on a paper about The Brother's Karamazov when I had only read the first quarter of the book. The trick was to relate the concepts discussed in class with the material I had actually read and with other texts read in that class. While I'm sure my professor would have been mortified to find this out, it speaks a lot about learning to analyze abstract concepts and come to conclusions that happen to be right.

In other words, The University of Chicago taught me to bullshit well.

Most of the time I talk about a topic, I really do understand the subject matter. But I'm not willing to let a lack of expertise or study prevent me from sharing my opinion, so today's topic is neuroscience. As a disclaimer, I've never studied this subject in an official capacity in my life. All the information I have is from personal reading into other studies, most of which are (I think) peer reviewed.

There! That's a more accurate disclaimer than you'll hear from any journalist, and yet they are often no better qualified than I am to write about these topics. In particular, I recently read an article on msnbc.com that hypothesized that your brain could be controlled by an inner zombie.

Yes, that's really their conclusion. And by "conclusion" I mean "hypothesis supported by circumstantial evidence that's phrased as a question so no one can refute your claim because you're not officially making one". Since there's no challenge in ridiculing a claim like this, let me instead give a fair and impartial summary of the article. Then I'll rip it to shreds and propose a hypothesis that better fits Occam's Razor by several orders of magnitude.

I'll admit the term "inner zombie" is just a term chosen to generate interest in the article. And in some sense it worked-- I'm linking to it. All they really mean by inner zombie is a thought process that's not conscious and not (always) connected to the rational decision making. The article cites some studies where people are blinded by deactivating the visual processing section of their brain, and then shown a word. The people have no conscious knowledge of the word, but when they are asked to "guess" what word might have been shown, they properly guess the word with much higher than expected accuracy. There's also a study that shows people who are temporary blinded can still reflexively react to visual information they can't see. And while the article doesn't mention it, there's also a study done on people who are blind because their brain doesn't process images even though their eyes are fine. Compared to other blind people, these people do a much better job than of dodging obstacles while walking down the street, like other people or sign posts.

I'd like to note that these results are all from real, peer reviewed studies. Scientists aren't questioning the validity of these results. But they also aren't jumping to the same conclusion that MSNBC did. Here's the basic argument the article makes:

1. People show the ability to reflexively process and react to visual information even when they consciously report blindness.
2. Therefore an unconscious process has control over their conscious minds.
3. Perhaps all consciousness is controlled by these unconscious processes and consciousness is a myth.

It's step 3 that doesn't make any sense. Sure, humans have unconscious processes that handle the same information conscious sections of the brain handle. But why does that mean the whole brain is controlled by the unconscious part? Given our daily experience, I'd suggest that the reverse is true. Our general actions are primarily controlled by conscious processes, and only when consciousness shuts off do the unconscious sections take control. There's no reason to suggest consciousness is a myth and a "zombie" is "controlling your brain".

But the brain is a really strange organ. The reasons the brain work this way are rooted in the differences between human brains, standard mammal brains, and the reptilian brain. Next week I'll talk more about these things and explain why I think dogs have consciousness but lizards do not.

The Last Place You Look

When I was growing up, I always found it ironic how lost things were always found in the last place you looked for them. For some reason, whenever I was looking for a lost toy it was never in my bedroom or the play room. I'd find it outside underneath the deck, in the basement, or inside the sofa. It wasn't until I was older that I realized this wasn't coincidence; it was a mathematical truth. Put another way, when you're looking for something and you've found it, you stop looking. Things are guaranteed to be in the last place you look.

That's not the same as saying all places are equally likely to hold the lost object, of course. If I'm looking for the TV remote, it's less probable that the dog took it as a chew toy than that the remote fell between sofa cushions. And it's far less probable that the remote is now part of an exhibit in the Smithsonian Institute.

The general purpose search algorithm that humans use for locating lost objects involves prioritizing possible locations from most to least likely and searching them roughly in that order. The actual order will get rearranged to save travel time. For example, if an object is most likely to be on top of your dresser, second most likely to be on the bathroom counter, and least likely to be under the bed, you'll still probably check your dresser first and under the bed second before heading to the bathroom. But in general the search is from most likely to least likely. That also explains why the place you find an object is always the last place you'd think to look. The optimal searching algorithm stipulates that you search in the least likely places last.

So this brings me back to last week's topic of octrees. I described how to build the structure that BrainWorks uses to determine which item a player is nearest. But I haven't actually explained how BrainWorks uses the octree to do this. Consider this two dimensional tree (a quadtree):


Each item in the tree is one of the colored dots. The player is the black dot with the circles around it. Every rectangle refers to a particular subsection of the tree. In this example, the red dot is the root node of the tree. The lower left section of the tree is divided by the brown dot into four sub-regions, and the brown dot's lower left region is further subdivided because it contains another item (the purple dot). The circles represent the boundary of the potential search space as the algorithm progresses.

When the search algorithm first starts, it checks the distance from the root node to the player. This distance defines a circle around the player. If an item is closer to the player than the root node is, it must be inside that red circle. At this point the algorithm doesn't know that the green or blue dots are inside the circle. It doesn't even know that no items in the lower left quadrant are closer than the red (root) item is. But it can mathematically guarantee that nothing in the upper right quadrant could be closer, so that quadrant is ignored.

Because the player is in the lower left quadrant, the algorithm prioritizes search in that section first. This is the quadrant that contains the greatest area of the red circle. The next most likely place to look is the lower right quadrant, as the player is closer to the lower right quadrant than the upper left. The upper left quadrant is scheduled third. So the areas to check are, in order:

• Lower Left
• Lower Right
• Upper Left

Then the algorithm merely recurses. First it checks the brown item in the lower left. A quick distance check shows the brown item is too far away, but the search continues on the brown region's subquadrants of upper right, then upper left, then lower right. As none of these regions have any items, the search of the brown region terminates quickly. And at this point in time, the red item is still the closest object to the player.

When the algorithm starts checking the lower right quadrant of the red item, it notices the blue item is closer. So from now on, it compares all potential search areas against the blue circle instead of the red one. No further items exist in the lower right quadrant, so the blue item remains the closest item to the player.

Last, the algorithm wants to check the region to the upper left of the red (root) item. However, when compared to the new blue circle, the search algorithm realizes that the region does not intersect the circle. Since the circle is the area of potentially closer items, nothing in the upper left can be closer that the blue item, so the entire upper left region is ignored. And since all regions were prioritized by distance to the player (from closest to farthest), the search process is done. All potential items have been checked, so the blue item is the closest. The algorithm doesn't even need to check how close the green item is to the player because that entire upper left quadrant was skipped.

The octrees in BrainWorks function the same way, only in three dimensions instead of two, and using spheres instead of circles. That answers last week's question of why the algorithm might need to search up to 7 subregions to find the optimal solution. The closest item isn't necessarily in the same section of the octree as the player, but the diametrically opposed region can always be ignored. That leaves 7 of the 8 regions to check. In practice most regions are quickly pruned away when a closer item was found, in the same way the region containing the green item was ignored when the blue item was discovered. Even though the example tree contained seven items, only three of them needed to be checked (Red, Brown, then Blue) before the closest item could be found.

Dude, Where's My Rocket Launcher?

Back in March I wrote about how the AI conceptualizes item placement. Rather than thinking of position in terms of raw coordinates, bots consider each item (or cluster of nearby items) to be a potential landmark. When statistical tracking is done for areas players are likely to be, for example, they are grouped by which item they are closest to. Statistical tracking is one of the most powerful tools available to AI if you have a sufficiently large and well organized data set. BrainWorks uses this data to analyze which areas of the level a player is most likely to be in, for example. Not only can this information help bots track down enemies; it also helps a hurt bot them avoid enemies. The more data it can track, the better. So by extension, the faster it can translate from raw coordinates to the nearest item, the better. However, this is not a simple request.

If a level has N items in it and a player is located at position (X, Y, Z), what's the fastest way to determine which item is closest to that player?

Well you can just check the distance to every item and use whichever item is closest. If you read last week's column, you'll remember that this search requires linear time. If you double the number of items on the level, it will take twice as long to find the closest. Certainly we can do better than linear time.

There are a number of data structures that can solve this problem. Some of them might require more setup time but give slightly faster search time. The structure I chose is an octree. It's a tree that holds some number of three dimensional locations. If you want to learn more, I recommend the Wikipedia article on quadtrees as well. A quadtree is the two dimensional analog of an octree, so it's a bit easier to visualize.

In the example I gave last week of a filing cabinet holding 100 pieces of paper, 1 cabinet held 10 folders and each folder held 10 papers. This is a total of 111 pieces of data stored (100 papers + 10 folders + 1 cabinet). In computer science terms, each data storage location in a tree is called a "node". The node where searching begins is called the "root node". In the filing cabinet example, the filing cabinet itself is the root node. The cabinet and folder nodes split 10 ways, and the pieces of paper do not contain any sub-nodes. Nodes that do not further branch are called "leaf nodes".

Getting back to the octree example, the BrainWorks AI code needs to store the spacial locations of 50 or even 200 items in a tree. Each node in the octree contains is one of the stored points, and the node branches 8 ways. Visually think of each node as dividing space into 8 octants-- upper north west, upper north east, upper south west, upper south east, and four more counterparts for lower sections. All points that are above, north, and west of the root node are stored underneath the upper north west node, and so on for all other octants.

For example, suppose there are 50 items on a level. One of them is stored in the root-- say it's a rocket launcher. Of the 49 remaining items, 6 of these item locations are above, north, and west of the rocket launcher. The root node will link to a node for one of these six items-- a megahealth. The other five items will be stored undernearth that megahealth.

Again, the octant division property applies to all nodes, not just the root. So the megahealth also divides its space into eight octants, and the five remaining items will be appropriately placed underneath it. Keep in mind that each of these items is guaranteed to be above, north, and west of the rocket launcher. But items that are above, north, and west of the megahealth will be stored in a different octant than those above, north, and east of the health. Given that there are eight possible areas and only five remaining items to store, chances are that these items will all be stored in one of the eight sub-nodes of the megahealth. (If two items happen to both be below, north, and east of the megahealth, then the first will be stored under the megahealth, and the second will be stored under the first.)

Searching a tree is generally proprortional to the depth of the tree-- the greatest distance from the root node to a leaf node. And for a tree of 50 items, the depth is usually 3 or 4. Going up to 100 items might push the depth to 5 for some level layouts. So the octree structure makes answering the question of "which item am I nearest?" much, much faster than checking all 50 or 100 items.

Given that items have fixed locations on the level, the octree needs to be created once when the level starts, but the tree will never modify during the game. (Ignore items that drop from dead players-- those are handled differently and not useful for statistical tracking anyway.) The actual algorithm is pretty simple, a bit slow, and very likely to produce a well balanced tree. Here's how it works.

Given a set of items:

• Average together all their positions to find the center
• Check each item to find which one is closest to the center
• Add that item as the dividing node
• Separate all remaining items into one of the eight octants this center divides
• Repeat the process on each octant that contains at least one item

By "not terribly fast", this algorithm could take up to half a second on a very, very large map. So still inconsequential, and well worth the one-time hit to produce a better tree.

Of course, there's still the question of how you search the tree to find the nearest item, and that I will be explaining next week. Here's some food for thought though: even if you identify which octant a point would reside in, you still need to search up to seven of the eight octants to guarantee you've found the closest item to your input point. Searching this tree is not done like most tree searches. For those of you who like thinking through these kinds of problems, try to figure out how the search algorithm actually works. I'll give the answer next week.

Given a set of item locations arranged in an octree and one player location, describe an algorithm to find the item nearest the player.

Good luck!

Needle In A Haystack

For a long time, I kept all my important documents in a single box. That would be stuff like my passport, car title, insurance information, and so on. After my wife and I bought a home, we had enough papers to file that our simple box wasn't sufficient. We bought large filing cabinet and it's served our needs ever since.

It's not that we needed to look up stuff any more frequently than before. But when we went from 100 pieces of paper to 1000, we didn't want it to take 10 times longer to find anything. To find stuff in the box, I riffled through it until I found the paper I needed, sometimes searching the entire thing. More stuff means the search takes longer.

A filing cabinet solves this problem by providing a natural structure for organizing the papers. For example, all the papers on the home can go in one file folder, all the car information in another, and all the identification documents like passports in a third. Then the lookup process becomes simpler, as I can ignore everything that's not part of the folder that keeps whatever I'm looking for.

This is a real savings in time. Imagine you have 100 different pieces of paper. You can either stuff them all in one box or you can organize them into 10 folders, each containing 10 papers. What's the average number of papers you'll have to look at to find any given piece, assuming you always know what folder should contain that piece of paper?

When looking through the box, you could look at anywhere between 1 and 100 pieces with equal probability. So you'll average (1 + 100) / 2 = 50.5 pieces before you find it. When looking through the folders, you have to find the correct folder from 10 options and then the correct paper of the 10 pieces in that folder. It will take between 1 and 10 tries to find the folder, or 5.5 on average. And similarly it takes on average 5.5 tries to find the paper in the folder. That's 11 tries total for the folder compared to 50.5 for the box. The filing system can be searched roughly five times faster!

Or is it really five times faster? What happens if you have 1000 pieces of paper instead of 100? When you have this much information, you could create folders and subfolders to further organize the papers. If you have 10 main folders, each of which contain 10 subfolders, and each of those contain 10 papers, then it will take 5.5 + 5.5 + 5.5 = 16.5 tries to find any one of the 1000 papers. It would take 500.5 tries if they were in a box. So in this case the filing system is about 30 times faster.

The more data there is to store, the more efficient the filing system is compared to the box. That's because the filing system is a whole order of magnitude more efficient. In mathematical terms, searching through the box takes linear time. When you add ten times as much stuff, it takes ten times as long. But searching the filing system takes logarithmic time. Adding ten times as much stuff just means it takes one more search step. Very roughly speaking, searching is proportionate to the number of zeros on the size of the data. Searching 100 things takes twice as long as 10 things, and searching 1000 things takes three times long. Want to search 1,000,000 things? That's six times longer than searching 10 things.

You might be wondering what all of this has to do with artificial intelligence. At the heart of almost all AI is data, and data doesn't mean anything if you can't find it when you need it. That means efficient data storage is the required foundation for artificial intelligence. An algorithm is only as good as the data it has access to, and good AI needs a lot of data. If all the data were just shoved in a box, there's no way the computer could run the AI's thought process fast enough. Indeed in almost all computer science, the way in which data is organized is just as important as the actual data being stored. After all, what good is information if you can't find it? Next week I'll give a concrete example of how BrainWorks puts this concept to use.

Sitting on the Fence

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.

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.

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.