Slashdot Mirror
The State of Game AI
Gamasutra has a summary written by Dan Kline of Crystal Dynamics for this year's Artificial Intelligence and Interactive Digital Entertainment (AIIDE) Conference held at Stanford University. They discussed why AI capabilities have not scaled with CPU speed, balancing MMO economies and game mechanics, procedural dialogue, and many other topics. Kline also wrote in more detail about the conference at his blog.
"... Rabin put forth his own challenge for the future: Despite all this, why is AI still allowed to suck? Because, in his view, sharp AI is just not required for many games, and game designers frequently don't get what AI can do. That was his challenge for this AIIDE — to show others the potential, and necessity, of game AI, to find the problems that designers are trying to tackle, and solve them."
Education can help; A lot of college CS programs don't force the breadth that an "AI game developer" would need. In my undergrad degree, graphics, AI, game programming, and distributed systems were "applications" classes, and you only needed one or two. Usually the game programmers would have to take graphics, because even if your the sound or networking guy, they'd expect you to know graphics like they did. If more game programmers had taken systems classes (such as operating systems), I don't think they would have had as rough a road with multicore either.
However, even given the current narrow classes, you can at least try to bleed through enough of the wider topics into game-oriented classes to get people footed. In the game programming course I was a teaching assistant for, I gave a couple lectures on AI (I was an AI/Robotics grad student). Then we gave them an AI-only assignment. It was a multiplayer tank game where we pitted their AIs against some test opponents, and then against one another in a tournament. It didn't allow much cheating in the AIs (only global visibility, where a player can see every unit at all times, which is nearly universal in game AIs). The assignment really seemed to be a hit, and hopefully for those students that went on to the games industry, it gave them the basis to branch out and learn other deeper AI techniques.
It would also help if the AI community wouldn't look down on things such as games as "lowly applications". In some sense I think game programmers would be best off talking to robotics people or even web machine learning people (spam filtering, web search ranking, etc). Those people are already doing applied AI, and particularly for robotics folks, working on many of the same problems that good game AIs would face.
When working on the RTS Empires: Dawn of the Modern World, we had a difficulty setting that was truly insane. The enemy wasn't a computer pretending to be a human, it was an impenetrable black wall of impending dismemberment. If you really wanted to defeat it, you had to pile-on 7 vs 1, with at least 3 top-notch players overseeing the operation. Those were long, intense, brutal battles... Helping to bringing down that beast was a real badge of achievement. Unfortunately we had to cut it back a bit before release for technical reasons, but the ability is still there.
A realistic FPS would have the enemy sneak up behind you and stab you before knew they were there. A realistic racing game would end in firey death the moment you accidentally rode up on the curb. A realistic tactical squad shooter would have your men pinned down by heavy opposition fire until they called in an airstrike on you. A realistic war game would involve lots, and lots, of digging.
This is a long way of saying that AI isn't about promoting hyperrealism, but rather is in service of making the game fun.
That having been said, I'd kill for 3D pathing that doesn't suck. If I need to do another escort mission with some idiot who can't walk around a boulder in the middle of the road, I'm going back to Tetris and I'm never leaving.
The ______ Agenda
I think that you are wrong about the AI community looking down on games as "lowly applications."
Well, at conferences such as AAAI, even robotics isn't treated as more than a "mere application". At least that's the treatment I felt going there and presenting work. Its ok I guess, because AI theory doesn't directly relate to where most work in applied AI happens (just like in applying machine learning -- most of the work is in the features, not the algorithms). However, I feel there is a real gap between what conferences such as AAAI are willing to embrace, and what happens at game development conferences or robotics conferences. Being someone who did RoboCup for many years, I really do know what it is like to span that gap -- some of the most important breakthroughs we made were not publishable in either type of conference. I really feel that the field lacks something like the AI equivalent of JGT (Journal of Graphics Tools) or Graphics Gems. If I were a more professorial type I might try to start something like that, but instead I just wait and hope someone else will, and then I could contribute to it.
I think that many posters here are confusing Artificial Intelligence with Machine Learning. The later is a subset of the former, but is often difficult to apply to games. Accepting adaptation is typically equivalent to abandoning Game Theory.
Other than the fact that applying machine learning successfully is difficult in general, I don't know if I really agree with that statement. Game theory is a subset of AI just like machine learning. Game theory is very important for abstract games such as chess, but I'd argue that most "physical simulation" games need things more like potential fields, advanced motion planning, high quality hand coded policies, and geometric stuff of that ilk. Old stuff like rule base AIs really has a place in games too -- the work done on scaling up expert systems is really like "software engineering for AI", and sadly a lot of that work didn't get published either.
A simple form of learning we used in our robotics work was weighted experts given a set of hand-coded policies (~= "a set of AI strategies" for the non AI people out there). We used that to learn during 30-minute autonomous robotics games against robotic opponents, and it worked, even during a relatively short game. All you need is a way to define successful subgoals (Ex: scoring in a team game, kills in an FPS, or areas won in an RTS) and you can get convergence to the optimal strategy in a logarithmic number of rounds. In a turn-based game, if those experts each applied game theory, you could have game theory and learning combined in a pretty reasonable way. Yes I know that would not be optimal, since you normally would just pick the strongest AI, but humans rarely play optimally, nor is even fun to always play against the same strong strategy.
Certainly there are entire fields of A.I. that are entirely unrelated, but there are many fields of A.I. whos core development is exclusively related to games.
True. I guess I just haven't really seen the dots connected. Then again, I haven't been to any AI conferences in the last year or two, so maybe that has changed already. I hope so.
Most games do not implement any heavy A.I. techniques because it is too difficult to provide skill gradients: Easy, Normal, Hard, Godlike. These skill gradients are pretty simple to implement as an escalation of "cheating," but not so simple as a tweak to AlphaBeta and pretty much futile with Machine Learning.
Well, here's another place where I think the communities need to work more closely. Coming up with search strategies that are more human-like when measured statistically would be fascinating work. Limiting search depth and random mistakes works in some games, but we could do a lot better. I think some of the commercial chess games already do a pretty good job of various skill
The problem there is that the two factors you mentioned (accuracy and commands-per-minute) are both things that AI can far exceed humans at, especially if you aren't careful to limit it.
You're correct. I've written AI for a number of commercial games. Some of the most challenging AI is for games in which the players are competing with the AI on what are supposed to be equal terms. An AI can home in on a player's forehead with a sniper rifle with little difficulty. It's a simple mathematical equation. How do you simulate the aiming a player has to do?
The solution I came up with was to put the target's aim point on a set of springs attached to the player. By jumping around and changing direction quickly, the player would tend to throw the bot's aim off (imaging the target bouncing around, attached by the springs). But, stand still or move in the same direction for too long, and the bot would home in on the player. And, of course, just like a human player, the AI would get in a lucky shot every once in a while as the target crossed in front of the player.
You have to come up with creative solutions to make the game "feel" fair. That's not the kind of stuff that's typically taught in college courses. Naturally, formal training doesn't hurt, but there are a lot of challenges unique to game development.
Irony: Agile development has too much intertia to be abandoned now.
But does increasing the I of the AI actually make games fun?
:).
:).
The Problem that AI is supposed to solve in most Games is not "how to beat the human".
The Problem is "how to make it fun for the human".
Creating an AI that can consistently beat humans is not hard. Making it fun for most humans might not be so easy.
Fact is humans aren't that good at most games (amongst other things). You don't have to be very intelligent to be good at most games. How many of you can beat a computer at chess at high difficulty? How many people actually _lose_ in tic-tac-toe - I've seen more than a few
It's often not hard to make a computer extremely good at a game, at least good enough to beat most people. But does that make it fun?
In most FPS games, stupid humans want to be able to mow down _thousands_ of stupider computer controlled enemies - "against the odds". That's what makes it fun for them.
That's just not possible if the enemies start having a lot more brains. Then most players might have difficulty getting past the first 3 enemies
It's not that difficult to make an enemy FPS "bot" have superb tactics, coordination, timing etc. Especially if the map is pre-known (which is usually the case). You can code the tactics and heuristics in. If you hear the player in position X, group A enemies head to position Y and group B head to position Z, and bye bye player.
Imagine if enemies that are low in health kept running away and hiding, and then snipe at you from far away when they see that you are busy doing something else. While that might be more realistic, it might not be so fun eh? Who really wants realism in games?
At that rate the player can never pretend to be the hero he wants to be. He'll just be dead. And your game won't sell.
Same goes for RTS games, believe me, you don't have to make a computer cheat to beat humans - a computer can micromanage better than most humans.
Just ensure that basic stuff like navigation is better. Stuff doesn't have to be that smart, but at least they shouldn't be totally stupid - they should be able to walk around stuff without getting stuck - even a "dumb" animal can navigate open spaces better than many computer controlled stuff in games.
Yeah, most people don't seem to get it. They show how stupid/ignorant they are by asking for "smarter/stronger" opponents.
It's trivial to program a computer to beat humans in most games.
But the problem AI is supposed to help solve in games is not "How to beat the human".
The problem AI is supposed to help solve is "How to make it _fun_ for the human, so that lots of humans will pay $$$ to play".
Most people would have near zero odds against a top notch computer opponent - FPS, RTS, whatever.
Does anyone really think that Starcraft, Doom etc would have sold so much if playing them was like playing against a World Champion or two?
I've seen the top humans play in FPS and they can aim pretty well. You'd never be the Hero winning against the odds if the _thousands_ of enemies you fought were even only half as good as a world champion.
1. I'll somewhat disaggree about RTS. Sure, in theory it sounds good, but I've yet to see a strategy game where the AI doesn't plain old cheat to stay alive.
Yes, it can "micromanage" better, in the sense of cycling through all units every frame or couple of frames. Sure, it can do a "for" loop better than a human. But actually allocate resources intelligently, apply smart tactics against a human who built in the unexpected place, etc, is where computers are still as stupid as it gets.
Again, we could argue about theoretically being easier to make them smarter, but way I see it, that's the basic rule of thumb: does it need to cheat? Does advancing in the storyline to face a new enemy, described as more cunning and ruthless, actually just mean the same retarded AI with a bigger pre-built base and more silos full of spice/tiberium/whatever and more reinforcements out of nowhere? Does it just mean that the new "cunning and ruthless" enemy just gets better units from the start? Does upping the difficulty actually just means that the AI gets even more money and a damage bonus, as opposed to just un-hobbling that supposedly super-AI a little?
If any of those are true, no, you have _not_ coded teh uber-AI and then dumbed it down for the player. You can claim to have a too smart AI when it can start just with a town centre and 2 peons, just like the player, and put up a better fight. And, oh, make it run just as long a way to the mines/geisers/spice-fields as the players, at that. Starting with 3 resource nodes in an already built base doesn't quite qualify as equal difficulty.
2. Yes, chess makes a good poster child, but that has had decades of real AI research into just that speciffic game, and at that by real AI researchers. A brand new game, with brand new rules, within 3 years, and with the cheapest team possible... heh... sorry. I can't take that seriously.
Most of the games so far have even trouble pathfinding, or keeping their flamethrower guys from frying their own team mates in front of them, etc. Or look at bigger scale strategy games, like Paradox's, where it takes several years of patching just to get the AI to no longer waste its whole army attacking Switzerland. And even then often the "fix" isn't as much AI, as just making fortifications randomly disappear in combat, so eventually the mountains around Switzerland just stop giving a defense bonus. You know, 'cause apparently 100,000 soldiers with rifles and grenades can demolish a mountain. And then invariably it becomes vulnerable in some other way, to some new exploit created by the previous fix.
3. Ditto for FPS. What the computer has as an advantage isn't really better AI, it's unerring accuracy. It's trivial to make a bot that never misses, and has faster reactions than any human, because it simply needs to calculate the angle and pretend it aimed accurately that way. It simply doesn't have the whole issue of moving the whole arm with the mouse, or the finite resolution of the mouse, or the whole lag of the pipeline from mouse to seeing the cursor move (the TFT alone introduces another 1-2 frames lag) which is already known to ruin one's accuracy because it lets you overshoot before seeing any results, etc.
Some cheat even further, by basically having eyes in the back of their head, or being able to see through walls, or just not having the issue of "does that 3 pixel tall figure over there look like one of our guys or one of theirs? Is it even a human?" It just doesn't have to parse an array of pixels, it already knows where everyone is. Even when you say "if you hear the player at position X", you're already cheating. A player can at most judge "I hear some footsteps in that general direction" (and even that at best in 30 degree increments), but not an exact position, nor know if it's a friend or foe or neutral there.
Give the computer a spread comparable to a human for the selected difficulty level, give it a similar lag in reacting and turning, and limit it to the exact same field of view, and that suppos
A polar bear is a cartesian bear after a coordinate transform.