Cover ERCIM News 57

This issue in pdf
(72 pages; 11,6 Mb)

Cover ERCIM News 56
previous issue:
Number 56
January 2004:
Special theme:
Analysis, Planning, Diagnosis and Simulation of Industrial Systems

all previous issues

Next issue:
July 2004

Next Special theme:
Automated Software Engineering

About ERCIM News

Valid HTML 4.01!

< Contents ERCIM News No. 57, April 2004

Multi-Agent Technology Applied to Real Time Strategy Games

by Marco Remondino

Multi agent technology has been successfully used to model and simulate social systems; thanks to the increased power of modern computers, it can also be implemented in strategy games.

At the Department of Computer Science, University of Turin, Italy, we are currently studying the field of computer simulation in collaboration with the Department of Applied Economics. Our main objective is to demonstrate that multi-agent techniques can be used successfully in several social and industrial applications, and first of all in real-time strategy games. Future plans include a working example based on this approach and a framework to develop games using multi-agent systems.

Computer simulation has been described as a third way to represent social models; in particular, it can constitute a powerful alternative to two other major symbol systems: verbal argumentation and mathematical notation. However, owing to its high portability, through programs or specific tools, and its capacity to describe complex behaviour starting from simple interacting entities, computer simulation has a great advantage over the other two. Computer programs can be used to model both quantitative and qualitative theories. Since real time strategy games are becoming increasingly intricate, and take place in dynamic worlds in which complex decisions, often based on partial knowledge must be made, the artificial intelligence behind them can be modelled with agent-based techniques, already used in social simulation. The degree of freedom in modern strategy games makes them a perfect field of application and testing for agent-based techniques, which often explore complex aggregate behaviour even when applied to real situations, like social, anthropological and economical simulations.

The actual trend in AI for games is to use schedule-based finite state machines (FSMs) to determine the behaviour of the player's adversaries. Although the results are satisfactory, FSMs are by their nature very rigid and behave poorly when confronted with situations not envisaged by the designer. An agent-based approach could deliver more realistic and less deterministic behaviour: agents could self-organize, producing intelligent aggregate behaviour, capable of puzzling the human player and of presenting different paths of evolution at every match.

Two Classes of Agents - artificial and human - interacting in the same environment.
Two Classes of Agents - artificial and human - interacting in the same environment.

Strategy games are those in which the player, who must manage and control military units, workers, resources and so on, has to make decisions and complete tasks (construction, conquest, organization, etc.) in order to reach a main objective. The environment can sometimes be changed by the actions taken by the player himself, or other actors, who can also be human players or, more frequently, artificial entities, managed by some form of AI. There are mainly two classes of strategy games: Turn Based and Real Time. Our research is currently focused on the latter, in which many actions (issued by different entities) take place in parallel. There is much similarity here with the actions of real time simulators of real world situations, eg stock market simulations. It can be amazing to see how closely general trends in an artificial stock market can resemble real trends in many ways. The market can be simulated by creating different types of intelligent agents, which follow inner rules; some of them can simply act randomly, while others will "study" the trend before acting. Some of them can even use advanced techniques, such as stop loss. We can now work on designing and developing a sort of real time strategy game, in which the main objective is to become richer and richer, and where one of the agents is indeed a human player, while the others are computer driven entities trying to pursue the same target.

Previous research has shown that network-based simulations, in which human agents act side by side with artificial entities, are feasible. As an example, we have ported the 'Prisoner's Dilemma' game to a working program that employs random acting agents and asks the user which decision she/he will take, step by step. In Figure 1 shows what can be done in a hybrid system in which artificial agents interact with a human being. The same artificial environment is shared by two classes of agents: those driven by artificial rules, coded by the programmer, and those controlled by human player(s). Both classes observe "brute facts", that can be exogenous (ie coded in the environment) or endogenous (ie produced by the agents' actions) and decide on which action they should perform. Artificial agents will have a set of rules, which can be static, ie coded 'a priori' by the programmer, or dynamic. Dynamic rules can evolve according to previous experience; this can be done employing advanced AI derived techniques, which try to mimic human thought processes, such as neural networks, genetic algorithms, classifier systems and so on.

We are currently studying the use of hybrid approaches (agent based and process based), which have the advantage of allowing intelligent agents to self-organize according to deterministic structures, just giving simple rules. This would guarantee that their behaviour is consistent with that observed in the real world, and is quite independent of programming choices. Games using such approaches could also deal with unforeseeable situations that were not implemented as possible ways of evolution. The main drawback of using such methods for simulating AI in a game is that these techniques are heavy on CPU resources. However, in the last seven years, we have witnessed the rise of dedicated graphics hardware (3D cards) which now, thanks to the integration of transform and lighting, pixel and vertex processing etc., leave just the management of the basic computing functions and of the AI component to the CPU.

It is our intention now to produce a working framework for this approach, which could be used as an example and, at the same time, as the starting point for practical research in this field.

Please contact:
Marco Remondino, University of Turin, Italy