Monday, January 7, 2008

The Rambo Problem

So imagine you're armed like Rambo. With a machine gun, shotgun, enough grenades to blow up a tank, and a missile launcher, you're a one man army. (Forget for a moment how you're carrying all this stuff; that's why it's a game!) There's just one problem. You only have two hands. So what weapon do you use? If you were one of the original Quake 3 bots, you would use whatever you felt like, as described by some randomly assigned weapon preference values. Unfortunately, that doesn't produce very good results. Shooting a rocket at a moving target far in the distance is bound to miss. What good players do is choose the best weapon to attack the selected target, and that's what BrainWorks bots do as well.

Of course, the devil is in the details: what makes a weapon "best" for the current situation? Well why do players attack targets anyway? To kill them, of course, since each kill is worth one point. The best weapon is whichever weapon will kill the target fastest. Mathematically estimating "Time to Death" (TTD) is an easy enough problem, given the following input variables for each weapon:
  • D = Damage per hit
  • R = Reload between shots
  • A = Bot's accuracy with this weapon
  • P = Percent of time the bot attacks with this weapon
And the all important:
  • H = Target's current health
If you'd like to follow along with the source code, it's located in ai_weapon.c in the BotTargetWeapon() function.

The bot will average one hit every R*A/P = T seconds with whatever weapon it's considering, and it will kill the target in H/D = K hits, with a minimum of 1 hit. In other words, a weapon that deals 100 damage will require 1 hit against a target with 20 health, not .2 hits. This bounding ensures that the bot properly penalizes itself for "overkill" on the last hit. Against a target with 120 health, the bot might continue using the 100 damage/hit weapon until it scores a hit, and then switch to something else when the target is at 20 health.

This tiny little bit of code creates the crucial bit of emergent behavior known as "weapon combos". BrainWorks bots can and do attack bots with some high damage, slow reload weapons, and then switch to a spray-and-pray weapon like the machine gun or shotgun to finish off wounded opponents. It's something every good human player does and I never wrote a bit of code that says, "switch to the machine gun if the target has less than 30 health." This emergent behavior is the payoff from properly designing the algorithm, and it handles far more situations than the one described.

At any rate, if the bot averages one hit every T seconds and needs H hits to kill the target, the estimated time to death with a given weapon is T*K... Right? Well yes, but for reasons more complicated than they first appear. The real time to death is the sum of a geometric series defined as, "Chance to kill in 1 shot multiplied by time to fire 1 shot plus chance to kill in 2 shots multiplied by time to fire 2 shots plus ..." But this value turns out to be T*K.

There are a few other caveats well. No reload time is incurred for the last shot required to kill a target, so the code deducts R/P seconds from time to death for that. And if the weapon being considered isn't the currently equipped weapon, there's a reload penalty for switching which increases the time to death. The weapon switch reload penalty is automatically incurred (possibly a second time) if the considered weapon doesn't have ammo to kill the target, since the bot will be forced to change once it runs out. But that's the algorithm in a nutshell:

Search all weapons available, find the one that kills the target fastest, and use it.

If you've been reading closely, there are still two details I've glossed over: Estimating target health and estimating weapon accuracy. For health, bad players don't even think about it, good players estimate based on sounds (wounded players sound different), and great players keep a running total of the health value based on the hits the score and the items they see their target pickup. Attempting to model this, the average and low skill BrainWorks bots assume everyone has a fixed health total. The above average bots roughly know their target's health to the nearest 25 health points. And the best bots will flat out cheat and look up the exact health value. That last part is a bit unrealistic, but the information is used in a realistic manner. You don't have to use strict causality and emergent behavior for every problem to get good results.

Estimating accuracy is much harder, hard enough that there is an entire ai_accuracy.c file devoted to tracking it, so I will cover that topic at a later date.


mirez said...

the all important:
* H = Target's current health

Sure it's nice to know enemy's health (your source):
health = BotEnemyHealth(bs); // Estimate the enemy target's health

But I think this info is not available to players (q3 source):
int health; // you only get this info about your teammates

Ted Vessenes said...

Technically that's correct. If you look at the source code for BotEnemeyHealth() in ai_self.c, the code estimates health differently based on the skill of the bot. Unskilled bots always assume their targets have 125 health, for example, and average skilled bots use the estimate as defined by BotEnemyHealthSet(). (This function is called by the scanning code in ai_scan.c when the bot hears a pain sound, since pain sounds change as the target gets more hurt.)

But yes, the high skill bots really do use the exact health totals of their targets, because good players know their target's health to better granularity than +/-25. It requires some concentration to count the damage ticks from each hit of plasma or lightning, multiply by damage per shot, and subtract from your last known value of the target's health, but it's not THAT hard for players to get an estimate within 5 health points. While it's technically not correct to look up the health values correctly, it produces more realistic bots, so I decided it was the right thing for the code.

Enclave said...

Amazing Ted. Keep up the great work. BTW what's the latest link for the current bot version download.

Enclave said...

Whoops, found it