FIT3080 – Assignment 1 – S2 / 2022
FIT3080 Artificial Intelligence
Assignment 1
2nd Semester 2022
This assignment is worth 14% of your final mark (subject to the hurdles
described in the FIT3080 Moodle Unit Information page).
Wednesday 7th September 2022, 11:55pm (Melbourne time)
There are 4 questions in total with 100 available marks.
Make sure you read this specification carefully. You should also pay
special attention to the additional notes (at the end) for tips on how to
respond to the questions and how to deal with unexpected difficulties.
Method of submission:
Your submission should consist of 2 files, both of which must be
uploaded to the FIT3080 Moodle site by the due date and time.
1. A text-based .pdf file named as:
FamilyName-StudentId-2ndSem2022FIT3080.pdf
2. A .py Python file named as:
FamilyName-StudentId-2ndSem2022FIT3080.py
All of your submitted work should be in machine readable form, and
none of your submitted work should be hand-written. Your answers for
(e.g.) search steps should be in readable .pdf rather than as an image.
Show your working and make your answers clear.
The pdf file will undergo a similarity check by Turnitin at the time you
submit to Moodle. The Python py file is only for the implementation of
Question 3. This question should also be addressed in the pdf file.
Read all of the instructions carefully, including the notes on the last page.
The details of the submission instructions are possibly subject to change.
In the event of any change, students will be notified.
Question 1
[(4 + 4 + 4 + 5 + 8 + 5 + 5) = 35 marks]
In the “pancake puzzle” a kitchen cook produces stacks of N differently
sized pancakes. Before they can be served the pancakes must be nicely
sorted by size, so that the smallest one is always on top. We do this with
the help of a spatula, which can be used to flip some or all of the
pancakes in the stack, thus reversing their order. Figure 1 shows an
example. Our job is to sort any given stack using the fewest possible
Figure 1 (a) In this size 5 pancake problem the stack is initially arranged
as [3, 1, 2, 5, 4]. (b) As an example, we insert the spatula between the 3rd
and 4th pancake and flip, which produces a new state [2, 1, 3, 5, 4].
Throughout the questions below, when doing a search, give values for
f(n), g(n) and h(n) at each node n.
(a) Construct a non-trivial heuristic, h1, for a state of the size 5
pancake puzzle (non-trivial means h1 is not always zero). Describe
your heuristic and then demonstrate (or prove) it is admissible.
(b)Construct a different non-trivial heuristic, h2, for the size 5 pancake
puzzle. Describe h2 then show that it too is also admissible.
(c) Construct another admissible heuristic, h3,which dominates both h1
and h2. Describe then demonstrate (or prove) that h3 is admissible.
(d) Choose one of your admissible heuristics, h1, h2 or h3. Using your
chosen heuristic, apply A* search for the problem instance in
Figure 1 (left). Show the graph that results after the first 12
expansion steps. Label the nodes clearly. For each one show the
state of the pancake stack, the corresponding g-, h- and f-value, and
the parent node. Also indicate the membership of OPEN and
CLOSED after the 12th expansion step.
(e) Report the cost of the plan (number of flips) and the corresponding
sequence of states eventually returned by A*. In one or two
paragraphs, state clearly why you believe that this is the minimum
number of steps. For example, you might refer to an enumerated
proof generated by the complete A* search (included as an
appendix) or you can refer to any other sufficient argument.
(f) Take your chosen heuristic from part (d) and change it to derive a
new heuristic h4 which works as follows: at the goal state the
returned value is 0, but if we are not in a goal state and the 5th
pancake is at the bottom of the stack then the heuristic value is very
large (>= 1000). Is h4 admissible? Explain why or why not using
examples as appropriate.
(g)What would happen if we do a greedy best-first search using h4?
Show the graph that results after the first 12 expansion steps of this
algorithm. Explain your answer, and show all working. Use the
same style of presentation for your answer as in question (d).
Hint: Familiarity with chapter 3 of Russel and Norvig, and associated
lecture material, may be very helpful when attempting this question.
Question 2
[5 + 5 = 10 marks]
The 8-Queens Problem asks us to place 8 “Queen” pieces on an 8×8
Chess board, such that no Queen is attacking any other. If you are
unfamiliar with the movement rules of Chess pieces, refer to the
following page: https://en.wikipedia.org/wiki/Chess#Movement
Consider the following start state in the 8-queens problem, with queens at
[a1, b7, c4, c6, e8, g2, g5, h3].
Consider moves based on leaving queens in the rows (or ranks) that they
are in in the start state and then move them one space: to the left (if not in
leftmost file or column, a) or one space to the right (if not in the rightmost
file or column, h). A successor state is produced after selecting and
moving one queen in the manner described.
Starting at the start state, you seek a goal state via search steps as
described above.
(a) Try a breadth-first search (BFS) until you find a goal state. You
can stop after 25 expansion steps if you have not found a solution.
Show all working.
(b)Try a depth-first search (DFS) until you find a goal state. You can
stop after 25 expansion steps if you have not found a solution.
Show all working.
https://en.wikipedia.org/wiki/Chess#Movement
Hint: When generating successors you may find it helpful to order the
successor set in some way. For example, you might begin with the queen
in the lowest rank that has not yet moved (rank 1, then 2, then 3 etc).
After you select a queen, generate the successor corresponding with a
move to the left (if possible), then generate the successor corresponding
with a move to the right (again, if possible).
Question 3 (40 marks)
In chess, a rook moves horizontally along ranks (or rows) and can also
move vertically along files (or columns); a bishop moves diagonally; and
a knight (which resembles a horse) moves “1, 2 and across” unaffected by
any pieces located between its location and its destination. In chess, a
queen has the combined powers of a rook and a bishop.
In Capablanca chess (a variant game attributed to José Raúl Capablanca
(y Graupera), who was world chess champion from 1921-1927), two
additional pieces are introduced:
● The archbishop, with the combined powers of a bishop and knight
● The chancellor, with the combined powers of a rook and knight.
Let us construct an additional piece (whether new or not), which we shall
call an omni (with plural omnis), which has the combined powers of a
rook, bishop and knight.
Consider now an 8 x 8 chess board (or an n x n chess board with n = 8).
We wish to place pieces on the board so that no piece can capture another
piece. We use the notions of various pieces (e.g., chancellor and omni)
introduced above.
We will get 5 points for each omni.
We will get 4 points for each queen.
We will get 3 points for each chancellor.
We will get 2 points for each rook.
No other pieces are allowed to be placed on the board.
Suggest and implement — in python — a search algorithm which can be
used to compute a best solution for this problem (i.e., one that can obtain
a maximum number of points).
There are two parts to this question: an implementation (which you will
need to submit) and a report. The report should describe your algorithm,
in words and pseudo-code. Justify your approach, including an analysis of
its complexity with respect to the problem. Include empirical data to back
up your arguments (e.g., experiments you undertook and the conclusions
you drew from them which helped you to arrive at your final
implementation).
Document your code in a manner consistent with the report, so that the
implementation can be followed.
Hint 1: Placing 8 rooks carefully on the board will get us 16 points.
Hint 2: Placing 8 chancellors at least as carefully on the board will get us
24 points.
Hint 3: Parts of Question 2 will enable us to get closer to 32 points.
Hint 4: If a piece is at (w, x) then w and x both lie in the values {1, 2, 3,
4, 5, 6, 7, 8}
Hint 5: No two or more pieces can go on the same square
Hint 6: A rook at (w, x) can capture a piece at (y, z) iff (w = y) or (x = z)
Hint 7: A bishop at (w, x) can capture a piece at (y, z) iff (abs(w-y) =
Hint 8: A knight at (w, x) can capture a piece at (y, z) iff ((abs(w-y) = 1)
and (abs(x-z) = 2)) or ((abs(w-y) = 2) and (abs(x-z) = 1))
Hints 6 and 7 are technically not correct if there is a piece in between, but
that does not concern us overly here because we care about whether any
piece can capture any other piece.
Hint 9: This is an open-ended question which you are free to tackle with
any approach. Chapter 3 and Chapter 4.1 of Russel and Norvig are good
starting points on your journey of discovery.
Note also that there will be prizes for achieving the most points among
all students in the class!
Question 4 (15 marks)
This fictional question is inspired by the various scientific contributions
of the people mentioned in the question, all of whom are now deceased.
They all did many important pieces of work. We shall focus on one such
piece of work – and we shall refer to that as “the problem of interest”.
Charles K. Kao or Lise Meitner or Maryam Mirzakhani or Florence
Nightingale or Emmy Noether or Srinivasa Ramanujan or Elizabeth Scott
or Chris Wallace (1933-2004) worked on an important problem which we
shall refer to as “the problem of interest”. At least one of these people
worked on the problem of interest.
If Emmy Noether worked on the problem of interest then Srinivasa
Ramanujan worked on the problem of interest.
If Florence Nightingale worked on the problem of interest or Charles K.
Kao worked on the problem of interest then Maryam Mirzakhani worked
on the problem of interest.
If Florence Nightingale worked on the problem of interest and Charles K.
Kao also worked on the problem of interest then Lise Meitner worked on
the problem of interest.
If Srinivasa Ramanujan worked on the problem of interest then Elizabeth
Scott worked on the problem of interest.
Maryam Mirzakhani, Elizabeth Scott and Chris Wallace (1933-2004) did
not work on the problem of interest.
Given the above statements, who worked on the problem of interest?
Construct an argument using logic. Show all your working.
This largely ends the assignment specification. Some additional notes
and reminders can be found below. Please read them and the notes on
page 1 carefully.
Give clear answers and justifications
As a general rule, 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 being awarded 0 marks for the relevant exercise.
Make it easy for the person marking your work to follow your reasoning.
The only question requiring any submitted programming is Question 3.
Any programming should be done in Python and submitted as a .py file –
with corresponding parts in the .pdf file.
Your .pdf should typically cross-reference any corresponding answer in
your (Question 3) Python .py file. Without clear cross-reference between
.pdf and .py, it is possible that any such exercise will be awarded 0 marks.
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. Show your working and make your answers clear.
Read the submission instructions carefully
Be aware of all the relevant submission details and related policies (e.g.,
Academic Integrity, Special Consideration, Late penalties, make sure to
hit the `Submit’ button, etc.). Please follow these carefully. If the details
of the submission instructions change then students will be notified.
Late penalties:
Work submitted after the deadline (possibly with a small amount of grace
time) will be subject to late penalties in accordance with the FIT3080
Unit Guide and Faculty and University policies, possibly 10% per
calendar day and certainly no less than 5% per calendar day.
If you do not submit matching .pdf and .py files (e.g., if you submit two
files but one is blank or unreadable, or if you only submit one file), then
any affected work will be deemed late – and will be subject to the relevant
penalties, possibly receiving a mark of 0. Work submitted 10 or more
calendar days after the deadline will be given a mark of 0.
Academic Integrity:
Recall that the text-based .pdf you submit will undergo a similarity check
by Turnitin. This is done at the time you upload your assignment to
Moodle. It is also our intention to perform such a check on the .py file at
the same time if you submit it.
Do not 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.
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. Remember that
Monash University takes academic integrity very seriously.
PLAGIARISM IS NOT ACCEPTABLE