Thursday, October 26, 2006

Two programs for one chess problem

Knight's tour is one of those chess problems I always wanted to solve, but I never had enough patience. Now, thanks to Prolog, it is easy--I just have to write a simple program. And, yes, I am completely aware of the fact that solving it by myself probably would take me less time; however, at the moment I don't own a chess board (without the board it is no fun) and I feel this is a good way of improving my Prolog skills. So, here we go.

To solve the problem to visit all the squares on the board, without any repetitions, moving by horse-jumps (that seems the best way of calling the movement of the knight). The starting square and size of the board are given as parameters.

Lets represent a square on the board by a pair of numbers divided by a slash.

First of all, the way the knight moves:
boardX(8).

boardY(8).

knight(X/Y,X1/Y1) :-
boardX(BoardX),
boardY(BoardY),

(
(X1 is X+2 ;
X1 is X-2),
(Y1 is Y+1 ;
Y1 is Y-1)

;

(Y1 is Y+2 ;
Y1 is Y-2),
(X1 is X+1 ;
X1 is X-1)
),
X1 >= 1, X1 =< BoardX,
Y1 >= 1, Y1 =< BoardY.

The dimensions of the board aren't hardcoded in case we want to solve the puzzle on a nonstandard board, eg. 4x8.
knights_way([_/_],_).
knights_way([First,Second|Rest],Visited) :-
knight(First,Second),
\+member(Second,Visited), % No repetitions, please!
knights_way([Second|Rest],[Second|Visited]).



knights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
knights_way(X,[]).

knights_tour(X) :-
N is BoardX*BoardY,
knights_tour_1(X,N).
Now, this seems pretty easy (although writing it properly took me some time--I don't know Prolog very well, yet). However, not everything in life is as easy as it seems. When you try to run knights_tour on your computer, you won't get an answer, unless your computer is very fast, or you are very patient and long-lived. Why? Let's compare the times:
?- time(knights_tour_1(X,59)).
% 46,797 inferences, 0.02 CPU in 0.01 seconds (141% CPU, 2339850 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour(X,60)).
% 1,677,669 inferences, 0.50 CPU in 0.50 seconds (100% CPU, 3355338 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour_1(X,61)).
% 92,595,863 inferences, 27.43 CPU in 28.15 seconds (97% CPU, 3375715 Lips)

X = [1/1, 3/2, 5/3, 7/4, 5/5, 7/6, 5/7, 7/8, ... /...|...]

?- time(knights_tour_1(X,63)).
C-c C-c
Action (h for help) ? a
abort
% 4,550,510,155 inferences, 1345.57 CPU in 1418.71 seconds (95% CPU, 3381846 Lips)
% Execution Aborted

It seems clear, that the number of inferences is growing very fast, or at least faster than we can afford. That shouldn't be a big surprise: the knight has on average from 2 to 8 possible moves--the size of the solution space we have to search grows exponentially. Blind search just won't do.

So, what we now need is a good heuristic. Fortunately, there's such a heuristic, and it has been developed in 1832 by H.C. von Warnsdorf, which says that the best available square is the one which is available from the least unvisited squares (see here and here). It is said not to work very well for boards bigger than 76x76, but I don't think it's a very big deal.

heuristic(X/Y, Visited, N) :-
findall(A,knight(X/Y,A),Possible),
subtract(Possible,Visited,List),
length(List,N). % I know this may be incorporated to the next predicate, but somehow I feel that splitting it apart is a good thing.

better_heuristic(Visited,A,B) :-
heuristic(A,Visited,HA),
heuristic(B,Visited,HB),
HA =< HB.

A crucial part of our program will be sorting the list of available moves using the heuristic. At first I thought this wouldn't be very important--there were going to be at most 7 elements in the list I wanted to sort--so I wrote a quite lousy linear insert sort. However, this turned to be a bad idea: the whole thing just worked too slow. Changing it to quicksort gave my program a big speed boost (practically, made it work).

Basically, I'm against rewriting things like sorting functions, if there are functions for doing the same provided by the interpreter, written in C and usually much faster. However, SWI-Prolog's sort/2 is lame: it just sorts a list of numbers. And I am used to the Lisp approach, which is a lot more flexible: you are supposed to provide a function that you want to use to compare the elements as an argument to the sorting function.

To my very surprise, implementing such a Lisp-style sorting function in Prolog using call wasn't tricky nor difficult. Of course, there are no lambda-expressions in Prolog, so the final effect is a bit crude: you have to very careful when planning the order of arguments in your predicates. However, this is acceptable--nothing is perfect. As far as I know, this isn't Prolog mainstream, and that's a pity. I feel it's the most elegant solution.

split(Fun,Pivot,[H|Tail],[H|Positives], Negatives) :- % Fun for function. We all know that fuctions are funny.
call(Fun,Pivot,H),!,%H > Pivot,!,
split(Fun,Pivot,Tail, Positives, Negatives).
split(Fun,Pivot,[H|Tail], Positives, [H|Negatives]) :-
call(Fun,H, Pivot),
split(Fun,Pivot,Tail, Positives, Negatives).

qsort(_,[],[]).
qsort(Fun,[Pivot|List],Sorted):-
split(Fun,Pivot, List, Bigger, Smaller),
qsort(Fun,Bigger,NewBigger),
qsort(Fun,Smaller,NewSmaller),
append(NewSmaller, [Pivot|NewBigger], Sorted).



Now, lets put everything together:

hknight(A/B,X,Visited) :- % the `h' is for `heuristic.'
findall(W, knight(A/B, W), Moves),
qsort(better_heuristic(Visited), Moves, SortedMoves),
member(X, SortedMoves). % member chooses the elements preserving the order.

hknights_way([_/_],_).
hknights_way([First,Second|Rest],Visited) :-
hknight(First,Second,Visited),
\+member(Second,Visited),
hknights_way([Second|Rest],[Second|Visited]).

hknights_tour_1(X,N) :-
length(X,N),
X=[1/1|_],
hknights_way(X,[1/1]).

hknights_tour(X) :-
N is BoardX*BoardY,
hknights_tour_1(X,N).


And voilĂ ! We have our problem solved. An example solution:

[ 1, 16, 51, 34, 3, 18, 21, 36]
[50, 33, 2, 17, 52, 35, 4, 19]
[15, 64, 49, 56, 45, 20, 37, 22]
[32, 55, 44, 63, 48, 53, 42, 5]
[61, 14, 57, 54, 43, 46, 23, 38]
[28, 31, 62, 47, 58, 41, 6, 9]
[13, 60, 29, 26, 11, 8, 39, 24]
[30, 27, 12, 59, 40, 25, 10, 7]

I updated this post on Fri Oct 27, 5:14 PM in order to incorporate some useful suggestions made by Daan Fierens. Thank you!

Wednesday, October 18, 2006

Is a goose worth sinning?

If there's a field, where Prolog is very good from first sight, it is no doubt solving logical puzzles. You know what I mean: those where you have to tell who owns the fish, how to measure two liters of water only with a bucket of 3 liters and one of 4 liters, solve a sudoku, and so on. Of course, Prolog will be able to deal only with purely combinatorial riddles--any involving self-reference or some dose of creativity are beyond its scope.

If one was to write it in an imperative programming language, it would take quite a lot of time to write a sound representation of the solution-space and then search through it; in Prolog, you just have to declare the rules which the world of the riddle must obey, and voilĂ !, it outputs the right answer.

For example, the Prolog code for solving the famous Einstein's riddle is quite straight forward (see also this solution):
%% the answer is a list of five houses, in the right order.
%% each house is a list of items in the following order:
%% [Color, Nationality, Beverage, Cigaretts, Pet]

left(L, R, [L | [R | _]]).
left(L, R, [_ | Rest]) :- left(L, R, Rest).

next(X,Y,List) :-
left(Y,X,List).
next(X,Y,List) :-
left(X,Y,List).

einstein(List,FishOwner) :-

List=[_,_,[_,_,milk,_,_],_,_],
List=[[_,norwegian,_,_,_],_,_,_,_],

member([red, brit,_,_,_],List),
member([_,swede,_,_,dog],List),
member([_,dane,tea,_,_],List),
left([green,_,_,_,_],[white,_,_,_,_],List),

member([green,_,coffee,_,_],List),
member([_,_,_,pall_mall,bird],List),
member([yellow,_,_,dunhill,_],List),

next([_,_,_,blends,_],[_,_,_,_,cat],List),
next([_,_,_,_,horse],[_,_,_,dunhill,_],List),
member([_,_,beer,bluemaster,_],List),
member([_,german,_,prince,_],List),
next([blue,_,_,_,_],[_,norwegian,_,_,_],List),
next([_,_,_,blends,_],[_,_,water,_,_],List),
member([_,FishOwner,_,_,fish],List),

write('The '),write(FishOwner),write(' owns the fish.').
Unfortunately, not all simple riddles are so simple for Prolog as the latter one. A good example may be the fox, goose and bag of beans puzzle. It is one of my favorite puzzles (my father told me it when I was five and it was the first real puzzle I've ever solved), so it was quite obvious that this was going to be the second program I would write.

These rules govern the movement of the farmer and his stuff:
next(state([rolnik|Tail],X), state(Tail, [rolnik|X])).
next(state(X,[rolnik|Tail]), state([rolnik|X], Tail)).

(The constants are in Polish: rolnik = farmer, koza = goat (goose), kapusta = cabbage (bag of beans), wilk = wolf (fox).)
next(state([rolnik|Animals], Right), state(NewLeft,[rolnik|Rest])) :-
member(X,Animals),
delete(Animals, X, NewLeft),
append([X],Right,Rest).

next(state(Left,[rolnik|Animals]), state([rolnik|Rest],NewRight)) :-
member(X,Animals),
delete(Animals, X, NewRight),
append([X],Left,Rest).
Next, we write which states of the world are acceptable, and which not:
meal(koza,kapusta). % goats eat cabbage
meal(wilk,koza). % wolfs eat goats

not_good(Bank) :-
\+member(rolnik,Bank),
meal(X,Y),
subset([X,Y],Bank).


good(state(X,Y)) :-
\+not_good(X),
\+not_good(Y).
and the constraints we want the solution to obey:
legal_chain([X]).

legal_chain([Car, Cadr|Tail]) :- % ah, Lisp reminiscences! :-)
next(Car,Cadr),
good(Cadr),
legal_chain([Cadr|Tail]).


Now, the most intuitive thing we could do now would be to state something like this:
naive-solution(Solution) :-
Solution = [state([rolnik, koza, kapusta, wilk], []) | _],
legal_chain(Solution),
last(Solution, state([], [rolnik, koza, kapusta, wilk]).
However, this definitely won't work. It may be perfectly correct from the declarative and logical point of view, but, as I have said in the previous post, Prolog is not logic. It doesn't automagically find the answer--it performs a depth-first search through the solution space. And in this case, the first path Prolog selects is one of the worst for us. The farmers goes to the other side of the river, returns, goes to the other side, and... Yes, ladies and gentlemen. An infinite loop.

Of course, it is possible to solve this problem in Prolog. The only think we have to do is think about our program more... well, as a program, not as a set of propositions, and change its search behavior. For example, we could implement an iterated, depth-first search (AFAIK, this was the least invasive way of altering my code so that it started to work).

(Well, it isn't precisely iterated depth-first (it looks for the answers only at the bottom o each layer), but the idea is quite the same.)
solve(Solution,N) :-
(
between(1,N,X),
length(Solution,X),
legal_chain([state([rolnik,koza,kapusta,wilk],[])|Solution]),
last(Solution,state([],[rolnik,koza,kapusta,wilk]))
),!
;
(
NewN is N+1,
solve(Solution,NewN)
).

solution(Solution) :-
solve(Solution,1).
You may have noticed that the program does nothing to avoid loops in the solutions. However, this is fine--for every “loopy” solution there exists a shorter one without loops, so we can be sure that the first solution we will find (the shortest one) is loop-free.

The last noteworthy thing is the cut operator (the red “!” in solve). Its task is to prevent backtracking after we have found a solution. It isn't really necessary--if you removed it, the program would just try to find other answers (and would find infinitely many of them--all except one loopy). Overusing it is considered very bad style in Prolog (as someone has said, “[cut] turns Prolog from a nice declarative language into a hybrid monster. Use cuts sparingly and with a sense of having sinned.”). However, I am still learning the language and couldn't resist the temptation of trying it, as soon as I found an adequate occasion. Yes, I am a sinner, and the goose was worth it. ;-)

Saturday, October 14, 2006

Lists are not sets, Prolog is not logic

In Ivan Bratko's Prolog. Programming for Artificial Intelligence, in the part introducing lists, there's an obvious exercise consisting in writing a program that gives all the subsets of a given list. In terms of Prolog: a predicate subset(Set,Subset), where all the elements of Subset are elements of Set.

The task seems elementary, but in fact it's quite tricky. The program I wrote did only half of the job, and when (after a half an hour of frantic debugging) I eventually checked the author's program in the Solutions, it turned out that it neither did all the job properly. The interesting point is that this example shows how logic background may in some cases influence your programming intuitions.

But first things first--the two programs and what is wrong with them. The “canonical” solution is the following:
subset([],[]).

subset([First|Rest],[First|Sub]) :-
subset(Rest,Sub).

subset([First|Rest],Sub) :-
subset(Rest,Sub).
My solution is a bit simpler:
m_subset(Set,[]).

m_subset(X,[Y|Tail]) :-
m_subset(X,Tail),
member(Y,X).
What's wrong with the two programs? Well, the canonical version deals fine with generating all the subsets of a given set/list--that is, when you give Prolog the following command:
subset([1,2,3],X).
However, when it turns to checking whether there is inclusion between two given sets, it appears to be quite lame: it won't give you the correct answer unless the two lists are given in the same order. That is, it says “no” to the query
subset([1,2,3],[3,2]).
(I have to make a remark that the stipulation that the lists should be sorted in the same way wasn't given in the text of the exercise).

My program, on the other hand, is great in determining if there is an inclusion, but as for the second task... Well, it just doesn't stop in the right moment. That is, after generating all the subsets of [1,2,3] it starts saying
[1,2,3,1] ;
[1,2,3,2] ;
[1,2,3,3] ;
...
etc.

In fact, that is true (if we want to use lists to represent sets, we should ignore any double occurrences), but if I wanted to have a list of all subsets and manipulate it, an infinite list would not really be the best thing.

I claim that my definition of subset is good, and in some aspects even superior over Bratko's: it is shorter, it's more intuitive, it takes account of some trivial set-theoretic facts the latter ones ignore (like for example that the empty set is a subset of every set). The only problem is that lists just aren't sets (very surprising, isn't it?), and they have different conditions of identity. So when Prolog finds the four element list, which represents a set that already was given, it thinks it is something new. Well, and (sadly), Prolog it's completely right: it is something new.

Now, this problem allows us to observe the fact that Prolog, even if it is not an imperative but a declarative programming language, it is still a programming language, not logic. And things like infinite classes just aren't good. So, my approach towards it should be more as my approach towards e.g. scheme than to logic. And that's why, even if my program was directly translatable to predicate calculus and set theory (of course, limited to Horn clauses), it just wouldn't do.