Final examination — take-home questions
UWL CS452/552 Artificial Intelligence Fall 2019
This document contains the two final examination questions which you should complete and submit separately from the in-class exam.
There are no short-answer questions on the final examination. Answers which respond to some aspect of a question with “yes,” a “no” or some other terse assertion but without any justification, with a simple list but without elaboration, or with a final formula, property, or value but without its derivation, miss the point of the question’s prompt. The question is giving you the opportunity to demonstrate your understanding of a concept (for example, admissibility) with a constructive argument that a particular example does or does not meet its requirements (for example, why a particular heuristic is or is not admissible for some search). When an answer omits the details of why you draw some conclusion, the answer does not demonstrate understanding of the underlying definitions, algorithms and concepts.
The final examination — both the take-home and in-class portions — is an individual assessment. You must not discuss or share your approach to, notes for, or writeup of its questions with others. Your answers must be your work alone.
Take-home question 1 — Analysis of your Tsuro agent
Write a short white paper on the implementation of AI concepts in your project. You should discuss the ideas and algorithms which you used to construct your agent, and how you varied the basic techniques to suit this particular application. Evaluate your choices in retrospect: discuss the properties of your approach both in theory and in your observations of its performance, and discuss how specific alternative approaches would improve your agent’s performance and behavior.
Take-home question 2 — Design of a Chocolate Fix agent
Chocolate Fix is a puzzle game in which the player finds the correct arrangement of pieces on a
square grid. Each piece has both a shape and a color. For a Chocolate Fix puzzle of size n: 1. There are n different shapes, and n different colors.
2. There are n2 pieces, each with a different shape/color combination.
Each puzzle has a set of clues showing how the grid, or some part of the grid, must be arranged. All of the examples we present here are on a 3 × 3 grid, but your solution should address the
general case of n × n puzzles. For a first example, here are three cards showing three different sets of clues:
1. In the first card on the left, there are two clues.
(a) The first (left) clue spans the entire grid. There are several requirements for a solution
expressed by this clue:
• It calls for two specific pieces in the two upper corners: brown triangle in the
upper-left, and white square in the upper-right.
• It gives a partial hint for the center square: a triangular piece will go there, but the
color is not disclosed.
• In the bottom row, it requires specific colors (red in the bottom left, white in the
bottom middle, brown in the bottom right), but not not insist on a particular shape.
• It says nothing about three squares: middle of the top row, middle of the left column,
and middle of the right column.
(b) The second clue fits within a 2 × 3 rectangle, which means it could apply to either the
top two rows, or to the bottom two rows — it is up to us to work out which.
2. In the middle card, we have more clues than on the leftmost card, but some of them might be applicable to many places: the fourth clue (bottom right) says that one of the brown piece will have a red piece below and to its right: there are four pairs of slots to which this
requirement could apply.
Note also that many of the clues in this card are silent as to some of the squares in the grid it specifies. The upper-right clue calls for a slot containing a triangle (of unspecified color) above and to the right of some other slot, but places no restrictions on the content of that other slot.
3. The rightmost card contains more clues, but most governing only some fragment of the overall grid, and most giving only a partial requirement for the squares of its fragment.
In all three of these puzzles there is a unique solution (which you can find at the end of this document).
Write a short white paper presenting and analyzing an algorithmic solution for an agent for solving Chocolate Fix puzzles. As with your Tsuro agent analysis, you should discuss the basic ideas and algorithms which your agent requires, and how you adapt the basic techniques to suit this particular application. How are puzzles encoded for your algorithm, and how are the solutions decoded? There are several additional example puzzles below. Step through at least one “Beginner” and one “Intermediate” example to show in detail how your approach would solve the puzzle, and at least one “Advanced” or “Expert” example in overview. Evaluate your design, discussing the properties of your design choices within the space of options of the technologies you choose, including but not limited to their complexity relative to the size n of the puzzle. What
2
are the differences among the Beginner, Intermediate, Advanced and Expert problems, in terms of the elements of your solution which each require?
Submission details
As with all non-programming work in this class, you should submit your answers as PDF files to Canvas. There are two separate submission points for the two questions — re-check both points to make sure that you have submitted the right response to each question. Both questions are due by 5pm on Wednesday, December 18. This deadline is firm — no late submissions will be accepted. I strongly encourage you to upload various drafts to Canvas as you complete your answers.
Appendix: Additional examples of Chocolate Fix puzzles “Beginner” level
“Intermediate” level
3
“Advanced” level
“Expert” level
Appendix: Images from the published game directions
4
Appendix: Solutions to Puzzles 4, 11 and 24
✷✷✷✷✷
5
Reviews
There are no reviews yet.