• More than one player can take actions at the same time.
• RTS games are “real-time”, which means that players have a very short time to
decide the next move.
• Most RTS games are partially observable.
• Most RTS games are non-deterministic.
• Last but not least, the complexity of these games, both in terms of state-space size
and in terms of number of actions available at each decision cycle is very large. For
example, the state space of Go is around 10
170 , while a typical StarCraft game has at
least 10
1685 possible states [7].
In general, to devise a satisfactory RTS game AI, a series of challenges must be
solved, such as opponent modeling, spatiotemporal reasoning, and multi-agent collaboration. These problems can be summarized into three levels: strategy, tactics, and
manipulation. Recently, with the rapid development of computing science, researchers
invested more effort in designing more intelligent RTS game AI and proposed new
intelligent algorithms to raise the game AI’s intelligent ability. For the convenience of
researchers’ reference, basic AI methods that are commonly used in games are summarized and presented. The framework of the survey is illustrated in Fig. 1, which
consists of Ad Hoc behavior authoring, tree search algorithms, evolutionary computation, machine learning.
2 Ad Hoc Behavior Authoring
Ad Hoc behavior authoring methods are the most popular kinds of AI methods used to
control the non-player characters in games. Finite state machine (FSM), behavior trees
(BT), and utility-based AI are three most representative algorithms ad hoc behavior
authoring methods.
FSM belongs to the field of expert system and is depicted with graphs where nodes
(states) store information about a task, transitions between states represent a state
change and actions that need to be executed within each state. The design, implementation, visualization and debugging of FSMs are very simple. However, FSMs have
the following shortcomings, i.e., it is hard to cope with a huge game, and it is in lack of
flexibility and dynamic characteristics [8].
Fig. 1. Main AI methods for game AI
A Review of Artificial Intelligence for Games
299
• RTS games are “real-time”, which means that players have a very short time to
decide the next move.
• Most RTS games are partially observable.
• Most RTS games are non-deterministic.
• Last but not least, the complexity of these games, both in terms of state-space size
and in terms of number of actions available at each decision cycle is very large. For
example, the state space of Go is around 10
170 , while a typical StarCraft game has at
least 10
1685 possible states [7].
In general, to devise a satisfactory RTS game AI, a series of challenges must be
solved, such as opponent modeling, spatiotemporal reasoning, and multi-agent collaboration. These problems can be summarized into three levels: strategy, tactics, and
manipulation. Recently, with the rapid development of computing science, researchers
invested more effort in designing more intelligent RTS game AI and proposed new
intelligent algorithms to raise the game AI’s intelligent ability. For the convenience of
researchers’ reference, basic AI methods that are commonly used in games are summarized and presented. The framework of the survey is illustrated in Fig. 1, which
consists of Ad Hoc behavior authoring, tree search algorithms, evolutionary computation, machine learning.
2 Ad Hoc Behavior Authoring
Ad Hoc behavior authoring methods are the most popular kinds of AI methods used to
control the non-player characters in games. Finite state machine (FSM), behavior trees
(BT), and utility-based AI are three most representative algorithms ad hoc behavior
authoring methods.
FSM belongs to the field of expert system and is depicted with graphs where nodes
(states) store information about a task, transitions between states represent a state
change and actions that need to be executed within each state. The design, implementation, visualization and debugging of FSMs are very simple. However, FSMs have
the following shortcomings, i.e., it is hard to cope with a huge game, and it is in lack of
flexibility and dynamic characteristics [8].
Fig. 1. Main AI methods for game AI
A Review of Artificial Intelligence for Games
299