Posted by Sam on May 07, 2008 at 06:21 AM UTC - 5 hrs
Dave Mark raises some interesting questions about artificial intelligence in games over at AIGameDev.com. First, he explains that although we're seeing more and better AI in games, a common complaint heard from gamers runs along the lines of "why can't they combine such and such AI feature from game X in game Y." Then, Dave poses the questions for developers to answer:
We can only cite limited technological resources for so long.
...
Perhaps, from a non-business standpoint... that of simply an AI developer, we should be asking ourselves what the challenges are in bringing all the top AI techniques together into the massive game environments that are so en vogue. What is the bottleneck? Is it money? Time? Hardware? Technology? Unwillingness? Unimaginativeness? A belief that those features are not wanted by the gamer? Or is it simply fear on the part of AI programmers to undertake those steps necessary to put that much life into such a massive world?
Let me first admit that I'd wager Dave Mark knows a lot more about this stuff than me. That's how he makes a living, after all. My experience in developing game AI comes from choose your-own-adventure text-based games as a kid (where the algorithm was very deterministic, with few options), making villagers walk around in Jamaicanmon!,
and making spaceships run away from you instead of seeking you out in Nebulus: Ozone Riders.
I even asked Glitch, Wes, and Jonathan (teammates on the project) to remind me of some simple vector math and draw it out on the wet erase board for Nebulus. And I still made them go the wrong direction (which ended up being pretty cool, actually).
In other words, I haven't had much experience with AI as it's typically implemented in games, and what little experience I have had is limited to things I wouldn't (personally) classify as AI to begin with.
Still, I have had some experience in what I might call "classical" AI (perhaps "academic" is a better term).
Stuart Russell and Peter Norvig wrote the Microsoft of books on Artificial Intelligence (90% market share for AI textbooks), and I've read through a fair bit of it. I've implemented a couple of algorithms, but mostly I've just been introduced to concepts and skimmed the algorithms. In addition, I've been through Ethem Alpaydin's book, Introduction to Machine Learning, which would have comparatively fewer ideas applicable to games.
I guess what I'm trying to say is: although I have some knowledge of AI, consider the fact that Dave's experience dwarfs my own when I disagree with him here: It is precisely the fact that we don't have enough processing power that gets in the way of more realistic AI in our games. Or, put more accurately, the problems we're trying to solve are intractable, and we've yet to find ways to fake all of them.
I'm not convinced you can separate the failures of AI from the intractability of the problems, or the inability to design and implement a machine to run nondeterministic algorithms for those problems in NP.
Compared to deciding how to act in life, deciding how to act in Chess is infinitely more simple: there are a finite set of states, and if you had the time, you could plot each of the states and decide which move gets you the "closest" (for some definition of close) to where you'd like to be N moves from the decision point. Ideally N would get you to the end, but even for Chess, our ability is limited to look ahead only a small number of moves. Luckily for Deep Blue (and others), it turns out that's enough to beat the best humans in the world.
Even though Chess is a complex problem whose number of game states prevent us from modeling the entire thing and deciding it, we can cheat and model fewer states - when we can make an informed decision that a particular path of the decision tree will not be followed, we can forgo computation of those nodes. Still yet, the problem will be huge.
There are other ways of "faking" answers to the AI problems that face us in development. Approximation algorithms can get us close to the optimal solutions - but not necessarily all the way there. In these cases, we might notice the computer doing stupid things. We can tweak it - and we can make special case after special case when we notice undesired behavior. But we are limited in the balance between human-like and rational. Humans are not rational, but our programs (often) are made to be.
Presumably, they give the policeman in GTA 4 a series of inputs and a decision mechanism, and he's thinking purely rationally: so sometimes the most rational thing for him to do based on the decision model we gave him is to run around the front of the car when he's being shot at. Sometimes he jumps off buildings. (Video via Sharing the Sandbox: Can We Improve on GTA's Playmates?)
It may not be smart, but it is rational given the model we programmed.
You can make the decision model more complex, or you can program special cases. At some point, development time runs dry or computational complexity gets too high. Either way, game AI sucks because the problems we're trying to solve have huge lower bounds for time and space complexity, and that requires us to hack around it given the time and equipment we have available. The problems usually win that battle.
Game AI has come a long way since Pacman's cologne (or maybe he just stunk), and it will get better, especially as we move more gaming super-powerful servers. Still, it's far from ideal at the moment.
What do you have to say? (Especially the gamer geeks: programmers or players)
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Last modified on May 07, 2008 at 07:24 AM UTC - 5 hrs
I can't recommend Russell and Norvig's book enough though.
Posted by Sammy Larbi
on May 07, 2008 at 06:52 AM UTC - 5 hrs
Because I think it is incredibly difficult to program "common sense" into a computer. As far as combining AI logic, just the prospect makes me shiver. I've never done anything near that kind of programming, but if you've ever gotten the directive "just make this work like that", and your code is finely tuned and relatively bug free, you're going to break things and make a LOT worse before it starts working like the other thing. I imagine it is the same with AI code, but perhaps to a greater extent.
Posted by Jeremy
on May 07, 2008 at 08:45 AM UTC - 5 hrs
I have a serious lack of experience with game A.I., something I wish to reverse soon. But taking a look at GTA IV specifically, and some of the related failings of other games I'd be inclined to think processing power isn't the problem.
A lot of the faults that I've seen in recent games seem to stem (in my opinion) from a lack of thorough testing. Not so much poor quality control, but the endless amount of possibilities that the player could confront the A.I. with.
For instance, the cops falling off the fire escape. Since the game is capable of stopping cars from running you over, and stopping pedestrians from walking out into oncoming traffic it seems rather fundamental that the cops should be able to stop themselves from launching off a building. Even if it is the physical momentum of the cop launching them off the building, it seems like a relatively simple fix (sorry for the massive speculation). Maybe that was never witnessed during play testing, and if that's the case it certainly sucks, but you can't fault any of the suggested reasons for the A.I.'s failing, other than lack of possibility coverage.
Also consider the recent Crysis A.I. hilarity. The A.I did some really stupid things, but it was done because the player did something prior to a scripted event ending, or starting, etc. It seems to me that a lot of the "Oh god.." moments are simply just reactions to states not originally thought of during testing and development.
I could be completely wrong in thinking this, but I'd like to maintain my fantasy that we have enough computing power to generate vast universes of artificially intelligent binary organisms for my personal entertainment.
:D
Posted by Glitch
on May 07, 2008 at 03:54 PM UTC - 5 hrs
"A lot of the faults that I've seen in recent games seem to stem (in my opinion) from a lack of thorough testing. Not so much poor quality control, but the endless amount of possibilities that the player could confront the A.I. with."
Of course, in many cases that lack of testing is what let the Artificial Idiocy through. My point is that while you can fix those, how much longer is it going to be until someone finds another spot where the AI does something stupid that we couldn't foresee? If not infinite, I'd expect they grow exponentially with the size of the game and number of actions an AI can perform.
And even if they fix thet, you might still think the AI sucks. It's good for what we're used to - but its not fulfilling the promise of unscripted, unlimited conversations, or its voice isn't right. Or perhaps it doesn't react as it should (you're the boss and you still have to walk the streets like a common thug?) or its "vision" doesn't see your subtle movement. Or you can hide in a corner and they are looking around for you, even though you are plainly visible. The possibilities are seemingly endless.
So certainly the "oh god" moments are a result of "states not originally thought of during testing and development." However, my hypothesis is that because of the size of the number of states possible, we can neither think of all of them, nor can we program it in a brute force way such that the algorithm covers it all.
Posted by Sammy Larbi
on May 16, 2008 at 09:56 AM UTC - 5 hrs
I think NP is a red herring. Humans aren't solving NP-complete problems. They're using approximations. It's unlikely they're even performing high-degree polynomial algorithms. I wouldn't even be surprised if a human brain is incapable of solving problems beyond O(N log N).
It's not the complexity that is the problem. It's the size of the problem. The brain runs many millions of tasks in parallel. Serializing those tasks is what makes computer AI slow. Reducing the size of the data, choosing game designs that are more amenable to AI, getting better approximations, and harnessing parallel processing are what will give us better AI in games.
Posted by Amit Patel
on May 19, 2008 at 11:51 AM UTC - 5 hrs
@Amit: I am not qualified to argue about what class of problems humans are solving when they are "being human," so I will grant your assertion that we're not solving NP-complete problems. =)
However, I think that the complexity and size of the problem you are talking about, along with the brain running massively in parallel goes against your assertion.
I don't think the problems we're attempting to solve in a lot of AI /need/ to be done serially. There is a small "n" so to speak as input, but the problem complexity explodes that to 2^n or greater. If we had the parallel power of the brain (which, for purposes here is equivalent to a nondeterministic machine) in a computer, then indeed these problems could be solved in polynomial time - thus, NP (nondeterministic polynomial time).
Anyway, by complexity, I meant computational or storage complexity - not algorithmic complexity. I suspect that miscommunication on my part may be the source of our seemingly divergent opinions.
Posted by Sammy Larbi
on May 21, 2008 at 08:29 AM UTC - 5 hrs
There really are two types of AI in games: the "fake" type, which makes your NPC's walk around on a seemingly meaningful path while the has nothing else to do (scripted,...really...) and the real AI (where your squad leader could learn, presumably from enemy behavior and your input as to whether the squad performed the right actions (Neural Net, BC3000 style anyone?!)
The huge dilemma for me is this: we could reproduce a lot of the fake AI behavior with "real" AI methods, maybe even see some emergence crop up here and there....but we would be using 100x the processing power, and our results would not be deterministic, which is something a game-play designer would just hate....There isn't even any guarantee that players will like it!
On the other hand, every now and then, there are games where there is a "real" AI problem to be solved, and there is a "real" (read: Academic!) Ai algorithm to solve it...and this is where I get really pissed: Management still wants us to do it via the "fake" AI! This has to end...otherwise there will never be a push for more CPU power from the AI side of games, and if we don't push...those render-hogs just won't give it to us! ;)
Good read ;) keep it up.
Posted by Babak
on Dec 27, 2008 at 09:01 PM UTC - 5 hrs
I'm not in anyway experienced in game design, creation, etc. But what you all are talking about here really interests me. My favorite aspect of games is to "toy with" or test the AI. In Oblivion for example I would steal all of a certain NPC's belongings (food, money), in an attempt to drive them to violence or crime. Never worked though, in a preview they had said that Skooma dealers would get killed constantly b/c of skooma addicts "want" for the drug, sadly they took it out b/c of lack of control and the PC would never know it happened anyway. In GTA4, I like to shoot one of the diner patrons and and run outside where the mobsters that protect the diner start shooting at you. I then call the police in and watch how they react. You can also get regular citizens to pull weapons on you, usually in Jersey. Anyway I guess my point is that I would like to see more of these "needs" to affect the AI. Sometimes I wish the devs would leave AI "broken" to an extent, b/c usually what I hear in previews sounds far more robust than what we get, albeit "game-breaking". Or maybe that's just them hyping the game, who knows. anyway regular joe's 2 cents.
Posted by Brent
on Apr 22, 2009 at 01:30 PM UTC - 5 hrs
@Brent: If you enjoy toying with AI and thinking about what goes on, you might enjoy this article from Gamasutra: Intelligent Mistakes: How to Incorporate Stupidity Into Your AI Code (http://www.gamasutra.com/view/feature/3947/intelli... It talks about how in reality, we have to program AI to be somewhat dumb, because we have the ability to make the computer act perfect with its shots (among other things), yet it would be no fun for the player if they lost every time.
Posted by Sammy Larbi
on Apr 23, 2009 at 08:18 AM UTC - 5 hrs
Game AI has come a long way since 