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

videogames (e.g., Crysis). The reasons for their use are clear: DTs are based on
a simple concept, can be easily interpreted, and helps to smooth the complexity
of other techniques (e.g., finite state machines are also easy to understand and
be interpreted but they introduce a high complexity if the model involves a high
number of states as it is not always easy to manage the whole set of relations
among all the states).
In FPS games, requiring higher quality opponents means obtaining enemies
exhibiting intelligent behavior; however, it is not easy to evaluate what a 'human-
like intelligence' means for a bot in these games. Generally speaking, it is well
known that the Turing Test is a procedure proposed by Alan Turing to corrob-
orate the existence of intelligence in a machine [6]. The basic fundament is that
a machine that behaves intelligently might be considered as intelligent in the
human sense. In this context, the “2k bot prize” is a competition 1 that proposes
an interesting adaptation of the Turing test in the context of the Unreal Tour-
nament 2004 (UT2004), a multi-player online FPS game in which enemy bots
are controlled by some kind of game AI.
This paper describes an on-going work to provide intelligence to the bots in
the context of UT2004, and we propose here two different DT-based algorithms.
These two different approaches are compared experimentally, first from an objec-
tive point of view considering two fitness functions, and second from a subjective
point of view according to the “2k bot prize” competition.
2 Proposals to Control the Bot AI
We have tested two different ways to generate the bot AI in UT2004. The first
implementation is manufactured via decision trees and was manually coded fol-
lowing our intuition under a process of trial, error, and debugging. In fact, this
is basically the process followed in most of the existing commercial FPS games.
The second of our proposals consists of automating the process of generating
an adequate strategy for the bot AI and is based on genetic programming (GP)
techniques [7]. In the following we describe both proposals.
2.1 A Hand-Made Decision Tree-Based AI
In a high level of abstraction the logic of the bot was manually coded as machine
with the following 4 states:
- Combat (if the bot is under attack).
- Pick items (if the bot detects an item).
- Pursue (if the bot detects an enemy).
- Idle (otherwise).
Each of these states is implemented with a specific hand-coded binary DT (i.e.
internal nodes have two children at most). Internal nodes represent bot percep-
tions that involve a question with two possible answers: yes or no, and leaves
1 http://botprize.org/ (accessed 14th of February, 2011).