Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMPSCI 367 Assignment
Weighting: This assignment counts toward 10% of your final mark.
1. [2.5 marks] This question asks you to formulate the following problem as a CSP.
Edmund Hillary and Tenzing Norgay play ten games of Rock-Paper-Scissors.1 Here are the given
facts:
- Norgay uses Rock once, Paper six times, and Scissors three times.
- Hillary uses Rock five times, Paper four times, and Scissors once.
- There are no ties in all 10 games.
- The order of the games is unknown (and unimportant).
(a) Formulate this problem as a CSP. State clearly the variables, the domains of the variables
and the constraints.
Note: We are given a limited vocabulary for how we can formulate our CSP constraints. We may use
standard mathematical operators, including equality (=), inequality (≠), addition (+), multiplication
(*), and exponentiation (^), where “2^3” is 2-to-the-power-of-3, as well as any other symbols that
have been used for CSP constraints in our lectures (e.g., <, >, ≤, ≥).
(Give this a go. If you get stuck, I have put a hint on how to solve this on the last page of this
assignment.)
(b) Let’s say that we have a partial assignment of game results as follows:
Game1 Game2 Game3 Game4 Game5 Game6 Game7 Game8 Game9 Game10
Norgay Paper Paper Paper Paper Paper Paper ?
Hillary Rock Rock Scissors Rock Rock ?
Given this partial assignment, perform the Backtracking algorithm and use your results to answer
the following questions:
(i) If Norgay plays Paper in Game 6, what must Hillary play in Game 6? Which of your
constraint(s), given the current variable assignments, entails this?
(ii) Given your answer to (i), what must Hillary then play in game 7. Which of your constraint(s),
given the new variable assignments, entails this?
(iii) After completing the search, who wins the greatest number of games? And how many do they
win?
2. [2.5 marks] This question asks you to solve a CSP problem. We are searching for the correct
assignment of numbers to variables.
Here are the given facts:
- The variables are: A, B, C, D, E, F, G, H.
- The Domain for each variable is: {1, 4, 5, 7, 9, 14, 16, 21}.
- None of the variables have the same value (i.e., each value is used only once).
- The following constraints must be satisfied:
(i) C + F = G
(ii) A + C = F
(iii) B + G = D
(iv) B + E = H
(v) D + F = H
(a) Draw the constraint hypergraph for this CSP problem. (For the purposes of drawing the
constraint hypergraph, you may ignore the constraint that no two variables have the same
value).
COMPSCI 367 Assignment 3 Page 3 of 6
(b) Begin with the partial assignment A=1. Apply the AC3 algorithm. At each step, if you have
a single variable value assignment, you can delete that value from the other temporary
domains. This has been done for you in the first row of the table below. None of the edge
consistency checks have been completed, so you will need to do this.
For each row, write the edge that you are testing for consistency in the first column and fill
in the rest of the row with the resulting temporary domains for each variable.
(Note: the edge may be written as (A,ii) for the edge between variable A and the constraint
“A + C = F”)
What are the resulting temporary domains for each variable after the application of the AC3
algorithm?
Edge A B C D E F G H
-- 1 4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
4, 5, 7, 9,
14, 16, 21
COMPSCI 367 Assignment 3 Page 4 of 6
Question 3 [5 marks]
For this question, you are asked to resolve the Seven Trick Candles logic problem using
PDDL.
There are seven trick candles in a circle. Initially, every Candle is Lit. When you blow on a
candle, your blow changes the state not just of the candle you blow on, but also both candles
either side of it. So, you can think of any blowing action affecting a Trio of candles. The trick
is that when a trio of candles is blown on, any candles in that trio that are currently lit will no
longer be lit, and candles in the trio that are unlit will become lit! The goal of this puzzle is to
blow out all of the candles.
Given what has been said, you can assume at the outset that every candle is a member of
exactly three different trios of candles. For example, if you give each candle a number, you can
assume that Candle3 will be in the trios: {Candle3, Candle4, Candle5}, {Candle2, Candle3,
Candle4} and {Candle1, Candle2, Candle3} and likewise for the other candles. Further, you
will note that there are only seven possible distinct trios of candles.