Exercise 3

%Author of paper:
% Jonathan Borgviken

\documentclass{article}
\usepackage[utf8]{inputenc}

\usepackage{authblk}
\usepackage{listings}
\lstset{showstringspaces=false, language=Matlab, frame=shadowbox, frameround=tftf}

\usepackage{graphicx} % Used to handle graphics
\graphicspath{}

\title{Perspective Course [Exercise 3]}
\author{Jonathan Borgviken}
\author{Christoffer Brun}
\author{Pajtim Cerimi}
\author{Niklas Ling}
\author{Lolita Mageramova}
\affil{School of Information Science, Computer and Electrical Engineering, Halmstad University}

\begin{document}

\maketitle

\section*{Task 1}
In this task we were supposed to explain how a given \textit{heuristic}\footnote{A \textit{heuristic} is in this context a function which evaluates a given board position.} works. We were also supposed to work out \textbf{why} it works better than letting a computer do random moves to try and solve the puzzle. In addition to this we were also supposed to provide examples of boards with higher, and lower \textit{heuristic score}\footnote{\textit{Heuristic score} is the function value of a \textit{heuristic} function.}.
\par
For our purposes, let us define the two artificial intelligences discussed in this section. If we let our first \textit{AI}\footnote{\textit{AI} is an abbreviation for artificial intelligence} in \textbf{MATLAB} be defined as
\begin{lstlisting}
  function direction = myAI(~)

  d = {'up', 'down', 'right', 'left'};
  direction = d{randi(4)};

  end
\end{lstlisting}
then what we have is an \textit{AI} which does not use any information available. It is, most would say, dumb in that sense.
\par
Our second \textit{AI}, let us refer to it as the smarter \textit{AI}, will be using a \textit{heuristic}, $h$, to its advantage. Without providing source code to the \textit{AI}, let us describe the \textit{AI} to base its decisions solely on our heuristic function $h$. In short, the \textit{AI} will let $h$ evaluate the board when asked to, hypothetically, make a move \textbf{up}, \textbf{down}, \textbf{left}, and \textbf{right} respectively. The move with the highest \textit{heuristic score} will be the move our \textit{AI} decide to do.
\newpage
\noindent If we let \textbf{B} be a matrix representing our board, in \textit{logarithmic scale}\footnote{In practice, we have converted our board from squares with values $2^k$ to squares with values of $k$ using the logarithmic function with base 2.}, our heuristic score is calculated according to $h$ as
\begin{lstlisting}
  function u = heuristic1(B)
  u  =  - sum(B(:));
  end
\end{lstlisting}
And as such, one could draw a parallel explanation from the perspective of a matrix \textbf{A} representing the board in its true form, in a more mathematical approach. Let \textbf{A} be an \textbf{r} (rows) times \textbf{c} (columns) matrix.
\[h(A) = -\sum^r_{i=1} \sum^c_{j=1}\log_2 A_{i,j} = -\left(\log_2 A_{1,1} + \log_2 A_{1,2} + \ldots + \log_2 A_{r,c}\right)\]
\par
Let us now provide some examples to show you what a board with higher, and lower heuristic score looks like. For simplicity, we will provide examples for our logarithmic matrix, i.e. just like our matrix \textbf{B}. Study the following matrices.
\begin{center}
 $X_1 =$
  \begin{tabular}{c|c|c}
    1 & 2 & 2  \\
    \hline
    3 & 0 & 0  \\
    \hline
    2 & 0 & 0
  \end{tabular}
  $X_2 =$
  \begin{tabular}{c|c|c}
    2 & 1 & 2  \\
    \hline
    3 & 0 & 0  \\
    \hline
    2 & 0 & 2
  \end{tabular}
\end{center}
\begin{center}
  $X_3 =$
  \begin{tabular}{c|c|c}
    5 & 3 & 2  \\
    \hline
    2 & 6 & 3  \\
    \hline
    2 & 3 & 1
  \end{tabular}
  $X_4 =$
  \begin{tabular}{c|c|c}
    4 & 5 & 5  \\
    \hline
    3 & 6 & 2  \\
    \hline
    2 & 1 & 3
  \end{tabular}
\end{center}
The portrayed matrices' heuristic scores are evaluated as
$$h(X_1) = -10,\qquad h(X_2) = -12$$
$$h(X_3) = -27,\qquad h(X_4) = -31$$
With this said, matrices $X_1$, and $X_2$ are the preferred boards for our smarter \textit{AI}. Their heuristic score is higher, and are therefore more sought-after. Matrices $X_3$, and $X_4$ on the other hand have, relatively, low heuristic score compared to our first two matrices, and as such are not preferred boards for our smarter \textit{AI}.

\newpage
\section*{Task 2}
\begin{figure}[h]
  \centering
  \includegraphics[scale=0.7]{hist_AI4.png}
  \caption{Histogram for $h_0$}
  \label{h0}
\end{figure}
\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.7]{hist_AI5.png}
  \caption{Histogram for $h_1$}
  \label{h1}
\end{figure}
\newpage
\noindent In this task we were asked to first compare two heuristics, see fig.~\ref{h0} and fig.~\ref{h1}. The first heuristic $h_0$ is the heuristic used in our smart \textit{AI} in the last section of this report. Our second heuristic $h_1$ is a heuristic which evaluates a board with high amounts of empty squares to have a high heuristic score.
\par
The two histograms portrayed are created from data running both $h_0$, and $h_1$ three hundred times, respectively. Let us compare the two simulations.
\begin{center}
  \begin{tabular}{|c| c c c|}
    \hline
    & Mean score & Max score & Highest block\\
    \hline
    $h_0$ & 4996 & 9170 & 512  \\
    \hline
    $h_1$ & 3848 & 7107 & 512  \\
    \hline
  \end{tabular}
\end{center}
From this we see that $h_0$ outperformed $h_1$ by far. Its mean score is 1148 points above, and its max score, whilst not too much of a difference, outperformed $h_1$ by 2063 points. However, we see that they both achieved 512 as their highest block.
\par
Further we were asked to create a new heuristic, using both $h_0$, and $h_1$. In the simplest way, we were to create a heuristic $h_{\alpha} = (1-\alpha)h_0+\alpha h_1$, where $\alpha\in[0,1]$. We went ahead and tried three values for $\alpha$, namely $\alpha = 0.25, 0.5, 0.75$. To test these three new heuristics, we tried simulating them three hundred time each.
\par
Take a look at each histogram on the following two pages, and then let us compare the results. We will, just as before, base our results on three parameters. First of all, how the mean score compares to the other $\alpha$ values, our other two parameters are the max score and their highest block.
\begin{center}
  \begin{tabular}{|c| c c c|}
    \hline
    $\alpha$& Mean score & Max score & Highest block\\
    \hline
    .25 & 5636 & 10400 & 1024  \\
    \hline
    .50 & 6160 & 11380 & 1024  \\
    \hline
    .75 & 4222 & 7644 & 512 \\
    \hline
  \end{tabular}
\end{center}
From this we see that $\alpha = 0.5$ gave us the best results. Comparing with the aforementioned heuristics ($h_0$ and $h_1$) one sees that using both heuristics yields better outcomes in all three categories. Experimenting more, one would most indubitably find a better value for $\alpha$, a quick glance gives the impression it may exist such a value $\beta \in\,].25,.50[$.

\newpage
\begin{figure}
  \centering
  \includegraphics[scale=0.7]{hist_025.png}
  \caption{Histogram for $\alpha = 0.25$}
  \label{h025}
\end{figure}
\begin{figure}
  \centering
  \includegraphics[scale=0.7]{hist_05.png}
  \caption{Histogram for $\alpha = 0.5$}
  \label{h05}
\end{figure}
\begin{figure}
  \centering
  \includegraphics[scale=0.7]{hist_075.png}
  \caption{Histogram for $\alpha = 0.75$}
  \label{h075}
\end{figure}

\end{document}