Warnsdorf Algorithm

As part of my follow research to my paper, I did some preliminary research for the Warnsdorf’s algorithm for finding knight’s tours.  I found three relevant papers on the subject (Pohl 1967, Pohl-Stockmeyer 2004, and Ganzfried 2004).  Basically, the Warnsdorf algorithm is to traverse the path with least degree.  In the case of a tie, the a path is randomly selected.  In reality, the Warnsdorf algorithm is not consistently successful as pointed out by (Ganzfried 2004).  The (Ganzfried 2004) paper modifies the Warnsdorf algorithm with key squares in which the move order changes, which improves finding knight tours.  The next step is generate a prolog program using the Pohl-Warnsdorf and Ganzfried algorithms.

Progress Report – June 2008

In this report, I focused on my presentation for the upcoming ICAI ‘09 conference in Las Vegas.  It has currently 18 slides.

I am also viewing the video lectures from the Summer Schools in Logic and Learning from Video Lectures dot Net.  Thus, I have completed the Introduction to Logic video lectures.

I was also reading Michalski’s article on A Theory and Methodology of Induction Learning. Basically it was an article describing the induction process and some the issues associated with induction such as descriptive language, background information, examples, generalization, and hypothesis space.  All this sounded familar when I was reading the two books on ILP.  Induction is a common theme with the two books.  Various familar algorithms are discussed amongst this material.  It appears there are no easy answers in the induction of rules from examples.

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).

Progress Report – May 2009

This month I submitted my paper A Brute Force Approach to Solving the Knight’s Tour using Prolog to the ICAI ‘09 conference, located at the Monte Carlo in Las Vegas, Nevada.  According to the conference chair, the conference acceptance rate was 27 percent.  This conference is in conflict the IJCAI conference in Pasadena, California.

Nevertheless, besides my research paper, much of my activity this month has been around logic programming and inductive logic programming (ILP).  I ordered from Amazon several books recently around this area, in particular The Art of Prolog and Inductive Logic Programming: From Machine Learning to Software Engineering.  The Art of Prolog has a gentle introduction to logic programming – it is very clear and instructive.  From this book I was able to understand early articles in Logic Programming.

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.

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.

Wumpus World

I have been getting many searches for the Wumpus World code.  The LISP version is located at the AIMA website.

For the java version, goto the AIMA Java Code web page.

There are prolog versions of the Wumpus World as well.

Progress Report – December 2008

The month began by reviewing my college Probability and Statistics book (Devore 1991).  I needed to review standard probability concepts mentioned in articles and the Stanford machine learning class.  For example, the article Learning with a Mixture of Trees (Meila and Jordan 2000) the authors explain the new algorithm by using Joint Probabilities and probabilistic mathematics to describe the algorithm – a similar used by Dr. Ng in his machine learning lectures.

WISE Compiled

After fixing the return of thread status call from a boolean to the thread.state type, inspite of the other 60 coding warnings, I successfully started the WISE software, and exited.

I will explore the User’s manual further on setting up a trial run.