Slashdot Mirror
A Look At Modern Game AI
IEEE Spectrum is running a feature about the progress of game AI, and how it's helping to drive AI development in general. They explore several of the current avenues of research and look at potential solutions to some of the common problems.
"The trade-off between blind searching and employing specialized knowledge is a central topic in AI research. In video games, searching can be problematic because there are often vast sets of possible game states to consider and not much time and memory available to make the required calculations. One way to get around these hurdles is to work not on the actual game at hand but on a much-simplified version. Abstractions of this kind often make it practical to search far ahead through the many possible game states while assessing each of them according to some straightforward formula. If that can be done, a computer-operated character will appear as intelligent as a chess-playing program--although the bot's seemingly deft actions will, in fact, be guided by simple brute-force calculations."
I have to say that the AI in Far Cry 2 is definitely one of the worst of current generation video games. I couldn't play that game for more than a couple days before getting utterly bored and frustrated at the idiotic AI.
Enemy Territory: Quake Wars, on the other hand, has some of the best AI I've seen AND its a multiplayer game. The bots' ability to attack and defend objectives while using infantry and vehicle skills against the random actions of human players is incredible.
Since you used an example from a role playing game , I'll respond with similar. Disclaimer: I'm totally hot for genetic algorithms, ever since I saw this article on pathfinding.
Oftentimes, a player character's "best" moves are limited by other factors rather than just needing to push the button - does he have enough combo points? does he have enough mana? is he in range? and so forth, before it's even a valid choice. Using a more complicated getInformation set than is outlined in the pathfinding program linked above, let's lay out what the mob can find out:
How many hostile enemies are there? .. And so on - I'm sure there are more checks you could give the AI access to - probably even depending on its intelligence.
What kind of targets are the hostile enemies (ranged, melee, soft [rogue,mage,etc], hard [warrior,paladin])?
How hurt is each target?
How much damage has each available target done to me?
How much healing has each available target done to other hostiles?
How devastating have the non-damage abilities of available targets been to friendlies?
Which abilities are available to me?
Which status ailments do the available targets have currently?
Add up levels of opponents and levels of allies. Who is larger?
Which ability did I use last?
Then there are the actions the MOB can take:
Choose target (can target self)
Attack target (melee)
Attack target (ranged)
Use ability on target (repeat for however many abilities are available to the MOB - limited by mana, and so forth)
Run away
Close distance
Run to ranged distance
It would take quite a bit of training (you could probably automatically cull the first several generations, but later on you might actually have to interact with it yourself), but this kind of technique could end up with some very "smart" AIs that are fun and challenging to play against. You don't get God AIs, because they have limited information. You don't get God AIs, because their abilities are limited - and not by simple randomness. You might actually get an AI that stuns you and runs if it realizes it's outmatched, instead of stupidly sitting there and whaling at you with its rusty sword of crumbling.
Granted, genetic algorithms have some HUGE drawbacks:
The decision tree can be quite large, and it can take quite a few cycles to evaluate. Of course, as your fitness check you could check how long it took to execute.
It can take quite a bit of training (hundreds of generations, with thousands of entities each) before you get something that resembles an intelligent algorithm.
Meanwhile, it might generate something that checks for contingencies you never thought to bake into the AI script.
GAs are interesting, but they're definitely less dynamic than the other approaches I mentioned. As you pointed out, GAs are much too slow to use on the fly, you have to prebake them. That has both pros and cons, the obvious con is that if you ever tweak any of the parameters, you'll have to rebake all of your behaviours. The obvious pro is that you can actually see the complete behaviour, and you can manually tweak it (if necessary).
Canonically, a GA is used when the search space is simply too large to search exhaustively. I'm not convinced that that's the case for most games, especially if you can apply a bit of domain knowledge to prune out irrelevant decisions.
I'm not saying GAs are pointless for real time games, but you'd probably need to use them in tandem with some more traditional game trees as well. (You also don't get God AIs because GAs generally don't find optimial answers.)
Game! - Where the stick is mightier than the sword!
Operation Flashpoint and its sort-of-sequel Armed Assault does something along these lines. The AI has a field of view roughly corresponding to what most players have in a first person shooter (~90 degrees), and the AI can't see you if you're outside this field, but he can hear you if you do something noisy.
Time of day, weather (rain/fog), foliage, obstacles, stance, movement speed and inherent camouflage of the unit will affect visibility and 'audibility'. Each weapon has two properties describing how visible and how audible it is, so a .50 calibre rifle will light up as a Christmas-tree and a silenced pistol will be almost undetectable.
The AI shares information the same way players are forced to share information: by communicating it to its squad mates. When a bot spots an enemy, he will relay what he knows about that enemy with varying degrees of confidence and then start acting based on his standing orders. His group will react to this information in what's usually a logical way.
The specific situation you refer to, with the shot ringing out and the AI reacting to it, is one you will see quite often if you play these games. When you shoot any enemy AI in the area will start to learn things about you, the first of which is they know there's enemies about that are shooting, so they will hit the deck and run for cover. Pretty soon they will know your location and then two things generally happen: AI with machineguns, grenade launchers, sniper rifles and RPGs will seek cover near their current position and start firing towards you. Other AI will start moving to your last known position. If you stay put for too long, you will be overrun.
Now this of course sounds like the perfect AI, but there are naturally some issues. Sometimes the AI learns too much about you when you fire a weapon. The best example is C4 charges. Place some on a road, hide a ways off in some bushes, blow a truck up as the convoy passes. Now *all* the surviving AI in the convoy will have a fix on your location. Sometimes the AI doesn't learn enough of your position so instead of reacting logically to being fired upon (cover, suppressive fire, flank) they will just run around seeking cover, making it very easy to pick them off. There are some big path-finding issues when there's many obstacles around (such as in towns), particularly when the AI is operating a vehicle, so instead of chasing you down with their big-ass tank they will spend the better part of an hour trying to get through town.
When it works though, it's great.
By the way... modern chess engines have an effective branching factor of about 2 (certainly less than 3)
There may be 36 moves available in a typical position, but the engine will almost always have enough information to examine the best move first or second, and then rapidly refute all of the others by proving that they are inferior to the fully-examined first move (i.e. a beta cutoff).
The effect is that it only takes about 2 full plies of extra depth to get a decent strength improvement (50-100 ELO).
Here are two great examples of using evolving neural networks to drive game AI:
Nero:
http://nerogame.org/
Galactic Arms Race
http://gar.eecs.ucf.edu/
They're both the brainchild of Kenneth Stanley.
His current research can be seen here:
http://eplex.cs.ucf.edu/
I am not talking about giving the AI any more information than the user has, nor any special controls/interface. When I say games have rules, I mean in regards to movement speeds, damage, and the like. A machine can process these things and respond to a changing environment quicker than a human.
3D image processing in a game is finite (especially using low-res models like in CS), and there are only 4 different heads to recognize for each side.
In a small data set like this, NNs can and will quickly outcompete humans.
I'm not sure if this is exactly how the NN would evolve to function. I'm thinking it would be evolutionary advantageous (shorter processing times) for them just to use a wall following tactic and shoot at anything that matches one of the four enemy heads. That's one of the problems with a genetic algorithm: you can't directly control how it will work. If I could isolate the selection pressure that would give an advantage to NNs that could recreate a 3D environment from a 2D image (even not in real time), I'd happily take your challenge. I don't really know anything about PoV rendering (except that it's almost impossible), so I can't comment beyond that.
Also, your analogy to driving a RC car is flawed: that analogy uses real world data, and Hebbian learning algorithms tend to balk when given completely new data sets (damned environmental stochasticity). Adaptation to new data sets is where our current ANNs models break down compared to actual neurons.
Obligatory Soundbite Catchphrase
That's because Go has enormous average branching factor (>300). Go is definitely not the simplest of all strategy games.
Game! - Where the stick is mightier than the sword!