COMP424- Homework 2 Solved

Question 1: Constraint Satisfaction
Consider the problem of placing two knights and two queens on a 4x4 chess board such that no two pieces attack each other. Suppose that rows 1 and 2 must each contain a knight, and rows 3 and 4 must each contain a queen, as follows:

 

 

a)     Formulate this problem as a CSP with binary constraints. List the variables, their domains, and the constraints. Draw the constraint graph.

 

b)     Run AC-3 on this problem, then apply backtracking search to find a solution if possible.

 

c)     Starting from the original problem (i.e., without running AC-3), run backtracking search with one-step forward checking.

 

          

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 paper and your friend plays rock, 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. 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.