Assignment 2 Searching under uncertainty

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 3x3 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