Evolutionary Computing

While searching for articles for Ivan Bratko at the Josef Stefan Institute website, I discovered the researchers at the Josef Stefan Institute are doing research in Evolutionary Computing and Algorithms. This the kind of bleeding edge technology that I am interested in. Evolutionary Computing and Algorithms are programs that evolve from experience or adapt to new situations – a form of darwinism for the computer software.

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

Man and Machine

Can machine gain awareness and take over man? There are doom theorist think it is possible for a machine to gain awareness and destroy mankind. Such scenarios are seen currently in science fiction movies and television programs such as Battle Star Galatica and the Terminator movies along with the Sarah Conner Chronicles. In the given examples, the machine or software becomes self aware, free their bonds from their human masters, and wages a war against mankind. Can software learn and become self aware? Today the answer is no. With computing power doubling every 18 months, it is possible for a machine or software to become self aware in the distant future.

However, in reviewing current literature of Artificial Intelligence or in particularly Machine Learning – machines are capable of learning and performing a task and develop an experience. Examples are speech recognition, software to detect credit card fraud, data mining for web based and medical based applications. Dr. Tom Mitchell, Director of the Carnegie Mellon University’s Machine Learning Department, has stated that learning machines have significant commercial value and will continue to do so in the next ten years. Here is a link to Dr. Mitchell’s white paper on Machine Learning. Based on current technology, I do not expect my robot vacuum cleaner to take over my household.

Artificial Intelligence is the science of developing intelligent machines or software. The basic tools for Artificial Intelligence are propositional logic, graph theory, state space search, and problem representation. The state space can get very large, thus heuristics are designed to prune the state space and to achieve the desired target in the most cost efficient manner. The aforementioned tools are a subset of all the tools since other solutions do exist as well as technologies such as expert systems, neural networks, SMVs, and bayes networks.

My main interest is two player games. If a machine or software was given a database of master games, can it develop via genetic algorithms the heuristics that mankind have developed? Or will take it a different direction? This is my exploration and adventure.

First, I will read the book Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Second Edition, by George F. Luger and William A. Stubblefield. Although I purchased this book back in the early 1990’s, this book is in its fifth incarnation and available from Professor Luger’s website. By reading the earlier editions, I can see the development of Artificial Intelligence in the past 16 years. As Professor Mitchell has stated above, there has been many exciting developments. Afterwards start exploring this exciting world of artificial intelligence and machine learning.