State space search is a general approach that can be applied to any problem domain that is deterministic, discrete, and static. In the reading from Russell and Norvig, they discussed a number of applications for this approach including route finding, VLSI layout, and automatic assembly sequencing. In class we examined how this approach could be applied to the traffic jam game and the water pitcher puzzle.

In this lab, you will begin with the naive search method that allows repeated states and test how inefficient it can be on the water pitcher problem. Then you will update the search method to add a dictionary of unique states, and only add nodes to the queue for states which have not yet been encountered. You will verify that the improved search is indeed more efficient. Finally you will formulate a new problem so that state space search can be used.

You may work with a partner on this assignment. Only one of you need turn in the code. Be sure both names are listed in every file.

1. Do an update63 to get a copy of the files you'll need to complete this lab. The following files will be copied to you cs63/lab/01 directory:
   • search.py
     This file contains a general solution to state space search. It is based on four classes: Queue, Node, Search, and ProblemState. Notice that the last class is completely abstract. This is intended to be an interface for how to formulate any appropropriate problem for state space search.
   • pitcher.py
     This file contains a concrete implementation of the ProblemState abstract class for the water pitcher problem.
   • missionary.py
     This file must be completed by you after you have formulated the missionaries and cannibals problem for state space search.
2. Start by reading through the classes defined in search.py. Then look at the file pitcher.py to see how the water pitcher problem has been implemented.
3. Test out the water pitcher problems given at the bottom of the pitcher.py file.

1. Modify the Search class to count how many nodes are expanded during the search. Print out the total number when the search ends.
2. Re-test one of the given water pitcher problems and see how many nodes are being expanded. Clearly there are a lot of repeated states in this domain.
3. Update the Search class so that it uses a dictionary to store a representation of all of the unique states that have been visited. The execute method should only add a node to the queue when its corresponding state is not already in this dictionary. This fix will eliminate all of the repeated states from the search.
4. Based on our discussion in class, we know that the water pitcher problem has only 14 unique states. Test your new version of search, which uses the dictionary, by using an unreachable state, such as (1,1)). You should see that no more that 14 nodes have been expanded and the search will fail.

This problem is famous in AI because it was the subject of the first paper that approached problem formation in a formal way. Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side of the river without ever leaving a group of missionaries on either side of the river that are outnumbered by the cannibals (lest they be eaten). The boat must have a person in it to travel across the river.

1. Formulate the missionaries and cannibals problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space showing the operators on the arcs. How many unique states does it contain? Given that the state space is relatively simple, why do you think people have a hard time solving this puzzle? Write your answers on the back of your diagram. Hand in your diagram outside my office.
2. Implement your formulation of this problem in the file missionary.py, using the pitcher.py implementation as a model. Note that this problem is slightly harder to implement than the water pitcher problem because of the constraints. There are several ways you can handle the contraints:
   • Generate states for all possible moves, even if they may create an invalid state. Then in the applyOperators method check each state for validity and only return valid ones.
   • Create operator methods that only return valid states and otherwise return None. Then in the applyOperators method only return states that are not None.
3. Test your implementation.
   • First test a simpler problem that only has 2 moves. Turn verbosity on (by adding True as the last parameter when you create a Search object). Make sure that all of the valid successors are being generated.
   • Next test your implementation on the goal state. Check the solution found against your diagram. Make sure that it is a valid solution.
   • Finally test your implementation on an invalid state. How many nodes are expanded? Does the number match your diagram? If not, which states are you missing?
4. Write clear comments in your code explaining your state representation for this problem.

Once you are satisfied with your programs, hand them in by typing handin63 at the unix prompt. Don't forget to also turn in your digram of the state space for the missionaries and cannibal problem outside my office door.