The title of this column, "Does This Mistake Make Your AI Look Smarter?", is a tongue in cheek way of pointing out that there are questions about our AI that are really difficult for us to answer honestly. Skipping over the amusing analogy at the beginning of the column, this is what the crux of it is:
...since the inception of game AI, we have been trying to have our agents make better decisions, not worse ones. We have been trying to eliminate stupid behaviors, not encourage them. We have been striving for more realism, not less… but wait a minute... Isn't this where we might be lying to ourselves? And do we really want to hear the answer if it means we have been wrong all along?
Back in January, I posted a snippet of a review regarding Ubisoft's claim that the AI in Far Cry 2 was going to be seriously cutting edge. Well, apparently, Far Cry 2 was apparently a hit at the recent Play.com LIVE event at Wembley Stadium. According to this review at 411mania.com the AI was at impressive. Of course, many things can be made to be impressive in a tightly controlled demo, but I would like to at least give them the benefit of the doubt. Here's some comments from the review:
Different factions and gangs are spread across the 50 square km environment, and it's up to you who you befriend and who you turn into mortal enemies. Walking around the wasteland area, the guards patrolling the area didn't seem very phased by the player's presence, carrying on with their everyday duties, and it was at this point that the specifics of the AI became obvious. It's evidently a very sophisticated system, as we were assured that the AI is totally non-scripted. Redding joked that the enemy AI is like "The Sims with guns," and it was clear where he was coming from. In the small preview we were shown, guards stopped to chat amongst themselves, went off for smoke breaks, and generally busied themselves about the area. They didn't look too happy when the player tried to steal one of their cars though! One guard in plain sight of the truck shouted out, and his comrades came running, forcing the player to hightail it out of there. Interestingly, the vehicles in the game have a detailed damage system, and you'll have to physically get out and repair them if they take too many hits. In the demo we saw, the player tried to hijack an abandoned vehicle, which was plainly kaput, so the player had to open the bonnet and use a wrench to fix various parts. We couldn't see LJ physically controlling this part, so I don't know exactly how interactive this portion will be, but it's a novel idea.
Just observing a few things here. It sounds like they are using a similar sort of A-life approach that may have been used in the game S.T.A.L.K.E.R. Although much maligned for some poor behavior, Crysis also had a lot of the very engaging "idle behaviors" that are mentioned here. They mentioned The Sims in there and I'm sure that's a nod to the "smart objects" model that was pioneered to such great effect by that franchise.
The idea of multiple factions also lends a lot of potential depth to the character behaviors. It will be interesting to see how this is handled. One question that I would have is how the alliance system is implemented. That is, if you make an enemy of one person in a faction, do they now ALL hate you immediately? If you quietly kill one guy, do they all know or can you continue to deal with them all happy-smiley-like?
Going back to the matter of the AI, the intense gunfight around the straw huts revealed some interesting snippets about how enemies react to being shot. Location-specific damage is nothing new, but Far Cry 2 takes it one step further, as the goals and objectives of enemy AI may change according to where they've been hit. Shoot them in the foot, and sure, they'll hop around in pain, but they'll still be in good enough condition to keep plugging you with hot lead. But we were shown a scenario whereby an enemy had taken a bullet in the upper thigh/groin region and was obviously in a bad condition. His primary objective therefore changed to finding safety, and he could be seen limping off to hide in a building. Naturally, the player finished him off for good measure, but it's refreshing to see enemies that don't act like mere moving targets, rooted to the spot until either you die or they do. FPS fans often have to deal with this kind of AI logic, so it's good to see enemies acting more like actual humans with real thought processes and the like.
It looks like they have hooked up not only the animations to the agent damage models, but also made a point to have the behaviors change as a result. I have seen a lot of the location damage animations lately, and occasionally we see behaviors change as a result of being under fire, but it is nice to see that people are trying to blend them both in. It is perfectly natural to expect an injured warrior to go off and try to lick his wounds to "fight another day". How does this affect the overall gameplay, however? Will they give up if injured? Are they a factor still or do you still need to clean up all the riff-raff that is hiding around? That makes for an interesting dynamic if you now have to root out all the cowering wounded people.
Whether or not Far Cry 2 will be plagued by the same overachievment strain issues that it's predecessor and cousin (Crysis) did remains to be seen. Prima fascia, they both looked pretty good at first only to be exposed later on. I, for one, would like to see these boundary-pushing experiments work. The AI world needs some successes in new stuff in order to open up people's minds to even more experimentation in the future.
In this week's column, "Thinking Beyond Single Frame Decisions", I wanted to provoke some thought about why it is that AI programmers have often painted themselves in the corner mentality that AI decisions need to be made in a single frame - 20ms or so - even if we have to cut corners on accuracy or depth in order to do so.
As AI programmers, we are forced (or force ourselves) up against the invisible wall of framerates. Our agents must live their lives in 20 millisecond slices -perceiving, pondering, planning and performing must all be arranged in little easily-digestible bites. What's more, they share their cramped temporal quarters with dozens, scores, or even hundreds of other cohorts - all clamoring for the leftovers that the art department has discarded... and all working under the same 20ms edict. If you can't decide what to do in 20ms, it isn't worth doing.
If you can spare the clock cycles, head on over to Alex Champandard's excellent community, AIGameDev.com. Remember to tap the RSS feed to the discussion column and his many other blog feeds! While you are there, spawn another helper thread and jump into the AI forums as well. (Forum registration is required but is quick and painless. If you are an AI programmer, you've dealt with more traumatic experiences than that!)
I have to admit, I am really enjoying writing for Alex and his site. I'm honored that he asked me to be a part of his team.
If you haven't already done so, make sure you subscribe to IA on AI to keep up with the latest news and notes on game AI!
According to this article at EETimes.com, there is an AI research group at Rensselaer Polytechnic Institute that believes that they are in the process of creating an AI entity that will finally be able to pass the legendary Turing Test. Their target date is this fall. They need to use the world's fastest supercomputer, IBM's Blue Gene in order to get the real-time results necessary, however. Interestingly, they are partnering with a multimedia group that is designing a holodeck... yes, as in Star Trek.
"We are building a knowledge base that corresponds to all of the relevant background for our synthetic character--where he went to school, what his family is like, and so on," said Selmer Bringsjord, head of Rensselaer's Cognitive Science Department and leader of the research project.
In order to come up with the complete personality and history, they are taking a novel approach. One of Bringsjord's graduate students is providing his life as the model. They are in the process of putting all that data into their knowledge base. Facts, figures, family trivia and even personal beliefs from the student are what is going to make up the synthetic character.
"This synthetic person based on our mathematical theory will carry on a conversation about himself, including his own mental states and the mental states of others," said Bringsjord.
However, before you game AI programmers get all excited about this as some sort of potential middleware product...
"Our artificial intelligence algorithm is now making this possible, but we need a supercomputer to get real-time performance."
It looks like they are doing more than just facts and figures on the project, however. They are going to great lengths to add psychology and even a form of empathy (my word, not theirs).
The key to the realism of RPI's synthetic characters, according to Bringsjord, is that RPI is modeling the mental states of others--in particular, one's beliefs about others' mental states. "Our synthetic characters have correlates of the mental states experienced by all humans," said Bringsjord. "That's how we plan to pass this limited version of the Turing test."
The difference with this compared to standard ,observable facts is "second-order beliefs". In order to do that, you have to be able to get outside of your own collection of perceptions, memories and beliefs and into the mind of others. In a demo that they put together on Second Life (which I will not bother embedding here since it is unexplained and boring), they show that they have been working on 1st order and 2nd order beliefs.
An example is, if something changes after a person leaves the room, you observe the change but they don't, you must know that the absent person will have no knowledge of that change even though you do. Therefore, the other person's belief is that it is actually unchanged. You have to be able to look at the world through their eyes... not just in the present tense, but by replaying the recent history and knowing that they would have no knowledge of the change that occurred.
Hell... as Soren Johnson pointed out in his GDC lecture, we can't even afford to do individual "fog of war" for 8 or 10 computer-controlled enemies. At least not on a typical PC. Imagine trying to keep all that activity straight in a running buffer of some sort... for everything in the environment. *sigh*
I keep having to go back to what Ray Kurzweil was predicting at his GDC keynote... that there is still a logarithmic growth in capability happening in technology. Given his figures, putting this sort of depth in a computer game will definately happen in my lifetime - and perhaps in my career. Now that will be scary.
I came upon an article that wasn't necessarily AI related, but it teaches a heckuva lesson. Carl Bialik of the Wall Street Journal does a regular column under the banner "The Numbers Guy". In his March 14th installment, entitled Can You Read as Well As a Fifth-Grader? Check the Formula he talks about how Microsoft Word's grammar checker uses an antiquated formula to decide if your sentences are in line with the typical readers' skill levels. He points to numerous such formulas the can differ wildly about the grade levels that they ascribe to your writing.
Things that are taken into consideration include words per sentence, the length of words, and the number of syllables per word. For example, he explains that Word's formula is as follows:
It multiplies 0.39 by the average number of words per sentence, adds that to 11.8 times the average number of syllables per word, and subtracts 15.59 from the total. The result is the supposed minimum grade level of readers who can handle the text in question.
Even as an AI designer and programmer, especially as one that specializes in algorithmic construction for simulations that purportedly mimic reality, I found that to be not only a little esoteric but rather simplistic. (That sentence scored a grade level of 20.9 - email me if you need help understanding it.)
Note that they don't care about what the text is saying or the sentence structure at all. (Grade 5.6) Therefore, as Carl pointed out:
The formulas treat writing as a mere collection of words and spaces. Word meaning and sentence structure don't figure. George Weir, a philosopher and computer scientist at the University of Strathclyde in Glasgow, says Word's readability test thinks grade-schoolers could handle the nonsense passage, "Acuity of eagles whistle truck kidney. Head for the treacle sump catch and but. What figgle faddle scratch dog and whistle?" Similarly, "Had lamb little a Mary" and "Mary had a little lamb" score identically.
I will let you peruse the rest of the article yourself in order to get the full, head-shaking magnitude of the stupidity of it all. (11.6) My point, as it relates to artificial intelligence, is that constructing formulas to score something is sometimes a complex issue bordering on the quixotic. (15.8 - although I admit spelling out "artificial intelligence" rather than "AI" just for the syllable count to get an extra 3 grade levels. On the other hand I should have gotten extra credit for "quixotic". Incidentally, for lots of extra credit, play it on a "triple word score" in Scrabble!)
Where's the AI, Dave?
One of the most common errors in constructing weighted sum formulas to score a concept or recreate a behavior is simply leaving out an important factor. You can play with the weights of the factors you did include all you want - and that is great for fine tuning - but if you left out an input that the "real world" takes into consideration, you will never be able to completely mimic the result set you are trying to match. In the case of the grammar checker, there was no accounting for the actual content of the text. I will give them a little slack in the fact that natural language processing is a large mountain to climb (can I use "quixotic" again?) even as a stand-alone application much less a simple convenience tool added onto an existing program. However, because it wasn't taken into consideration, the results not only suffered greatly, but when tested to the corners of the envelope, failed in rather spectacular fashion. (Grade 14.6 for the whole paragraph.)
Therein lies another lesson. If I were to type up a school paper, a blog post, or even my next contribution to the "AI Game Programming Wisdom" series, I would likely be falling into the comfort zone of the algorithm. I would be giving it input that it expects and, therefore, can deal with in a relatively safe manner. The results may not be accurate to a fine degree, but they don't look ridiculous. However, if I were to hammer it with the nonsense words and phrases that the testers did, I expose the alleged "grammar checker" for what it is - a mathematical algorithm that falls flat on its face once you move beyond some vague threshold of comprehensibility. (11.3... welcome back to high school!)
But isn't this the way at least some portion of the gaming public approaches our games? In a brief blurb over on Post-Play'em, (Driving Crisis in Crysis) I pointed out an issue that Crysis had with exactly this problem. If people played the game within certain bounds of behavior, the AI looked fantastic. However, once people started realizing that certain factors were not taken into account by the AI agents, the soft underbelly of the engine was not only exposed but widely publicized on YouTube. They had "broken" the AI. (Not as in "broken a code" but as in "my car is broken... again.") (8.7?!? I'm regressing!)
So, the challenge to us as AI designers is... "what else have I not considered?" It may be an input from the game mechanics that we haven't added, a constraint on a variable that may get out of control, or a scaling of a continuous input that becomes more or less relevant as it moves up and down the scale. The point is, we constantly are wrestling with trying to mimic the grandiosity and magnitude of chaos theory as it manifests itself in the "real world". As much as the game AI world celebrates the increase in clock cycles that we are being granted by the Powers That Be (the graphics programmers), we will never have enough to completely do deterministic modeling on the scale of reality. So, we will always need to pick and choose what inputs we are using in the first place. Then, and only then, should we allow ourselves to be free to adjust... and tweak... and massage... and tinker... and tune... (10.7 - although one sentence in there had an 18.2!)
So, in closing I would like to suggest the following:
We shall heretofore proceed with unambiguous certitude upon a magnificent, glorious expedition into sesquipedalian practices with our ultimate ambition being that of maximizing our alleged numerical educational equivalence as ostensibly adjudged by the ill-conceived but utilitarian application of algorithmic approaches used by the multinational, multidisciplinary, conglomerate known colloquially, industrially and professionally as Microsoft.
(How does a grade level of 36.6 for that sentence hit you? I rule!! As my high school chemistry teacher was apt to tell my class "Your loquaciousness is exceeded only by your verbosity." We were Juniors and that sentence scores a 12.6... no wonder no one understood him. Translated: "The only thing you do more than talk too much is... talk too much.")
(I only get 11.1 for the whole article? Are you kidding me?!?)
Is it possible for an AI to be both "good" and "fun"?
Take the time to jump on over and read it... and then comment either here or in the excellent AI forums there. (Forum registration may be required to comment... but then if you are an AI programmer, you need to be involved over there anyway!)
Well, I knew it would happen soon enough. People have started using Second Life as an AI platform. There is an article on KurzweilAI.net about a project by Rensselaer Polytechnic Institute researchers doing exactly that.
Rensselaer Polytechnic Institute researchersunveiled "Eddie," a 4-year-old virtual child in Second Life who can reason about his own beliefs to draw conclusions in a manner that matches human children his age.
I thought the following bit was amusing, however.
This research is supported by IBM and other outside sponsors, and the team hopes to engineer a version of the Star Trek holodeck.
If you are going to be shooting for a holodeck experience, you have a long way to go from Second Life.
Here's a link to the original article from PhysOrg.com. There's far more information there on the nuts and bolts of it.
OK... anyone who has ever followed Peter Molyneux and Lionhead studios knows that he is the master of hype. He can drag a significant portion of the gaming community along behind him on his words alone. This is especially relevant to AI programmers since it always seems like Peter is on some sort of cutting edge. Well, here's an interview(-let) where Peter talks about some mysterious project (based off of the Dimitri Project) that will apparently blow the doors off of what we have seen from him so far. The only info that he gave on it in a prior interview was that you would be able to "replay your life".
Considering that he is still incubating the egg that is Fable 2, I'm not entirely sure what to think of this. (To be fair, the previews of Fable 2 that I saw at GDC were kinda cool. More on that when I can get around to typing up my notes.)
Here's an excerpt from the interview:
Since Black & White, we’ve been thinking a lot about AI, Lionhead was founded with that thought of AI in mind. In terms of the core or the theory of the AI, we’ve moved from Black&White onto a project called Dimitri, which I’ve been tantalizing you about for a long time. And that team kept on researching. Dimitri was always an experimental thing, which is why I never showed it.
And then it moved from that experiment to a moment in time that happened six months ago when a discovery was made, and this discovery has been so exciting that it has lead to Lionhead focusing on it and sculpting a game around that. I think that discovery is so significant... This discovery has lead us to start a game and that game will be on the front cover of Nature magazines and Science magazines.
What the heck does that mean? The blog author/interviewer pointing out that we are likely talking some sort of artificial life simulation. That makes for interesting conjecture since Spore is (allegedly) right around the corner.
If you think back to the one thing about Black & White that was most fascinating, you’d have to say it was that creature that learned behavior and seemed, for a certain glimpse, to be alive. Imagine if you could take that and multiply it by a billion…
Oh well. I know that I will be following whatever it is that they do there. I'm sure many others will be warily but curiously watching what comes out of the king lion's mouth (so to speak).
Just in case anyone has any problems, I have routed the RSS feed for this blog through Feedburner. I think I did all I was supposed to in order to get it all to work correctly... and even forward correctly for those of you that have subscribed. If you are visiting because your feed was giving an error, however, please use the links on the top right to update the new feed address.
The reason I wanted to do this was to keep track of the subscriber numbers... that counter on the Feedburner chicklet should be jumping up in the next few days as everyone checks in!
2008 AI Programmers' Dinner - Neil Kirby's Monologue
Not really all that tasty as an AI bit, but relevant nonetheless. I just uploaded Neil Kirby's opening of the 2008 AI Programmers' Dinner at the GDC. There are a couple of notes from it... he talks about the Eric Dybsand Scholorship Fund, thanks the corporate sponsors of the dinner and a few other things.
Sorry it's so dark, but this was on the still camera and I didn't have a light on it. Thankfully, as always, he was wearing his "I really am a rocket scientist" lab coat so we can at least see him as some ghostly apparation.
A bit later on in the evening, he called for a toast to the memory of Eric Dybsand. I didn't know it was coming and I had very little space left for video so I didn't tape it. I sure wish I had. We all miss you bud.
AIGameDev.com has a great, in-depth interview with Dmitriy Iassenev, the AI mastermind for S.T.A.L.K.E.R. The game has a very extensive A-life system that lends a lot of depth to the game. In Dmitriy's words:
The gist of the A-life is that the characters in the game live their own lives and exist all the time, not only when they are in the player’s field of view. It eventually runs counter to the customary optimization processes used in games development (why perform operations invisible to the player?). Thus, such a scheme is reasonable to be used only when you know exactly what you want to have in the end. We had the game designers’ requirements to have the characters that could not only live inside a certain level, but move between the levels, memorizing the information they obtained during their existence. Consequently, we have decided that each character should come with only one logical essence regardless of the level he is at; whereas we could try to implement that with various tricks involved.
Read more of this very detailed interview over at AIGameDev.com - the place for the killer AI stuff on killer games!
Damian Isla of Bungie has uploaded his slides from his GDC presentation (which I haven't written up my commentary on yet). He also discusses the history of the "Objectives" system that they used in Halo 3 on this blog post at Game/AI.
I will be breaking down his presentation in a few days (I'm still trying to get caught up).
Some people were complaining that the audio interview with the AI lead on Bioshock was either playing too fast or the applet itself was not loading. I have edited the original page to show a link to the actual audio file. Let me know if that is not working for you.
Yet another new installment in the Discussion series at AIGameDev.com.
