Teaching Genetic Algorithm-based Parameter

Optimization Using Pacman

Carlos N. Silla Jr.
Intelligent Systems Laboratory (LASIN)
Graduate Program in Computer Science (PPGIa)
Pontifical Catholic University of Parana (PUCPR)
Curitiba, PR, Brazil 80215-901
Email: [Link]@[Link]

Abstract-Previous artificial intelligence education research an automated Pacman player using at least a greedy search
(DeNero and Klein, 2010) has used the classic video game Pacman with different heuristic functions (more details about this
to teach introductory artificial intelligence concepts. One of the
assignment are presented in Section 2). This is necessary as
advantages of the work proposed in (DeNero and Klein, 2010)
is that the same framework, in this case using the video game
by using different heuristic functions the students will need
Pacman, can be used for different student assignments covering to combine the outputs of the different heuristics. The way
different artificial intelligence algorithms and methods. The issue the students combine the outputs is to assign weights to each
of how to use the same practical framework is an important heuristic and they use a manual trial and error approach
one, because if students have to learn a different framework
to adjust the weights, i.e. they try different parameters for
for every assignment they will often feel discouraged. For this
reason, the main contribution of this paper is to present a
each heuristic weight and evaluate what happens with their
practical assignment to teach students about genetic algorithm­ developed Pacman player.
based parameter optimization using the Pacman framework. The remainder of this paper is organized as follows: Section
III presents a brief overview of Genetic Algorithms. Section IV
I. INTRODUCTION
presents the GA-based pacman assignment. Section V presents
Genetic Algorithms (GAs) are a search and optimIzation the discussion about the assignment in practice as well as
procedure that can be used to find solutions to several scientific student feedback and learning outcomes. Section VI presents
and engineering problems [1]. The GAs were originally devel­ the related work and finally in Section VII we present the
oped by John Holland in the 70's [2] and given its importance conclusions of this work.
to real world problems they are often taught in the context of
artificial intelligence undergraduate classes. II. PRE-REQUISITES

Previous approaches to teach GAs to undergraduate students In order to use the assignment proposed in this work
include: Using a "hands on" strategy using poppet beads to (presented in Section IV) it is important that the students
represent Biston betula moths [3]; Developing visual and inter­ have already completed a previous assignment, which was
active tutorials, such as the GATutor [4] and the Evolutionary originally suggested by DeNero and Klein. The main idea of
Algorithms Sandbox [5]; Using Japanese nanograms to teach the assignment is to use informed search methods to create an
about advanced GA features [6], [7]; and using GAs to design automatic player for Pacman.
controllers for non-player characters in games [8].
In the context of artificial intelligence education research, A. The Java Pacman Framework
DeNero and Klein [9] have used the classic video game In our classes, we use a java-based version of the Pacman
Pacman to teach several introductory artificial intelligence framework that was developed by Ted Grenager. The java
concepts. One of the advantages of the work proposed in Pacman framework runs with a textual interface by default
DeNero and Klein [9] is that the same framework, in this (Figure 1), with a graphical user interface (Figure 2) with
case using the video game Pacman, can be used for different the parameter -display gui or with no interface with the
student assignments covering different artificial intelligence parameter -display none (Figure 3). As it can be noted
algorithms and methods. The issue of how to use the same from Figure 2, this version of the game does not contain the
practical framework is an important one, because if students powerups (fruits) that allows pacman to eat the ghosts.
have to learn a different framework for every assignment they In order to execute an automated player, it is necessary
will often feel discouraged. to pass the player as a parameter to the framework using
For this reason, the main contribution of this paper is to -pacman player where player is the name of the class
present a practical assignment to teach students about genetic that has the implemented Pacman player. In order to create an
algorithm-based parameter optimization using the Pacman automated player the students need to realize (implements in
framework. In order to use the approach present in this paper java) two interfaces, namely PacmanPlayer and StateEvalua­
it is mandatory that the students have already developed tor.

978-1-5090-1790-4/16/$31.00 ©2016 IEEE

 The PacmanPlayer interface enforces that the method
Move chooseMove(Game game) is implemented. The Move
class is an enumeration of the valid Pacman moves, namely
UP, DOWN, RIGHT, LEFT and NONE. Therefore, the
chooseMove method receives a game state and returns
a move to be executed in the game. The StateEvaluator
interface enforces that the method double evaluateState(State
s) is implemented. The State class represents a state of the
Pacman board.
The framework also allows for different scenarios to be
evaluated, i.e. using different number and/or types of ghosts.

0 0 0 ••• 0 0 0 ••• 0 0 0 0 0 . 0 . 0 0 0 0
o . • •

Fig. 4. An Example of a Particular Game State.

• • • 0
o . • •
• • ••• • • • • •••• • 0 0 • • •••• • • • •
• • 0 • • 0

• • ••• 0 0 0 0 • • •
•
o
•
• •
• • • • ••• 0 0 0 • •

0
•
•
0
•
B. Pacman as an Informed Search Problem
... ................ ...
• • 0 • • 0

0 0 0 ••• • • •• 0 0 0 0 •• • • • •
· .
· .
0 0 0 ••• • • • ••• 0 0 0 0 0 0 0 ••• • • • •

Considering that the students do not need to worry about

Fig. 1. The Pacman Framework Text Based Interface. the Pacman game implementation, they can focus on the
development of an artificial intelligence for the game. The
main idea is to use informed-search methods for the problem.
The easiest approach is to implement a greedy best first search
algorithm [10]. In order to use the greedy best first search
algorithm, we need to know how to differentiate between
different states at a given time. For example, considering
Figure 4 the automated Pacman player can perform all five
valid moves, therefore all possible moves are evaluated and a
particular move is chosen.

This raises the question about how to chose a particular

move at a given game state. The answer to this question is
to use an heuristic function. For example, the different states
could be compared by using the number of items left on the
board after Pacman performs a particular move. Using this
heuristic, in the scenario illustrated in Figure 4, Pacman would
move LEFT. However, another heuristic could be to stay at a
safe distance from the closest ghost, in which case Pacman
could move UP. Given the complexity of the game it is not
recommended to use only one heuristic, such as eat the closest
Fig. 2. The Pacman Framework Graphical User Interface. item, as Pacman might die too often. Therefore, it is necessary
to implement different heuristics and combine them in order to
have a good automated Pacman player. Normally the students
combine their developed heuristics in a manual trial and error
approach. Other informed search algorithms such as the Breath
First Search and A * search algorithms can also be used to
develop an automated Pacman player. However, they should
be implemented using fixed-depth (i.e. limiting the maximum
number of levels they will explore) given the complexity of
Fig. 3. The Pacman Framework Without an User Interface. the problem.
C. The First Pacman Assignment Initial Evaluation Selection
Population (Fitness)
In our artificial intelligence undergraduate classes, students
are told to work on teams of at most two students and are
asked to: Crossover
• Implement the greedy best-first search [lO].
• Implement the Breath First Search Algorithm with fixed­
Mutation
depth [lO].
• Implement the A * Search Algorithm with fixed-depth
[10].
• Implement at least eight heuristics to evaluate the non­
Returns the
terminal states. Best Individual
• Implement at least one strategy to avoid loops.
• Design and run experiments to evaluate the different
Fig. 5. Overview of the Basic GA (Adapted from [11]).
components of their developed players, for example:
Which heuristics should be used?
What is the impact of different depth values? • The individual representation. In a GA an individual is
What is the effect of different weights for the heuris­ one solution to the problem we are trying to solve. Each
tics? individual is encoded in a chromosome. Each indivisible
What was the best parameter setting you found for a piece of a chromosome is called gene and normally in
given ghosts setting (e.g. using three random ghosts a population all individuals have a fixed sized chromo­
and one stalker ghost.)? some. Many researchers represent the chromosome of an
• Write a detailed report explaining everything that they individual as a string of bits, however chromosomes can
did and reporting any issues they had. be encoded using any type of data structure.
• A fitness evaluation function. In a GA the fitness func­
We also run an in-class live tournament where the students
choose whether or not they want to participate. tions measures how good (or bad) an individual is to
In order for the students to successfully employ the GA­ the problem at hand. The fitness function will always be
based parameter optimization (presented in Section IV) it is specific to a particular problem.
• The genetic operators. These operators are responsible
mandatory that all teams implement at least the greedy best­
first search and as many heuristics as they can. In the case for the evolutionary process of the population. The most
conunon genetic operators are mutation and crossover.
that the students implement only the greedy best-first search
and a number of n heuristics, they already have a parameter However before a genetic operator can be applied it is
optimization problem, as shown in Equation 1, where they necessary to select individuals from whom new individ­
manually try to adjust the weights (w) of each heuristic (h). uals will be created (off springs). The common selection
processes are the roulette wheel and the tournament.
In the roulette wheel, usually a pre-determined num­
ber of individuals will be selected based on a fitness­
In the case that the students also implement the fixed­ proportional draw, where individuals with better values
depth search methods, they will also have to deal with another of fitness have greater chances to be selected. In the
parameter, namely the depth of the search. Regardless of the tournament, a k number of individuals are selected at
search methods implemented by the students, it is important random and the one with the best fitness is selected.
that they record the weights used for a particular ghost setting After selecting the individuals it is possible to apply the
that achieved their best results. This information will be genetic operators of crossover and mutation. It should be
used as a baseline for their experiments in the GA-based noted that these operators have a user defined probability
assignment. of being applied. The traditional crossover operator is
known as one point crossover and exchanges the genetic
III. BRIEF OVERVIEW OF GA FUNDAMENTALS material between two parents two create two off springs.
In this section we present a brief overview of Genetic The traditional mutation operator changes the value of a
Algorithms to elucidate how they can be used to optimize gene from 0 to 1 or vice-versa.
the parameters of the assignment presented in Section II. An Normally in our classes, we demonstrate each step of the
overview of a basic genetic algorithm is shown in Figure 5. basic GA execution using the OneMax problem [12]. The
One important aspect of the GAs is that the same structure onemax problem consists of given a bit string of size n,
presented in Figure 5 can be used to solve different types generating an individual where all values are 1's. This is a
of search and optimization problems. The GAs have this nice example to first show the students how the GA operates.
flexibility because they have three main components that must However, in order to allow the students to apply this
be defined according to the problem: techniques to real world problems it is important that they
 TABLE I
ANALYSIS OF THE PACMAN PARAMETER OPTIMIZATION ASSIGNMEN T

Team Framework # of Heuristics Representation Selection Cross-over Type Mutation Type Improved Results
with the GA?
1 ECl 8 Float (Diff. Ranges) Tournament OnefTwo Gauss �
2 ECl 10 Float (Diff. Ranges) Tournament OnefTwo/Any Gauss �
3 ECl 3 Integers (0 to 100) Tournament OnefTwo Reset �
4 ECl 8 Float (Diff. Ranges) Tournament OnefTwo Gauss �
5 ECl 8 Integers (0 to 100) Tournament OnefTwo Reset �
6 ECl 4 Integers (0 to 100) Tournament OnefTwo Reset �
7 ECl 8 Integers (Diff. Ranges) Tournament One Reset �
8 ECl 8 Integers (0 to 100) Tournament Two Reset �
9 ECl 8 Integers (0 to 100) Tournament One Reset �
10 ECl 8 Integers (0 to 100) Tournament One Reset �
11 ECl 8 Integers (-100 to 100) Tournament One Reset �
12 ECl 9 Integers (-100 to 100) Tournament OnefTwo Reset �
13 ECl 8 Integers (-100 to 100) Tournament OnefTwo Reset �

understand both the core concepts as well as why the standard V. EVALUATION OF THE ASSIGNMENT
GA's might need to be modified. For this reason, in our classes,
Table I presents an overview of GA-based pacman assign­
we also demonstrate how the GA could be used to provide
ment evaluation. The analysis of Table I and of the reports
solutions to the Travelling Salesman Problem (TSP). The TSP
handed in by the students after they completed the assignment
in an interesting example because the individual representation
show some interesting insights.
can be based on the list of cities (one route in the TSP), there
First, all students choose to use the Java-based Evolutionary
is a clear fitness function (find the smallest route) and the
Computation Research System (ECJI). This choice might
standard genetic operators of mutation and crossover might
have been influenced by the use of the ECJ framework in
generate invalid routes. This two examples are enough, in our
one of our practical classes where the students run some
experience, to prepare the students to deal with the parameter­
simulations using the max one tutorial. However, despite the
based optimization problem presented in the next section.
students familiarity with the framework, this shows that the
students decided to take a deep understanding of how the
IV. THE GA-B ASED PACMAN ASSIGNMENT ECJ framework works rather than implementing their own
AG. When we asked the students about their reason for using
In order to motivate the students and help them develop the ECJ framework, their common answer was that within
practical skills for using GAs to solve an optimization prob­ the framework they only needed to implement/modify a few
lem, we use the same Pacman framework that the students classes to have their assignment working. Furthermore, the
have used in a previous assignment (presented in Section II) students liked some of the built-in facilities that the ECJ
and ask the students to: framework offers, such as parallelism and the ability to create
• Design and Implement a representation that takes into and restore checkpoints.
account the search depth (only if they implemented the Second, most teams have used a vector of Integers to
Breath First and/or A * Search Algorithm with fixed­ represent their individuals. While some teams used only pos­
depth) and the weights assigned to each heuristic. itive values (normally from 0 to 100), others allowed their
• Design and Implement at least two fitness functions to chromosomes to receive negative values as well. It should
evaluate their developed individuals. be noted that for the teams that implemented the breath first
• Decide whether or not it is necessary to modify the search and A * search algorithms, they normally encoded the
genetic operators of mutation and crossover. depth of the search as being the first gene in the chromosome.
• Design and run experiments in at least two ghost settings Furthermore, all teams that implemented the depth-limited
to evaluate: search methods took safe guard measures to not allow the use
What is the impact of changing the population size? negative or relatively high (e.g. higher than 5) values in the
gene responsible for the depth. Figure 6 presents information
What is the impact of changing the probability values
about which search methodes) were used in the GA-based
of the genetic operators of mutation and crossover?
What was the best individual found in your experi­ optimization of each team.
ments? Is this individual better than the solution you Third, all teams used the selection by tournament. Fourth,
found in the previous assignment? while some teams only used the one point crossover that they
learned about during the lectures, the majority of the teams
• Write a detailed report explaining everything that they
did and reporting any issues they had. I Available at: [Link]
 1 1 1 1 1 111 10 1 1
. G reedy

Team 01 Team 02 Team 03 Team 04 Team 05 Team 06 Team 07 Team 08 Team 09 Team 10 Team 11 Team 12 Team 13

Fig. 6. Search methodes) used by each team in the GA-based Pacman assignment.

250000 ,-----

200000 +------

150000 +------

.Manual

.GA-Based
100000 +-----

50000

o
Team 01 Team 02 Team 03 Team 04 Team 05 Team 06 Team 07 Team 08 Team 09 Team 10 Team 11 Team 12 Team 13

Fig. 7. Comparison of the scores obtained by manuaUy adjusting the weights against the GA-based approach for each team.

also researched about the two point crossover or, in the case of their importance, different authors have addressed the issue
one particular team, the any point crossover. Figure 8 presents of how to teach Genetic Algorithms in different ways.
the crossover types percentage used by the different teams. In the work of Venables and Tan [3] the authors proposed a
Fifth, due to the representation being used (Integers in "hands on" strategy to teach genetic algorithms using poppet
all but three cases, in which floats were used), the students
also had to research how to adapt the mutation operator. For
the integers representation the students employed the reset
mutation type, which randomly changed the current value of
a gene by a random value within the gene valid values range.
Sixth, as we have requested the students to design and
implement at least two fitness functions, they all implemented
the absolute score as one of the fitness function. Figure
9 presents the percentage of the different types of fitness
functions used by the different teams. The analysis of Figure 9
shows that 31 % of the teams did not propose a second fitness
function, while the others teams used the score and the game Fig. 8. Different types of crossover used by the students.
time in different ways or the last achieved level before death.
Seventh, all teams reported that by using the GA-based
.None • level .Time .Score - Time .Score / TIme
approach, they were able to achieve better Pacman players than
.8%
the one developed by manual trial and error. Figure 7 presents
a comparison of the best scores obtained by manually adjusting
the weights against the best GA-based approach weights for
each team. .38%

VI. RELATED WORK

Genetic Algorithms are an important artificial intelligence .8%

technique that can aid in the development of solutions for

different scientific and engineering applications [1]. Given Fig. 9. Different types of fitness functions used by the students.
beads to represent Biston betula moths. The main idea is that Pacman framework to learn about genetic algorithm-based
individuals can be represented by using a string of black and parameter optimization. This is important as students often
white poppet beads, similar to a bit string vector. The students feel discouraged if they have to learn different frameworks
are then asked to: (1) work in pairs and randomly create a for different assignments. The proposed assigned was inspired
population of eight moths (with chromosome size = 8); (2) by the work of DeNero and Klein [9] who uses the classic
select the 4 fittest individuals; (3) clone these individuals and video game Pacman as a framework for different assignments
randomly divide them in pairs of two; (4) Use the cloned involving several artificial intelligence techniques.
individuals to perform crossover; (5) Randomly change the The evaluation of the assignment in our undergraduate
color of one poppet in the current population (which is artificial intelligence classes have shown that the students
equivalent to the mutation operator). properly learned about the core concepts of applying a genetic
In the work of Salcedo-Sanz et al. [6] and Tsai et al. [7] the algorithm to an optimization problem. Furthermore, when
authors use Japanese puzzle, also known as nanogram to teach comparing their GA-optimized players with their previously
advanced features of genetic algorithms. In order to solve the developed players all students reported that the performance
puzzles using the GA's the students need to learn about the of their players was enhanced.
problem and use binary matrices to represent the individuals.
ACKNOWLEDGMENTS
For this reasons they also need to adapt the inner working of
the generation operators of mutation and crossover. The author would like to thank DeNero and Klein for their
In the work of Fernandez-Manjon et al. [8], the authors pro­ inspiring work on teaching artificial intelligence using the
pose two games that can be used to teach genetic algorithms. classic video game Pacman, Ted Grenager for making the java­
The first game is based on the rabbit and the dogs game, which based version of the Pacman framework and the anonymous
consists of a board games with 3 dogs that try to catch a rabbit. reviewers for their valuable feedback.
The GA is used to automatically developed a controller for
REFERENCES
the game and they use different fitness functions according
[I] D. A. Coley, An Introduction to Genetic Algorithms for Scientists and
to the difficulty level (easy, intermediate or advanced). The
Engineers. World Scientific,1999.
students can also configure the number of: (1) individuals for [2] J. H. HoUand, Adaptation in Natural and Artificial Systems. The
each generations; (2) max number of generations; (3) mutation University of Michigan Press,1975.
[3] A. Venables and G. Tan, "A 'hands on' strategy for teaching genetic
probability). The second game is the ten and a half card game
algorithms to undergraduates," Journal of Information Technology Edu­
which the objective is to draw cards to get as close as 10.5 as cation, vol. 6,2007.
possible. As with the previous game the students can configure [4] C. Prince,R. L. Wainwright,D. A. Schoenefeld,and T. TuU,"Gatutor: a
graphical tutorial system for genetic algorithms," in Proceedings of the
several parameters. twenty-fifth SIGCSE symposium on Computer science education, 1994,
Other authors developed tools to aid the understanding pp. 203-207.
of how genetic algorithms work in interactive framework. [5] B. G. Gardner and D. Simon,"Evolutionary algorithm sandbox: A web­
based graphical user interface for evolutionary algorithms," in Proc. of
Examples of this approach are the GATutor developed by the IEEE International Coriference on Systems, Man and Cybernetics,
Prince et al. [4] and the Evolutionary Algorithms Sandbox 2009,pp. 577-582.
developed by Gardner and Simon [5]. Cao and Wu [13] have [6] S. Salcedo-Sanz, J. A. PortiUa-Figueras, E. G. Ortiz-Garca, A. M.
Perez-Bellido,and X. Yao,"Teaching advanced features of evolutionary
used Matlab to teach genetic algorithms. algorithms using japanese puzzles," IEEE Transactions on Education,
The review presented in this section about the state of the art vol. 50,no. 2,pp. 151-156,2007.
on teaching about genetic algorithms shows that many interest­ [7] J.- T. Tsai,P.-Y Chou,and J.-c. Fang,"Learning intelligent genetic al­
gorithms using japanese nonograms," IEEE Transactions on Education,
ing and inspiring initiatives have already been done. However, vol. 50,no. 2,pp. 164-168,2012.
we are unaware (to the best of the authors knowledge) of [8] J. M. Chaves-Gonzalez,N. Otero-Mateo,M. A. Vega-Rodriguez,J. M.
any approaches that have the video game pacman to teach Sanchez-Perez, and J. A. Gomez-Pulido, Game Implementation: An
Interesting Strategy to Teach Genetic Algorithms. Springer,2007,ch.
about optimization using genetic algorithms. In the context of Computers and Education,pp. 205-223.
optimization education, an interesting approach was developed [9] J. DeNero and D. Klein, "Teaching introductory artificial inteUigence
by Syberfeldt and Syberfeldt [14] where they developed a with pac-man," in Proceedings of the Symposium on Educational Ad­
vances in Artificial Intelligence (EAAl), 2010.
serious game using a Lego factory to teach students about [10] S. J. RusseU and P. Norvig,Artificial Intelligence: A Modern Approach.
production optimization. The idea behind the game is that the Pearson Education,2003.
student becomes the factory production manages and has to [11] Y-H. Liao and c.-T. Sun,"An educational genetic algorithms learning
tool," IEEE Transactions on Education, vol. 44,no. 2,2001.
find the best possible configuration to maximize profit. The [12] J. D. Schaffer and L. 1. Eshelman, "On crossover as an evolutionary
game is designed to make students realise the infeasibility of viable strategy," in Proc. of the 4th Int. Con! on Genetic Algorithms,
exhaustive testing and the benefits of AI-based optimization. 1991,pp. 61-68.
[13] Y J. Cao and Q. H. Wu, "Teaching genetic algorithm using matlab,"
The students then had to implement their own evolutionary International Journal of Electrical Engineering Education, vol. 36,
algorithm. no. 2,pp. 139-153,1999.
[14] A. Syberfeldt and S. Syberfeldt, "A serious game for understanding
VII. CONCLUSIONS artificial intelligence in production optimization," in Proceedings of the
2010 IEEE Coriference on Computational Intelligence and Games, 2010,
The main contribution of this work was to present and pp. 443-449.
evaluate an assignment that allows the students to use the