Monday, February 23, 2009

Nowhere To Run

Recently I was contacted by the project leader for Q3/PMX. As far as the AI for PMX goes, the plan is similar to BrainWorks: they want a solid AI groundwork for Quake 3 that other mods can easily build off of. As it's been nine years since the initial release of Quake 3, computer processing power and memory storage has greatly increased, so Q3/PMX has some pretty cutting edge objectives for new AI technology. In fact, computers these days are so fast that they can run Quake 3 in a browser. As I understand it, one major portion of PMX will be reworking how Quake 3 AI handles its pathing and routing, which has been a major thorn in my side. If that problem were solved, in my mind there would be one hard problem remaining for artificial intelligence in Quake 3:

Where do you go when there are no items on the level?

This might not seem like a big deal at first glance. But remember that bots use items as the primary motivating factors for deciding where to go. The pathing and routing code will tell you how to get from point A to point B, but all of that is meaningless if you don't know what point B is. The typical strategy is for the bot to pick up the items that help it the most and require the least amount of movement. If the bot can't find any enemies, it will head to the nearest generally useful item and hope a target wanders by. Item placement is the core component of goal selection in BrainWorks.

If you take away the items, everything falls apart.

The bots will simply run after enemies and hope to maintain a reasonable distance. Even a marginally competent player could exploit the bot's predictable behavior.

When two human players are in a level that contains no items, however, they don't get confused at all. Instead they strategically run and hide around the map, using cover to create good shots on the opponent while dodging their return fire. What BrainWorks is missing (and all first person shooter AI bots for that matter) is this dynamic tactical movement. You just don't notice it's missing from BrainWorks because of the item pickup code.

It's very difficult to design AI that can recognize and avoid dangerous areas of terrain while simultaneously taking advantage of opponents in those spots. But it's not impossible. And thanks to nine years of increased processing power and memory, I think it could be a reality in today's games.

Here's the basic algorithm I have in mind. The first objective is to create a "danger map" for the level. The danger map estimates how tactically risky it is to be in each area of the level. Note that "area" needs to be relatively small-- roughly one to two square meters on the ground. Too much larger and the algorithm will get muddied, mistaking good regions for bad. Too much larger and the computation will become prohibitive.

It's far too hard to analyze the geometry of a level to create a danger map, although some simple techniques could be used for a first pass analysis. Instead, the AI could analyze statistical data of players on the level, recording where players are when they got shot and where the attacker was when they made the shot. When this data is combined with statistical tracking of how often players are in a given area, you can create an estimate of how likely you are to get shot in a given region, and how likely you are to shoot someone else. The danger map would be generated using actual statistics from hundreds or thousands of hours of play time on the map.

The likeliness of getting shot is your "danger estimate", and the chance of shooting someone else is the complementary "tactical estimate". Using these values, the AI can evaluate which areas it should definitely avoid (high danger) and which areas it should head towards (high tactics). Note that some areas might be both dangerous and valuable. Standing on top of a pillar gives great vantage for shooting nearby targets, but offers very little cover and escape routes. Bots that were high on health might consider maximizing their tactical position more important than minimizing danger, while a wounded bot would do the reverse.

This all sounds well and good on paper, but if it were actually that easy, it would have been done already. You might be wondering what the catch is.

This algorithm requires an awful lot of training data. If you divide the level into one cubic meter boxes and track danger estimates for all of them, it will take a very long time before you have reasonable estimates for the entire map. There are some tricks that can improve the estimates when less data is available, however.

The basic idea is that if you don't have enough information for the current location, you average together the data for nearby locations. You might not know exactly what position (107,523) looks like, but it's probably similar to the data you have for (110,520). If you have enough other sources of nearby information, you can come up with a reasonably good estimate. The less data you have, however, the further away you have to look for estimates, and the less likely that data is relevant.

Once you have a solid danger map, you just have to teach the bots to avoid dangerous spots and seek out high-value spots. The algorithm could even be expanded to learn which tactically advantageous spots are the best at shooting at targets in a particularly dangerous location. In other words, if the bot realized its target was in a pit, it would look for high ground that's specifically good for shooting into that pit. This might sound more sophisticated than any first person shooter AI currently in existance, and it probably is. But I believe that even simple algorithms can give results far better than the current crop of AI code. This is something that could work on today's computers.

Monday, February 9, 2009

God of Stone

A few weeks ago, I found a Catholic religious pamphlet in a subway car extolling The Infant Jesus of Prague. According to the pamphlet, praying devotions to the statue will cause God to intervene on your behalf and bless you with prosperity. Most non-religious people would regard such claims with mild amusement and derision, but I found myself deeply offended. My issue was not with the mystical claims, but the encouragement to pray to a statue. It goes directly against one of the Ten Commandments, something all Christian denominations (including Catholics) uphold to this day.

The second command says, in abridged form, "do not make or worship any idol". This command was ostensibly from God himself. It doesn't say, "do not worship idols unless they are of me or my messiah". The text is very clear. So when the Catholic church simultaneously says "don't worship any statues" and "give reverence to the Infant Jesus of Prague", they are being logically inconsistent. More than anything, I am offended at the irrationality of the claims. The Catholic church cannot have it both ways. I'm sure they would claim that this is not really idolatry because the statue is of Jesus, the true God. But the actual text in the ten commandments is clear that no physical object should be worshiped, even ones that represent God.

When I went to church as a child, I was taught that the Bible's warnings against idolatry were really a warning against making other things more important than God. In other words, if you value your friends or your grades higher than God, then you've made those things into an idol. While this explanation makes logical sense given the premise that nothing is more important than God, it is fundamentally reinterpretive. When the authors of the Bible warned against idolatry, they really were warning against worshiping stone statues. Now some of the post-exilic writings contain threads reminiscent of the modern reinterpretation, such as the Book of Haggai.

But I wonder how much reinterpretation is too much. Is it really fair to say that the Torah really meant to say, "idolatry is making anything more important than God?" If that statement is true, why does it matter whether the Torah said it or not? The source of a statement doesn't matter as much as the content. It is better to let the ancient writings say what they say, and be honest about our revision. "We allow people to eat pork because there's no good reason to disallow it, even though the Torah says otherwise."

Ancient religions depend on modern reinterpretation to remain relevant today. Or put another way, religions that fail to remain relevant lose followers. I believe this is why there are so many different religions and sects. The religions that have survived for millenniums are those that are most tolerant of revision. Christians and even many liberal Jews have no problems eating pork or letting women wear pants, something that would have shocked Moses. Even one hundred years ago, interracial marriage was outlawed nearly every Christian church in America. I suspect that in another hundred years, the majority of Christian churches will marry gay couples. When a religious law no longer has practical benefits, the religion always revises itself, even if it's a century too late.

This makes me wonder, however, why religions are so willing to revise their laws but so hesitant to revise their gods. The status of legendary religious figures does change slowly over time though. For example, in pre-exilic writings, Satan is portrayed as a henchman of God whose job is to test humanity. After the Babyblonian exile, Satan becomes the adversary of God whose job is to destroy humanity. The clear concept of the messiah doesn't appear in Jewish writings until this time either, although post-exilic rabbis began to interpret the Torah as if it subtly implied a messiah. And the Christian church didn't official decide Jesus was actually God (not just the son of God) until a few centuries after his crucifixion. But in the grand scheme of things, the identity of a religious figure changes much slower than the interpretation of a religious law.

Perhaps the application of ancient laws to modern life produces a stronger discorde than imagining diefic powers operating in Manhattan. The revision of religious figures only seems to occur after the religion's followers as a whole face extreme persecution-- the Babylonian captivity, or Christian oppression under Roman emperors.

From my perspective though, I don't see much of the use of these religious figures. There's a lot of good philosophy in Christianity, and that is worth keeping. But the concepts of God, Jesus, and Satan don't have any real impact on my life. I used to imagine they did in the same way early Jews worshiped idols of Baal. God was my idol of stone, and I realized the good Christian philosophy didn't have anything to do with praying to Jesus. Revising my concept of God might shock modern Christians, but to me it's no different from revising prohibitions on pork. In the end, all religious philosophies evolve to become a set of rules that benefit society as a whole. Dieties aren't required.