Comp 210 Lab 10: Missionaries and Cannibals

Link to Homework 9

This lab will be spent working on and discussing possible solutions to the Missionaries and Cannibals problem. You will be working in groups of two, so pick a partner right away.

1. General discussion of the problem (5 minutes)
2. Try Exercise 32.2.1
   1. Work in groups of 2 (10 minutes)
   2. Discuss different solutions (15 minutes)
3. Try Exercise 32.2.2 -- no hard coded values!
   1. Work in groups of 2 (15 minutes)
   2. Discuss different solutions (15 minutes)
4. Try Exercise 32.2.3
   1. Work in groups of 2 on the first part of the exercise only. (15 minutes)
   2. Discuss different solutions (15 minutes)
5. Try Exercise 32.2.4 -- if there's time
   1. Work in groups of 2 on the first part of the exercise only.
   2. Discuss different solutions

General hints:

• Don't forget that you should now be using abstract functions, where applicable. As previously described, you may choose to develop your programs the "old-fashioned" way and then edit them to use any appropriate abstract functions. By the way, you might find the following built-in abstract function useful:

     ; build-list : natnum (natnum -> alpha) -> list-of-alpha
     ; (build-list n f) = (list (f 0) ... (f (sub1 n)))

• One way of approaching this problem is by searching a set of states, and indeed this is its interest in AI. We can describe the state of the world by giving how many Missionaries and Cannibals are each side of the river and where the boat is. We denote the initial state by ``MMMCCCb-'' to show three Missionaries and three Cannibals and the boat on the left side of the river. Starting from the initial state and obeying the rules of the game (never leave a group of Missionaries outnumbered), the search space begins:

                    MMMCCCb--
                    /     \
                   /       \
                  /         \
                 v           v
            MMMC--CCb     MMCC--MCb
             /     \        /   \
            /       \      /     \
           /         \    /       \
          v           v  v         v
       MMMCCCb--    MMMCCb--C    MMMCCCb--

There are two main ways of searching a set of states like this: depth-first and breadth-first. In depth-first search, we explore one move from the initial state, then one move from that, and so on until we get stuck. Then we back up and try another move and so on. Note that in depth-first search, we need some way to remember what states we have already visited, or else we may end up repeating states forever and never find a solution. In breadth-first search, we try all possible moves from the initial state, then all moves from them, and so on. With breadth-first search, we are certain to find a solution, if one exists, even without remembering the previously visited states. By the way, in the case of the Missionaries and Cannibals, there exits a solution in eleven moves, and this is the shortest that is possible.

• If the final program utilizes the functions detailed in the first 4 Exercises, it will generate all states reachable with, say, seven crossings before it generates all those states reachable with eight crossings. Therefore you do not have to worry about cycles in solution attempts. Why are there cycles and why is this a problem for a computer program? You might wish to write the program in three stages. Your first program should represent states in a manner that allows the program to find out whether a final state is reachable. This first program can return true if it is possible. Then, for the second edition, you must create state representations that include the list of crossings that got the the group to this state. Of course, for the initial state this is just the empty list. For the third, final, and completely optional stage (that is, if you complete it, you will learn something but you won't get credit for it) eliminate all those states that represent solution attempts in which the same state would be reached (at least) twice. If you implement this third edition, you might wish to determine whether this measure saves time and how much it saves.