Decision Tree-Based Algorithms for Implementing Bot AI in UT2004 - Foundations on Natural and Artificial Computation - page 382

Decision Tree-Based Algorithms for
Implementing Bot AI in UT2004

Antonio J. Fernandez Leiva and Jorge L. O'Valle Barragan

Dept. Lenguajes y Ciencias de la Computacion, ETSI Informatica,
Campus de Teatinos, Universidad de Malaga,
29071 Malaga - Spain
[e-mail], [e-mail]

Abstract. This paper describes two different decision tree-based ap-
proaches to obtain strategies that control the behavior of bots in
the context of the Unreal Tournament 2004. The first approach fol-
lows the traditional process existing in commercial videogames to pro-
gram the game artificial intelligence (AI), that is to say, it consists of
coding the strategy manually according to the AI programmer's experi-
ence with the aim of increasing player satisfaction. The second approach
is based on evolutionary programming techniques and has the objective
of automatically generating the game AI. An experimental analysis is
conducted in order to evaluate the quality of our proposals. This anal-
ysis is executed on the basis of two fitness functions that were defined
intuitively to provide entertainment to the player. Finally a comparison
between the two approaches is done following the subjective evaluation
principles imposed by the “2k bot prize” competition.

1 Introduction and Related Work

Until recently, research on videogames was mainly focused on having more realis-
tic games by improving graphics and sound. However, in recent years, hardware
components have experienced exponential growth and players demand higher
quality opponents controlled by better artificial intelligences (AI). In this con-
text AI plays an important role in the success or failure of a game and some
major AI techniques have already been used in existing videogames [1,2] (e.g.,
evolutionary computation and neural networks are beginning to be considered
with moderate success [3]). However, traditionally game developers have pre-
ferred standard AI techniques such as Artificial Life, Neural Networks, Finite
State Machines, Fuzzy Logic, Learning, and Expert Systems, among others [4,5].
One technique used with success for implementing the game AI in First Person
Shooter (FPS) games is Decision Tree (DT); a decision tree is basically a tree
that takes as input a specific situation (e.g., a combination of values correspond-
ing to a set of perceptions) and outputs a yes/no decision. In other words, a
decision tree is a tree in which its internal nodes represent questions that can be
answered with yes or no, and its leaves are actions to be executed. Decision trees
have already been employed as decision-making techniques in successful AAA