kwc.org Photos Spare Cycles MythBusters

AI in computer games

I like video games. I work in an AI lab. I am compelled to post this: AI in Computer Games - Can Computer Games Employ AI Artfully? (ACM Queue)

Comments (6)

Mike:

As an insider on the game production side, the author is correct that A* is the primary algorithm used in pathfinding. Almost everything else mentioned in the article is up for debate. The author tends to oversimplify and generalize.I am not one to believe that a consumer will ever choose AI over graphics. It just doesn't happen.

For example, he mentions that AI is one of the last systems to be implemented -- that it's more important for the game to be visually interesting as a demo than to highlight good AI. It really does depend on how it's designed, but a primitive AI is usually part of the tech demo, if for no other purpose than to show off 'moving target technology', because frankly speaking, a non-moving target is boring.

The author also makes the statement about standardizing AI, but I think that because of the need to create specialized AIs for each game, it's something that is quite unavoidable in the games industry, although within the game and possibly within the genre, AIs are certainly recyclable.

I think the next step in AI in in the area of terrain mapping -- that is, creating difficulty and challenging the player in a dynamic way.

kwc:

(all of this is said with the caveat that most of what I say here is probably ready for primetime)

1) Consumers will always choose graphics over AI, but there will come a plateau where the difference in graphics becomes marginally smaller, which will shift emphasis into other areas of play. It may be a poor example, but the Star War MMORG seems like a good example of this - beautiful environment, but the missions are boring, simplistic, and unengaging.

2) Following my MMORG comment, this would be a good area for AI to start developing. You have thousands of people online, with only small number of game masters controlling the environment. Good AI in this area could help create an environment that would continue to be engaging by increasing the dynamic nature. A MMORG could provide so much training data to an AI -- imagine a WWII game where the AI uses a genetic algorithm to evolve different attack techniques based on the results of the battle.

More importantly for the game companies, AI could decrease the number of people necessary for monitoring the online environment by taking over more control tasks. You could also create more intelligent NPCs that act as guides to point the user to where cool stuff is currently happening (e.g. "Hey dude, there's a huge battle going on!" "Where?" "Over at the castle, follow me!").

It could also decrease development time if the AI could be effectively leveraged to do a lot of the world development on its own. Some retailers use AI programs that simulate consumers to try and determine the best way to layout products in their stores. Imagine instead using AI programs to populate your system and figure out the best way to distribute goods, where the cheats are, load test your system, rate the difficulty of missions, etc...

This brings up another point: the AI in the videogame doesn't have to be apparent to the user or in any code that the user actually runs. In the case of MMORG, the AI could be in the tools that the developers use to monitor the system health. The shift in who is using the AI is important: CPU performance is much less of an issue if the user isn't running the AI.

3) I think one of the points with AI is that it can be a general technology that you can use to save the effort of creating a specialized system. Instead of having to write rules upon rules to govern your system behavior, you could use the AI to identify those rules and program them in a much higher-level fashion.

This would require, though, that AI modules be standardized such that they could be used as tools, rather than additional code that has to be written. Eventually this might happen, so that it would be easy enough to pick up, say, a natural language conversation algorithm and a preference learning algorithm, and throw it into the game.

If applied appropriately, certain AI techniques could be introduced earlier and save programming effort, much like DirectX/Sound has taken a lot of the effort of 3-D + sound programming. A "DirectAI" would be a great benefit to programmers by providing them with optimized code (instead of having to code up something from a textbook), and a readily available toolkit could adjust where in the pipeline AI techniques get used.

An AI module that classifies what the player is currently doing could be used to program the appropriate game response, rather than writing a whole bunch of specialized code that is time consuming and attempts to do the same thing. In fact, I think a near-term huge benefit from the AI community would be trying to use AI techniques to identify cheaters in a more generalized fashion. The learned cheating rules could also be dynamically updated.

Mike:

1. There has yet to be a MMORG in which gameplay is anything but boring, repetitive and unengaging. This is not so much a result of the AI, but rather a result of the poorly thought out game design of MMORGs.

2) Although some MMORGs have tried to utilize AI to fill a dynamic world (Dark Ages of Camelot uses an AI to repopulate areas with monsters that have been killed by players, and Anarchy Online creates a dungeon for you based on your player level), these efforts have mainly failed to create a good normal gameplay experience for the player. That doesn't mean that it's impossible to create a good gameplay experience with AI -- just that with dynamic efforts, one does have to take a tremendous amount of effort in designing the variations such that it doesn't appear to just be random.

Interestingly enough, most of the complex NPC AI behaviors don't appear until very late stages in most games (as simplistic AIs which are easy to defeat are less frustrating to beginners). In EverQuest, for example, the monsters at the early levels don't run away when their health drops below 25% -- in the later levels they will run away, or teleport away, or they will call for help, or do other interesting actions which makes the game play experience differnt than the "whack-a-mole" of earlier levels. In today's games, monster actions are following a crude decision-making tree, but not learning from their actions. It is then up to the programmer to adjust and tune the AI if it is too difficult or too easy to defeat -- the result of which is usually the players screaming foul for 'changing the rules on them'.

This, of course, leads me into the issue of fairness and balance. Some developers believe that the obstacles that a player encounters should be balanced on the side of the monster (an encounter with a dragon is an encounter with a dragon, regardless of the number of players, their levels or their weaponry), while other game designers prefer to use players as the measuring stick for encounters (the dragon is a challenging encounter for 5 people, but adding a 6th person, the dragon increases in difficulty by 20%). I have seen both systems work, and I have seen both systems abused.

Where does one draw the line between abusing an AI and downright cheating against an AI? How much information is an AI allowed to have? What sources should the AI be able to draw on?

In creating an AI with access to information, you don't want to create an AI that is too good, and has learned too much. For instance, how interesting would the game be if the Level 1 Skeleton AI determined that it's best chance of survival lay in running away as soon as it was attacked? What would then be needed would be a way of controlling the information the AI has access to, or a counter-balancing AI that knows when an AI has gotten too smart. To further continue on the lines of the example, if only 10% of the Level 1 Skeletons created have been killed for the last month, it needs to be able to determine that the reason why their survival rate is 90% and bring that down to the level you want, which is probably around 10% (these are easy monsters -- beginners should be able to destroy them 90% of the time).

Finding balance is key (at the later levels, having each battle being good 50-50 odds of survival is a good goal), and unfortunately, the designers don't often go through their own encounters to find the perfect balance -- they blindly assume that whatever obstacle they set before will be conquered by the player.

One of the major differences these days in playing a MMORG and boardgame is that the rules are no longer in front of the player, so the player has to determine (through experimentation and experience) the logic path of the AI. After this logic path is determined by the player, the player is then able to create actions that undermine the AI.

Do I think there is a place for AI GM-tools that help analyze and create obstacles and goals for players? Or help in designing new areas? Absolutely, but one must be very careful in the conclusions drawn from the data.

Mike:

While I agree that AI cheat detection would be a major leap, almost the only thing that works is sanity checking whenever an action is performed, when they are actively cheating -- passive cheating (like getting map data for areas you have not entered) is a design hole in architecture that does require programmer effort to fix -- an AI is not likely to detect it. With any kind of game cheating detection, it has to first identify a cheater, and then draw some conclusions -- i.e. cheaters and a correllation with their kill percentage and their play style.

kwc:

I think we have to be careful as to what I would call an "AI" here. Simply programming out an explicit decision tree, is not an AI in the sense that I'm describing, and those types of programs will have a lot of problems with gamers, because they effectively pit the skill of the programmer against the skill of the gamer. In general, I think those types of rules are a major bottleneck for MMORGs, because it is very difficult to explicitly define every single rule that every single monster and character acts by.

Where AI can help, I believe, is in introducing learned and/or dynamic behavior. To elaborate on a previous examples, imagine the players fighting against the dragon. Say that the players do figure out the "rules" that the dragon is playing by and start beating it every time. With a good enough AI, it could see that it was losing, and trying to evolve its behaviors in "real" ways by changing its decision tree, e.g. changing the sets of attacks it uses, or changing what attacks it uses based on the players that its fighting -- "fake" ways would be increasing damage, hit points, etc... If there are 100+ such battles occuring everyday on the system, there is a lot of opportunity for the AI to try different variations and improve it's technique, without programmer intervention.

Like you said, it does take a "tremendous effort" on the part of the designers to introduce dynamic behaviors in the system. I would take that as a symptom of the designers using the wrong techniques to design the system. A battlefield is complex, more complex than a believe an individual can comprehend fully in their head, and an explicit, rules-based system cannot cope. When the AI becomes easily available and computationally reasonable, the cost equation may shift enough that the AI can actually reduce the design cycle period, and thus become something that is introduced first, not last. It may also mean that when an MMORG is released, you only need half or less as many people watching the system and fiddling with the knobs and switches to counter the latest tricks.

Mike:

Yes, in the example you gave of fighting a dragon, what would most likely happen in the MMORG business is a programmer would go in and tweak the encounter by augmenting stats rather than modifying behavior greatly. Part of this has to do with principle of fairness or the name of balance. The other part is lazy programmer syndrome.

Talking about this has definitely piqued my interest in the subject, and the development and design of MMORGs in general.

As far as technical feasibility goes, I think that AIs running MMORGs is not very far off, but that social acceptance of AIs running events in MMORGs would be, because the AI then acts as both the referee and the opponent. Although it is not very different from MMORGs today, one can take comfort in that the rules the NPCs follow is only as smart as the programmer's foresight. With an adaptive AI, players would develop the insistence that the AI is 'cheating' or that the AI is not playing fair since Group A had an obviously easier fight against the dragon, but that Group B had a re-tuned, more experienced dragon to fight. Those that first encounter an un-tuned AI which is much too hard, or worse, much too easy -- but in doing this, it is also possible to adjust the rewards that result from the battle.

So far, our discussion has mainly focused on battle mechanics, but AI can be applied to other aspects of the MMORG as well -- such as pairing what the merchants will buy and the price they'll pay based on the rarity and utility of the item being offered. Further expanding on its capabilities, the AI would be able to create play area layouts, populate it with appropriate monsters and generate a quest for it.

Right now, most MMORGs use a random generator to generate quests and quest rewards and quest obstacles -- the results of which are typically very uninteresting. If an AI could do that work, based on the data that a programmer feeds to it, the results could be very interesting, or it could be almost cookie-cutterish in that it fulfills the parameters and nothing more.

Damn. Now I wish I had an AI and MMORG to play with.

tags.

related entries.

what is this?

This page contains a single entry from kwc blog posted on March 17, 2004 7:26 PM.

The previous post was A new toy.

The next post is Samplin' the google rankin'.

Current entries can be found on the main page.