Monday, July 14, 2008

The Power of Spite

In almost any situation where there are limited resources, people are presented with the option of spiteful action. These are actions where someone else is penalized for an action where you received no benefit. Most of the time the spiteful play even had a slight cost, such as additional time. In war, there can be spiteful military decisions, such as General Sherman's sowing of salt during his march to the sea during the American civil war. Sowing salt makes the land completely unfarmable for a period of several years, and Sherman's choice to do this crippled a large part of Georgia's agriculture.

Of course, one of the cardinal rules of war is "waste nothing" since resources are tight. While these spiteful actions cost Sherman's troops a little time and resources, they had a tremendously detrimental effect on the Southerners, both demoralizing them and making it harder for the local citizens to survive. Without commenting on the ethics of this decision, I will merely note that Sherman's spiteful actions gave an advantage to his own side, the North.

So in a first person shooter game like Quake 3, players have countless opportunities to make spiteful plays. Every time they pick up an item they don't need, they are potentially preventing another player from getting that item. A good AI player needs to know when it should pick up an item out of spite. And naturally it shouldn't pick up every item, or it would waste far too much time. There has to be a method for deciding when the spiteful play is worthwhile and when it's not.

In BrainWorks, the additional time cost is automatically factored into the item selection code, as extra time spent grabbing items means a loss of points from delaying the bot's main goal. But the bots still need to know exactly how much an item pickup costs the opponents. Once that value is known, the bot estimates its relative score gain as the spiteful point loss divided by the number of opponents. In other words, keeping an item from 1 of 2 opponents is a lot more valuable than keeping it from 1 of 10. The fewer opponents the bot has, the more they prefer spiteful pickups. So while these spite values don't matter much in large group games, they can have a significant impact on a bot's item pickup selection in 1-on-1 matchups.

This still begs the question of exactly how much a spiteful item pickup costs opponents. Players know that it's great to grab armor even when you're at the maximum and grabbing ammo will rarely have an effect. But BrainWorks bots need to derive this fact. The AI does that by predicting how an individual item pickup will increase a players score for each of three typical players. There's a freshly spawned player, who generally wants armor and weapons. There's a hurt player, who benefits the most from health. And there's a decked out player who probably wants powerups. The AI computes the scores for each player with and without each possible item. The item's spite value is defined as the greatest point gain it gives any type of player. The code uses the maximum estimate rather than the average because players that most need an item are the most likely to pick it up.

That means the spite value is really just an estimate of the item's general usefulness. In fact, the bots use these estimations to isolate the most valuable items on the level and time their respawns, and just as a general area that other players are likely to be in.

1 comment:

Dave Mark said...

Brilliant. I love your posts, Ted.