The Missionaries and Cannibals problem is a classic AI puzzle that can be defined as follows:
On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.
How can the boat be used to safely carry all the missionaries and cannibals across the river?
The initial state is shown to the right here, where black triangles represent missionaries and red circles represent cannibals.
This problem can be solved by searching for a solution, which is a sequence of actions that leads from the initial state to the goal state. The goal state is effectively a mirror image of the initial state. The complete search space is shown in figure 1.
Figure 1: Search-space for the Missionaries and Cannibals problem
Arrows in figure 1 represent state transitions and are labelled with actions, e.g. 2c represents the action of two cannibals crossing the river. The initial state is shown again on the left, whereas the goal state is all the way to the right.
MissionariesAndCannibalsApp is a Java application that explores the above search space using a number of (uninformed) search strategies. Download the application and double-click it. Alternatively, run the command "java -jar MissionariesAndCannibalsApp.jar" from the command line. Either should bring up a window that looks essentially like the one shown in figure 2.
Figure 2: The window of the application
To search for a solution, first select a search strategy. Next, there are some configuration options for the search process. If the search space is to be searched as a graph, multiple paths leading to the same node will usually only be explored once. In a tree, search states that can be reached by multiple paths will also be explored multiple times. The number of states to be generated can be limited to the given value, resulting in the search being abandoned at that point. For a depth-first search it is also possible to set a depth limit, meaning no states at a greater depth will be explored.
Finally, a trace of the search can be written to the window and/or a text file. The operation performed by a search engine consists of selecting a current search node and generating its successors, and the trace reflects this process. For example, the line:
current state: 11: <State L: 0m,1c - R: 3m,2c,b>
indicates that the selected node contains the given state. The number (11 in the example) is the unique identifier for the search node. Note that there may be multiple nodes that contain the same state, especially when tree search is performed. Then there is a description of the selected state which can be read as follows: on the left bank (L:) there are no missionaries (0m) and one cannibal (1c), and on the right bank there are 3 missionaries (3m), two cannibals (2c) and the boat (b). Other states follow the same pattern. The lines following this one in the trace describe the successor states that have been generated, for example:
successor state: 12: <State L: 0m,2c,b - R: 3m,1c> successor state: 13: <State L: 1m,1c,b - R: 2m,2c>
So, expanding the given search node (11) resulted in two new search nodes (12 and 13).
Even with tracing off the window will display some information about the search (which is not part of the trace). It will show how many states have been explored (the goal test has been performed and successors have been generated) and how many states have been generated (explored states plus fringe nodes). If a solution is found this will also be printed. Finally, the elapsed time taken to perform the search is printed. Note that writing the trace usually takes more time than searching itself.
S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach, chapter 3. Prentice Hall, 2nd edition, 2003.
S. Amarel. On Representations of Problems of Reasoning about Actions. In: D. Michie, editor, Machine Intelligence 3, pages 131-171, Edinburgh University Press, 1968. Reprinted in: B. Webber and N. Nilsson, editors, Readings in Artificial Intelligence, pages 2-22, Tioga, 1981.