\documentstyle[fancyheadings,12pt]{article}

\pagestyle{fancy}

\addtolength{\headheight}{5pt}

\setlength{\headrulewidth}{1pt}


\setlength{\topmargin}{-0.6in}		%for dvi-imagen
\setlength{\oddsidemargin}{0.0in}   	%prev:-0.1 for dvi-imagen, -ve needed.
\setlength{\headheight}{.3in}
\setlength{\headsep}{.3in}
\setlength{\textheight}{8.8in}
\setlength{\textwidth}{6.5in} 
\setlength{\marginparwidth}{0in}
\setlength{\marginparsep}{0in}
\setlength{\marginparpush}{0in}

\lhead{Ph.D. Comp.Exam.}

\chead{Artificial Intelligence}

\rhead{Fall 1996}

\cfoot{}



\setcounter{secnumdepth}{3}	%to get numbers on subsubsection in text
				%default is 2.
\setcounter{tocdepth}{3}	%to get numbers on subsubsection in toc
				%default is 2.
\setlength{\unitlength}{1mm}
\renewcommand{\baselinestretch}{1.2}  % for kind of double spacing
%\setlength{\parskip}{.3in}
\setlength{\baselineskip}{0.5cm} %JUST CHANGED FROM 0.5
\setlength{\parindent}{0.3in} %JUST CHANGED FROM 0.2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55

\newcommand{\ria}{\rightarrow}
\newcommand{\Ria}{\Rightarrow}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\xsp}{\hspace{0.5em}}
\newcommand{\ysp}{\vspace{1.1ex}}
\newcommand{\appr}{\sqsubseteq}
\newcommand{\trr}{\triangleright}
\newcommand{\lf}{\tt} %%%%%%%%%%%%%%%%%%%%%%%%%%%% LISP FONT, MAYBE CHANGE LATER
\newcommand{\etal}{{\em et al.}} 
\newcommand{\etc}{{\em et cetera}} 
\newcommand{\eto}{ evaluates to }
\newcommand{\col}{ Common Lisp}

\def\heading#1{ \begin{center} {\bf \ul{#1}} \end{center}}

\newcommand{\asmtabs}
	{mmmmm\=mmmmmmmm\=mmmmmmmm\=mmmmmmmmmmmmmmm\=  \kill}
\newtheorem{thm}{Theorem}
\newtheorem{propn}[thm]{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{examp}{Example}
\newtheorem{exercises}{Exercises}
\newtheorem{program}{Program}

\def\correct#1{\relax \ifmmode \expandafter #1 \else
$\expandafter #1$\fi}            % forces mathmode

\def\db#1{\correct{[\![ #1 ]\!]}}
\def\exer#1{\begin{exercises} \rm
{ #1 }
\end{exercises}}
\def\th#1{\begin{thm} \rm
{ #1 }
\end{thm}}
\def\exam#1{\begin{examp} \rm
{ #1 }
\end{examp}}
\def\lem#1{\begin{lemma} \rm
{ #1 }
\end{lemma}}
\def\prog#1{\begin{program} \rm
{ #1 }
\end{program}}
\def\verba#1{\begin{verbatim}
{ #1 }
\end{verbatim}}

\begin{document}
\setlength{\itemsep}{\parskip} 

{\bf Answer all questions.}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%1:
\item 
``Anti-tic-tac-toe'' is a two-player, zero-sum game 
played using a $4\times 4$ grid.
Player X places a cross on an empty square,
and player O places a circle on an empty square.
The two players play in succession (as in regular tic-tac-toe),
we may assume X plays first.
Player O wins
if three crosses are placed in adjacent squares in the same ``loss line''
(any of the four rows, four columns, or six ``diagonal'' lines with 
 slope 1 or $-1$).
Similarly, player X wins
if three circles are placed in adjacent squares in the same loss line.
For instance, the following states indicate wins for player X,
dashes indicate empty squares.

\begin{verbatim}
--OX    OOOX    -O-X    -O-X    ---X    O--X	----	---X
-OX-    --X-    -OX-    -XO-    OX--	-O-X	--OX	---O
O-X-    --X-    -OX-    --XO    -OX-    --O-	-OX-	X-OX
----    ----    ----    ----    --O-    XX--	O--X	-O--
\end{verbatim}

\begin{enumerate}
\item
Execute alpha-beta search 
 using the following heuristic evaluation function:
$$10(\mbox{number of loss lines with 3 X's} - \mbox{number of loss lines with 3 O's})$$
$$~~+(\mbox{number of loss lines with exactly 2 X's} - \mbox{number of loss lines with exactly 2 O's}),$$
assuming that you (player O) must move next, from the following position:
\begin{verbatim}
X-XX
OO--
O-XX
-OOX
\end{verbatim}
[Note that the board evaluation function yields
 $10(3 - 0) + (2-7) = 25.$]

Examine precisely three levels of the tree:
your current move, X's next possible move, and your next possible move.
You may assume that the game terminates when
 a win or lose position is reached, so that the game tree cannot
 be elaborated below that position.

\item
Compare the heuristic function given above to the following one:
$$
\left\{ \nonumber
\begin{array}{l}
100 \mbox{ if there is a line with 3 adjacent X's} \nonumber \\
-100 \mbox{ if there is a line with 3 adjacent O's} \nonumber \\
(\mbox{number of lines with 2 adjacent X's} - \mbox{number of lines with 2 adjacent O's}), \mbox{ otherwise.} \nonumber
\end{array} \nonumber
\right. \nonumber
$$
Which of the two heuristic functions is likely to 
yield better results, and why?

%\item
%Suggest your own heuristic function that may perform better than
% the two mentioned above.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%2
\item
{\bf Given:}
Landrew is a thinking being.
Landrew has tape drives.
No machine is a thinking being.
Only machines have tape drives.
No machine has tape worms.
\\
{\bf Prove}, using resolution and the refutation theorem-proving method, that:
\begin{quote}
Landrew has tape worms.
\end{quote}
Note: Clearly translate the above English sentences into 
formulas, identifying the intended meaning of each symbol used.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%3
\item
Using the AI techniques you have learnt, 
 design a tour planner for 
 a group of people  traveling together in Europe
 for a two-week vacation.
Each city has several possible locations that can be visited.
Obviously, not every possible location can be visited
 in the limited time available.
With each possible  location that can be visited, there 
 is a certain activity that can be performed.
Each member of the group has his own preferences among various activities,
 but would also like to indulge in more than one activity;
 for instance, John Doe likes art museums, 
 but wouldn't want to spend the entire trip in museums.
Due to cost constraints, all in the group must drive together everywhere
 in the same car.
Note that it takes time to travel from city to city.
Also, different locations may have different levels of attraction 
 to the tourists even if they correspond to the same activity,
 e.g., the Louvre museum is preferable to an unknown museum in Stuttgart.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4
\item
Let $B=\{(0,0), ~(0,1)\}$.
Describe the effects of the following operations:
\begin{enumerate}
\item
Dilation by $B$
\item
Dilation by $B$, followed by dilation of the result by $B$
\item
Dilation by $B$, followed by erosion of the result by $B$
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\item Answer one of the following parts:
\begin{enumerate}
\item
Discuss whether  one can develop a neural network
 whose output is ``1'' if the input supplied 
 is a grammatical sequence of words
 (according to a given, arbitrary grammar),
 and ``0'' otherwise.
\item
Discuss whether a rule-based  expert system can be developed
  to determine whether a given sequence of words
  is a grammatical sentence  (according to a given, arbitrary grammar).
\end{enumerate}
\end{enumerate}

\end{document}

\item
Discuss (in detail) how the following ``menu selection''
problem may be solved, in the light 
of the AI techniques you have studied.
\begin{quote}
A group of very hungry people go to a restaurant.
Each member of the group has his/her preferences among menu choices.
Each item on the menu has its own price.
Unfortunately, they do not have enough money 
between them to pay for each person's first choice.
\end{quote}
