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.