COMP 424 Assignment 2

General instructions:

• Submit a single pdf document containing all your pages of your written

solution on your McGill’s myCourses account. You can scan-in handwritten pages. If necessary, learn how to combine many pdf files into

one.

1 Searching under uncertainty

Oh no, one of your friends, Grasshopper, is trapped in a tunnel system and is

in mortal danger! You and three other of your friends have to help him.

Fortunately, one of your friends, William, is a psychic and drew you a map

and showed you where Grasshopper (marked with a ’G’) is located.

Figure 1: Map of tunnel system. Thick lines represent walls and white spaces

are tunnel spaces in which you can travel.

There are 4 portals each connected to one of the 4 entrances marked on the

map (marked as 1-4) . Not even William can tell you which portal leads to

which entrance.

1

Before you and your friends drew near the portals, William tells you that you

should each take a different portal to maximize your chance of saving

Grasshopper.

1. Assuming that each of you and your friends’ initial beliefs includes all

states (not just the portal entrances) except G, what is the total number

of possible beliefs of any one of you in this domain? You don’t have to

care about where your friends are.

2. When you, or one of your friends, is in a tile you can perceive the

neighboring walls (ex. Grasshopper is trapped in a dead-end with walls

on the east/west/south sides) . How many distinct percepts are

possible in this domain?

3. Are there landmarks (unique percepts) that can indicate where you are

in the map? If there is indicate where it is. Otherwise, indicate which

percept gives you highest confidence of where you are and with what

probability. You can use a coordinate system where the bottom-left most

point is the origin (e.g. location of portal entrance 2 is at (4,1) ).

4. William got another vision! You can delay no longer; Grasshopper will

suffocate if you don’t save him . He is saved if any 2 of you reach G in

strictly less than 60 minutes. You 4 must teleport into the tunnel system

to save him right now.

There are 4 actions you can take at each tile: walking northwards,

southwards, eastwards, or westwards. Each of these actions will move

you to the tile in that direction costing you 5 minutes, even if you run

into a wall.

Is there a conformant plan that can save Hopper? If so share it. If not

explain why. You can use (⇒ N)

2 ⇒ S to mean the sequence of actions

{”Moves North” , ”Moves North” ,”Moves South”}.

2 Game playing

Miraculously, you have successfully located Grasshopper in the knick of time,

but he remains in peril. All of a sudden, William seems to have entered a

trance, and utters, “To save Grasshopper you must win the game”. In front of

you appears a set of boxes. Some boxes are red and some are blue. Joy, urgent

to save Grasshopper, placed a red box at random and soon following that the

ground opened up and a blue box appeared. William tells you that you must

not allow boxes of the same colors to align or else it will not end well for

Grasshopper. The board has a mind of its own and will try to play the best

move possible.

2

2.1 Summary

1. Board is a 3×3 grid with the initial state shown in Fig 2

2. You are responsible for placing red boxes

3. The adversary places blue boxes

4. You lose if either Red or Blue forms:

• A row

• A column

5. You win if board fills up

6. Good Luck!

Figure 2: Current state of laser emitting boxes. R represents red laser emitting

boxes and B represents blue laser emitting boxes

3

1. To prevent making a mistake (because a life is at stake here), you decide

to draw the set of game states before advancing your next move. Please

ignore all symmetrically equivalent states. For the remaining questions

you can use this graph to show the algorithms.

2. Apply the minimax algorithm to find the best course of action. Can you

save Grasshopper? If so show how the game would play out.

3. Bobby suggests that you can save time if you use alpha-beta pruning.

(a) Apply alpha-beta pruning to the search tree by going down the

branch where the first move of Red is on the tile on the second row,

third column.

(b) How much time did you save in terms of number of nodes pruned?

Assume best case scenario.

(c) Is this the most time you can save? If not how many more nodes

can you save if you have went down a different branch first?

3 Propositional Logic

1. How many models are there that satisfy each of the following?

(a) A ∨ B

(b) A ∨ B ∨ C ∨ D ∨ E

(c) (A ∧ B) ∨ C

(d) A ∧ (A ⇒ B) ∧ ¬ B

(e) ¬ (A ∧ B ∧ C ∧ D ∧ E ∧ F) ∨ (B ∧ C)

2. State whether each of the following sentences is Valid, Unsatisfiable, or

Satisfiable. Support each of your answers using a truth table or a logical

inference.

(a) A ∨ ¬ A

(b) (A ∧ ¬ A) ∨ B

(c) (( (A ⇒ B) ∧ A) ⇒ B) ⇔ (B ∨ ¬ B)

(d) False |= A ∨ B ∨ C ∨ D ∨ ¬ A

(e) True |= ((A ∨ B) ∧ ¬ A ∧ ¬B)

4 First Order Logic

Dustey, Elody, and Michael joined William at the local snack shop. Each of

them bought at least one of 3 snacks: eggo, chocolate pudding, or

3-musketeers. Those who bought pudding did not buy eggos and those who

4

bought 3-musketeers also bought pudding. Elody is mad at Michael, so out of

the 3 snacks she bought everything that Michael did not buy. Michael and

Dustey bought a bar of 3-musketeers.

For the following questions use Bought(x,y) to mean x bought y.

1. Define the relevant predicates and translate the facts listed above into

first-order logic. Clearly distinguish between variables and constants in

each formula.

2. Convert all facts from part 1 to CNF. Number each of the clauses.

3. Query: Did any of them only buy eggos?

Answer the query by using proof by resolution or explain why not. Use

the numbers from part 2 for your proof/explanation.

Hint: To show A∨B is false show that both A is false and B is false

5