Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
FIT3080 Artificial Intelligence
Assignment 2:
This assignment is worth 24% of your final mark (subject to the hurdles described in the
FIT3080 Unit Guide, Moodle preview and other locations). Among other things (see below),
note the need to hit the `Submit’ button.
Due Date: Thursday 14th October 2021, 11:55pm (Melbourne, Australia time)
Method of submission: Your submission should consist of at least 1 and at most 4 files:
1. A text-based .pdf file named: FamilyName-StudentId-2ndSem2021FIT3080_2.pdf
All the files must be uploaded on the FIT3080 Moodle site by the due date and time. The
text-based .pdf file will undergo a similarity check by Turnitin at the time you submit to
Moodle. Please read submission instructions on last page carefully re use of Moodle.
2. A .py Python file named as: FamilyName-StudentId-2ndSem2021FIT3080_2_Qu4.py
3. A .py Python file named as: FamilyName-StudentId-2ndSem2021FIT3080_2_Qu7.py
(The Python .py files are only for Question 4 and Question 7. Question 4 and Question 7
would be answered both in the .pdf and in .py files.)
4. A .xls (or .xlsx) file named as: FamilyName-StudentId-2ndSem2021FIT3080_2_Qu5.xls
or FamilyName-StudentId-2ndSem2021FIT3080_2_Qu5.xlsx .
The details of the submission instructions are possibly subject to change. In the event of any
change, students will be notified.
Total available marks: 10 + 15 + 15 + 15 + 15 + 15 + 20 = 105 marks, to a maximum of 100
marks. Anyone achieving 100 or more marks will be given 100 marks.
Note 1: Please recall the Academic Integrity exercises from week 2 and the start of semester.
In submitting this assignment, you acknowledge both that you are familiar with the relevant
policies, rules and regulations regarding Academic Integrity and also that you are familiar with
the consequences of being deemed to be in contravention of these policies.
Note 2: And a reminder not to post even part of a proposed partial solution to a forum or
other public location. If asking a question in public, you are advised to please make an effort
to ensure that your question is asked in a way that does not contain even part of a proposed
partial solution. It will often be helpful to find a way to post it as a general question (not
directly pertaining to the Assignment) and then to put it in the General category at Ed
Discussion. You are reminded that Monash University takes academic integrity very
seriously.
Note 3: As previously advised, it is your responsibility to be familiar with the special
consideration policies and special consideration process.
Note 4: As a general rule, please don’t just give a number or an answer like `Yes’ or `No’
without at least some clear and sufficient explanation - or, otherwise, you risk possibly being
awarded 0 marks for the relevant exercise. Make sure to explain your answer and show your
working in all parts of all questions. Make it easy for the person marking your work to follow
your reasoning. Your .pdf should typically cross-reference any corresponding answer in your
(Question 4 and Question 7) Python .py files. Without clear cross-reference between .pdf and
.py, it is possible that any such exercise will be awarded 0 marks. Your .pdf should typically
also cross-reference any corresponding answer in your (Question 5) .xls (or .xlsx) spreadsheet
file. Without clear cross-reference between .pdf and .xls (or .xlsx), it is possible that any such
exercise will be awarded 0 marks.
Note 5: The only questions requiring any submitted programming are Question 4, Question 5
and Question 7. Any programming for Question 4 and Question 7 should be done in Python
and submitted as a .py file – with corresponding parts in the .pdf file. Any spreadsheet
programming for Question 5 should be done in MicroSoft Excel and submitted as a .xls (or
.xlsx) file – with corresponding parts in the .pdf file.
Note 6: As a general rule, if there is an elegant way of answering a question without
unnecessary extra work, try to do it that way. More generally, more elegant solutions are
preferable - and might at least sometimes be given more marks, possibly many more marks.
Show your working and make your answers clear. (Another way to think of this is to try to put
yourself in the marker’s situation.)
Note 7: All of your submitted work should be and must be in machine readable form, and none
of your submitted work should be hand-written - with all cases of handwritten work possibly
resulting in 0 marks. Show your working and make your answers clear.
Note 8: If you wish for your work to be marked and not to accrue (possibly considerable) late
penalties, then make sure to upload the correct files and (not to leave your files as Draft but)
also to hit `Submit’ to make sure that your work is submitted.
----
----
Question 1 (5 + 5 = 10 marks)
For a modified version of (rock (R), paper (P), scissors (S)), we have the following pay-off
matrix:
Player II R P S
Player I
R (0, 0) (-1, 1) (4, -4)
P (1, -1) (0, 0) (-2, 2)
S (-4, 4) (2, -2) (0, 0)
An entry (x, y) means that x is the payoff to Player I and y is the payoff to Player II.
Show your working in answering the questions below.
(a) If Player II plays (R, P, S) with the corresponding probabilities (4/7, 1/7, 2/7), then what is
player I's expectimax strategy and what is the expected payoff?
(b) If Player II plays (R, P, S) with the corresponding probabilities (2/7, 4/7, 1/7), then what is
player I's expectimax strategy and what is the expected payoff?
----
Question 2 (5 + 5 + 5 = 15 marks)
In the following 2-person zero-sum game, players alternate their moves.
Player I seeks to maximise the stated value, and Player II seeks to minimise the stated value.
Consider the following (sub-)tree emanating from a particular node in the game, with an
evaluation given in each leaf:
I
/ | \
II II II
/ | \ / | \ / | \
2 1 3 -1 4 8 6 -2 I
a b c d e f g h / \
5 7
i j
Put another way, I has three available moves. After I’s 1st move, II has 3 choices (respectively
with evaluation 2, 1, 3). After I’s 2nd move, II has 3 choices (respectively with evaluations -
1, 4, 8). After I’s 3rd move, II has 3 choices. After II’s first 2 choices, the evaluation would
respectively be 6 and -2. After II’s 3rd choice, I has two choices, respectively with evaluation
5 and 7.
Label the paths in the (sub-)tree systematically - e.g., the bottom rightmost leaf node (j) with
evaluation 7 could have a path I 3 (3rd of 3 possible moves), II 3 (3rd of 3 possible moves), I 2
(2nd of 2 possible moves), and so could be described as I 3 II 3 I 2 or even as (3, 3, 2).
Assume an appropriate search strategy, with optimal (or rational) play by both sides.
(a) How many leaf nodes need to be explored without use of alpha-beta pruning?
Show these nodes on your search tree. Show the order in which the nodes are searched.
(b) With use of alpha-beta pruning, how many leaf nodes need to be explored?
Show these nodes on your search tree. Show the order in which the nodes are searched.
(c) Using an appropriate search strategy, with optimal (or rational) play by both sides (i.e.,
player I plays maximin and player II plays minimax), what is the path to the resulting node and
what is the pay-off for player I?
----
----
Question 3: Modified Vacuum Cleaner World (6 + 3 + (2+2+2) = 6 + 3 + 6 = 15 marks)
Make sure to show your working and explain your answer to all parts of this question.
Recall the modified vacuum cleaner world example discussed in lab 6a. For this assignment, it
is changed as follows: After any action, exactly one of the two blocks becomes randomly dirty
- with probabilities ?and ?for the left block (?) and the right block (?), respectively.
(Note that ? + ? = 1 .)
There are two actions:
1) stay in the current block and vacuum (abbreviated by “S&V”),
2) move to the other block and vacuum (abbreviated by “M&V”),
Using these two actions, the vacuum cleaner should clean the dirt and receive a reward.
The reward for staying in the same block and vacuuming, “S&V”, (if dirty) is two times the
square root of the respective probability (i.e., if in ? then 2?? and if in ? then 2?? ).
The reward for moving to the other block and vacuuming, “M&V”, (if dirty) is equal to the
maximum of the two probabilities ?and ? (i.e., max(?, ?)).
If the block where the vacuum cleaner moves is not dirty, you will receive a zero reward and
the game ends. The goal is to maximise the cumulative sum of discounted rewards.
(a) Assuming the probabilities ? and ? are given, formulate this modified vacuum cleaner
world as a Markov Decision Process (an MDP), writing down the reward function (, , ′)
and the transition function (, , ′) as tables. (6 marks)
(b) Assume that the vacuum cleaner always starts from the right block, ?. Moreover, if at the
beginning, the vacuum cleaner takes the “M&V” action, then assume that it receives a non-zero
reward equal to 1.5?.
Based on the above, calculate the exact values for ?, ?, and the Transition and Reward
matrices. (3 marks)
Note: You can use a calculator and round the numbers to 3 decimal places, e.g., 2.4557 can be
displayed as 2.456.