Assignment 2 Searching under uncertainty

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