COMPSCI 367 Assignment 3 Page 1 of 6
School of Computer Science
COMPSCI 367 Assignment 3 due Wednesday 19 October 2022
Due: by 11:59pm on the due date. This is a hard due date. Late assignments will not be marked.
Total marks: 10.
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.)
1. See here for more information: https://en.wikipedia.org/wiki/Rock_paper_scissors.
COMPSCI 367 Assignment 3 Page 2 of 6
(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.
Also, note that every time you select a trio of candles to blow on (an action), there are only
eight possible combinations of the current states of the candles—lit or unlit—in your selected
trio (and eight corresponding effects as a result of the trio being blown on). See the table here:
Action Before: After:
BlowTrioType1 lit c1, lit c2, lit c3 not(lit c1), not(lit c2), not(lit c3)
BlowTrioType2 not(lit c1), lit c2, lit c3 lit c1, not(lit c2), not(lit c3)
BlowTrioType3 lit c1, not(lit c2), lit c3 not(lit c1), lit c2, not(lit c3)
BlowTrioType4 lit c1, lit c2, not(lit c3) not(lit c1), not(lit c2), lit c3
BlowTrioType5 not(lit c1), not(lit c2), lit c3 lit c1, lit c2, not(lit c3)
BlowTrioType6 lit c1, not(lit c2), not(lit c3) not(lit c1), lit c2, lit c3
BlowTrioType7 not(lit c1), lit c2, not(lit c3) lit c1, not(lit c2), lit c3
BlowTrioType8 not(lit c1), not(lit c2), not(lit c3) lit c1, lit c2, lit c3
COMPSCI 367 Assignment 3 Page 5 of 6
(a) Write a PDDL domain file candles_domain.pddl that specifies the eight action schemas:
BlowTrioType1, BlowTrioType2, BlowTrioType3, BlowTrioType4, BlowTrioType5,
BlowTrioType6, BlowTrioType7, and BlowTrioType8.
You need to use the PDDL syntax starting from the following:
(define (domain candles)
(:requirements :strips :equality)
(:predicates (candle ?c) (lit ?c) (trio ?t) (intrio ?t ?c))
…//fill in the description here//
)
Note 1: the “equality” requirement in the code above allows you to check whether two objects
are different, which will be useful for checks in your action schemas. For example, it allows the
following type of check: (not (= ?c1 ?c2)), which will return True if the variables ?c1
and ?c2 refer to different objects.2
Note 2: The (intrio ?t ?c) relation can be used to check whether a Candle is in a particular
Trio of candles or not. For example, if Trio3 contains {Candle2, Candle3, Candle4} then a
precondition in an action that checks (intrio Trio3 Candle3) will return True. Likewise,
the same code could be used elsewhere in part (b) of this question to assign Candle3 to Trio3.
(b) Write a PDDL problem file candles_task.pddl that specifies the initial state and the goal
state.
Submit the two files candles_domain.pddl and candles_task.pddl.
You may use the PDDL Editor to test your code: http://editor.planning.domains/
2. You can read more about “Equality” in the PDDL wiki: https://planning.wiki/ref/pddl/requirements#equality
COMPSCI 367 Assignment 3 Page 6 of 6
Hint for Question 1(a): One way we might specify constraints for sentences like “Norgay played
Rock five times, Paper four times, and Scissors once” is to utilise the properties of prime
factorisation. Instead of the Domain for each game using letters—say, “R”=Rock, “P”=Paper and
“S”=Scissors—the domain could instead use a different prime number, pi, to stand in for each of the
options (p1=Rock, p2=Paper, p3=Scissors).
So, for example, if we knew that for a series of games, G1, G2, G3, that a player used Rock twice and
Scissors only once, and we use prime numbers 2=Rock and 3=Scissors (so that the domain for each
outcome is {2,3}), then we can specify the constraint that: G1 * G2 * G3 = 2^2 * 3^1.
Also note that formulating the constraint this way means that a partial assignment of two-Scissors
(i.e., two-3s) to G1 and G2 in this case would be illegal, as the value of 2^2 * 3^1 (=12) cannot be
divided by 3^2 (=9). Thank goodness for prime numbers!