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.