Sunday, December 28, 2008

Missionaries, Cannibals and Prolog

Apparently, many generations of computer scientists have been concerned with the problem of letting cannibals and missionaries crossing a river with the very same boat.

Before them, logicians were looking for a way to have married couples doing the very same thing with slightly different inherent problems.

Centuries ago, the problem was that no woman should be with another man without her husband being present (this is now called a threesome). However, since women now are emancipated and nobody cares if a woman is with another man (with the possible exception of her own husband, especially when there are no football matches on TV), the cannibal problem seems more interesting.

It is widely accepted that if missionaries outnumber cannibals, they convert the cannibals. Since we believe in freedom of cult, no cannibal shall be converted. Someone may be familiar with another version of this problem, since once having people converted was considering a good thing, while having missionaries eaten was bad.

However, recently cannibals became vegans and until Churches will develop soy-missionaries the problem is how to let cannibals retain their own religion.

Basically, this is the job for a Prolog interpreter. Though humans solved this problem long ago, a human can only solve the problem for small numbers of cannibals and missionary (and though we hope both populations remain small in number, cannibals can always mate and missionaries can convert new people).

This is a short Prolog program that given an initial state (all cannibals and all missionaries on the same side of the river) and the desired final state (all cannibals and missionaries on the other side of the river), computes the strategy our poor bootman has to pursue in order to carry over the whole lot of people.

initial_state(mc, mc(left, bank(3,3), bank(0,0))).
final_state(mc(right, bank(0,0), bank(3,3))).

Above we say that the initial state has the boat on the left, three cannibals and three missionaries are on the left bank and no one is on the other one. The final state encodes what we have already said.

Now we have to describe possible moves:

move(mc(left, L, _R), Boat) :-
    choose_passengers(L, Boat).

move(mc(right, _L, R), Boat) :-
    choose_passengers(R, Boat).

choose_passengers(bank(C, _M), boat(2, 0)) :- 
    C > 1.
choose_passengers(bank(_C, M), boat(0, 2)) :- 
    M > 1.
choose_passengers(bank(C, M), boat(1, 1))  :- 
    C > 0, M  > 0.
choose_passengers(bank(C, _M), boat(1, 0)) :- 
    C > 0.
choose_passengers(bank(_C, M), boat(0, 1)) :- 
    M > 0.

Basically, when the boat is on the left bank, we choose passengers from the left bank. When the boat is on the right bank, we choose passengers from the right bank. We can only take 2 people on the boat. That means that, provided there is enough people on the bank, we can only carry 2 cannibals, 2 missionaries, 1 cannibal, 1 missionary or 1 cannibal and 1 missionary. Since the boatman is usually agnostic, the cannibal aboard with one missionary is not going to be converted.

The Prolog system choses one of the possible moves and proceeds. If the move is wrong, it back-tracks and tries another solution. Until the number of choices is small, it is rather efficient.

The predicates that describe how the system changes when one move is performed are:

update(mc(B, L, R), Boat, mc(B1, L1, R1)) :-
    update_boat(B, B1),
    update_banks(Boat, B, L, R, L1, R1).

update_boat(left, right).
update_boat(right, left).

update_banks(alone, _B, L, R, L, R).
update_banks(boat(C, M), left, 
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM - M,
    RM1 is RM + M,
    LC1 is LC - C,
    RC1 is RC + C.

update_banks(boat(C, M), right,
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM + M,
    RM1 is RM - M,
    LC1 is LC + C,
    RC1 is RC - C.

Eventually, we have to tell legal and illegal configurations apart. Basically, if in the bank we leave there are more missionaries than cannibals, we are breaking the law. If not, everything is fine (since the boatman works for free, so he does not have to pay taxes).

legal(mc(left, _L, R)) :-
    \+ illegal(R).

legal(mc(right, L, _R)) :-
    \+ illegal(L).

illegal(bank(C, M)) :-
    M > C.

The solution algorithm is trivial:

solve_dfs(State, _History, []) :-

solve_dfs(State, History, [Move|Moves]) :-
    move(State, Move),
    update(State, Move, State1),
    \+ member(State1, History),

solve_dfs(State1, [State1|History], Moves).

print_moves([M|Ms]) :-

go :-
    initial_state(mc, State),
    solve_dfs(State, [State], Moves),

We generate new moves and check if the updated state would be legal and if we did not get in the same state before (if it happens we are looping, the boatman becomes hungry and eats whoever is on his boat -- that’s the main reason why he does not travel with the empty boat).

The full source is here:


harish said...

I tried your program and it doesn't give the list of moves instead it prints false. Can you explain the moves little more clear at update_banks. I am newbie and it is little confusing to understand

rik0 said...

A small typo. Of course, boat in the move predicate should have been Boat.

Besides, some Prolog also do not have writeln. Here I fixed both the boat -> Boat and removed writeln.

I also discovered that Prolog is the only major language not supported by Gist/Github. I used Erlang syntax, which at least deal correctly with variables vs. atoms.

harish said...

Thanks for the code. I was able to eliminate the typo but the solution doesn't seem right. This is what I am getting
boat(1, 1)
boat(0, 1)
boat(0, 2)
boat(0, 1)
boat(1, 1)
boat(0, 1)
boat(0, 2)
boat(0, 1)
boat(1, 1)

Infact the moves are repeating and there should be 11 moves and the solution has only 9 moves

rik0 said...

No. The solution is correct.

1. the logical model is correct, therefore the solution *must* be correct. You can even formally prove it without having any output (but it would not be very interesting).

2. I understand the output is not clear; in fact those are the boats and essentially boats in odd lines go left to right and boats in even lines go the other way round. It is perfectly normal that boats repeat (part of the problem human have when solving this problem is that they have to do something they perceive as steps backward (and repetition).

3. I understand that you have a solution in 11 steps. That may be correct as well (in fact, I believe there are infinite solutions). That does not make the one found incorrect.

4. I modified the printing routines. I just return different data (not the boats, but also the state at each step) and now I can have a better output (btw, with just the boats and initial state you could just build the very same data; the modifications to the core are not important, indeed).

This is the full output:
bank(3,3) * bank(0,0)
-> boat(1,1) ->
bank(2,2) * bank(1,1)
<- boat(0,1) <-
bank(2,3) * bank(1,0)
-> boat(0,2) ->
bank(2,1) * bank(1,2)
<- boat(0,1) <-
bank(2,2) * bank(1,1)
-> boat(1,1) ->
bank(1,1) * bank(2,2)
<- boat(0,1) <-
bank(1,2) * bank(2,1)
-> boat(0,2) ->
bank(1,0) * bank(2,3)
<- boat(0,1) <-
bank(1,1) * bank(2,2)
-> boat(1,1) ->
bank(0,0) * bank(3,3)

harish said...

Thanks for the pretty quick reply. When I traced the problem earlier it was giving me the right steps but it was printing a different answer. So I thought may be there was something wrong in the logic in the illegal move. Latest one works absolutely fantastic.
Can you please suggest me few online links or text book for prolog. I will have to do a project using prolog so I wish to learn it. I might have to develop a scheduling mechanism with prolog and wrap the mechanism with a different programming language.

rik0 said...

I learnt prolog "the hard way", unfortunately. The only (english) book I own explicitly about prolog is this one:

The Art of Prolog, Second Edition: Advanced Programming Techniques (Logic Programming)

The first time I read it I did not actually appreciate its depth. I was more into, "let's hack something with Prolog". On the other hand the book focuses on the logical programming paradigm. I had lots of troubles for programming with prolog without such a solid foundation, though.

This book looks very promising:

Prolog Programming for Artificial Intelligence

Keep in mind that Prolog has dozens of different implementations. Embedding Prolog (or FFI) are extremely implementation specific topics which are not at all dealt in Prolog books. Once again, I advise you to fully understand Prolog model before doing such a thing, because otherwise some API choices would seem awkward.

I have some experience with FFI and embedding SWI-Prolog. The documentation is terse but correct and easy to read.

ratzko said...

I tried your program and I think there is some bug inside it. This state 'bank(2,1) * bank(1,2)' can't be possible. Can you explain it to me?

rik0 said...

What do you mean with "the state 'bank(2,1) * bank(1,2)'"?

As far as I can tell I never used the functor *, for example.

ratzko said...

This is a line from output. It isn't in the program code.
I believe that functor * just shows where is boat at the moment.

But by state I mean that it's imposible that on one bank for example 2 missionaires and 1 cannibal and on the opposite bank 1 missionaire and 2 cannibals.

rik0 said...

Sorry for the long time it took me to answer.
However, there is no bug that I can see.

It is probably easier to verify directly the source code. Essentially the interpreter choses a solution and before committing it checks that it is legal.

A solution is not legal if the number of cannibals is less than the number of missionaries in the bank we are leaving.

As I said in the specs, there is freedom of cult. We are concerned that missionaries do not force their religion on the cannibals (which they can do if they outnumber the cannibals, which although recently become vegan still remain proud warriors in one-to-one combat).

You can see that in fact I esplicitly check the condition in "illegal":

legal(mc(left, _L, R)) :-
\+ illegal(R).

legal(mc(right, L, _R)) :-
\+ illegal(L).

illegal(bank(C, M)) :-
M > C.

Sawdaq Loay said...

please check the result, it's wrong!

in more than one case, there are more cannibals than missionaries on one side

enrico franchi said...

It is perfectly normal that there are more cannibals than missionaries. As I specifically mentioned in the introduction, the problem is when the religious outnumber the cannibals, because then the missionaries would try to convert the poor cannibal and that is bad because we respect cannibal's culture and don't want it to disappear.

Cannibals are pretty peaceful people nowadays.