Name ………………………………….
Instructions:
Paper Code: COMP717
Artificial Intelligence
Lecturer: Ji Ruan Assignment 1
Due Monday, 3 May 2021
ID number……………………..
Please attach this sheet to the front of your assignment.
• This assignment contributes 50% towards your final 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, 3 May 2021. The submission requirement is specified at the end of each option.
• You can team up with another student. If you work as a team, both students should sign this page, but only one submission is needed.
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.
Here is a quote from Richard Feynman, a well known scientist, “The first principle is that you must not fool yourself and you are the easiest person to fool.”
Please sign to signify that you understand what this means, and that the assignment is your own work.
Signature: ………………………………….
1
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 Tutorial 1, you were given the opportunity to play a game named “Win an additional mark if U can!”. The same game was played again in a lecture with a larger attendance.
All the participants were presented an online form like this:
Everyone were given time for thinking and submitting the answers. This is a variant of Keynes’ Beauty Contest Game discussed during a lecture. Your tasks are as follows.
Task 1 (10 Marks)
Here is a simplified 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. (4 marks)
(b) Which pure strategy should each of the two rational players choose? Show your argument. (4 marks)
(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. (2 marks)
2
Task 2 (60 Marks)
The game has been played for a few times. You’ll look at the sessions of this year and 2019. Here are more details. The data files are available under the assignment folder.
• Year 2021:
There are 3 tutorials/labs (A, B, and C, in chronicle order). In week 1, the participations are all online. The participants in B and C were informed the winners’ choices of earlier session A. Both A and C happened during the tutorial, while B was given longer time by receiving the game by email.
In week 3, we had a discussion of the results in week 1 and the theoretical solution assuming perfect rationality as a common knowledge, then we played the game again. The participants were from the physical classroom and online.
We’ve made data files of all results by replacing the name and student IDs with pseudo IDs of letters followed by a number: 2021week1data.csv is for week 1; 2021week3data.csv is for week 3.
• Year 2019:
We played the same game in a slightly different setting. There were 3 labs (A, B, and C, in chronicle order), and each lab played in tutorial 1 (week 1) and tutorial 2 (week 2). In tutorial 1, the participants in B and C were informed the winners’ choices of earlier sessions. In tutorial 2, the tutor gave a suggestion on what he thought the average for each lab and made it public: 30 for A, 20 for B and 10 for C.
A final game was then played during week 5, where the players were given a choice of 10, 20 or 30. It was played during a lecture.
We’ve made a data file of all 7 sessions by replacing the name and student IDs with pseudo IDs of letters followed by a number: 2019data.xlsx.
Your task is to study these two data files and write a report of 5 pages maximum. You need to discuss at least the following points:
(a) Discuss what is rationality. Discuss if the winners win by rational thinking, pure luck, or a combination of both. Your shall utilise the data files to support your argument. (5 marks)
(b) Give a classification of players in terms of different levels of rationality and their knowledge about other’s rationality. A good classification scheme shall cover at least 3 classes. For each class, you give a clear criteria, so that each row in the data file can be classified into one of the classes. You need to show this as part of your answer. You can use IDs to refer to the players.
To support your scheme, you shall utilise the reasons given by the players (but be minded that the players do not necessarily articulate their reasons very clearly). (20 marks)
(c) Across all plays in 2019 of the same week, Lab B’s winning number is lower than that of A, and Lab C’s winning number is lower than that of B. Explain the possible reasons of this phenomena using the data sets.
Discuss in 2019 if the suggested numbers given by the tutor may have affected the results. Compare the difference between year 2021 and 2019.
(10 marks)
(d) What is the pure strategy Nash equilibrium of this game assuming the perfect rationality of all agents? None of the lab winners chooses this strategy. If we repeatedly play this game, what would be likely to happen? Note that in 2019, each lab had a repeated play of this game.
Design an experiment to test/verify your reasons. Recruit some friends or family to play in your exper- iment (with no less than 6 players).
(15 marks) Hint: you’ll need to think about what reward to be offered, e.g. we used additional marks for the labs.
3
Task 3 (30 Marks)
Using the knowledge in game theory to design a normal-form game that can be played by multiple people. The game should be designed in a way that the outcome is decided by the players collectively, not by a single player. Write a report to at least discuss the following points.
• The game design: players, actions, rewards. And the game theoretical analysis, e.g. is there a Nash equilibrium assuming perfect rationality of the players?
• The experimental results. Extra marks (up to 5)
Extra marks can be given if you are able to do something extra, e.g., visualising the data in an interesting and meaningful way; doing extensive experiments to verify your prediction, etc. 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. One submission per team. You are required to provide:
(1) Your solution to Task 1, and
(2) Your report for Task 2 (Limited to 5 pages; clearly indicate (a)-(d)), (3) Your report for Task 3 (Limited to 3 pages).
We prefer (1), (2) and (3) are included in a single PDF file. If you have extra data, your submission should including everything in a zip file. The file name follows the following format: AI2021A1A-XY.zip, where XY is your student ID(s). The submission is via Blackboard.
4
Option B: Game Playing Agent
The aim of this assignment is for you to better understand computer game playing by implementing a special game playing agent with the minimax algorithm and evaluation function.
Task 1 (10 Marks)
Tic-Tac-Toe This problem exercises the basic concepts of game playing, using Tic-Tac-Toe (Naughts and Crosses) as an example, so that you have a better understanding on the main method in Deep Blue beating the best human chess player.
Tic-tac-toe has two players, X and O, who take turns marking the spaces in a 3×3 grid. X player starts first. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins the game.
(a) Estimate the number of possible game plays of Tic-Tac-Toe. One game play is a sequence of moves from initial state till a terminal state. (2 marks)
(b) Show the whole game tree starting from an empty board down to depth 2 (i.e. one X and one O on the board), taking symmetry into account. (2 marks)
By symmetry, we mean that if you turn the whole board around (without moving the relative position of the pieces), you’ll get the same configuration. For example, the following 4 states are the same under symmetry.
They are different from the following state no matter how hard you turn
(c) Mark on your tree the evaluations of all the positions at depth 2. The evaluation function is given as follows. (2 marks)
We define Xn as the number of rows, columns or diagonals with exactly n X’s and no O’s. Similarly, On is the number of rows, columns or diagonals with just n O’s. The utility function assigns +10 to any position with X3 >= 1 and -10 to any position with O3 >= 1. All other terminal positions have utility 0. For the nonterminal positions, we use a linear evaluation function defined as
Eval(s) = 3X2(s) + X1(s) − (3O2(s) + O1(s))
(d) Using the minimax algorithm, mark on your tree the backed-up values for the positions at depths 1 and
0, and use those values to choose the best starting move. (2 marks)
(e) Circle the nodes at depth 2 that would not be evaluated if alpha-beta pruning were applied, assuming the nodes are generated in the optimal order for alpha-beta pruning (i.e., in that order, you can prune the most numbers of nodes). (2 marks)
(f) (Optional) If minimax (or alpha-beta) were to search the entire game tree, it would evaluate all opening moves equally – because it assumes the opponent will play optimally, which leads to a draw in the end, no matter what the opening move. However, if we assume the opponent could make an error, we can see that some opening moves are better than others. Explain why.
5
Task 2 (60 Marks)
Consider the Take-away game discussed in the lecture:
• There is a pile of X chips on the table.
• Two players take turns to remove 1, 2, or 3 chips from the table, with player 1 starting first.
• The player removing the last chip(s) wins the game.
In this task, you are asked to develop a game playing agent which can play the Tic-Tac-Toe and the Take-away games against a human player. In particular, you will need to:
(a) Implement the minimax algorithm in two versions: (40 marks)
• (i) complete tree search.
You may use Depth-first search (DFS).
• (ii) depth limited tree search and an evaluation function.
For depth limited tree search, you just need to introduce a depth variable and when it decreases to 0, either the evaluation value or the terminal value is returned. For Tic-Tac-Toe game, the evaluation function is outlined in task 1. For Take-away game, you need to come up with your own evaluation function.
A Pseudocode can be found at https://en.wikipedia.org/wiki/Minimax Report on the details of your program design (data structures, and functions).
Let two versions compete against each other and report on the performance difference, e.g., win-draw-lose rate, and resource consumption.
(b) Implement an intuitive user interface which allows the human player know the game state/actions to play. In the start of games, the human player should be able to choose who plays first and which version of the minimax algorithm to use (in the case of depth limited, allowing to set the search depth).
Note that for the Take-away game, when the number of chips is large, it might not be practical to display chips visually. In that case, you can use numbers.
Report on the program design.
(10 marks)
(c) Your agent is resource bounded, so the response of the player will be slower if the game gets larger. Design experiments to study the scalability of your game playing agent by using the Take-away game.
Specifically, here are some important aspects to consider:
• Varying the value of X.
E.g., when you have a large value, say X=1000, the game tree for Take-away will be super large, more than 3334 leaves (the branching factor b=3 (three actions), and the depth of leaves ranges from 334 – 1000). So one question on scalability will be: what is the maximal value of X that your agent (running in your hardware) can handle (producing a response in a reasonable amount of time, say 100 seconds?)
• Extending the number of chips the players are allowed to take away.
E.g., you could add two more actions: taking away 4 chips, taking away 5 chips. This will increase the branching factor to 5.
• Varying the limit of search depth.
Report on your experiment design and results. Your hardware and software configurations should also
be noted as they are very relevant to the results.
6
(10 marks)
Task 3 (30 Marks)
Implement a game player for a game of your own interest. Here are the requirements.
• Describe the game clearly, including the players, actions, game dynamics, terminal conditions and goals.
• Your player should use the minimax algorithm in Task 2, and the alpha-beta pruning algorithm. A Pseudocode can be found at https://en.wikipedia.org/wiki/Alphabeta_pruning
• Let two versions compete against each other and report on the performance difference, e.g., win-draw- lose rate, and resource consumption. It is required that the game has enough complexity so that you are able to see the difference.
Extra marks (up to 5)
Extra marks are given if you are able to do something extra, e.g., the optional tasks, or adding another game, such as the more complex Nine-board Tic-Tac-Toe. These extra marks can make up your loss in other parts of assignments. The total mark is capped at 100.
Submission
You can team up with a classmate to work on this assignment. One submission per team. You are required to provide:
(1) Your solution to Task 1.
(2) A report for Task 2. (Limited to 5 pages)
(3) A report for Task 3. (Limited to 3 pages)
(4) The source code and the compiled program of your game playing agent (with notes on what library it may depends on and instructions on how to run it). There is no restriction on your programming language.
We prefer that (1), (2) and (3) are included in a single PDF file. Your submission should including
everything (report and source code) in a zip file. The file name follows the following format: AI2021A1B- XY.zip, where XY is your student ID(s). The submission is via Blackboard.
7