\documentclass[11pt]{article}
\usepackage[margin=1.0in]{geometry}
%% \usepackage{accanthis}
\usepackage{graphicx,color}
\newcommand\refnote[1]{\textsuperscript{[\ref{#1}]}}

\title{Designing heuristics}
\author{Artificial Intelligence}
\date{}
\parindent 2ex
\parskip 1ex

\begin{document}
\maketitle
\thispagestyle{empty}
%
For your second homework, please experiment with heuristics to
optimize the A* search for solutions to configurations of my son's
game Rushhour.  Rushhour is a children's puzzle based on sliding
blocks back-and-forth on a grid.  One of the blocks represents the
family car, which is stuck in traffic: one or more blocks sit in
between the family car and an exit the end of the family car's row of
the grid.  My son solves the puzzle by moving cars within their row or
column so that the path from the family car to the exit becomes clear;
you and I will solve the puzzle by tuning a heuristic search algorithm
to find a series of moves which are as optimal as we can manage.
\begin{center}
  \begin{tabular}{c@{\rule{25mm}{0mm}}c}
    \includegraphics[height=40mm]{startgame.jpg}
    &
    \includegraphics[height=40mm]{endgame.jpg}
    \\ Stuck in traffic.
    &
    Driving free!
  \end{tabular}
\end{center}
Only the family car is allowed to exit; the other vehicles must remain
in the frame.

You will receive a substantial amount of working code for your
experiments: the Java code you will produce for this homework will
include little more than implementating your ideas for heuristic
functions\footnote{But there is also written work; keep reading.}.
There are links to the code and its Javadoc on Canvas; some starting
points for exploring the code are:
\begin{itemize}
  \item Package \textsf{rushhour.model} is an implementation of
    the game mechanics --- the Rushhour board, cars, possible moves,
    etc.
    \begin{itemize}
    \item Class \textsf{rushhour.model.Boards} has some sample
      initial board configurations.
    \end{itemize}
  \item Package \textsf{search.graph} is a generic implementation of
    several of the graph search algorithms we have discussed.
    \begin{itemize}
    \item The heart of this implementation is class
      \textsf{GraphSearcher}, which implements the
      \textsc{Graph-Search} algorithm of Russell and Norvig in its
      general form.  The specific behaviors of the frontier, the
      explored set, checking for goal nodes, etc.\ are provided
      through the generic type arguments, and through the behaviors
      passed as constructor arguments.
    \item You will make particular (if indirect) use of class
      \textsf{AStarSearcher}, which specializes \textsf{GraphSearcher}
      with the priority queue details of A* search.
    \end{itemize}
  \item Package \textsf{rushhour} links the generic search
    implementations with the Rushhour model.
    \begin{itemize}
    \item Class \textsf{rushhour.BreadthFirstFinder} solves
      Rushhour puzzles using breadth-first search.  This class is your
      frenemy: On the one hand, this class gives you a working example
      of how we specialize the general search algorithms to a
      particular problem.  But on the other hand this class is your
      rival, since the entire point of designing good heuristics with
      A* is to \emph{beat blind search algorithms like BFS}.
    \item For each heuristic function you implement, you will write
      one class extending \textsf{rushhour.MovesFinder}.  Note
      that the constructor for \textsf{MovesFinder} takes only one
      argument --- the heuristic function.  Your subclasses should
      provide that constructor argument, and nothing more: do not
      otherwise override any methods inherited from
      \textsf{MovesFinder}.
    \item Finally, you will extend class
      \textsf{rushhour.AbstractSolution} to wrap up all of your
      work on one bundle (see the \emph{Deliverables} section below).

      The \texttt{run} method of this class is suitable for calling
      from the \texttt{main} method of your concrete \texttt{Solution}
      class, such as with
\begin{verbatim}
  new Solution().run();
\end{verbatim}
      The given version will apply all of your solvers, plus BFS, to
      all of the sample boards, and print the results as a table.  Of
      course you are free to override or edit this method locally to
      print additional calculations useful for your analysis of the
      effective branching factor.
    \end{itemize}
\end{itemize}

\section*{Deliverables and submitting them}

There are three deliverables for this homework:

\begin{enumerate}
\item\textbf{Contributions to \textsf{rushhour.model.Boards}.}
  As I write this document, there are a small number of example boards
  in that class, but we will all find it useful if there are more.
  Therefore this weekend or early next week I will scan some Rushhour
  cards, and will ask each of you to encode two for inclusion in that
  class, and then email me the revised \textsf{Boards.java}.  Later in
  the week, I will update that class with all of your contributions.
  
  Follow the naming convention of the board which are already in that
  file, make sure it compiles and runs under BFS, and email me your
  updated \textsf{Boards.java} file.  This portion of the homework is
  due by \textbf{Thursday, October 3}.\footnote{If you signed out your
    board sheet the week after, then this portion is due Thursday,
    October 10.}

\item\textbf{Heuristic function implementations.}  Using the
  approaches we studied for designing heuristics, I expect you to try
  \emph{at least \textbf{\textcolor{blue}{three}} distinct ideas} for
  heuristics for Rushhour, implementing each one as a separate class
  extending \textsf{MovesFinder}.  Your heuristics should be
  independent of board size: although the physical toy does use a
  $6\times 6$ board, the \textsf{BoardState} class which represents
  one configuration of the board can have a different size set at its
  creation.

  In addition, you should provide one \emph{additional}
  \textsf{MovesFinder} extension which combines your individual ideas
  using pointwise maximization.\footnote{See the discussion in the
    text (Sec.\ 3.6.2 in Russell and Norvig 2010), for a way to react
    to the situation where we create different heuristics which all
    seem good, but without a ``single `clearly best' heuristic.''}

  When you are debugging your code, it may be helpful to use the
  \textsf{setDebug} method to generate debugging information from
  running your code.  However, the versions of your
  \textsf{MovesFinder} extensions which you submit should \emph{not}
  set this flag, or otherwise print output messages.

  Finally you should write one additional class \textsf{Solution} in
  the \textsf{rushhour} package extending
  \textsf{rushhour.AbstractSolution}.  This class simply allows me to
  run all of your code at once.  Your \textsf{Solution} class should
  look something like:
\begin{verbatim}
package rushhour;
public class Solution extends AbstractSolution {
  public Solution() {
    super(new MyFinder1(), new MyFinder2(),
          // ...
          new MyFinderNminusOne(), new MyFinderN(),
          new MyComboFinder());
  }

  // Use *exactly* this main method
  public static void main(String[] args) { new Solution().run(); }
}
\end{verbatim}
  where the \textsf{MyFinderN}'s implement your individual heuristic
  ideas, and \textsf{MyComboFinder} performs the pointwise
  maximization across them.\footnote{Note that except for
    \texttt{Solution}, I do not care what you actually name these
    classes --- so long as I can compile them and run
    \textsf{Solution}.}

  Submit your code to Canvas as a \textsf{zip} or \textsf{tgz} file
  which expands to a \textsf{src} directory containing your Java
  source at the top-level.  I will expand your archive and then run
  commands like
\begin{verbatim}
  javac -cp codeIGaveYou.jar src/*.java
\end{verbatim}

  This portion of the homework is due on \textbf{Monday, October 21}.

\item\textbf{Written report.}  Analyze each of your heuristics,
  discussing
  \begin{itemize}
  \item How you derived them.
  \item Their properties, especially admissibility, consistency, and
    complexity.  Do not spend time on heuristics which are not
    admissibile and consistent, and do not duplicate solving the
    problem in the heurisitic.
  \item Their performance, including consideration for each heuristic
    of
    \begin{itemize}
    \item Its effective branching factor on each board relative to
      both the theoretical branching factor for that board, and the
      effective branching factor by the provided BFS implementation
      for that board.
    \item How stable its effective branching factor is across
      different boards.
    \end{itemize}
    Gather many numbers!
  \end{itemize}
  Discuss the factors behind each heuristic's advantages, and draw
  conclusions as to which of your heuristics are better or worse.
  Submit this report to Canvas as a PDF as discussed in the syllabus.

  This portion of the homework is due on \textbf{Monday, October 21}.

\end{enumerate}

\section*{Bug bounty}
I wrote the code distributed with this assignment with haste.
Although I have run it successfully, I have not thoroughly tested it,
and you are as likely as not to find bugs in it.  I will award a small
amount of extra credit for the first accurate emailed report of each
bug in the code.  A report must contain a minimal example which
triggers the bug; reports which also identify suspected details of the
bug will be assessed as more valuable.

\end{document}

%% Local Variables:
%% mode: latex
%% End: