homework2.tex

\documentclass[12pt]{article}
\renewcommand*{\familydefault}{\sfdefault}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{fullpage}
\usepackage{tabularx}
\usepackage{graphicx}
\begin{document}
\title{CS540 Artificial Intelligence Homework 2}
\author{Yuchen Hou}
\maketitle

\section{Best first search}
The text in each node has the following format: x, y, d; g(n) + h(n) = f(n);
\subsection{$h(n)=city\_block\_distance+angular\_distance$}
The search tree is shown in Figure \ref{fig:bfs}.
\begin{figure}[htb]
  \centering
      {\includegraphics[width=1\linewidth]{homework2_1_1.png}} \rule{1\linewidth}{1pt}
      \caption{Best first search: $h(n)=city\_block\_distance+angular\_distance$}
      \label{fig:bfs}
\end{figure}
\subsection{$h(n)=city\_block\_distance^2+angular\_distance$}
The search tree is shown in Figure \ref{fig:bfs2}.
\begin{figure}[htb]
  \centering
      {\includegraphics[width=1\linewidth]{homework2_1_2.png}} \rule{1\linewidth}{1pt}
      \caption{Best first search: $h(n)=city\_block\_distance^2+angular\_distance$}
      \label{fig:bfs2}
\end{figure}
\subsection{Conditions for optimality: admissibility and consistency}
It is not admissible. An admissible heuristic nver overestimates the cost to reach the goal; but the heuristic from part(b) overestimates the cost(e.g. it overestimates the cost to goal at node 1,1,r as 5, where the real cost to goal is 3). Therefore it is not admissible.

\section{Hill-climbing search}
\begin{figure}[htb]
  \centering
      {\includegraphics[width=1\linewidth]{homework2_2.png}} \rule{1\linewidth}{1pt}
      \caption{Hill-climbing search}
      \label{fig:hcs}
\end{figure}
The search tree generated by hill-climbing search is shown in Figure \ref{fig:hcs}. Node $(2,2,u; 1/(3+0^2+0)=1/3)$ is returned.

\section{Alpha-Beta pruning}
\begin{figure}[htb]
  \centering
      {\includegraphics[width=1\linewidth]{homework2_3.png}} \rule{1\linewidth}{1pt}
      \caption{Alpha-Beta pruning}
      \label{fig:abp}
\end{figure}
The game tree generated by alpha-beta pruning is shown in Figure \ref{fig:abp}. The text has the format [player];[minimax] for evaluated nodes, or an 'X' for the pruned nodes. MAX should take action a1.
\end{document}