COMP329 ARTIFICIAL INTELLIGENCE
Assignment 2 Finalised (Weight: 20%)
Evolutionary Algorithms for Adversarial Game Playing
Due: 06:00pm, Nov 06, 2019 (Wednesday, Week 13)
The goal of this assignment is to appreciate the efficacy of Evolutionary Algorithms, specif-
ically Genetic Algorithm (GA), in the context of Game Theory, in particular, Iterated Pris-
oners Dilemma (IPD) and the Iterated Game of Chicken (IGC).
You will be using the DEAP package for Genetic Algorithm in order to evolve strategies
for playing IPD and IGC. We have come across the Prisoners Dilemma and the Game of
Chicken from the lecture slides (Week 10). Use the matrix provided in Table 1 and Table 2
for PD and GC respectively.
Table 1: Payoff matrix to be used for Prisoner’s Dilemma. D: defect; C: cooperate
D C
D (1, 1) (5, 0)
C (0, 5) (3, 3)
Table 2: Payoff matrix to be used for the Game of Chicken. D: straight, C: swerve
D C
D (0, 0) (5, 1)
C (1, 5) (3, 3)
The main issue is the representation of a strategy for playing a game like PD or Chicken
as a bit string. A paper is provided in the Assignment folder that will help you with this.
Note: This assignment was discussed at the start of the lecture in Week 11 (Tuesday).
Students may find it helpful to consult the video (Echo360).
1
Task Specification
1. BACKGROUND KNOWLEDGE ASSESSMENT [5 marks]
(a) Consider the Cuban missile crisis of the cold war era (see this wiki page). Sup-
pose we want to model it as a two person adversarial game. Which of the two,
Prisoners Dilemma and the Game of Chicken, is a more appropriate model of
this situation? Answer this question in no more than 50 words.
(b) Suppose we want to represent strategies for playing IPD of memory depth 3 in
the context of GA. How many bits shall we need to represent the individuals,
and why? Answer in no more than 50 words.
(c) Suppose we want to represent strategies for playing IGC of memory depth 3 in
the context of GA. Considering the similarities in the payoff structures of the
two games, what representational modifications, if any, will be required for this
purpose?
(d) Consider a strategy (individual/chromosome) of memory-depth 2 for playing
IPD represented by the template: CDDC ∗∗∗∗ ∗∗∗∗ ∗∗∗∗ ∗∗∗∗. Describe
its behaviour in English.
(e) Consider a strategy (individual/chromosome) of memory-depth 2 for playing
IPD represented by the template: ∗∗∗∗ ∗∗∗∗ ∗∗∗∗ ∗∗∗∗ CCDC. Describe
its behaviour in English
2. IMPLEMENTATION [12 marks]
(a) Implement in Python the function:
payoff_to_ind1(individual1, individual2, game):
returns payoff
Note: individual2 is the adversary, and payoff is determined by latest
moves obtained from respective appropriate memory locations and the payoff
matrix for the relevant game (PD or GC). Assume memory-depth of 2.
(b) Implement in Python the function:
move_by_ind1(individual1, individual2, round):
returns individual1’s move
Note: individual1’s next move is based on both the individuals’ earlier
moves and individual1’s strategy (encoded in individual1’s chromo-
some). The move to be returned can be C/D or 0/1 depending on your rep-
resentation. Note that in early rounds some default moves are made. Assume
memory-depth of 2.
2
(c) Implement in Python the function:
process_move(individual, move, memory_depth):
returns success / failure
Note: individual’s relevant memory bits are appropriately updated based
on its latest move move and memory depth.
(d) Implement in Python, using the DEAP package, genetic evolution of strategies
for playing IPD. Assume a memory depth of 2.
(e) Modify the code you wrote as part of Task 2d so as to genetically evolve strate-
gies for playing IGC. Assume a memory depth of 2.
(f) What is the best IPD-individual you generated via GA? What parameters (fit-
ness function, type of crossover, mutation rate, etc.) did you use, and why?
(g) What is the best IGC-individual you generated via GA? What parameters (fit-
ness function, type of crossover, mutation rate, etc.) did you use, and why?
3. ANALYSIS [3 marks]
(a) Describe in English the behaviour of the IPD-strategy you obtained via task 2f
above. Exploit any pattern you notice in it for this purpose.
(b) Describe in English the behaviour of the IGC-strategy you obtained via task 2g
above. Exploit any pattern you notice in it for this purpose.
(c) Compare the two strategies above in terms of traits such as being nice, being
forgiving and being provocable. Make an attempt to explain any major differ-
ence in these two strategies in terms of their payoff structures.
3
What to Submit, and When
You will submit two files:
1. code.py
2. report.pdf.
Your code file should include all the Python codes you wrote for this assignment.
Your report file should include all the answers (including the Python codes copied-and-
pasted). It must be submitted in the pdf format. It must have as cover page the one that has
been supplied (as part of the document template), duly filled and signed. Also, if relevant,
note in the last section anything relevant that is worth noting.
You will submit the files in two stages. In the first stage you must submit two draft files
(that you will be able to update) by 6:00pm, Wednesday Week 12:
(a) of the program file code.py including at
least the implementation of functions specified in Tasks 2a and 2b.
(b) of your report file report.pdf with an-
swers to Tasks 1a-1e. You can modify these files while preparing your final ver-
sion. However, failure to submit the two draft files by the required date will attract
a penalty of 4 marks. The final version of these three files must be submitted by
6:00pm, Wednesday Week 13.
4