Instructions:
Please attach this sheet to the front of your assignment.
This assignment contributes 20% towards your nal grade. The total mark is 100.
Choose one of the options A or B and submit an electronic copy through Blackboard before 11:59 p.m.
on Monday, 4 June 2018. The submission requirement is speci ed at the end of each option.
For both Option A and B, you can team up with another student.
The School of Computer and Mathematical Sciences regards any act of cheating including plagiarism, unau-
thorised collaboration and theft of another student’s work most seriously. Any such act will result in a mark
of zero being given for this part of the assessment and may lead to disciplinary action.
Please sign to signify that you understand what this means, and that the assignment is your own work.
Signature: ........................................
Option A: Knowledge and Rational Agents
The aim of this assignment is for you to gain a better understanding of knowledge and rationality in building
intelligent agents. During Workshop 8, you were given the opportunity to play a game named \Win an
additional mark if U can!". All the participants were presented an online form. like this:
Then about 5-10 minutes were given for thinking and submitting the answers. This is a variant of Keynes’
Beauty Contest Game discussed during Lecture 8. Your tasks are as follows.
Task 1 (20 Marks)
Here is a simpli ed version of the game \Win an additional mark if U can!".
There are two players.
Each player names an integer between 1 and n.
The player who names the integer closest to two thirds of the average integer gets a reward of 2, the
other players get nothing.
If there is a tie, each player gets reward of 1.
(a) Represent this game in Normal Form. You can select any n 5.
(b) Which pure strategy should each of the two rational players choose? Show your argument.
(Hint: The selection of your strategy must be obtained by applying the concept of dominated strategies
to rule out a succession of inferior strategies until only one choice remains.)
(c) Explain that the above strategy is indeed a Nash equilibrium.
Task 2 (80 Marks)
There are in total 3 labs (A, B, and C, in chronicle order). A, C were given by tutor Alvaro, and B was
given by tutor Koz. The participants in B and C were informed the winners’ choices of earlier sessions.
We’ve made a data le of all results by replacing the name and student IDs with pseudo IDs of a letter
followed by a number. Visit this link for online version:
https://bit.ly/2HQDDMi
The same game was played last year in three labs of a similar setting and here is the data le:
https://goo.gl/GTbDsL
Note that under the [File] menu, it can be downloaded for o ine access:
Your task is to study these two data les and write a report of 5 pages maximum (longer reports will be
penalized by a direct subtraction of 1% for every extra line over 5 pages). You need to discuss at least the
following points:
(a) What is rationality? Were the winners win by rational thinking, pure luck, or a combination of both?
Your argument should be supported by evidences.
(b) Give a classi cation of players in terms of di erent levels of rationality and their knowledge about other’s
rationality. You shall utilise the reasons given by the players.
(c) Explain the possible reasons of Lab B’s winning number is lower than that of A, and Lab C’s winning
number is lower than that of B.
Compare the di erence between year 2017 and 2018.
(d) What is the pure strategy Nash equilibrium of this game? None of the lab winners chooses this strategy.
If we repeatedly play this game, what would be likely to happen? How is this related to the AI learning
techniques taught by Prof. Ajit Narayanan?
Extra marks (up to 10) will be given if you are able to do something extra, e.g., visualising the data in
an interesting and meaningful way when you discuss (b), doing extra experiments to verify your prediction
when you discuss (d). These extra marks can make up your loss in other parts of this assignment. The total
mark is capped at 100.
Submission
This is an individual assignment. You are required to provide:
(1) Your solution to Task 1, and
(2) Your report for Task 2.
We prefer that both (1) and (2) are included in a single PDF le. If you have extra data, your submission
should including everything in a zip le with the following format: AI2018A2-XY.zip, where XY is your
student ID(s). The submission is via Blackboard.
Option B: Tiger vs. Dogs in GDL
The aim of this assignment is to develop your ability of formalising abstract concepts and enhance your
understanding of logical reasoning in General Game Playing.
Game Description
Here is a very ancient game originated from China: Tiger vs. Dogs.
In the above 4 4 board, there are one tiger (represented by a white stone in the center) and 16 dogs
(represented by black stones in the perimeter).
The tiger is controlled by the tiger player and the dogs are controlled by the dog player. The tiger player
goes rst and then they take turns. Each player can go one step along the line to an adjacent position that
is not occupied.
When the tiger enters a position such that the following condition hold \two dogs are adjacent to this
position such that they three are in the same line, and also these two dogs have no adjacent dogs in the
same line", then these two dogs are killed by the tiger. If 6 dogs are killed, then the tiger player wins and
the dog player loses.
When the dogs surrounded the tiger such that there is no unoccupied adjacent position for the tiger to
move, then the tiger player loses and the dog player wins.
Task 1 (30 Marks)
Describe this game mathematically (Refer to Lecture 9). Here are some key points:
(a) The set of game states S. Give your estimation of the number of di erent states.
Hint: take the Tic-Tac-Toe for example, a state can be described using,
9 variables of Cell(1,1), Cell(1,2), Cell(1,3), Cell(2,1), Cell(2,2), Cell(2,3), Cell(3,1), Cell(3,2),
Cell(3,3), with possible values x, o, b to represent if cell is marked by xplayer, oplayer or is blank.
1 variable of control, with possible values xplayer and oplayer, to represent which player is in control
e.g., for the initial state, s0, it can be described as h Cell(1,1)=b, Cell(1,2)=b, ... , Cell(3,3)=b, con-
trol=xplayer i
A very rough estimation of the number of states for Tic-Tac-Toe is: 39 2, because for each of 9 cells,
it has 3 possible values, and the control variable has 2 possible values. But you could be more precise
by removing some impossible states (the states are not reachable from the initial state), e.g.,
hCell(1,1)=x, Cell(1,2)=x, Cell(1,3)=x, Cell(2,1)=o, Cell(2,2)=o, Cell(2,3)=o, Cell(3,1)=b, Cell(3,2)=b,
Cell(3,3)=b, control=xplayer i
In the above state both xplayer and oplayer have formed 1 line of their own markings, but this is not
possible as once one player manages to get 1 line of its own marking, then the game is over.
(b) Players P =f1;2g. You may use 1 to represent the tiger player and 2 the dog player.
(c) Actions A. You may use abstraction to get as few types of actions as possible.
Hint: use A1 for the tiger player, and A2 for the dog player. A = A1 A2.
Just list all possible actions for each player, e.g., you can use left as one action for tiger player. Note
that for a particular state, not necessary all actions are possible.
(d) Transition function S A!S. This function is huge, so you may just select a few representative ones.
Hint: You can just use the following format:
give a state s, and players’s joint action (a1;a2), then give the resulting state s0.
(e) Terminal states and utilities. Just describe a few representative ones.
To help you to understand this game, here are a few examples:
Example:
When the dog makes the move by red arrow, the tiger is
surrounded.
Example:
When the tiger makes the move by red arrow, the marked two
dogs are killed.
Example:
When the tiger makes the move by red arrow, the marked two
dogs are killed.
Example:
When the tiger makes the move by red arrow, the marked two
dogs are not killed because there is a dog in the same line that
is next to dog 2 (as marked).
1 2
Task 2 (70 Marks)
(a) Write a game description in GDL (KIF form) for this game. Note that this involves in making the
concepts developed in Task 1 into GDL. The transition function in Task 1 is now succinctly represented
as a set of logical rules. Your GDL should be annotated for better readability.
(b) Test and debug your game description using the game controller (refer to workshop) to ensure that it
runs correctly.
http://sourceforge.net/projects/ggpserver/files/gamecontroller/
In your submission, you need to include at least two execution traces generated by the game controller
with both players using the random type.
Extra marks (up to 10) will be given if you are able to do something extra, e.g., classifying and
visualising the transition function in 1(d) and the traces in 2(b). These extra marks can make up your loss
in other parts of this assignment. The total mark is capped at 100.
Submission
You can team up with a classmate to work on this assignment. You are required to provide
(1) Your solution to Task 1,
(2) Your GDL le for Task 2(a), and
(3) Your test results for Task 2 (b).
We prefer that (1) and (3) are included in a single PDF le. Your submission should including everything
in a zip le with the following format: AI2018A2-XY.zip, where XY is your student ID(s). The submission
is via Blackboard.