The Art of Prolog

The book The Art of Prolog (Sterling and Shapiro 1994) is an excellent treatise in the subject of Logic Programming and Prolog.  The book is divided into four parts – Logic Programming, The Prolog Language, Advance Prolog Programming Techniques, and Applications.

Beginning with Logic Programming, chapter one provides the best introduction into Logic Programming as well as the first definition of the abstract interpreter for logic programming.  The definitons for term, functor, compound term, clause or rules, logic programs, and the meaning for logic programs are presented.  The summary is worth reading.

Advance Prolog Programming

Reading the comp.ai.prolog news group, I noticed the prolog FAQ did not make any references to any advance prolog programming websites.  Though it mentions the Craft of Prolog as the book for the advance reader, it was published before the ISO Prolog standard was finalized.  I have in my wish list in Amazon the book Prolog Programming in Depth by Michael Covington et. al (Fascimile edition), which seems from the table contents a book that could compliment the Bratko’s Prolog: Programming for Artificial Intelligence and The Art of Prolog.  Here is an example:

cycle(X) :-
   (    X < 1 -> true
        ;
        write(X),
        nl,
        X1 is X - 1,
        cycle(X1)
   ).

The above example is used to count down from X to 1.  In all the online tutorials, I have not seen example using the -> control construct.  I will on occasion will publish some prolog code.

Advice Language

Back in 1990, since my goal back then was to develop a chess playing computer algorithm using prolog, as part of my research, I stumbled into Max Bramer’s book Computer Game Playing: Theory and Practice.  In that book there was a chapter by Ivan Bratko called Knowledge-based problem-solving in AL3, which according to the book the article appeared in Machine Intelligence 10.  In summary the AL3 system was basically a production system for chess problem using the Donald Michie Advice Language concept and utilizing Bratko’s IF condition THEN action rule concept.  At that moment of time, many of the concepts presented in the paper were foreign to me, and unbeknownst to me, many of the ideas are presented in Bratko’s AI book (1990).

Wumpus World Revisited

I have noticed there has been many searches for the wumpus world problem.  The LISP version is located at the AIMA website.  The Prolog version by Professor Larry Holder is located at this URL, which is written for Quintus Prolog.  Both versions are based on the analysis by Stuart and Norvig’s book.

Knights Tour Part III

Once again, I am looking the knight’s tour problem again.  Upon a google search of the knight’s tour and prolog, I discovered there are other prolog implmentations (one solution was written in Turbo Prolog as well as a Common LISP implementation).  As of this time I only have downloaded copies of the other implementations, and I am not certain how efficient these implementations are.

One observation about this puzzle is the use of a heuristic and magic squares.  One approach is to implement a version with the warnsdorf heuristic.  The heuristic requires a look a head procedure to maximize the good squares.  I have little knowledge about this heuristic since it was published in 1823.  The second approach is to use the concept of magic squares to fine solutions quickly and efficiently.  This is useful; however, the implementation of these solutions into logic programming is the question as well as the Prolog implementation.

Logic Programming Prolog

I am reading the book Logic, Programming and Prolog (2nd ed).  After completing the preliminaries chapter, much of the material was familiar since it was defining predicate calculus and logical inferences.  The material is mathematically rigorous by authors Ulf Nilsson and Jan Maluszynski.  They develop a series of definitions to build the language of predicate calculus and inference.  The familiarity was due to my studies from the material presented in Luger and Stubblefield (1992), and Stewart and Norvig (1995).

The authors continue with the SLD-Resolution along with Unification.  They illustrate a unification algorithm as well as proof trees.  Afterwards negation is discussed; thus  they develop the SLDNF-Resolution.  The cut and mathematics is covered.  If used improperly, cuts can make programs unsound and yield false answers.  All this tied into logic programming theory.  The theorems and propostions come from various resources.  The goal of the book is teach programmers on how to write logic programs that are sound, correct, and finite.

I found this book interesting thus far and good introduction to logic programming and prolog.

Knight’s Tour Revisited

In my previous posting of the Knight’s Tour problem, I had posted the following code:

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X). on interpreter line.
%
% Verify clause
%
verify(X,Y) :- X > 0 , X  0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

In that posting, I stated that my code found a solution within 35 seconds and considered an improvement due to hardware technical reasons. However, I modified and improved the code by testing boundary conditions. I changed the verify clause from:

verify(X,Y) :- X > 0 , X  0 , Y < 9.

to test the boundary conditions instead as follows:

verify(9,_) :- !, fail.
verify(10,_) :- !, fail.
verify(0,_) :- !, fail.
verify(-1,_) :- !, fail.
verify(_,9) :- !, fail.
verify(_,10) :- !, fail.
verify(_,0) :- !, fail.
verify(_,-1) :- !, fail.
verify(_,_).

The modification improved by finding the first solution in six seconds of CPU utilization, which is a significant improved from 35 seconds.  The idea of testing the boundary came from reading the Othello chapter from Peter Norvig’s book Paradigms of Artificial Intelligence Programming as well as other sources for checking the border.  The new code, tested with SWI-Prolog, is as follows:

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X). on interpreter line.
%
% Verify clauses
%
verify(9,_) :- !, fail.
verify(10,_) :- !, fail.
verify(0,_) :- !, fail.
verify(-1,_) :- !, fail.
verify(_,9) :- !, fail.
verify(_,10) :- !, fail.
verify(_,0) :- !, fail.
verify(_,-1) :- !, fail.
verify(_,_).
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm derived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

The above code generates open-circuit solutions. I have not checked for closed-circuit solutions. The first 14 solutions are found with just 2m07s of CPU utilization.

The test environment is Red Hat Linux v4.6, running in a VMWare session.

Knight’s Tour

As part of my earlier studies into Artificial Intelligence, I was challenged to write a prolog program to solve the knight’s tour for an 8×8 board. I had early success using UNSW4 prolog interperter on SCO Unix machine, and the program resolved a path in 45 minutes in early 1995. Later that year, using the same prolog program and prolog interperter, the program resolved the knight’s tour on Sparc Center 2000 in 25 minutes. In my opinion I accomplished quite a feat. My code was influenced by Clocksin and Mellish book Programming in Prolog, which had an example of depth first search algorithm.

Here is the original prolog code for UNSW prolog interperter.

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X)? on interpreter line.
%
% The following clauses are from Programming in Prolog by Clocksin
% and Mellish:
%
%   membership,
%   rev, and
%   append
%
% Verify clause
verify(X,Y) :- X > 0 , X < 9, Y > 0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Classical membership test
%
member(X,[X|T]).member(X,[H|T]) :- member(X,T).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(Place,T,R,L) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R,L1),
        L is L1 + 1.go0(X,T,[X|T], 1).
%
% Classical rev clause
%
rev([],[]).
rev([H|T],L) :- rev(T,Z), append(Z,[H],L).
%
% Classical append clause
%
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R, Len),
        Len == 64,
        rev(R, Solution),
        !.

Recently I have ported the UNSW prolog interperter to a RHEL 4.5 in VMWare environment on a PC running 3.0 GHz Intel processor. The result was the program resolved a path in 35 seconds.

However, I modified the same code above and ported to GNU Prolog, the result is simpler:

%
% Verify clause
%
verify(X,Y) :- X > 0 , X < 9, Y > 0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

The irony is that Luger in Artificial Intelligence: Structures and Strategies for Complex Problem Solving treats the knight’s tour problem as a simple student exercise, in which he not only challenges the student to resolve in Prolog, but also in LISP, the premier AI programming language for which I have little experience with.