Similar to FSM, BT also models transitions between a finite set of behaviors [9].
Compared to FSM, BTs are more flexible to design and easier to test due to the
modular design concept, which promotes its successful application in games such as
Halo 2 and Bioshock.
In order to eliminate the modularity limitations of FSMs and BTs, utility-based AI
methods are proposed. Following this method, instances in the game get assigned a
particular utility function that gives a value for the importance of the particular
instance. While FSMs and BTs check one decision at a time, the utility-based AI
methods check all available options, assign utilities to them, and chooses the most
appropriate option [10]. In comparison with other ad hoc authoring techniques, utilitybased AI has obvious advantages including modularity, extensibility, and reusability.
As a result, utility-based methods have been successfully used in Kohan 2, Iron Man,
Red Dead Redemption, and Killzone 2.
3 Tree Search Algorithms
It is generally accepted that most, if not all, of AI is actually just search. Almost every
AI problem can be transformed into a search problem, which can be solved by finding
the best plan, path, model, function, etc. Tree search algorithms can be seen as building
a search tree, where the root node is the initial state, the edge of the tree represents the
operation taken by the agent from one state to another, and the node represents the
state. Tree need to branch because usually several different operations can be performed in a given state. The main differences between tree search algorithms are the
branch position and branch order.
It’s no exaggeration to say that Monte Carlo Tree Search (MCTS) is the most famous
algorithm in the tree search field. MCTS have a long history within numerical algorithms and have also had significant success in various games, particularly imperfect
information games such as Scrabble, Bridge and Go. As is known to all, MCTS is an
indispensable part of AlphaGo [11]. The core loop of the MCTS algorithm can be
divided into four steps: selection, expansion, simulation and backpropagation [4].
It is noteworthy that there are many variants of the basic MCTS methods. The flat
UCB presented in [12] treats the leaves of the search tree as a single multi-armed bandit
problem. Coquelin and Munos [13] present an algorithm that combines MCTS with
TDL using the notion of permanent and transient memories to distinguish the two kinds
of state estimation. In [14] the simulation phase of UCT is described as a single agent
competing with itself rather than considering the influence of multiple agents.
4 Evolutionary Computation
Randomized optimization algorithms which include several solutions are named
Evolutionary Computation (EC), inspired by Darwin’s theory of evolution. On the
basis of population evolution, where each individual represents a solution with a certain
degree of fitness. By selecting and mutating operators, the population gradually
300
X. Fan et al.
Compared to FSM, BTs are more flexible to design and easier to test due to the
modular design concept, which promotes its successful application in games such as
Halo 2 and Bioshock.
In order to eliminate the modularity limitations of FSMs and BTs, utility-based AI
methods are proposed. Following this method, instances in the game get assigned a
particular utility function that gives a value for the importance of the particular
instance. While FSMs and BTs check one decision at a time, the utility-based AI
methods check all available options, assign utilities to them, and chooses the most
appropriate option [10]. In comparison with other ad hoc authoring techniques, utilitybased AI has obvious advantages including modularity, extensibility, and reusability.
As a result, utility-based methods have been successfully used in Kohan 2, Iron Man,
Red Dead Redemption, and Killzone 2.
3 Tree Search Algorithms
It is generally accepted that most, if not all, of AI is actually just search. Almost every
AI problem can be transformed into a search problem, which can be solved by finding
the best plan, path, model, function, etc. Tree search algorithms can be seen as building
a search tree, where the root node is the initial state, the edge of the tree represents the
operation taken by the agent from one state to another, and the node represents the
state. Tree need to branch because usually several different operations can be performed in a given state. The main differences between tree search algorithms are the
branch position and branch order.
It’s no exaggeration to say that Monte Carlo Tree Search (MCTS) is the most famous
algorithm in the tree search field. MCTS have a long history within numerical algorithms and have also had significant success in various games, particularly imperfect
information games such as Scrabble, Bridge and Go. As is known to all, MCTS is an
indispensable part of AlphaGo [11]. The core loop of the MCTS algorithm can be
divided into four steps: selection, expansion, simulation and backpropagation [4].
It is noteworthy that there are many variants of the basic MCTS methods. The flat
UCB presented in [12] treats the leaves of the search tree as a single multi-armed bandit
problem. Coquelin and Munos [13] present an algorithm that combines MCTS with
TDL using the notion of permanent and transient memories to distinguish the two kinds
of state estimation. In [14] the simulation phase of UCT is described as a single agent
competing with itself rather than considering the influence of multiple agents.
4 Evolutionary Computation
Randomized optimization algorithms which include several solutions are named
Evolutionary Computation (EC), inspired by Darwin’s theory of evolution. On the
basis of population evolution, where each individual represents a solution with a certain
degree of fitness. By selecting and mutating operators, the population gradually
300
X. Fan et al.