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."

Comments

Holy Acronym Overload

[cjfs]

F.E.A.R. , short for First Encounter Assault Recon .... University of Alberta GAMES (Game-playing, Analytical methods, Minimax search and Empirical Studies) .... called STRIPS (for STanford Research Institute Problem Solver)

Combine that with such gems as:

players view the virtual world from the perspective of the characters they manipulate, making Counter-Strike an example of what's known as a first-person-shooter game.

and I'm not sure that belongs here.

Then again, maybe I'm just bitter that I still can't beat GNU chess.

College AI Project

[Dripdry]

Back in college I worked with a guy, Jeff, on an AI project. We were to play the game Freecell through to its finish.
(if you're reading this, jeff, I'm still sorry I didn't do more coding on that and I owe you one)

While I can understand the difficulties in doing a brute force search, and that a simplified "version" of the game could be helpful, OR even that parsed "states" or "instances" of situations in the game could be broken down and analyzed, wouldn't a simpler way be to use a fitness test on various actions? No, no... I lose points for not reading the article, perhaps.

We used a combination of fitness and searching to determine a way to win a Freecell setup. Admittedly this is VERY simplified, and done in a sort of static system as opposed to a (usually) dynamic one in games.

If there is less memory, the obvious answer seems to be to use a system to determine better ways of doing things. Rather than simplifying the game, couldn't the AI have a library of responses designed to fit certain situational profiles, then act in a (perhaps semi-random) manner that fits ? Perhaps the responses could be genetically determined, even.

Also, this use of situations versus individual actions could help lengthen the time the AI has to come up with a response.

Just some thoughts, though I'm sure others more experienced than me have these on the brain. I'm looking forward to the responses on this topic.

Re:College AI Project

[Mad Merlin]

Games of perfect knowledge versus an opponent are pretty simple to solve. You'll find they all basically boil down to minimax applied to game trees plus an evaluation function (which gives you a fitness value). There's also alpha-beta pruning and things like Negascout which are just optimizations for Minimax. The trickiest part of this is writing an effective (and fast) evaluation function.

Freecell is a bit different because it's a single player game, but ultimately you can apply a similar method as above.

Real time decision making in games is often quite different. One problem is that you don't necessarily always want to make the "best" move. In Game! for example, each monster has a regular attack and may have one or more special attacks. Using simple AI to pick one (such as, pick the attack that does the most raw damage) each time wouldn't be as interesting as picking randomly. Say one of the special attacks for the monster is to steal some gold from the player, why would the AI ever pick that? It doesn't benefit the AI at all, but it does make the monster more interesting to fight for the player. Similarly, if one monster has an absolutely devastating attack, a "smart" AI would always use it. But if the AI always uses the devastating attack then either that monster will be impossible to kill, or the regular attacks must be really boring. But, if the monster with the devastating attack only uses it occasionally, it keeps the player on their toes, perhaps they'll heal more often, or use more powerful attacks to try and dispatch the monster faster.

Having said all of that, random picking isn't always the best way to go (although it's quite efficient with CPU time). The main problem with game trees is their branching factor. Chess is a fairly CPU intensive game for AI to play, as it has an average branching factor of ~36. For real time games, it's likely that you can use domain knowledge to substantially prune the branching factor, which makes the problem much simpler. For example instead of considering to, say, turn left 1 degree, or 2 degrees, or 3 degrees or... you could just consider turning left 90 degrees or 180 degrees. If you only end up with a dozen options left to pick from, you can fairly quickly expand several levels of the game tree and then make an informed decision.

However, some games are not games of perfect knowledge (Backgammon, for example), often they rely on chance. In this case, the value of deeper game tree expansion rapidly diminishes, and you simply need to temper your fitness values based on the expected probability of that move being possible. The other problem with games of chance is that the branching factor is usually very high, which typically makes it unfeasible to expand too many levels in the game tree anyways.

Of course you can precook a number of situations, most good Chess AIs have a large collection of book openings that they use. It's really just an application of domain knowledge again, then you can reuse your game tree expansion with evaluation function on each of the book openings to find the most appropriate one instead of doing an exhausive search of all possible moves.

Re:College AI Project

[bishiraver]

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?
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? .. And so on - I'm sure there are more checks you could give the AI access to - probably even depending on its intelligence.

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.

Re:College AI Project

[Mad Merlin]

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.)

Re:College AI Project

[timbalara]

You bastard, now I'm working in the auto industry thanks to your lack of coding! - Jeff (I kid, I kid!)

Re:College AI Project

[Anonymous Coward]

"But if the AI always uses the devastating attack then either that monster will be impossible to kill, or the regular attacks must be really boring. But, if the monster with the devastating attack only uses it occasionally, it keeps the player on their toes, perhaps they'll heal more often, or use more powerful attacks to try and dispatch the monster faster."

The problem is balancing reality against unreality, if you give too much power to your AI monsters or opponents, the game is not going to be fun. There has to be some challenge or else you will get bored very quickly. Truth be told, the study of monsters/AI in and of itself is really it's own discipline, since you have to take into account a lot of things the more attacks/etc, you add to a monster, the more likely it is it will be even more difficult to balance.

Re:College AI Project

[mR.bRiGhTsId3]

As an interesting other direction, neural networks can make interesting state evaluators. The only drawback being that the must be trained ahead of time. You end with (theoretically) more flexible state evaluators in the face of changing game environments.

Re:College AI Project

[CodeBuster]

Games of perfect knowledge versus an opponent are pretty simple to solve. You'll find they all basically boil down to minimax applied to game trees plus an evaluation function (which gives you a fitness value)

All of which, when applied to the simplest and most abstract of all strategy games (GO), fails to produce a competitive program. Search has its limits, even in zero-sum, perfect information, partisan, deterministic strategy games.

Re:College AI Project

[JTeutenberg]

Despite calling them GAs, the grand-parent is referring to Genetic Programming.

Canonical GAs are never the correct tool for a problem. They combine a crude random local search (mutation) with the cross-over operator that is intended to splice partial solutions. The trouble is that even on problems designed to be exploited by GAs, like the Royal Road, a random restart hill-climber will perform better with the same number of fitness evaluations.

I'm not as familiar with GP, but given the minute number of attributes quoted and millions of fitness evaluations... I'd say a typical greedy tree learner would perform much, much better.

Re:College AI Project

[Mad Merlin]

All of which, when applied to the simplest and most abstract of all strategy games (GO), fails to produce a competitive program. Search has its limits, even in zero-sum, perfect information, partisan, deterministic strategy games.

That's because Go has enormous average branching factor (>300). Go is definitely not the simplest of all strategy games.

Re:College AI Project

[CodeBuster]

What could be more abstract than GO? The rules are simple, the pieces are simple, and the board is simple. It is the interactions that are complex. It is an example of what is called "emergent complexity" or complex situations arising out of a simple set of rules in an evolving environment. It has also been said that if there is intelligent life somewhere else in the universe then they probably play GO too.

Re:College AI Project

[Anonymous Coward]

Games of perfect knowledge versus an opponent are pretty simple to solve.

Are you high? Go is the classic hard-game-to-implement, and it's a game of perfect knowledge against an opponent.

Lest we forget...

[Anonymous Coward]

...that chess-playing programs are also brute force.

one important point

[SirSlud]

Article is pretty bang on. Adaptive AI is tough to do, as is balancing being a tunable-level of smart and being beatable. One thing I have not seen enough of in games is AI agents communicating with each other about intentions. More often it is simple a matter of saying, "I'm in this area, so don't try and go here." I've yet to really feel in a game that the enemies are working together. I saw a very nice presentation on Halo 3 high level AI at GDC 08 that kind of nailed some of these problems with a pretty simple solution - there should be some top level AI manager that handles requests from AI agents on what to do next when a high level goal becomes useless to attempt to achieve. Left4Dead sort of deals with this, not by talking to agents that are still alive, but by deciding when to introduce new agents, but the Halo 3 approach to me seemed very elegant. It was higher level AI than the article was talking about, but in effect it was a similar setup: AI achieves something, and says, "What's next?" Since the AI manager would know the state of the other enemies in its unit, it could decide that you might as well not start firing at the player since the two others were doing that. Maybe some other game vets could clue me in, but I havn't seen too many games like that where a module is advising the AI based on balancing attack/protect/advance ratios during gameplay. /framework/tools programmer //not AI programmer

Re:one important point

[hax0r_this]

Actually, what the article is talking about is typically applied in systems of multiple levels of AI. Consider an ideal squad based shooter:

1. Command AI issues squads orders (do/accomplish something) based on a very simple model of the battlefield
2. Squad AI issues individual units orders (go somewhere) based on a more detailed model of the immediate area.
3. "Conscious" individual AI computes a good way of following orders from the squad AI based on yet a more detailed model.
4. "Subconscious" individual AI makes moment-to-moment decisions, for example about how to avoid minor obstacles that the "conscious" AI ignored.

Of course that is very idealized.

Re:one important point

[Nanidin]

This sounds like a great approach. If you read my post below, many of the teams start at what you have called the Conscious Individual. If they finish that with enough time, I've seen them move on to the Squad and Command levels also. The main difference though is that since our game state has traditionally been pretty simple, there hasn't been a need to compose a simpler model of the state for the upper levels.

The multi-tiered AI approach does seem very useful and intuitive though.

Re:one important point

[theheadlessrabbit]

interesting idea.

let me make sure i understand it correctly:

an RTS AI took a FPS AI out for a couple of drinks, and the resulting offspring would be an awesome AI that can work in teams to defeat all humans.

i'm sure someone can throw 2 AIs together relatively quickly, release a game and see what happens.
maybe a command and conquer: renegade 2?

Re:one important point

[rdnetto]

Wouldn't that behavior be unrealistic though, since the NPCs would 'know' things that they shouldn't? e.g. that they have a bunch of allies hiding behind that wall. If each NPC acted individually, perhaps they could use swarm-based behavior when they teamed up.

Re:one important point

[tucuxi]

Additionally, a multilevel AI helps to even out the use of CPU. You don't want to take high-level command decisions every quarter second, because that would not leave enough time for any of the lower tiers to do anything useful, and would require too much CPU. With a multi-tiered AI, you can dedicate small and frequent AI slots to low-level decisions, and hold high-level decisions for less frequent and more CPU-intensive thinking.

Re:one important point

[tucuxi]

Depends on the setting. It makes perfect sense within a networked-battlefield scenario: what one unit sees, it will try to convey to others, and commanders can take decisions based on everything that is seen by any of their units.

In a medieval setting, they would have to shout to each other (and be within hearing distance) to request assistance. Or wave colored flags, or send messenger pigeons.

The radio squawking in Half-Life added an element of realism to this - you could actually "hear" what the bad guys were "saying" to each other. Even though it was crude: it would have been even better to hear things like "he's hiding behind the wall" or "he's nailed Bob! the #@!"

Re:one important point

[Anonymous Coward]

The radio squawking in Half-Life added an element of realism to this - you could actually "hear" what the bad guys were "saying" to each other. Even though it was crude: it would have been even better to hear things like "he's hiding behind the wall" or "he's nailed Bob! the #@!

In FEAR, the radio chatter was a lot more elegant than Half-Life. Not surprising, given the disparity in when they were made.

They did, in fact, say, "He's in the walls!" or, "He's in the ceiling!" when a squadmember detected you there.

As for nailing Bob, if you got a headshot on a member of a squad that didn't know you were there, one of two things would happen. If they traced the shot, they'd open fire. If they didn't, they'd yell, "Holy shit!" or, "Where the fuck did that come from?"

It really did at a lot of verisimilitude. Of course, the drawback was that 90% of the enemies you fought in FEAR were squads of troopers, so you had advanced warning of nearly every fight in the game.

Re:one important point

[msbmsb]

As an NLP person, what I would love to see/develop is AI that "listens" to the players. Take for example a game like WoW or Halo where the players are chatting publicly (text is easier than speech) with each other about their next motion or attack or defense moves. If the AI was within "hearing" range, it could pick up on that public chatter and if possible, decide to counter in someway or ignore it as if it was diversionary or irrelevant (or simply misunderstood).

It would be an interesting experiment at least.

Re:one important point

[Hyperspite]

I think the real problem with that isn't a technical one (although it would be really really really cool!). If you make it so players have to shut up in a dungeon or whatever, they'll just use an alternate means to communicate (ie telephone or voip). This will destroy immersion and annoy players. The only way this could work is really in a single player game where you have to talk to NPCs in english....

Re:one important point

[msbmsb]

Players would have the option for easier communication at a risk, or would have to find some other way to communicate which would carry it's own advantages and disadvantages, which I think is a reasonable disruption in modern gameplay and not one I'm so sure would annoy players so much.

Plus, methods like true, range-based "whispering" could be useful, and would also carry with it some interesting risk (i.e., the intended person wasn't close enough to hear). The fact that a particular AI might only understand one or a handful of languages seems fine to me.

I'm sure others have had similar ideas, it's just one that has interested me for a while.

Re:one important point

[VeNoM0619]

Except an RTS/FPS AI merge wouldn't accomplish certain aspects of strategy.

An RTS decides 'what' units to make, but does nothing about what to do with a current group of units. Nor does an RTS decide what to do in battle; have x units do this, while y units do flank. If unit z is below condition w, retreat/heal other units. Instead it simply says: I have x units. Send them all in to attack... No attack strategies, just build strategies. Hardly useful in an FPS when you are using 'pre-built' units to attack with.

Look at the scripting for AIs (I have only looked at starcraft's) in RTS's for a general feel of how it is done... It isn't really all that intelligent, especially since it knows the entire map. Hell, in half of the RTS's, the difference between normal and expert is whether the game cheats and has unlimited resources.

Re:one important point

[mcvos]

Article is pretty bang on. Adaptive AI is tough to do, as is balancing being a tunable-level of smart and being beatable.

Being beatable? I keep forgetting that in FPS games it's so easy to make near unbeatable bots. I'm a strategy gamer, and I'd love it if someone would make an unbeatable AI. Or at least a halfway decent one. Strategy is the area where some real advances in game AI are still needed.

And then there's CRPGs of course, but I suspect that's another order of magnitude harder.

AI? In video games?

[Anonymous Coward]

If modern games are an indication of AI, then they're obviously smarter then we can hope.

Just today, the AI in Far Cry 2 spotted me at long range after 1 shot with a sniper rifle, proceeded directly to me, despite heavy foliage for cover.

Color me impressed. Even Sherlock Holmes would be proud of how quickly they deduced where I was.

Re:AI? In video games?

[JoshJ]

The problem is that internally the game "knows" where you are- after all, it has to track your location.

Every play against someone in counterstrike who was hacking? Wallhacks, aimbots, the whole nine yards? There's really nothing at all stopping the developers from doing that; and in fact some older games basically did do that, just with arbitrary delays before the AI snapped on you, deliberate fudge factors on accuracy, whatever it took to make the difficulty level sane for a human player.

It's possible to compartmentalize it, of course, so it doesn't know that; but you as a player have no idea which approach they took. If the AI is incredibly good in a game, it's possible it's "cheating" and doesn't really have to deal with hidden information.

Re:AI? In video games?

[acidrainx]

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.

Re:AI? In video games?

[Eivind]

That is true. The computer is simply very different, so modeling our strengths is just as hard as our weaknesses.

It's trivial for an AI-controlled enemy to get headshots all the time. It's trivial for the AI to have complete knowledge of the battlefield and state of all items and characters on it. Humans can't do that.

It's a lot -less- than trivial for an AI to notice patterns in the enemy and exploit them. Thus the same approach tends to work 100 times against the same AI. It can't learn from its mistakes.

Re:AI? In video games?

[cheater512]

I remember some bots for Quake and bots for bzflag which connect as regular users.

That is a very good way to start an AI.
The fudge factors can be toned down a lot because it cheats less.

Re:AI? In video games?

[bishiraver]

So very true. A huge improvement to the AI would be visibility determining. IE, the AI might be able to tell the shot came from the southwest, but it can't see you exactly because of all the foliage - to root out the threat, it sends a squad to comb the area.

Unfortunately, the squad pulls out a giant comb and starts running it through the foliage..

Re:AI? In video games?

[bishiraver]

It could if the AI decision tree were a genetic algorithm.... each entity gets its own decision tree, and the ones that survive mate. :P

Of course, that only really makes sense in an MMO 'verse.

You could do some AI juggling, so that after every map (or every time the AI loses), it runs its algorithms against all previous scenarios until it wins (or at least, gets better at not losing).

But then you end up with an AI that wins all the time, and a huge amount of CPU cycles.

Re:AI? In video games?

[stjobe]

But then you end up with an AI that wins all the time

And we don't want that. We want an AI that wins some of the time, and that is beatable. That is, it should present us with a challenge, but the challenge can't be too great because then the game will be no fun.

So, we only want a smart-enough AI, not a god AI.

Re:AI? In video games?

[tucuxi]

You are overly optimistic regarding GAs. I very much doubt that, whatever the AI cycles, you can evolve an AI team capable of winning against a good (as in top-third of the table) human team at, say, counter-strike.

Gotcha: the AIs would not be allowed to cheat, and would have the exact same information at their disposal as the human team: a lot of visual input (but not the actual noise-free game geometry) and the same set of commands as human players.

If you can evolve that kind of AI, the DARPA Grand Challenge is looking for you.

Re:AI? In video games?

[kungtotte]

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.

Re:AI? In video games?

[bluntman2008]

Of course you could (assuming enough processing power), just have all the AI team constantly spinning 360 degrees and performing pattern matching on the visual input , as soon as a potential match is made fire at it ( to stop friendly fire have all the AI team choose the 1337 outfit and match against colour ). Also the DARPA challenge has already been beaten using pattern matching and learning algorithms (http://www.darpa.mil/grandchallenge/index.asp).

Re:AI? In video games?

[bluntman2008]

Doh, I missed the caveat about it having to be an evolved algorithm, but I still think it could be done.

Re:AI? In video games?

[Anonymous Coward]

Everyone of my gaming friends agree that QW has the best AI we've ever seen. I've spent some games just following AI snipers to see where the best spots are.

Sometime it is hard to tell the difference between the bots and real players. It's only the absence of bad squeaky singing, incessant excuses about lag, and numerous opinions about my mother's sexual preferences that gives the game away.

Re:AI? In video games?

[thepotoo]

I think you're under-optimistic regarding GAs.

They can, with training (just against themselves!) beat human opponents at simple turn based games (citation). That's the same level playing field you describe.

It's been 10 years of GA optimization and theory, and 10 years of Moore's law since then. Computers have much better reflexes than humans, and you're telling me that a GA couldn't beat a master at CS?

Tell you what: give me $50,000 in funding, six months to train the AI to general FPS rules (headshot, movement, general weapon effectiveness, etc.), and another six months for the GA to advance it for CS, and it will beat anything.

If I had to pick an approach to take right now, I'd partition up the tasks (defuse bomb/identify player/is friend or foe/aim for head/etc.) to various independent, co-evolving, ANNs. There might be a better way, but that approach seems have worked pretty well for these guys (albeit that's not real time).

The point is, games have rules. Once you've learned the rules, you're unstoppable.

Re:AI? In video games?

[thepotoo]

Did the AI improve in later patches? Because I played QW when it first came out, against my brother (LAN) and the bots were as dumb as they come. Constantly driving vehicles into walls, running in front of me while I was shooting to try to give me a med pack, standing up out of cover to reload.

It was a game-ruining experience, and if it's actually been improved since then, it would probably make QW worth playing.

Re:AI? In video games?

[cptnapalm]

Man that is nothing.

Game: Far Cry 2

Time of day: 3 AM

Weather: Thunderstorm.

Distance: 200-300 yards

Location: Jungle with heavy undergrowth.

Position: crouching behind a tree, not moving.

Result: Spotted and snipered.

Re:AI? In video games?

[blahplusplus]

"The point is, games have rules. Once you've learned the rules, you're unstoppable."

There is an enormous difference though, the computer doesn't have any of the deficiencies of the human mind to get in the way. Most human beings 'wing it', most thought is 98% unconscious, therefore most of the time what you are testing how good someones unconscious processing is.

You'll probably find the following interesting:

(Quick version)
http://i35.tinypic.com/10fruxh.jpg

(Longer version)
http://www.linktv.org/video/2142

To get to the good part, watch from 15 minute mark to ~25:00

Re:AI? In video games?

[tucuxi]

games have rules. Once you've learned the rules, you're unstoppable

Ah, but I want both to play the same game, while your are suggesting giving the machine a special representation with a high-level vocabulary. The interface I am proposing is the same one you are using: images and sounds come out and commands are executed. Not "high-level game data" - only images and sounds.

You talk about teaching the AI how to headshot. I am talking about the difficulty of processing a 2D image and interpreting it as a PoV rendering of an (unknown) 3D model, and locating a set of pixels that happen to compose the 'head' of something that is an 'enemy'.

Tell you what: give me $50,000 in funding, six months to train the AI to general FPS rules (headshot, movement, general weapon effectiveness, etc.), and another six months for the GA to advance it for CS, and it will beat anything.

If I give you 50k $, will you sign a document agreeing to deliver accurate 3D model-building from a (sythetic) video in real-time or give me my money back plus interest rates?. That's what I was referring to when I wrote about the DARPA Grand Challenge. You and me can both pilot a remote-control car with a wireless lo-res camera slapped on top. Try to teach a computer to do that reliably, and you have solved many, many problems in AI.

Re:AI? In video games?

[BigJClark]

I'm pretty sure he was joking. Welcome to Slashdot, enjoy your stay.

Re:AI? In video games?

[Hyperspite]

Just adjust your fitness function accordingly :P

Re:AI? In video games?

[Anonymous Coward]

Sounds like what I and others I know encountered both from insurgents and from our own mates in Iraq.

Add in a 'stress' indicator or other pseudo-personality to the AI at the individual level and you start getting something that would really be a close simulation to actual combat environments.

Fog of War in information retrieval and dissimination, misqueues based on misunderstood or incorrect information, 'fear' based non-optimal reactions, etc.

One thing that never seems to be present in any MMO or tactical game is a sense of the passage of time.

Fatigue, mental and physical, needs to be an element in the decision process of any AI just as it is with humans. No, I don't get physically exhausted sitting in my house playing a game, but after running a series of missions or quests for 8-10 hours straight with very few breaks, mental fatigue definitely becomes a factor.

Re:AI? In video games?

[thepotoo]

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.

accurate 3D model-building from a (sythetic) video in real-time

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.

Re:AI? In video games?

[acidrainx]

Yeah they made some major improvements in later patches. Although I never saw them drive into walls. It's obviously more fun to play against human players and I would suggest that over playing against the bots, but the AI is still some of the best I've seen.

Re:AI? In video games?

[VeNoM0619]

So, we only want a smart-enough AI, not a god AI.

So the problem becomes: we don't want it to beat us all the time, but if we make it smart, it will beat us, but we want it to be smart!

So the solution is: make it capable of beating us all the time. Then flip a coin to determine if it will choose the winning strategy, or sit like a lame duck so it won't win all the time.

Re:AI? In video games?

[tucuxi]

Machines "can" do all sorts of wonderful things, but so far nobody has been able to get them to do them. Please cite examples or research that demonstrates accurate real-time 3d modeling from a synthetic 2d video, or stop making things up. Yes, I am sure it can be done. No, I very much doubt anybody can do it right now.

You say that synthetic video is finite. So is 2^256, or the number of grains of sand in the beach - what is your point? Are you suggesting that finite is always manageable?. Ok, maybe you can pick up a head from the background, and even shoot at it real quick. Good luck with navigating the map and defusing the bomb with visual input alone; fortunately, CS is not all about sniping, and a good human team can easily counter a dumb-but-accurate ai-sniper team. Probably with lots of grenades and shields, and good ol' cooperation to rush weak spots.

My analogy to the RC car hints at a larger problem. FPS games are not entirely self-contained, they try to reflect a lot of things that, for an AI, should also be considered rules: a 3D world, geometry, light, physics, ballistics, sound propagation. That is a huge amount of implicit rules we are talking about. And some of those (such as robust visual processing) are tough to teach. Playing chess is easy - just throw in more processing power. Vision is hard: nobody knows exactly what to do with extra power.

ANNs are still in their infancy. It is not that our current models break down in certain cases -- they only work well in certain very specific tasks, and we are quite clueless regarding how to design, say, a roach.

Re:AI? In video games?

[Zaatxe]

You should have been modded insightful, not funny. I saw the same happening in Left 4 Dead: my AI companion survivors could "see" the zombies through the heavy foliage, but I could not.

Re:AI? In video games?

[thepotoo]

I cannot find any citations for 3D modeling from 2D video, but I didn't look very hard. You're probably right, it's beyond current models.

I think you're missing what I'm trying to say here, though. A sufficiently advanced neural network may be able to play CS without the need for actual 3D processing.

I'm pretty sure that I'm right, but I really can't prove it without more time and a supercomputer to run it on. I'm currently writing proposal for a grant so I can model the selection pressures leading to the evolution of the human brain, if I get funding, it would be simple to modify my proposed algorithm to play CS. I'll get back to you in about 5 years with the results, assuming funding doesn't fall through.

Also, we are a little less that clueless on the design of a roach. Insects are simple, stupid creatures that are still around because they can survive in many environments and reproduce quickly. They are a poor model for any AI, as they don't show nearly as much Hebbian reinforcement as other, more "advanced", species. If we could create a mouse-level intelligence, OTOH, we could "easily" select it up to a strong AI given a few decades.

Re:AI? In video games?

[mcvos]

But then you end up with an AI that wins all the time

And we don't want that. We want an AI that wins some of the time, and that is beatable. That is, it should present us with a challenge, but the challenge can't be too great because then the game will be no fun.

So, we only want a smart-enough AI, not a god AI.

I'd love to see god AI, but then, I'm a strategy gamer. AI is really bad at strategy.

Game AI For Fun

[Nanidin]

The ACM Chapter that I preside over at Missouri S&T (Formerly the University of Missouri - Rolla) has been writing simple RTS games with AI APIs for the last two semesters. We're currently working on a third game to add to our repertoire. We host a tournament at the end of each semester and invite anyone that will come - the main site is at http://acm.mst.edu/~mstai. The API is easy enough to get a handle on that a C++ novice could pick it up and do something with it within a few hours. Competitors are given 24 hours to write their AI, then we pit them against each other. Generally speaking, for the RTS style games we have written, AIs that act on an individual unit level only perform the best (both in execution time and scoring). This is probably due to the 24 hour time limit imposed, but it does show that even simple/greedy algorithms can perform well in game AI situations. I believe the winning team of our first tournament had an algorithm that went like this: for each unit: doBestActionForUnit(unit)

Re:Game AI For Fun

[nevermore94]

I have recently started playing Balanced Annihilation based on the Spring game engine. http://spring.clan-sy.com/ The game has mainly been oriented to online play, but at least 3 good working AI's have been built by the community and I have enjoyed pitting them against and watching how they behave. http://spring.clan-sy.com/phpbb/viewforum.php?f=15 You can almost anthropomorphise them to have different personalities. Being that it is all free and open source, if you are interested in RTS game AI, you may want to check them out.

Simplify and use heuristics

[syousef]

So what they're saying is simplify and use heuristics? Hasn't this been done for years now. One some level every single game out there does it because you can't model the real world 100% and the state you're considering is therefore simplified. What they're saying is simplify further by considering a subset or creating a model of the model that makes up the full game.

In the case of simplifying further, isn't this exactly how a chess engine works?

In the case of making a simplified model, I'd be surprised if lots of simulators didn't already do this - the trouble with this approach is that your simplified model may not behave well (ie. as expected) under certain conditions and even corner cases can break the illusion pretty badly.

Artificial intelligence, isn't

[Iamthecheese]

If you're deciding between "intelligent" and "beatable" then you're not talking about AI. An average person far outclasses, in any sufficiently complex game, a computer in the area of general intelligence. Knowing the physics equasions for a certain hit, being able to throw a hundred commands per second at your unit, having 100 percent perfect aim, these things don't involve intelligence. A game that can, without cheating beat a person on equal footing will be intelligent. I don't think there are any.

Re:Artificial intelligence, isn't

[Anonymous Coward]

You seem to define cheating as the ability to do better than a human on some aspect of the game (like speed or aim). That's not cheating. In gaming, cheating is using computer abilities in a venue reserved to humans.

Re:Artificial intelligence, isn't

[mcvos]

Cheating is the AI using information that it wouldn't have if it was a human. Like looking through walls or dense foliage, and firing each shot with deadly accuracy because it knows the exact coordinates of its target. That's cheating. That used to be common in strategy games too, but nowadays people want strategy games to have a level playing field, and that means the AI loses big time, because no AI is capable of grasping complex strategic situations like a human can. Maybe that's easier on the tactical scale of FPS games, I don't know.

Bungie's Awesome Halo AI

[Anonymous Coward]

http://ca.youtube.com/watch?v=F7pjw8vs6Ug

I guess I would spend my time babbling about AI at conferences instead of actually getting my shit working if I had Microsoft spending ten million bucks buying reviews and saturating the press with marketing.

same algorithms different game

[Anonymous Coward]

more boring weighted graph walking. Stuff displayed by games are incremental technological improvements but not actual AI/cognitive science that will lead to strong AI. e.g. the game developers (whether that's chess, go or FPSs) don't have any motive to solve the symbol binding problem, so the machine doesn't even know it's playing a game.
There was a primate intelligence documentary on PBS a while back which paraphrased concluded with "perhaps they're intelligent. or perhaps our interpretation of their behavior says more about us humans as social creatures perpetually seeking to ascribe intent to actions than it does about them" The machine didn't /want/ to pull off a clever flanking maneuver, or understand what it's doing any more than your computer "wants" a DVD when the drive opens.

So it's not just science fiction anymore

[joeflies]

Let's hope they don't take their research from game AI too literally. Most game AI i've seen is programmed to hunt and kill the player.

Easy solution

[OpenSourced]

Use silver instead of copper. Silver is an excellent conductor, better than copper in fact. That will surely baffle all those copper thieves.

Re:Easy solution

[hoytak]

+1 insightful, assuming we're talking about a virtual world of AI copper thieves...

Multi-algorithm approach

[Anonymous Coward]

The difficult part of AI design is that is has to be tailored to the game type you're playing, or even the specific game if it has some unusual elements (trying making an AI that could play Portal, for instance). A* and other algorithms have got pathing down, but one of the major flaws is we are still using nav-pathing (where you basically draw lines on the ground that tell the AI where it can go) even in newer games like Crysis. This leads to fairly flat movements. So one of the challenges is getting bots to "see" the surroundings, since I've also seen them shoot through stuff like thick foliage in Far Cry 2 since they don't actually see it.

On the coordination end, I think multiple algorithms can be applied. If we want to look at a military simulation of some sort, let's have a fireteam. The fireteam has a sergeant leader, of course. As long as he is alive, his AI calls the shots and is pretty controlling with it. However, if he's killed, then the remaining soldiers might become confused or each start trying to control the situation. Just like in a real fight, it might devolve into chaos. That is one option. The other is that there is a second-in-command or something else who takes command, but his AI isn't as good since he's not as good of a leader.

And by "good" I mean tactically sound. That's one thing that's rarely mentioned in AI: mistakes. AI as it stands doesn't make mistakes. Obviously at the level we were at with chess we just wanted it to make the best choice and prove it could do it. now, we want realism. And realism is that we, as humans, make mistakes. We run out when we should be under cover, spray bullets when we get surrounded, and do a lot of other behaviors that can be hard coded into each AI construct. This is more than movement orders: it's how they respond to the state of the game. If you can simulate the emotions behind the player, you'll get a better, more realistic AI.

Let's take L4D for example there (and I realize this is a long post, but I'm a CS major going into AI Game Design so it's kind of my passion lol). The Survivor AI is terrible, not because it's a bad shot or doesn't move well (it just follows you around like a good teammate I guess) it's that, when I get pinned by a hunter away from the group, they IMMEDIATELY come get me, no matter how pressed they are with zombies. That's not how I see other players react. They tend to take care of their zombie problems then come help me. In a case like that, you have to playtest and watch your players. Code their methods of approaching the game into your AI.

It's not a matter of just being "smart", it has to be realistic to feel like a good challenge. That's why a lot of people prefer multiplayer so much: the opponents are humans. Make an AI that acts like that and you'll see people turn back to single player games a bit.

Please send AI nobel prize this way.

[Anonymous Coward]

Must'nt the purpose of this be to develop a computer AI that will emulate a human player perfectly enough that you can not tell whether you are playing against a human or a machine?

Like a multiplayer game turing-test?
if human player is sneaking up behind computer player.

If so I have a very simple solution.

ALGORITHM:
1, Computer player can see any human players and automatically headshot them
1.a, across the entire map
1.b, when human is completely behind computer player and siltent/sneaky
1.c, hidden behind a wall or other obstacle, in which case computer bot can shoot just straight through any onstacle or wall.

2, If, unlikely, computer bot health drops below 50%, computer bot will get automatic insta-health-boost back to 100%.

2.a, Computer bot by design can never drop below 50% health. Not even by multiple rocketlauncher hits straight in the face. Computer bot can however take out 90% of your health from the other side of the map, even with 10+ walls separating you.
Any player that invokes this rule and temporarily drops computer bot below 50% is immediately headshot killed. Even if on the other side of the map.

3, Computer bot has a loop of 5-10 different curses a 12 year old thinks cool and uses this to continously spam any and all voice channesl. Repetably. Forever.
Using a sub-teenage voice.

Would just be exacly like playing against real humans on xbox-liv^H^H^Hcrap.
If you cant tell the difference between man and machine, thats kind of the definition of the turi ng test...

I finished your research to perfect online-gaming turing-test. Please send nobel-Prize here >.

Re:Please send AI nobel prize this way.

[Anonymous Coward]

Man, those kids must have pwnd you hard.

NPC AI under construction in Eve-Online

[egnop]

Actually the EVE-Online community, including devs are really gonna try to make AI happen in NPC encounters: http://myeve.eve-online.com/ingameboard.asp?a=topic&threadID=917074

Re:NPC AI under construction in Eve-Online

[Cornflake917]

God I hope so. Right now EVE's AI behavior is: If player is within a visibility range, go to an optimum range of player and orbit; if player is in locking range, lock on player; if player is locked, fire weapons on player. I love how you can just destroy a whole squadron of enemies while the other squadron nearby just sits there and acts like nothing happened. God Eve is boring.

AI does not need state trees, it needs statistics

[master_p]

AI in games is approached the wrong way: instead of finding all the game states and choosing the best path, a far better approach is to apply statistics and do pattern matching. In fact, brains work with the latter method, not the former.

The problem

[Anonymous Coward]

The problem with game AI isn't that we can't make better AI, it is that we don't make it a priority. Todays machines are powerful enough to give us good visuals but not powerful or memory spacious enough to really devote resources to too much beyond that. In Mass Effect I want to say we devoted something like 75% of the memory budget to textures, and we still had to downgrade the textures before the final ship. I don't know what the final stats were, but I wouldn't be surprised if about 90% of the budget was allocated to textures and polygons.

That's not to say if you were to quadruple the memory on today's machines that AI would suddenly improve drastically, though. Many teams don't have the resources to devote to programming, so they need to take whatever is in the package. There's room for some entrepenureal spirits to create snap in AI programs, like what Havoc does for physics. Get started now, and you may have a refined product ready for the next generation of consoles.

As an animator, I just want to point out that most anything smart you see in a game is a scripted sequence. An AI marine flipping a table and taking cover is mostly animation work. The only real code there is is a simple set of conditions that determine if the animation should be played and then some state changes to coincide with the animation. The measure of an AI isn't what kind of cool things it can do, because that's animator work, it's how quickly it figures out what it should do, and how well it figures out the quickest way to do it. When you see AI running out in the open, taking the long route to cover, getting hung up on corners or doing circles, that's bad AI.

To give credit (and blame) where credit (and blame) is due, designers choose what kind of behaviors that are possible, so they too are highly responsible for the final appearance of the AI. If a designer neglects a cover system, then it can make even an intelligent AI look stupid by just having enemies stand in harms way. If a designer includes a visceral chainsaw attack, even a poor AI that gets a kill can still seem impressive.

Re:The problem

[jgtg32a]

I blame the console for this, when I saw the original specs for the 360 and the ps3 I was surprised that they both only had 1 gig of ram.

The x box is shared, and the PS3 is 512 vid 512 system. IIRC

Most games these days are built the the least common denominator.

Re:The problem

[tlhIngan]

I blame the console for this, when I saw the original specs for the 360 and the ps3 I was surprised that they both only had 1 gig of ram.

The x box is shared, and the PS3 is 512 vid 512 system. IIRC

Most games these days are built the the least common denominator

Actually, both are only 512MB. Xbox360 is shared (512 for 3 PowerPCs plus GPU), PS3 has 256MB main system RAM and 256MB for GPU.

I thought this story was about me

[Anonymous Coward]

Back in High School, I had all of the latest games. You name it, I had it. They used to call me "Modern Game Al."

Lo and behold, years later I see an article named "A Look At Modern Game Al" I felt so special.

"Modern Game" Al Perkonkey

God are you there?

[kenp2002]

It neve ceases to amaze me that that while science is fiercly opposed to God or Theology infiltrating science as a process, in AI development they almost "assume" that intelligence was crafted by a God.

COMPLEX BEHAVIOR IS EMERGENT, NOT DESIGNED.

In AI development they seem to assume that the proper development of AI to to be a God and design a system or method of AI that accomplished a specfic set of goals or objectives.

Day after day evolution is a truth in science, and thats fine; but when it comes to AI development I swear they have never heard of evolution.

Your behavior is a result from a wide and largely independent array of inputs.

Your eyes don't make any decisions and aren't designed for decision making, they're input.
Your feet, lungs, and regions of your brain operate as a COMPLEX INTEGRATED SYSTEMS OF INDEPENDENT FACULTIES.

This is a much larger problem then the specifics of the task at hand. We are talking an organic development model for AI rather then a deterministic method. That is the largest flaw of Computer Science. Computers are largely deterministic devices, intelligence, isn't deterministic. A determinstic method of AI development is doomed.

You have to evolve the AI. The AI needs to know the limitations of it's organism for proper development.

Light, Dark
Up, Down
Here, There
Friend, Foe
Move from A to B ...
Find A Weapon
Assess Threat
Attack or Flee
etc...

The very process of evolving the AI api in an organic model give the model itself the ability to ignore irrelevant data by feeding abstract and generalized data up the cognitive food chain with irrelevant data dying off early in the process. If the general data is insufficent then the AI simply asks it faculties for more specific input.

OUT - I WANT TO READ HAMLET
IN - BOOK SHELF NEAR, OBJECTS FOUND ON BOOKSHELF, ASSUME RECTAGLE OBJECTS ARE BOOKS
IN - BOOKS OVER THERE ON THE BOOK SHELF (RECTANGLE OBJECTS CONFIRMED AS BOOK)
IN - BOOK ON TOP SHELF IS ABEL (Binary Search fo the book shelf)
IN - BOOK ON BOTTOM SHELF IS ZEUS
OUT - LOOK IN THE MIDDLE OF THE BOOK SHELF
IN - FIRST BOOK IS HOUSE OF M
OUT - GO BACK A FEW BOOKS TO THE LEFT
IN - FOUND BOOK HAMLET
OUT - GET BOOK
IN - TOO FAR AWAY
OUT - MOVE CLOSER
IN - I AM NEAR THE BOOK
OUT - GRAB BOOK
IN - LEFT ARM WON'T MOVE
OUT - USE RIGHT ARM
IN - I HAVE THE BOOK IN HAND

Additionally AI evolves with the organism itself (physical charactersitics influence mental development).

The reality of an AI is they need to be compiled or GROWN to fit the organism (say a terrorist or counter-terrorist in Counter-Strike)

BASE FACULTIES + ORGANISM DEFINITION + CIRCUMSTANTIAL OVERIDES + GAME PLAY OVERIDES = Source Code for AI

AI Complier then builds out an organic, almost B-Tree like info passing\storing pipelines based on the limitations.

A creature with no eyes would never have to process visual data. In that case distant objects are irrelivant except for memory storage.

My Prediction: AI isn't something that is developed, it's something that is Grown.

You define it then compile it.

Re:God are you there?

[Anonymous Coward]

Evolution is also a process that took billions of years before a human capable of playing Counter-Strike came into existence. Jokes aside, what's the difference between what you're talking about and GAs?

Effective branching factor of chess is more like 2

[Anonymous Coward]

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).

Use evolution

[greg_barton]

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/

Re:COONS

[Anonymous Coward]

wooosh at mods

That was a line from clerks 2

Wait a sec, alot of games don't use AI

[NotSoHeavyD3]

Instead they use R.C., Real Cheating.

Predators

[SgrA*]

I have pragmatically programmed predator behavior, based on a instinctive behavior matrix which considered creature energy level, anger, hunger, time of day, proximity of food, proximity of other predators, success of prior encounters, etc. Predators could also sense the environment over a limited range. This produced a composite behavior probability which translated into the energy put into prey acquisition and tracking. Available pathways to food (links in the game network) also applied difficulty levels. It' not quite AI, but it did provide a degree of uncertainty as to how often and vigorously the predators attacked.