Monday, April 7, 2008

Getting it "Just Right"

There's not much difference between driving 55 and 56. Unless of course the speed limit is 55, in which case that small amount of speed could make you get a speeding ticket. Standard outside temperatures average between 0 and 100 degrees Fahrenheit, but people easily notice the difference between 68 and 72 degrees. And yet for other measurements in our lives, small changes are completely unnoticed. A car with a full gas tank drives just as well as a car with a quarter tank left-- you only notice the problem when the last drop of gas is gone.

When you design artificial intelligence, everything needs to be broken down to numbers, since a computer can only understand numbers. And a lot of times you have no idea what numbers best simulate the behavior you want to elicit from the AI, or even if the number encodes the correct concept.

Think of the problem this way. Suppose I have a value that encodes the maximum error a bot can make while attempting to aim. If the AI doesn't behavior properly with the initial value I selected, I'll want to try other values. By trying different values, I'll rapidly find out whether this number is very sensitive to changes (like temperature) or insensitive (like a gas tank). But if the bot doesn't seem to be doing the right thing, there's still no way to know what the right value is.

A sensitive number is extremely hard to tweak, because you won't see the right behavior until you get things "just right". If the value doesn't encode the right concept, then that "just right" state won't exist, but you'll never know that. You'll just see how all kinds of different values don't work in different ways.

And an insensitive number generally just has an impact when it crosses an important boundary (for example, driving 56 instead of 55, or your gas tank being 0% full instead of 1% full). There's often no indication where this interesting numerical boundary might be.

Additionally, values can depend on each other. Perhaps changing this maximum error value makes some other value be sensitive, when before that value was insensitive (and thus not aggressively tweaked).

All this to say that when you write AI, there's an awful lot of number tweaking going on. Either you do it by simulations, by neural network training, genetic algorithms, or by hand. But one way or another, you'll have dozens of numbers that all need to be "just right" to present the illusion of intelligence. The good news is that once you've spend time finding these values, you'll have excellent insight into how humans approach the problem. That's how research works, I guess.

For example, do you know what value is the single biggest factor in determining a player's aiming accuracy? It's how fast the player moves the mouse, not the error in mouse movement. The most important factor is the maximum allowed acceleration of the bot's simulated mouse. I know this because of all the values that go into aiming (and there's close to a dozen of them), the acceleration factor by far has the largest impact on actual bot accuracy. There are some very good reasons why that is the case, which are a bit to complicated to explain right now. But simply change the the maximum acceleration for high skill bots from 1400 to 1600 and you'll see an immediate increase in actual bot performance. This value was one of the last values I decreased before release, actually, so BrainWorks bots didn't have the same ungodly aim that traditional Quake 3 bots have.

At any rate, getting artificial intelligence to feel "just right" really comes down to finding the appropriate things to measure and the values those measurements should have. There's no right way to do this, and certainly no magic solution. BrainWorks uses statistical modeling for some things (weapon accuracy) and fixed numbers derived from simulations for others (aiming). Seeing how much the final result can change from just minor alterations in one number certainly gives an appreciation for the complexity that goes into genuine intelligence. If changing just one of twelve values has a dramatic impact on how skilled a bot appears, try to imagine the complexity of millions of neurons in your brain. And yet they all operate together in a (mostly) cohesive unit. It boggles the mind.


Dave Mark said...

Wow. Dead on.

I wish you had written this before I did my last 2 columns over at AIGameDev. One, on Chaos Theory and Emergent Behavior hits a similar nerve as far as tiny changes having big ramifications. The other was about intelligent-looking errors. Again, a lot of it has to do with tweaking the values we use so that we avoid that mathematical exactness that is decidedly un-human.

Good work again!

alexjc said...

Do you have any examples of sensitive numbers in mind? I've really not seen that many at the individual AI level...

Most parameters I have are important to tweak, but rather insensitive.


Ted Vessenes said...

Do you mean examples from BrainWorks? For a full list of configurable variables and comments on them, check out the ai_vars.c file. Apologies for the formatting-- tabs are four spaces in my text editor.

The two most sensitive variable pairs are bot_reaction_min/max (their twitch reaction time) and bot_view_actual_accel_min/max (how fast they move the mouse). The acceleration parameter is harder to explain, but for reaction time, this parameter can add up very fast.

You have a reaction time delay when you first notice an enemy before your brain considers them an eligible target. Then you start aiming at them, but it still takes some time to line up. And after you decide to fire, there's another reaction time delay when your fingers respond to your brain's firing decision. This kind of thing adds up quickly. It was so important to get this right that I had a bunch of gamers (around 100) run a twitch reflex test and post their reaction times so I knew good upper and lower bounds. Interestingly (or perhaps uninterestingly), the bots seem the most realistic when giving the reaction times players use.

alexjc said...

Thanks for clarifying Ted. Awesome article by the way :-)

My perspective on tweaking numbers is still very much based on FPS AI, so bare with me!

Having talked to Dave a bit more about this, it's no doubt true that when you have many systems that interact then the complexity of tweaking individual parameters explodes. (Especially in any kind of simulation-based AI like Dave works with on his Sim game.)

However, in the case you mention, I'd treat that as a design flaw if it was my system :-) I mean, I'm sure it's nice to have emergent properties when you tweak a parameter, but in some cases you should be making your system robust enough to deal with any such parameter (in a more insensitive way).

So, in this case, it would involve, for example, building a PD controller that can aim "correctly" no matter what the bot's precision settings are.

See what I mean?


Dave Mark said...

Wow Ted... you REALLY need to read some of my columns. I just had one on multiple frame decisions since you have to account for reaction time anyway.

Also, I think you will appreciate the one this Tuesday since it kinda falls out of the conversation that Alex is talking about (and others). Pop on over on Tuesday.

Ted Vessenes said...

Thanks for the heads up. I'll be sure to check it out.

alexjc said...

@Dave: I think your column will save the world soon too... :P

@Ted: Hehe, don't mind us! We've obviously got as much to learn from you ;)

I'm also looking forward to digging into the project once my current contract is over.

Keep up the good work!