198 lines
6.0 KiB
HTML
198 lines
6.0 KiB
HTML
<!--startcut ==========================================================-->
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
|
|
<HTML>
|
|
<HEAD>
|
|
<title>Artificial Intelligence on Linux LG #43</title>
|
|
</HEAD>
|
|
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#0000AF"
|
|
ALINK="#FF0000">
|
|
<!--endcut ============================================================-->
|
|
|
|
<H4>
|
|
"Linux Gazette...<I>making Linux just a little more fun!</I>"
|
|
</H4>
|
|
|
|
<P> <HR> <P>
|
|
<!--===================================================================-->
|
|
|
|
<center>
|
|
<H1><font color="maroon">Artificial Intelligence on Linux</font></H1>
|
|
<H4>By <a href="mailto:afsilva@liberty.edu">Anderson Silva</a></H4>
|
|
</center>
|
|
<P> <HR> <P>
|
|
|
|
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.
|
|
|
|
<P> 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.
|
|
|
|
<P> 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.
|
|
|
|
<P> 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.
|
|
|
|
<P> 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.
|
|
|
|
<P> Allow me to show a very basic search algorithm known as the
|
|
<A HREF="gx/silva.ai.jpg">Depth First Search</A> (click for image).
|
|
|
|
<P>
|
|
<HR>
|
|
|
|
<P> The Program below is the representation of the graph above in
|
|
Prolog.
|
|
|
|
<PRE>
|
|
% 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).
|
|
</PRE>
|
|
|
|
<HR>
|
|
|
|
<P> The algorthim that searches the graph for a specific goal:
|
|
|
|
<PRE>
|
|
% 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([]).
|
|
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'),
|
|
query_goal,
|
|
dfs([], INode, Solution),
|
|
reverse_write(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]'),
|
|
nl,
|
|
read(Node),
|
|
assert(goal(Node)).
|
|
|
|
|
|
% 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.
|
|
|
|
goal(standard).
|
|
|
|
% 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),
|
|
</PRE>
|
|
|
|
|
|
<!--===================================================================-->
|
|
<P> <hr> <P>
|
|
<center><H5>Copyright © 1999, Anderson Silva <BR>
|
|
Published in Issue 43 of <i>Linux Gazette</i>, July 1999</H5></center>
|
|
|
|
<!--===================================================================-->
|
|
<!--startcut ==========================================================-->
|
|
<P> <hr> <P>
|
|
<A HREF="index.html"><IMG ALIGN=BOTTOM SRC="../gx/indexnew.gif"
|
|
ALT="[ TABLE OF CONTENTS ]"></A>
|
|
<A HREF="../index.html"><IMG ALIGN=BOTTOM SRC="../gx/homenew.gif"
|
|
ALT="[ FRONT PAGE ]"></A>
|
|
<A HREF="scheidler.html"><IMG SRC="../gx/back2.gif"
|
|
ALT=" Back "></A>
|
|
<A HREF="silva.ip_masq.html"><IMG SRC="../gx/fwd.gif" ALT=" Next "></A>
|
|
<P> <hr> <P>
|
|
</BODY>
|
|
</HTML>
|
|
<!--endcut ============================================================-->
|