AI Search to Solve the Missionaries and Cannibals Problem

• Download source files - 13.8 Kb

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.

1. Create a variable called SearchAgenda (say) and set it to the initial state (Root, from our example).
2. 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:
     1. Apply the rule to generate new state(s), these are called Successor states.
     2. If the new state is a goal state (Solution), quit and return this state.
     3. 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.