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

Fig. 1. Simplified decision tree for 'Pick Item'
contain actions that have to be directly executed by the bot; note that a specific
action associated to a leaf is executed when all the internal nodes in the path
from the tree root to the leaf have been traversed. The perceptions that the bot
perceives are of the type “have I an item close?”, “am I under attack?”, “do I see
an enemy?”, “am I armed?”, “do I see an item?”, etc. The actions that a bot can
execute are of the type “shoot”, “do nothing”, “re-equip with weapons”, “look
for a specific item (i.e., health kit, weapon, armor,.,etc.)”, “pick item”, “turn
(right, left)”, “jump”,...,etc. Due to the complexity of these trees we will not
show them completely. Figure 1 shows a (very simplified) illustration of the tree
associated to state “Pick Item” (here the perception “Have I chosen an item to
look for?”, and the actions “Continue looking for it”, and “Choose item to look
for” are over-simplifications corresponding to more complex DTs.
2.2 A Genetic Programming Based Approach
Note that the approach previously described requires an important effort from
the programmer point of view as the strategy that controls the behavior (i.e., the
logic) of the bot has to be intuitively coded. In fact, this strategy was the result
of directly applying our experience as players. We have also considered an auto-
mated process to generate bot AI. This process is based on genetic programming
(GP) techniques [7]. More specifically, we have implemented a GP algorithm to
optimize the bot AI. The basic idea here is that the individuals are represented as
decision trees (in fact as 4-states machines as explained in the previous section)
where the actions correspond directly with terminal symbols and the percep-
tions are associated with non-terminal symbols. Our automated algorithm is a
standard GP method that uses the following parameters: random initialization
via the classical “grow” method, binary tournament selection, crossover based
on random node selection and interchange of the respective subtrees, mutation
based on the replacement of a complete subtree, and replacement of the worst
parent. Our GP algorithm manages the following set of symbols:
T(Terminals) = Jump, RunToTarget, RunAway, Attack, Shoot, StopShoot-
ing, Disarm, Arm, TurnSomeDegrees, GoToPosition, Idle, PickWeapon, PickMed-
icalKit, PickArmor, PickAmmunition, NoOperation.