Assignment 2 Solution

General instructions:




This is an individual assignment. You can discuss solutions with your classmates, but should only exchange information orally, or else if in writ-ing through the discussion board on myCourses. All other forms of written exchange are prohibited.




Unless otherwise mentioned, the only sources you should need to answer these questions are your course notes, the textbook, and the links provided. Any other source used should be acknowledged with proper referencing style in your submitted solution.




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 les into one.




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 di erent portal to maximize your chance of saving Grasshopper.




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.



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?



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 con dence 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) ).



William got another vision! You can delay no longer; Grasshopper will su ocate 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 f"Moves North" , "Moves North" ,"Moves South"g.




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




Board is a 3x3 grid with the initial state shown in Fig 2



You are responsible for placing red boxes



The adversary places blue boxes



You lose if either Red or Blue forms:



A row




A column




You win if board lls up



Good Luck!









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









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.



Apply the minimax algorithm to nd the best course of action. Can you save Grasshopper? If so show how the game would play out.



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



Apply alpha-beta pruning to the search tree by going down the branch where the rst move of Red is on the tile on the second row, third column.



How much time did you save in terms of number of nodes pruned? Assume best case scenario.



Is this the most time you can save? If not how many more nodes can you save if you have went down a di erent branch rst?



Propositional Logic



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



A _ B



A_B_C_D_E



(A^B)_C



A^(A)B)^:B



:(A^B^C^D^E^F)_(B^C)



State whether each of the following sentences is Valid, Unsatis able, or Satis able. Support each of your answers using a truth table or a logical inference.



A_:A



(A^:A)_B



(((A)B)^A))B),(B_:B)



False j= A _ B _ C _ D _ : A



True j= ((A _ B) ^ : A ^ :B)



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





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.




De ne the relevant predicates and translate the facts listed above into rst-order logic. Clearly distinguish between variables and constants in each formula.



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



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