Homework 2 Constraint Satisfaction

COMP-424: Artificial intelligence
Homework 2

General instructions.
• For each problem, you can solve manually, or write a program to help you. You can use a programming language of
your choice. You can modify code from other sources if you provide adequate citation; this cannot be code from
other students in the class.
• Submit a single pdf document containing all your pages of your written solution on your McGill’s myCourses
account. You can scan-in hand-written pages. If necessary, learn how to combine many pdf files into one.
• Submit any code developed to answer questions as a separate file to McGill’s myCourses.
Question 1: Constraint Satisfaction
Consider the following problem:
Find a 10-digit number such that the first digit is the number of zeros in the number, the second digit is the number of
ones in the number, …, and the tenth digit is the number of nines in the number. The first digit must be non-zero.
a) Formulate this problem as a CSP. List the variables, their domains, and the constraints. Draw the constraint
graph.
b) Show the first ten steps of backtracking search on this problem, where you order the variables from the first
digit to the last digit, and the values from lowest to highest. Recall that backtracking search uses a depth-first
strategy to expand the search tree.
c) Show the first ten steps of backtracking search on this problem with one-step forward checking, where you
order the variables from the first digit to the last digit, and the values from lowest to highest.
d) Not for marks: Solve this problem in as many ways as you can! You may want to write code to do this. For
example, you could implement backtracking, or try a local search method.
Question 2: Search and Game Playing
You are playing rock-paper-scissors with your friend, but with a twist. The game now consists of three rounds, and
each round, players may not play something that they have played before. So, if you play rock the first round, you
cannot play it again in rounds two and three. The winner of the game is the player who wins the most rounds.
a) Draw the AND-OR tree associated with this game.
b) In the first round, you play rock and your friend plays scissors, giving you the first win. Can you guarantee a
win of the game overall? Explain by extracting a contingency plan from the AND-OR tree above.
c) Check your answer by reformulating the AND-OR tree into a game tree where you apply the Minimax
algorithm.
Question 3: Propositional Logic
a) How many models are there for each of the following statements in propositional logic?
i) (𝐴 ∧ 𝐵) ∨ 𝐶
ii) 𝐴 ∧ (𝐴 ⇒ 𝐵) ∧ ¬𝐵
iii) ¬(𝐴 ∧ 𝐵 ∧ 𝐶 ∧ 𝐷) ∨ (𝐵 ∧ 𝐶)
b) State whether each of the following is valid, unsatisfiable, or satisfiable. Support your answers with a truth
table or a proof using rules of logical inference.
i) ((𝐴 ∨ 𝐵) ⇒ 𝐶) ⇒ (𝐴 ⇒ 𝐶) ∧ (𝐵 ⇒ 𝐶)
ii) ((𝐴 ⇒ 𝐵) ∧ (𝐴 ∨ 𝐶)) ⇒ (𝐵 ∨ 𝐶)
Question 4: First Order Logic
This question is not for marks, and will not be marked. It is here to help you prepare for the midterm.
(Adapted from Russell & Norvig, 8.10)
Consider a vocabulary with the following symbols:
Occupation(p, o): Predicate. Person p has occupation o
Customer(p1, p2): Predicate. Person p1 is a customer of person p2.
Boss(p1, p2): Predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: Constants denoting occupations.
Emily, Joe: Constants denoting people.
a) Use these symbols to write the following assertions in FOL:
i) Emily is either a surgeon or a lawyer.
ii) Joe is an actor, but he also holds another job.
iii) All surgeons are doctors.
iv) Joe does not have a lawyer.
v) Emily has a boss who is a lawyer
vi) There exists a lawyer all of whose customers are doctors.
vii) Every surgeon has a lawyer.
b) Give a model of the above FOL such that clauses i) – vii) above are satisfied.