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)
Copyright By PowCoder代写 加微信 powcoder
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. Atext-based.pdffilenamedas: FamilyName-StudentId-2ndSem2022FIT3080.pdf
2. A.pyPythonfilenamedas: 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 flips.
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.
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.
Hint4: Ifapieceisat(w,x)thenwandxbothlieinthevalues{1,2,3, 4, 5, 6, 7, 8}
Hint 5: No two or more pieces can go on the same square
Hint6: Arookat(w,x)cancaptureapieceat(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) = abs(x-z))
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”.
. Kao or or or or Emmy Noether or Srinivasa Ramanujan or or (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 worked on the problem of interest or . Kao worked on the problem of interest then worked on the problem of interest.
If worked on the problem of interest and . Kao also worked on the problem of interest then worked on the problem of interest.
If Srinivasa Ramanujan worked on the problem of interest then worked on the problem of interest.
, and (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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com