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

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

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

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

[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

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

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

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: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?

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