From kalita@pikespeak.uccs.edu Sat Aug 17 12:09:59 1996
Received: from pikespeak.uccs.edu by sanluis.uccs.edu; (5.65/1.1.8.2/19Jul96-8.2MPM)
	id AA19609; Sat, 17 Aug 1996 12:09:56 -0600
Received: by pikespeak.uccs.edu; (5.65/1.1.8.2/24Jul96-8.2MAM)
	id AA17165; Sat, 17 Aug 1996 12:09:48 -0600
Date: Sat, 17 Aug 1996 12:09:48 -0600
From: J Kalita <kalita@pikespeak.uccs.edu>
Message-Id: <9608171809.AA17165@pikespeak.uccs.edu>
To: jhjulkun@sanluis.uccs.edu
Status: OR

 
\documentstyle[11pt,fancyheaders]{article}

\def\ti{\list{}{\rightmargin 0pt \leftmargin 2.5em}\item[]}  % set rightmargin to 0 pt.

\input{lfix}
\marginfix

%\pagestyle{empty}
\pagestyle{fancy}
\lhead{{\sf October 1995}}
\rhead{{\sf CS 482-582}}


\cfoot{}
%\rfoot{\fancyplain{}{\rm\thepage}}
\rfoot{\sf\thepage}
\lfoot{{\sf University of Colorado at Colorado Springs}}

\setlength{\headrulewidth}{5pt}
\setlength{\plainheadrulewidth}{5pt}
\setlength{\footrulewidth}{.4pt}
\setlength{\plainfootrulewidth}{.4pt}

\setlength{\parskip}{10pt}

\flushbottom


\begin{document}
\markboth{CS482-582}{Home Work Assignment 3}

\begin{center}
{\LARGE University of Colorado at Colorado Springs}\\[.2in]
{\Large  Home Work Assignment 3}\\
Heuristic Search\\
{\sf Out 10-19-95, Due 11-7-95}\\
\end{center}
\vspace*{.15in}

\noindent
\mbox{} \hrulefill \mbox{}\\


\section{The Word Ladder Game}

{\em Word-ladder} is a game in which a single player
is given two words with the same number of letters (we will be using
3-letter words) in each.  For example, DOG and CAT\@.  He or she has to
change the first word into the second word by replacing
one letter at a time with any other letter as long as the result is a
proper English word.  For example, we could change DOG to FOG but not
to GOG (not a proper English word) nor to GOD (two letters were
changed).  Thus, one way of getting from DOG to CAT might be:
\begin{quote}
DOG $\Longrightarrow$ COG $\Longrightarrow$ COT $\Longrightarrow$ CAT
\end{quote}
There are many ways to make most translations.  Here is another way:
\begin{quote}
DOG $\Longrightarrow$ HOG $\Longrightarrow$ HOT $\Longrightarrow$ HAT 
$\Longrightarrow$ CAT
\end{quote}
Some examples are very hard to do.  Try changing WHY to ASK\@.

To make the problem more interesting, we will assume that there is a
cost associated with using a letter as a replacement.
The cost of replacing any letter of a word by A, E, I, L, N, O,
R, S, T, or U is 1,  the cost of replacement by B, D, G, C, M, P, F, H,
V, W, or Y is 2 and the replacement cost for K, J, X, Q, or Z is 4\@.  For
example, the following transformation has a total cost of 8:
\begin{quote}
DOG $\stackrel{4}{\Longrightarrow}$ JOG $\stackrel{1}{\Longrightarrow}$ 
JOT $\stackrel{2}{\Longrightarrow}$ COT $\stackrel{1}{\Longrightarrow}$ CAT
\end{quote}

\subsection{The Assignment in General}

For this assignment you are asked to write a Lisp system that plays
word-ladder using a  general {\tt graphSearch} algorithm 
part of the code for which is given to you.  You
will be provided with the problem-independent parts of {\tt graphSearch} and
will have to write the problem-dependent parts.  

The {\tt graphSearch} function that you will use takes five arguments:
\begin{itemize}
\item The initial node.
\item A predicate which is true of goal nodes.
\item A function to compute the successors of a node.
\item A function to estimate the distance from a given node to a goal node.
This is just the {\em h\/} function discussed in class.
\item A function which estimates the total cost of a path from the start
node to a goal node passing through a given node.  This function takes
the {\em g\/} and {\em h\/} values for a node and combines 
them to produce the {\em f\/}
value.  For the algorithm A* discussed in class, this is just
\begin{verbatim}
(lambda (gvalue hvalue) (+ gvalue hvalue))
\end{verbatim}

\end{itemize}

You will have to write the problem-dependent parts for the word-ladder problem,
i.e.\ the {\tt wordladder\/} function, the {\tt computeSuccessors\/} 
function and various versions of the {\em h\/} and {\em f\/} functions.


\subsubsection{{\tt wordladder}---the top-level function}
The {\tt wordladder\/} function takes two arguments, the initial and final
words, invokes {\tt graphSearch} with the proper arguments for the problem
and returns the result.

\subsubsection{{\tt computeSucessors}---generates a node's successors}
The {\tt computeSuccessors\/} function is given a node and returns a list
(possibly empty) of the successors of that node in the search space and
the cost associated with arcs from the node and each sucessor.  The
function should return a list of tuples where the first element of each
is a successor node and the second is the associated arc cost.  For
example:
\begin{verbatim}
(computeSuccessors 'dog) -> ((bog 2) (cog 2) ... (jog 4) ... (dot 1)) 
\end{verbatim}
Note that the successor states must be valid states (i.e.\ legal English
three-letter words). A possible way to attack the problem of generating
the successor states is to write a function which given a word W
generates the 78 possible words formed by replacing a letter in W with
any letter in the alphabet.  This list must then be ``filtered'' to
remove the illegal words. Some functions you may find useful
have been provided for you:

\begin{itemize}

\item {\tt (explode <atom>)} ---  A function which, given an atom, returns a
list of the characters in that atom.  For example:
\begin{verbatim}
(explode 'dog) -> (#\D #\O #\G)
\end{verbatim}
\item {\tt (implode <list>)} ---  A function which, 
given a list of characters,
returns the atom formed by concatenating the characters.  For example:
\begin{verbatim}
(implode '(#\d #\o #\g)) -> DOG
\end{verbatim}
\item {\tt (legalWord <s-expression>)} --- A predicate which 
returns T iff its argument is a legal English word with three
letters.
\end{itemize}

\subsection{The Assignment In Particular}

\begin{enumerate}
\item Write the functions to compute a node's successors and the top level
function to solve a word-transformation problem.

\item Write versions of the {\em h\/} and {\em f\/} functions 
to do the following
kinds of search and solve the word-ladder problem for each one.
\begin{enumerate}

\item {\em random search\/}: No information about the 
{\em f\/} or {\em g\/} values is used. This should be easy.
\item {\em breadth-first  search\/}: The node with
lowest-cost path form the start is chosen for expansion.
\item {\em best-first search\/}: The node which appears closest to the goal
is selected for expansion. Devise a reasonable estimator (i.e.\ {\em h\/})
function and describe it in the comments in your code.
\item {\em algorithm A search\/}:  The node which appears to be on the shortest
path from the start to the goal state will be selected for expansion.
\end{enumerate}
\item Modify the graph search package to do a bi-directional search.  That is,
it should simultaneously search from the initial state toward a
given goal state and from the goal state toward the initial state.  The
search will terminate when a node is reached from both directions.
This part is hard.   You may want to introduce more structure to the
main function graphSearch before complicating it any further.
\item Hand in  a listing of your code and the results for the four forward
searches and the four bi-directional searches.  You should turn
{\tt tpflag\/} off when you produce the results.
\end{enumerate}


\subsection{The graphSearch Package}

The graphSearch package, the dictionary, and the {\tt legalWord\/} function are
in the file\\
{\bf /usr/local/ug/ai-archive/cs482-582/search.lsp}.   
You are recommended to copy this
file into your area, and to play with it in order 
to understand it.  This section gives a few notes to help you.

\subsubsection{Debugging Information}

The variable {\tt tpflag\/} controls the printing of certain information
about the graphSearch process.  If it is non-nil, then a message will
be printed
\begin{itemize}
\item when a node is added to the graph,

\item when a node is expanded,

\item when a new shortest path to a node has been identified.
\end{itemize}
You may find this information useful when debugging your program.

\subsubsection{rememberSuccessors}

Whenever {\tt graphSearch} expands a node, it needs to know the node's
successors and the associated arc costs. Rather than recompute this
for each graphSearch run, we have cleverly arranged to remember what
they are.  If you change the dictionary or discover a bug in your
{\tt computeSuccessors\/} function, however, you need to forget all the
old answers.  The control of whether or not the successors of a node
are remembered is determined by the flag {\tt rememberSuccessors\/}.  If it
is non-nil then old values will be remembered.  If  it is nil then new
values will be computed each time.

\subsubsection{Altering the Dictionary}

You can change the dictionary that we have provided with the functions
{\tt addWord\/} and {\tt deleteWord\/}. For example,
\begin{verbatim}
(addWord 'foo)
\end{verbatim}
adds the word {\tt foo\/} to the dictionary, and 
\begin{verbatim}
(deleteWord 'foo)
\end{verbatim}
removes the word {\tt foo\/} from the dictionary.  
The atom {\tt dictionary\/} is
bound to a list of all the words currently in the dictionary.

\subsubsection{Rest of the code}
For rest of the code, look at  the relevant file specified.


\section{Playing a Game of Chess: {\em For graduate students only}}

Write a brief research paper discussing the issues that arise in the
implementation of a game of chess. Also discuss how some such issues
have been addressed by researchers and game implementors. Discuss any
open questions  you think have not been addressed properly.

In actually formatting the paper,
follow  the  {\em Instructions to Authors}\footnote{The instructions
are for submitting papers to a conference by the American Association
for Artificial Intelligence. You may ignore some of the very  specific
instructions given and use your own judgement.}  given to you along with
this assignment.  
Will you be willing to give a brief presentation (say, 10-15 minutes)
to the class on your findings? 


\end{document}


