"Linux Gazette...making Linux just a little more fun!"

Artificial Intelligence on Linux

By Anderson Silva

Artificial Intelligence is a very controversial subject, but the way I will approach it in this article is simple and fast. The way I have been approaching AI is not through the philosophical or biological aspect, but just as a computational subject. When humans want to fly, they don't need to study the birds to learn how to do it, they just get into an airplane. This is my way of approaching AI. We want to solve puzzles and games through a computer without really comparing the way a human accomplishes tasks differently from a computer.

For the first time in the history of my school, there was going to be offered an Artificial Intelligence (AI) class. I was very excited about this class because you hear a lot about AI, but you don't really see a lot of material for it on magazines and online articles.

Probably the greatest example of an AI application is Turing's Test. The test consists in a person being a room with a computer terminal, and this person would start to chat with the computer. At the end the person would have to figure out if he talked to a real person on the other end of the terminal or with a computer program. And if the user confuses the person with the computer then we would have reached AI.

At, LU we chose Prolog to be the implementation tool for AI. Our labs at school are Windows NT based and we have only one linux machine which is designated to students. But I have been a linux user for almost 2 years, and I wanted to implement all my Prolog assignments in Linux.

I did some research on the web and I found a great Prolog compiler for linux. Prolog is like linux in a certain way, there are several flavors that you can pick from. The one I chose was SWI Prolog (http://www.hio.hen.nl/faq/SWI-Prolog.html). Prolog is a very flexible language. Unlike other languages like C, C++ or Java, Prolog is based on formal mathematical logic, in this case: Predicate Calculus. A Prolog program is normally made of facts with a set of rules. To reach the final solution it has to satisfy this set of rules. Interpreting these rules allows the computer to deduce the solution by itself. In Prolog the facts are normally stored on a separate file called the knowledge base, and rules on another file that is the actual program.

Allow me to show a very basic search algorithm known as the Depth First Search (click for image).

The Program below is the representation of the graph above in Prolog.

% Name:   Anderson Silva
% Date:   March 10, 1999

% ================================
% A graph that will be used for a
% Depth First Search Algorithm
% Knowlodge Base.
% ================================

% linked/2
% A nodes and its children

linked(a, [b,c,d]).
linked(b, [e,f]).
linked(c, [g,h]).
linked(d, [i,j]).
linked(e, [k,l]).
linked(f, [l,m]).
linked(g, [n]).
linked(h, [o,p]).
linked(i, [p,q]).
linked(j, [r]).
linked(k, [s]).
linked(l, [t]).
linked(m, []).
linked(n, []).
linked(o, []).
linked(p, [u]).
linked(q, []).
linked(r, []).
linked(s, []).
linked(t, []).
linked(u, []).

% arc/2
% A rule that checks to see if
% there is an arc between two given nodes.

arc(X,Y):- linked(X,L), member(Y,L).

The algorthim that searches the graph for a specific goal:

% Name:   Anderson Silva
% Date:   March 10, 1999
% ================================
% This is the Depth First Algorithm
% implemented in Prolog that will
% use the graph.pl knowlodge base
% ================================

% reverse_write/1
% Inverts the order of the stack.

reverse_write([H|T]):-reverse_write(T), write(H), nl.

% solve/2
% Gives the path in the reverse
% order since dfs is implemented as
% a stack

solve(INode, Solution):- consult('graph.pl'),
                         dfs([], INode, Solution),

% query_goal/0
% Creates the goal to be reached
% during execution
% We start with abolish, so if solve is ran more
% than once, it will make sure it
% forgets the old goals and only look for the
% new on.

query_goal :- abolish(goal(Node)),
              write('Goal? [Followed by a period]'),

% goal/1
% When the program runs for the frist time
% query_goal needs to abolish at least one goal
% and that is why goal(standard) is used.


% dfs/3
% The Actual recursive algorithm for the
% Depth First Search

dfs(Path, Node, [Node|Path]):- goal(Node).
dfs(Path, Node, Sol):- arc(Node, Node1),

Copyright © 1999, Anderson Silva
Published in Issue 43 of Linux Gazette, July 1999