path: root/doc/tex/systemDesign.tex

\section{System Design}

\subsection{Class Diagram}

The full class diagram is shown in \fref{fig:fullClasses}.

\begin{figure}[h]
	\begin{center}
		\makebox[0pt]{\begin{minipage}{1.2\textwidth}
			\includegraphics[width=\textwidth]{diagrams/fullClasses.png}
			\caption{Full class diagram.}
			\label{fig:fullClasses}
		\end{minipage}}
	\end{center}
\end{figure}

The design of each system of the diagram is explained after this section
together with diagrams for each subsystem, since the full class diagram can be
too big to be comfortably analyzed.

\subsection{Game}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.55\textwidth]{diagrams/gameModule.png}
		\caption{Design of the implementation of the game of Go.}
		\label{fig:game}
		A game is represented as a tree of moves.
	\end{center}
\end{figure}

A regular Go match is composed of a list of moves. But since game review and
variants exploration is an important part of Go learning, \program{} and most
playing and analysis existing programs allow for navigation back and forth
through the board states of a match and for new variants to be created from each
of these board states. Therefore, a match is represented as a tree of moves. The
GameMove class has the information about a specific move and also a reference to
the previous move and to a list of following moves, implementing this tree
structure and allowing for navigating both forward and backwards in the move
history.

The state of the board at any given move must be stored so liberties, captures
count and legality of moves can be addressed, so it is represented with the
GameState class, which holds a reference to the current move.

Moves depend on a representation of the game board to have access to its current
layout and count of captured stones. There are also many logic operations needed
to be performed on the board, such as getting the stones in a group, counting
their liberties or checking if a move is playable. The layout of the board and
these operations are implemented as the GameBoard class.

A game can be started by the executable \texttt{go.py}.

These classes and their relationships can be seen in \fref{fig:game}.

\subsection{Engine}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.8\textwidth]{diagrams/engineModule.png}
		\caption{Design of the GTP engine.}\label{fig:engine}
	\end{center}
\end{figure}

An implementation of GTP, that is, the piece of software which offers the GTP
interface to other applications. It is designed to be used by a software
controller but can also be directly run, mostly for debugging purposes. Its
design is shown in \fref{fig:engine}. The core of the engine is related with
three components, each with a separate responsibility:

\begin{itemize}

	\item The ImagoIO component is the one imported from executables or other
		applications and offers the text interface. It reads and processes input
		and calls corresponding commands from the core of the engine.

	\item The GameEngine contains the logic of the commands available from the
		IO component. It uses a GameState to keep a record of the game and uses
		a DecisionAlgorithm to generate moves.

	\item The DecisionAlgorithm component is responsible of analyzing the match
		and generate moves. The engine core uses it when a decision has to be
		made by the AI, such as when a move needs to be generated by the engine.

\end{itemize}

Two implementations of DecisionAlgorithm have been made: one for the Monte
Carlo Tree Search algorithm (on the MCTS class) and the other for neural
networks (on the Keras class).

The Keras class also makes use of the NeuralNetwork class, which offers
functions for creating, training, saving and using neural network models. The
designs of the network are implemented in the subclasses DenseNeuralNetwork and
ConvNeuralNetwork as examples of dense and convolutional networks, respectively.

The engine can be started with the executable \texttt{imagocli.py}.

\subsubsection{Monte Carlo Tree Search Explained}

Monte Carlo Tree Search is an algorithm that can be useful for exploring
decision trees. It was used by AlphaGo in conjunction with neural networks as
explained in the AlphaGo 2016 paper\cite{natureAlphaGo2016}.

The algorithm assigns a score to each explored node based on how likely the
player who makes the corresponding move is to win and updates this score on each
exploration cycle.

The exploration of the tree has 4 steps:

\begin{enumerate}

	\item \textbf{Selection}: The most promising move with unexplored children
		is selected for exploration. Unexplored children are viable moves which
		are not yet part of the tree.

	\item \textbf{Expansion}: An unexplored children of the selected move is
		added to the tree. This children is selected at random.

	\item \textbf{Simulation}: The score of the new move is evaluated by playing
		random matches from it.

	\item \textbf{Backpropagation}: The score of the new move, as well as its
		previous moves up to the root of the tree, is updated based on the
		results of the simulation.

\end{enumerate}

The suggested move is the children of the current move with the best score from
the perspective of the player which has to make the move.

The implementation of the algorithm will use the existing GameMove class from
the Game System to access the game logic it needs, such as to get the possible
children from a node or to simulate random games.

\subsubsection{Neural Networks Explained}

A neural network is composed of nodes or ``neurons''. Each node contains a value
named weight. During execution the node receives a numeric input, multiplies it
for its weight and applies a function called activation function to the result.

Nodes are organized in layers so that a network contains several layers and each
layer one or more neurons. The input to the network forms the input layer, which
contents are forwarded to the second layer. The second layer applies the weight
and activation function as discussed before in each of its nodes and the result
is forwarded to the next layer, and so on. At the end the last layer, called the
output layer, contains the result of the input evaluation. Each layer can have a
unique activation function for all its nodes and a different strategy of
connecting to the previous and next layers.

Several kinds of layers have been used in this project:

\begin{itemize}

	\item \textbf{Dense layers}, which connects each of its nodes to each of the
		nodes of the previous layers.

	\item \textbf{Convolutional layers}, which process their input by applying
		a filter function to adjacent values. In the case of this project, the
		board is filtered by grouping its vertices in 3x3 squares. The aim of
		these layers is to detect patterns in the input, such as curves, edges
		or more complex shapes, so they are used a lot on neural networks
		processing images. They are used in this project because a configuration
		of the Go board is not that different from a two-dimensional image.

	\item \textbf{Max pooling layers}, which process their input in a similar
		way to convolutional layers, but reducing the size of the input by
		keeping the highest value in each of the groups they process. This
		reduction accentuates the patterns detected by convolutional layers and
		helps on the detection of bigger, more complex patterns.

	\item \textbf{Flatten layers}, which just change the shape of the input so
		that all the values are on one dimension.

\end{itemize}

Combinations of these layers have been used to define two neural networks.

First, a network using mainly dense layers as an example of a more general
purpose design of a network.

Then, a network with convolutional and max pooling layers to compare the
approach used on image processing to the more general one and studying its
utility on the analysis of the Go board.

These networks have been implemented on the DenseNeuralNetwork and
ConvNeuralNetwork classes, respectively.

The networks have been designed to process boards of size 9x9, which is the
introductory size to the game. It is the easiest both for the hardware to handle
and for the analysis of results while keeping able to support meaningful
matches.

Both networks have the same design for their input and output.

Their input is a three-dimensional matrix of size 9x9x2 with values either 0 or
1. It represents two views of the board, one with ones as the stones of a player
and the other with ones as the stones of the other player.

Their output is a vector with 82 elements of type float. Classification networks
typically use a vector of probabilities with one element for each class they are
trying to classify. Here the classes are the 81 positions of the 9x9 board and
the pass move, hence 82 total elements. Each element signifies the chance of
playing that move for the input board position, so the element with the highest
value represents the suggested move.

\subsubsection{Dense Neural Network Design}

\begin{listing}[h]
	\inputminted{text}{listings/denseModel.txt}
	\caption{Dense neural network model.}
	\label{code:denseModel}
\end{listing}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.7\textwidth]{img/models/denseModel.png}
		\caption{Dense neural network model.}
		\label{fig:denseNN}
	\end{center}
\end{figure}

This network first uses two dense layers with 81 nodes each. This number has
been selected so each node can have as input each of the vertices of the board.
A flatten layer acts then to make the output one-dimensional, and a final dense
layer provides the vector containing the likelihood of each possible move.

The design of this network is shown in \flist{code:denseModel} and
\fref{fig:denseNN} as provided by Keras' summary and plot\_model functions
respectively.

\subsubsection{Convolutional Neural Network Design}

\begin{listing}[h]
	\inputminted{text}{listings/convModel.txt}
	\caption{Convolutional neural network model.}
	\label{code:convModel}
\end{listing}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=0.7\textwidth]{img/models/convModel.png}
		\caption{Convolutional neural network model.}
		\label{fig:convNN}
	\end{center}
\end{figure}

This network uses two pairs of convolutional and max pooling layers with the aim
of being trained to recognize patterns on the board. A flatten layer acts then
to make the output one-dimensional, and a final dense layer provides the vector
containing the likelihood of each possible move.

The design of this network is shown in \flist{code:convModel} and
\fref{fig:convNN} as provided by Keras' summary and plot\_model functions
respectively.

\subsection{Training}

\begin{figure}[h]
	\begin{center}
		\includegraphics[width=\textwidth]{diagrams/trainingModule.png}
		\caption{Components of the SGF file parsing module.}
		\label{fig:trainingModule}
		Components not showing a capital C are not classes, as in they not
		follow the object-oriented paradigm and do not implement any classes,
		only functions.
	\end{center}
\end{figure}

Neural networks can be powerful machine learning algorithms, but they have to be
trained first so they can provide meaningful results. For a Go AI it makes sense
to have its algorithms trained on Go games. There exists a common text format to
store Go games: SGF. If the system is able to process SGF files, it can provide
the games stored on them to the neural networks for training. And so the need
for an SGF parser arises.

To parse SGF files a lexer and parser have been implemented using PLY.\@ The
result of the parsing is an AST (Annotated Syntax Tree) reflecting the contents
of the text input, each node with zero or more properties, and with the ability
to convert themselves and their corresponding subtree into a GameMove tree. This
is done for the root node, since from the SGF specification there are some
properties only usable in the root node, like those which specify general game
information and properties such as rank of players or komi.

Here follows an explanation of the role and motivation before each component of
the Training module to show how these previous concerns have been addressed and
solved. These components are shown in \fref{fig:trainingModule}.

\begin{itemize}

	\item \textbf{SGF}: Provides a high-level method to convert a path to a SGF
		file to a GameMove tree.

	\item \textbf{sgfyacc}: The implementation of a SGF parser using PLY. Takes
		the tokens generated by \textbf{sgflex} and creates an ASTNode tree from
		them.

	\item \textbf{sgflex}: The implementation of a SGF lexer using PLY.\@ Takes
		text input and generates the tokens of the SGF language from them.

	\item \textbf{ASTNode}: The AST resulting from the parsing of a SGF file.
		Has a method to convert it to a tree of GameMove and so obtain the
		contents of the SGF in the internal representation used by the project's
		systems.

	\item \textbf{Property}: The representation of a property of an ASTNode
		tree. Each property is made of a name and one or more values and this
		class helps handling this specific situation.

The training can be started with the executable \texttt{train.py}.

\end{itemize}

%\subsection{Modules}
%
%One module to store the state of the game and the game tree. One module to parse
%moves. One module to read and write SGF files. Modules are shown in
%\fref{fig:modules}.
%
%\begin{figure}[h]
%	\begin{center}
%		\includegraphics[width=\textwidth]{diagrams/modules.png}
%		\caption{Modules.}\label{fig:modules}
%	\end{center}
%\end{figure}