AI Search to Solve the Missionaries and Cannibals Problem
4.40/5 (24 votes)
Nov 3, 2006
5 min read
197206
2799
An AI search to solve the Missionaries and Cannibals problem.
Introduction
This article describes how to solve a logic problem using the AI Search technique.
So what is the problem that are trying to solve
The problem is specified like this. On one side of a river, there are three missionaries and three cannibals. There is a boat which can be used to transfer people from one side of the river to the other.
No more than two people can fit in the boat and it must have at least one person in it during any transfer. The problem is to find the shortest sequence of transfers which gets all six people from one side to the other without ever creating a situation where missionaries outnumber cannibals on either side of the river. (The idea being that if this happens, the missionaries will then be able to corrupt the cannibals by 'converting' them.) To solve this problem satisfactorily, your program must explicitly identify all of the optimal (i.e., shortest) solutions to the problem.
How does an AI search algorithm work
Well, there are different varieties of search which can all be used, such as breadth first, depth first, or iterative deepening. Each of these different search methods has different properties such as whether a result is guaranteed, and how much time and space is needed to carry out a search.
This article uses breadth first search, as this search method is guaranteed to find a solution state.
Search is generally concerned with looking for a solution, or solutions in a search space of individual search states. Typically, a search space is a list or some sort of collection which contains each of the states that is to be checked to see if it is a solution state.
A breadth first search algorithm
A breath first search relies upon the basic search principles mentioned above. What is of specific interest, is how the breadth first search actually goes about looking for a solution state.
To illustrate this, consider the following diagram, where each of the ovals is an individual state:
It can be seen from the diagram above that there are a number of states, but how did the search choose which ones to look at for a given solution?
With a breadth first search, each state at a given layer is expanded before moving to the next layer of states. In the diagram above, it can be seen that the root state was expanded to find the states A1, A2, and A3. There were no more states at this level, so A1 was picked and expanded, which yielded A1.1 -> A1.3. However, A2 and A3 must also be expanded before looking at these new states A1.1 -> A1.3, so A2 and A3 will be expanded next. If there are no more states at the current level to expand, the first node from the next level is expanded, this carries on until a solution (or solutions) is found. This is the basis of a breadth first search.
So how does this translate into an algorithm
The following algorithm illustrates how a breadth first search should function when looking for a single solution.
- Create a variable called SearchAgenda (say) and set it to the initial state (Root, from our example).
- Until a goal state (Solution) is found or SearchAgenda is empty, do:
- Remove the first element from SearchAgenda and call it CurrState. If SearchAgenda is empty, quit.
- For each way that each rule can match the state described in CurrState, do:
- Apply the rule to generate new state(s), these are called Successor states.
- If the new state is a goal state (Solution), quit and return this state.
- Otherwise, add the new state to the end of the SearchAgenda.
This is the basis of the algorithm. But there are some considerations, which are fairly important to any AI search technique. These are explained below.
Finding successor states
This is a fundamental part of any search algorithm, and is really the key to having a successful search algorithm. For the Missionaries and Cannibals problem, we could consider the following diagram.
From the figure above, we can see that several of the states are invalid, so have been pruned (discarded) from the search tree. This means these states will not have successor states generated.
Determining if the new state is a goal
For the Missionaries and Cannibals problem, this is simply having all three missionaries and all three cannibals on the opposite side of the river.
Using the code
The demo project attached actually contains a Visual Studio 2005 solution, with the following three classes:
Program
Is the main entry point into the CannMissApp application. Essentially, all this class does is call the getSolutionStates method of the SolutionProvider, and then print the solutions (if there are any):
.....
.....
SolutionProvider S = new SolutionProvider();
ArrayList Solution = S.getSolutionStates(new State("Root", 3, 3, false,1),
new State("Goal", 0, 0, true,999999));
printSolutions(Solution);
....
....
//This method prints the Solutions returned
//by the SolutionProvider object.
//However, there may not actually be any solutions to print.
//
//Once a SolutionProvider is created this
//class asks it to provide all the
//solutions. If there are any solutions
//returned these are then printed
//
//param : Solution the Solutions returned
// by the SolutionProvider object.
private static void printSolutions(ArrayList Solution)
{
//Are there any solutions
if (Solution.Count == 0)
{
Console.WriteLine("\n\nNO SOLUTIONS HAVE BEEN FOUND\r\n");
}
else
{
int Solfound = 1;
//show the Solutions
for (int i = 0; i < Solution.Count; i++)
{
State s = (State)Solution[i];
Console.WriteLine("=====FOUND SOLUTION [" +
Solfound++ + "]=====\r\n");
Console.WriteLine("This solution was found at level [" +
s.getStateLevel() + "]\r\n");
s.Print();
Console.WriteLine("\r\n");
}
}
}
SolutionProvider
Provides solutions to the "Cannibals and Missionaries" search problem:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;
namespace MissCanApp
{
#region SolutionProvider CLASS
//SolutionProvider - Provides solutions
//to the "Cannibals and Missionaries"
//Search problem.
//
//HOW THE SEARCH IS PERFORMED
//
//This class uses a breadth 1st search
//to search for possible solutions.
//A ArrayList is used to store the agenda.
//The agenda consists of a list of State
//classes. The root State will be the 1st
//item in the agenda. When the root
//is taken from the agenda, it is compared
//to the goal state, if it is the goal
//state it will be stored within a
//SolutionsFound ArrayList. However the 1st node
//in the search agenda it not likely to
//be the goal so different successor
//states will be generated from the root
//and these will be added to the agenda.
//Each of these states will then be taken
//from the agenda and compared to the
//goal, if they are equal to the
//goal they will be stored within a
//SolutionsFound ArrayList. However if they
//are not the goal state, they too will
//be expanded to create successor states,
//which will then be added to the agenda.
//
//The solutions may be found at various
//levels within the search tree. This application
//should return the optimal solustions.
//To achieve this the 1st solution has its level
//within the search tree recorded. Then when new
//solutions are found they are compared
//to this level, if they are less than or the
//same they too are stored as valid optimal
//solutions. Only when the solutions found are
//found at a higher level does the search know
//that it has found all the optimal solutions.
//When this occurs the search is ended, and the
//optimal solutions returned.
class SolutionProvider
{
// Instance fields
private int CURRENT_ROOT_STATE = 0;
private ArrayList searchAgenda = new ArrayList();
//SolutionProvider Constructor
//Simply creates a new SolutionProvider object
public SolutionProvider()
{
}
//Creats a new State based on
//a parent state. The formal parameters
//supplied dictate what changes are
//to be applied to the parent
//state to form the new child state
//
//@param : StateName represents the new state name
//
//param : parent is the parent State
//that this State should be generated from.
//Ie the new State will be a child of this parameter
//
//param : nMiss number of Missionaries
//in the boat for the new state
//
//param : nCan number of Cannibals in the boat for the new state
private void addStateToAgenda(String StateName,State parent,
int nMiss, int nCan)
{
// BoatDirection holds either 1 or -1, depending on the side.
int BoatDirection = parent.Side ? 1 : -1;
//Get the name of the parent state and add append the new state
//suffix to it
String newStateName = parent.getStateName() + StateName;
//Create a new state based on the parent state parameter that was
//supplied when calling this method
State newState = new State(newStateName,
parent.nMiss + nMiss * BoatDirection,
parent.nCan + nCan * BoatDirection,
!parent.Side,
parent, parent.getStateLevel() + 1);
//Try and add the newly generated State to the search agenda
addStateToAgenda(newState);
}
//Tries to add the NewState parameter provided to the search agenda.
//If the state parameter provided is
//not a valid state, the state will not
//be added to the agenda. The State
//class deals with checking for a ValidState
//
//param : NewState the state to try and add it to the search agenda
private void addStateToAgenda(State newState)
{
// Dont allow invalid states to be added to search agenda
if (newState.InvalidState())
return;
//Valid state so add it to the agenda
searchAgenda.Add(newState);
}
//This is the main method that does most of the work. It carries out
//various tasks. These are described below
//
//The 1st thing that is done is the
//internal SolutionsFound collection is
//initialized and the StartState
//(From the formal parameter) is added to the
//Search Agenda
//
//Then a loop is enetered that loops through
//the entire agenda taking off
//the 0 element when 1st entering the loop.
//For readability I have defined
//the 0 elemenet to be an int called
//CURRENT_ROOT_STATE. This variable is
//a simply int that is set to 0 when
//the SolutionProvider class is constructed.
//
//When the CURRENT_ROOT_STATE element
//is removed from the Search Agenda it is
//cast to a State then compared to
//the GoalState (From the formal parameter).
//If it equals the goal state (Dealt
//with by the State class) and is the 1st
//solution found the level of the state
//is recorded, and the state is stored
//within the SolutionsFound collection.
//If this is not the 1st solution found
//the state level of this new solution
//is compared to the recorded state level
//of the 1st solution. If this solution
//is less than or equal to the recorded
//optimal level, then it too may be added
//to the SolutionsFound collection.
//However if it is not the goal state,
//which is will not be for the 1st State
//(ROOT) then new succeessor nodes will
//need to be created based upon this parent
//node. The generateSucessors method deals with this.
//
//param : StartState the StartState, with all Cannibals/Missionaries
//on one side of the river
//
//param : EndState the StartState, with all Cannibals/Missionaries
//on the opposite side of the river
//
//return : ArrayList that holds all the solutions found
public ArrayList getSolutionStates(State StartState, State EndState)
{
//initialise local fields
int optimalSolfoundAtLevel = 0;
bool allOptimalSolutionsFound = false;
bool foundFirstSolution = false;
//Initialise SolutionsFound collection
ArrayList Solutions = new ArrayList();
//Add StartState to the Search Agenda
addStateToAgenda(StartState);
//Loop through search agenda until
//we have found all the optimal solutions
while (searchAgenda.Count > 0 && !allOptimalSolutionsFound) {
//Get the current root state from the Search Agenda
State CurState = (State)searchAgenda[CURRENT_ROOT_STATE];
//Remove the current root state from the Search Agenda, is has been
//dealt with now
searchAgenda.RemoveAt(CURRENT_ROOT_STATE);
//Is the current root state the Goal State
if (CurState.Equals(EndState)) {
//Has the 1st solution been found
if (foundFirstSolution) {
//YES the 1st solution was found so lets
//compare this states level to the existing level
//from when the 1st solution was found
if (CurState.getStateLevel() <= optimalSolfoundAtLevel) {
//If it is, store the state in
//the SolutionsFound collection
Solutions.Add(CurState);
}
else {
//since the current state level is
//greater than the optimalSolfoundAtLevel
//this solution must be more costly,
//we must have already found all the optimal solutions.
//so need to break out of loop, so set break condition
allOptimalSolutionsFound =true;
}
}
else {
//At this point this must be the 1st solution
//found, so store it and record its level
//in the optimalSolfoundAtLevel, so that this
//can be used to compare against
//for the next solutions found.
//Also prevent this logic froming running
//again by setting the foundFirstSolution to true.
foundFirstSolution=true;
optimalSolfoundAtLevel = CurState.getStateLevel();
Solutions.Add(CurState);
}
}
else {
//The current root state is NOT Goal State, so create
//sucessor states based on it
generateSucessors(CurState);
}
}
return Solutions;
}
//This method simply calls the addStateToAgenda method
//passing in all required derivations of the CurState state
//to be new sucessor nodes
//
//param : CurState the current state
//to use to create sucessor nodes from
private void generateSucessors(State CurState) {
//if this method has been called the CurState, was NOT the goal,
//so need to create new sucessor
//states based on it. So try and create
//some new states.
int nCan, nMiss =0;
int stateName =1;
//loop through all possible combinations
for (int i = 0; i <= Program.boatsize; i++)
{
for (int j = 0; j <= Program.boatsize; j++)
{
//prune the search tree, getting rid of invalid states
if (i==0 && j ==0)
continue;
if (i + j > Program.boatsize)
break;
//good state found, so add to agenda
nMiss = i;
nCan = j;
addStateToAgenda("_" + stateName++, CurState, nMiss, nCan);
}
}
}
} //End of SolutionProvider class
#endregion
}
State
Is a representation of a node with the Search Agenda. Each State holds various bits of data which help to model a specific state, such as number of missionaries, number of cannibals, the side the boat is on etc.
using System;
using System.Collections.Generic;
using System.Text;
namespace MissCanApp
{
#region State CLASS
// State - Is a representation of a node
//with the Search Agenda. Each State
// holds various bits of data which help to model a specific state.
// These data elements are described below.
//
// Number of Missionaries within the current state
//
// Number of Cannibals within the current state
//
// Side that the boat is on. False is one side, True is the other side
//
// Name of the State. This will be expanded
//upon for each successor state
// so that a full StateName can be printed, to show the full search path
// that this state used to get to where it is now
//
// PrevState is the previous state, this is the parent state from which this
// state was created. This will be null for the ROOT state, as it does not
// have a previous state
// State Level is the level that this states in on in the search tree
class State
{
// Instance fields
public int nMiss, nCan;
public bool Side;
private int NumOfEachAtStart = 3;
private String Name;
private State PrevState;
private int stateLevel = 0;
//State Constructer (1), Use this for the root state
//Simply creates a new State with the name, number of Missionaries,
//number of Cannibals and side to match the values supplied by
//the formal parameters. In this case there will be no PrevState as this
//is the 1st state
//
//param : Name is the name for this State
//param : nMiss the number on Missionaries for this state
//param : nCan the number on Cannibals for this state
//param : Side the side of the river that the boat is now on
//param : stateLevel the level this state is on,
// 0=root / 1st layer, 1 = 2nd layer, 2 = 3rd layer
public State(String Name, int nMiss, int nCan, bool Side,
int stateLevel) : this(Name, nMiss, nCan,
Side, null, stateLevel)
{
//Call the overloaded constructor with the formal parameters
//provided, but make PrevState=null, as the 1st State does not
//have a PrevState to point to
//this(Name, nMiss, nCan, Side, null, stateLevel);
}
//State Constructer (2), Use this to
//create States based upon other States
//Simply creates a new State with the name, number of Missionaries,
//number of Cannibals,side and PrevState to match the values supplied by
//the formal parameters. In this case PrevState will be a pointer to this
//nodes parent node
//
//param : Name is the name for this State
//
//param : nMiss the number on Missionaries for this state
//
//param : nCan the number on Cannibals for this state
//
//param : Side the side of the river that the boat is now on
//
//param : PrevState a pointer to this State's PrevState (parent)
//
//param stateLevel the level this state is on,
// 0=root / 1st layer, 1 = 2nd layer, 2 = 3rd layer
public State(String Name, int nMiss, int nCan, bool Side,
State PrevState, int stateLevel)
{
//Assign parameters to local instance fields
this.Name = Name;
this.nMiss = nMiss;
this.nCan = nCan;
this.Side = Side;
this.PrevState = PrevState;
this.stateLevel = stateLevel;
}
//Simply returns this States stateLevel
//
//return : int representing this States stateLevel
public int getStateLevel()
{
return this.stateLevel;
}
//Simply returns this States name
//
//return : String representing this States name
public String getStateName()
{
return this.Name;
}
//Prints a full search path of how this state came to be at the
//goal state. Makes use of the PrevState to recursively call
//the Print method until there is no PrevState. This way each
//State only prints its own data
public void Print()
{
//Check that there is a PrevState, Root node will not have one, so
//that is when all states from Goal - to start have been printed
if (PrevState != null) {
//Use recursion to allow Previous
//state to print its own data paths
PrevState.Print();
}
//Use the conditional operator to figure out what side we are on
String WhatSide = Side ? " BOAT RIGHT->" : "<-BOAT LEFT ";
//Print the current state.
Console.WriteLine(nMiss + "M/" + nCan + "C " + WhatSide + " " +
(NumOfEachAtStart - nMiss) + "M/" +
(NumOfEachAtStart - nCan) + "C");
}
//Simply returns true is 2 states are the same
//
//param : StateToCheck is the State to check against
//
//return : True if the number of Missionaries,
//number of Cannibals and
//Side are the same for this State
//and the StateToCheck against. Otherwise
//false is returned
public bool Equals(State StateToCheck)
{
return (nMiss == StateToCheck.nMiss &&
nCan == StateToCheck.nCan &&
Side == StateToCheck.Side);
}
//Simply returns true if this State is a valid state
//This method makes use of the command line argument that
//specfies whether there should be more
//Cannibals than Missionaries,
//OR whether there should be more
//Missionaries than Cannibals. Either
//way it uses this global flag to work
//out if the state is valid for the
//given choice that the user made
//when running this application.
//
//return : True only if the number
//of PersonType1 does not outnumber
//the PersonType2 in this state.
//The allocation of whom PersonType1 and
//PersonType2 are, is governed by
//the command line argument to this
//application.
public bool InvalidState()
{
int PersonType1 = 0;
int PersonType2 = 0;
//Check to see if the user requested
//that there be more Cannibals than
//Missionaries. If this is the case set
//PersonType variables for this
//situation
if (Program.CanOutnumberMiss)
{
PersonType1 = nCan;
PersonType2 = nMiss;
}
//Otherwise set the siutation to be that
//there be more Missionaries than
//Cannibals
else
{
PersonType1 = nMiss;
PersonType2 = nCan;
}
// Check for < 0, which could actually
// happen unless it is checked for here
if (nMiss < 0 || nCan < 0 ||
nMiss > NumOfEachAtStart ||
nCan > NumOfEachAtStart)
return true;
//Do PersonType2 outnumbers
//PersonType1(only worry when there is at least
//one PersonType1) one Side1
if (PersonType1 < PersonType2 && PersonType1 > 0)
return true;
//Do PersonType2 outnumbers PersonType1
//(only worry when there is at least
//one PersonType1) one Side2
if ( (NumOfEachAtStart - PersonType1 <
NumOfEachAtStart - PersonType2) &&
(NumOfEachAtStart - PersonType1 > 0))
return true;
//At this point the State must be valid
return false;
}
} //End of State class
#endregion
}
The results
When run, the application will print all valid solutions that were found. It will find more than one.
The results should look something like the following:
Points of Interest
I hope this article is of interest to someone.
History
- v1.0 - 03/11/06.