\documentstyle[a4,alltt]{article}
 
 
\topmargin 0.9 in         %   Nominal distance from top of paper
                          %   to top of page - 1in
\textheight 7.3 in        %   Height of body of page
\textwidth  5.25 in       %   Width of text area
\oddsidemargin  0.5 in    %   (Left margin on odd-numbered pages-1in)
\evensidemargin 0.5 in    %   (Left margin on even-numbered pages-1in)
\marginparwidth 1 in      %   Width of marginal notes.
\parindent 0.25 in        %   Amount of indent on first line of para
 
\begin{document}
 
\newcommand{\idx}[1]{}
 
\title{Supplement 6}
\author{Jocelyn Ireson-Paine}
\maketitle
 
 
\section{Introduction}
 
This supplement gives some practice with arithmetic and \verb#not#. It also
talks about how the Traveller route-planner works, and introduces {\it
lists}\idx{lists!routes as|ee}, which you will meet again after leaving the Tutor.
 
 
\section{Traveller}
 
\idx{Traveller|(ee}
 
\subsection{Some arithmetic}
 
\idx{arithmetic|(ee}
\idx{is/2@\verb#is/2#|(ee}
 
In Supplement 5, I asked you to amend COLLIER\idx{COLLIER|ee} so that he would buy more
fuel if he was at a fuel station and had less than 10 units left. At the
time, you only knew how to make him buy a fixed amount, regardless of
his need.
 
Now, using \verb#is#: can you amend your definition (or that in COLLIER2\idx{COLLIER2|ee}), so
that he always buys exactly what's needed to refill his fuel tank up to
its limit?
 
Now, consider moving from Colliery Row to The Hub. Even if you do make a
coal trader who always buys exactly the right amount of fuel, he will
eventually run out of money, because the net cost of fuel on each cycle
is greater than the profit to be made from coal. The Hub offers richer
pickings; both televisions and glasses should (barring chance events)
enable a careful trader to make a steadily increasing profit. Can you
program a Hub trader?
 
\idx{arithmetic|)ee}
\idx{is/2@\verb#is/2#|)ee}
 
 
\subsection{Gateways}
 
\idx{gateway/2@\verb#gateway/2#|(ee}  \idx{not/1@\verb#not/1#|(ee}
 
I have written the code of a more intelligent trader. One of the
predicates in it is \verb#gateway(Region,Square)#.
This is true if Square is
a gateway to Region; that is, if Square is inside Region, but also
connects to a square that is outside it. What is wrong with the
definition below?
 
\begin{alltt}
    gateway( Region, Square ) :-
        in( Square, Region ), \idx{in/2@\verb#in/2#|ee}
        adjacent( Square, Other ). \idx{adjacent/2@\verb#adjacent/2#|ee}
\end{alltt}
 
%sann
%{\it We need to stipulate that Other is not in Region}.
 
 
\subsection{Using {\tt not} to find the cheapest goods}
 
\idx{nearest\_gateway/3@\verb#nearest_gateway/3#|(ee}
 
Having found and corrected the error
in \verb#gateway#, have a look at
\verb#nearest_gateway#, below. The idea is that
\verb#nearest_gateway(From,Region,Gateway)# is true if Gateway is that
gateway to Region which is nearest to From. It could be used by a trader
who has started off some way from a particular region, and who wants to
move into that region before starting to trade.
 
\begin{alltt}
    nearest_gateway( From, Region, Gateway ) :-
        gateway( Region, Gateway ),
        distance( Gateway, From, D ),\idx{distance/3@\verb#distance/3#|ee}
        not((
                gateway( Region, Other ),
                distance( Other, From, D1 ),
                D1 < D
           )).
\end{alltt}
 
Translate the definition into English. There is a bug in it (one I
committed myself when writing the game); what is it?
\idx{gateway/2@\verb#gateway/2#|)ee}
\idx{nearest\_gateway/3@\verb#nearest_gateway/3#|)ee}
 
%sann
%{\it Other must be different from Gateway}.
 
Now, one can write a structurally similar predicate for finding the
cheapest wholesaler. Call it
\verb#cheapest_seller_in_region(Good,Region,Square)#\idx{cheapest\_seller\_in\_region/3@\verb#cheapest_seller_in_region/3#|ee}. It is true when Square
offers the lowest price of any square selling Good within Region.
Define it!
 
You will find the answers in TRADER.\idx{TRADER|ee}.
 
 
\subsection{Searching for regions}
 
Suppose we wanted to find all regions R not equal to a given region
ThisR (which might be, say, \verb#'The Hub'#) Would the question
\verb#R \= ThisR?# \idx{\\=/2@\verb#\=/2#|ee} find them? If not, what would?
 
\idx{Traveller|)ee}  \idx{not/1@\verb#not/1#|)ee}
 
 
\section{Route finding and lists}
 
\idx{lists|(ee}
\idx{route-finding|(ee}
\idx{search methods!and route-finding|(ee}
 
I talked earlier about a trader that might, using \verb#nearest_gateway#\idx{nearest\_gateway/3@\verb#nearest_gateway/3#|ee},
begin at a random point on the board and make his way to a particularly
favourable region before starting to trade. In order to do this, we need
some means of finding a route between two squares. In fact, it ought not
to be {\it a} route; it ought to be the {\it shortest} route.
 
Supplement 2 asked you to write \verb#on_route_to#\idx{on\_route\_to/2@\verb#on_route_to/2#|(ee} for the caves world\idx{caves world|ee}. If
you were happy with recursion\idx{recursion|ee}, you may have succeeded in producing
something logically correct. However, your predicate probably had
several disadvantages:
 
\begin{enumerate}
 
\item If the goals\idx{goals!and order of execution!left-recursion|ee} were in the wrong order (something technically called
left-recursion\idx{recursion!left-|ee}),
the predicate may have got into an infinite
loop\idx{loops!in logically correct predicates|ee}
 
\item Even if not, it may have got trapped in a loop if there were
closed paths in the space being searched. This is almost certain, since
I have not yet introduced the techniques necessary to prevent this.
 
\item Even if the predicate avoids looping, it might find a path that
is not the shortest. The two problems above are specific to Prolog; they
arise because it is not faithful enough to logic. This third problem
is language-independent. In order to write a predicate that finds
shortest paths, you need to know a lot about {\it search}. This is a
large topic in A.I. and operational research, and there are many
different methods for writing programs to find shortest or least-cost
paths in various types of network.
 
\end{enumerate}
\idx{on\_route\_to/2@\verb#on_route_to/2#|)ee}
 
\begin{sloppypar}
\idx{route/3@\verb#route/3#|(ee}
\idx{Traveller!and route-finding|(ee}
Traveller itself defines such a predicate:
\verb#route(Square1,Square2, Route)#.
It is true if Route is the shortest
route between Square1 and Square2. To see how it represents routes, load
TRAVELLER\idx{TRAVELLER|ee}, and then ask the question
\begin{verbatim}
    route( 66, 11, R )?
\end{verbatim}
You may notice a slight pause before the answer.
\end{sloppypar}
 
For the route between squares 66 and 11, \verb#route# will give the answer
\begin{verbatim}
[28, 25, 26, 35, 34, 23, 24, 17, 33, 5, 6, 7, 29, 30, 31, 32, 11]
\end{verbatim}
Tracing the sequence out on the board should convince you that it is the
shortest route. It is represented as a new type of Prolog
object, one you have not met before. In A.I., we frequently need to deal
with sequences: sequences of words making up a sentence, sequences of
actions making up a plan, sequences of points making up a path.
This need was realised in the early days of A.I. computing, round about
1958, and gave rise to programming languages, the most famous of which
is Lisp, with facilities for handling {\it lists}. Prolog also
implements lists\idx{lists!routes as|ee}, and this is what \verb#route# returns.
\idx{route-finding|)ee}
\idx{search methods!and route-finding|)ee}
\idx{Traveller!and route-finding|)ee}
\idx{route/3@\verb#route/3#|)ee}
 
Lists are particularly valuable because they can vary in length. When I
introduced \verb#act#\idx{act/4@\verb#act/4#!using lists as arguments|ee}
in Traveller\idx{Traveller!\verb#act/4# and lists|ee},
I said that if your action was \verb#move#, the next
argument had to be \verb#dummy#. This is because \verb#act# has a
fixed number of
arguments\idx{arguments!to \verb#act/4#!using lists as|ee}, and so an argument
that's not needed by some action still has to be
there. With lists\idx{lists!of Traveller actions|ee} we would not have this problem: we could represent
actions as
\begin{verbatim}
    [ move, 18 ]
    [ buy, coal, 20 ]
    [ sell, peaches, 5 ]
\end{verbatim}
where we only use as many places as we need.
 
Another situation in which lists\idx{lists!game states as|ee} would make sense is the
noughts-and-crosses\idx{noughts-and-crosses|ee} game of Supplement 2. In this, we had facts like
\begin{verbatim}
    o_moves_to( bbbbxbbbb, obbbxbbbb ).
    o_moves_to( bbbbxbbbb, bobbxbbbb ).
\end{verbatim}
where positions on the board are represented as atoms\idx{atoms!lists better than|ee}. This is not a
good way to represent them, though it's all that was available at the
time. For example, if we were printing out the result of a move, we
would
need to produce a diagram of the board. To do this, we must, for each
square on the board, be able to determine whether it contains an O or an
X. Now, although we can see that the 5th letter (corresponding to the
middle square, say) of \verb#bbbbxbbbb# is \verb#x#, there's no way to discover
this from within a program.
Atoms\idx{atoms!lists better than|ee} are indivisible: that's why they're called atoms. However, if we
represent board positions as lists
\begin{verbatim}
    [ b,b,b,b,x,b,b,b,b ]
\end{verbatim}
then it is possible to write a
recursive\idx{recursion!in list-processing|ee}
predicate that returns the Nth
item of any list. We do in fact have a stock
list-handling predicates, including a ``find Nth element'' one, if
you need them later.
 
Lists\idx{lists!sentences as|ee} are also good for representing sentences.
Later on in the course, you will see how to use lists of words in
building your own Eliza\idx{Eliza|ee}; to tell it for instance that
the response to any list
\verb#[my,R,hates,me]# where R names a relative (e.g. sister) is
\verb#[tell,me,more,about,your,R]#, while that to \verb#[i,like,A]# where A
names an action (e.g. sailing) is \verb#[you,say,you,like,A]#.\@
It is possible
to write general rules or templates that recognise certain kinds of list
and transform them into other lists, and this gives Prolog a lot of the
flexibility you need for A.I.
 
%sann
%{\it We do not use lists again until after finishing with the Tutor, but
%it is worth showing students now that Prolog can provide something more
%than atoms\idx{atoms!lists better than} and numbers for handling complex data. For simplicity, I
%generally use lists throughout the course, and don't mention other
%structures at all. Chapter 3 of~\cite{scott} describes a simple Eliza whose
%input and output are both represented as lists.}
 
\idx{lists|)ee}
 
\end{document}
