diff options
Diffstat (limited to 'doc/tex/systemDesign.tex')
| -rw-r--r-- | doc/tex/systemDesign.tex | 327 |
1 files changed, 278 insertions, 49 deletions
diff --git a/doc/tex/systemDesign.tex b/doc/tex/systemDesign.tex index ccd1c48..80a2ccb 100644 --- a/doc/tex/systemDesign.tex +++ b/doc/tex/systemDesign.tex @@ -1,95 +1,324 @@ \section{System Design} -\subsection{Class diagram} +\subsection{Class Diagram} -The full class diagram is shown in \fref{fig:fullClasses} +The full class diagram is shown in \fref{fig:fullClasses}. \begin{figure}[h] \begin{center} - \includegraphics[width=\textwidth]{diagrams/fullClasses.png} - \caption{Full class diagram.} - \label{fig:fullClasses} + \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} -% From here +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 +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 IO component is the one called from other applications and offers - the text interface. It reads and processes input and calls corresponding - commands from the core of the engine. - \item The EngineBoard component stores the state of the match, recording - information such as the history of boards positions and whose turn goes - next. The engine core uses it for these state-storing purposes. - \item The EngineAI 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. + + \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=\textwidth]{diagrams/engineModule.png} - \caption{Design of the GTP engine.}\label{fig:engine} + \includegraphics[width=0.7\textwidth]{img/models/denseModel.png} + \caption{Dense neural network model.} + \label{fig:denseNN} \end{center} \end{figure} -\subsection{Modules} +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. -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}. +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=\textwidth]{diagrams/modules.png} - \caption{Modules.}\label{fig:modules} + \includegraphics[width=0.7\textwidth]{img/models/convModel.png} + \caption{Convolutional neural network model.} + \label{fig:convNN} \end{center} \end{figure} -\subsection{Representation of a match} +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. -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{} allows 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 state of the board at any given move must -also be stored so liberties, captures count and legality of moves can be -addressed, so it is represented with its own class, which holds a reference both -to the game tree and the current move. Moves depend on a representation of the -game board to have access to its current layout and count of captured stones. -These classes and their relationships can be seen in -\fref{fig:gameRepresentation}. +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=0.7\textwidth]{diagrams/gameRepresentation.png} - \caption{A game is represented as a tree of moves.}\label{fig:gameRepresentation} + \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} -\subsection{SGF} +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 GameTree. This is -done for the root node, since from the SGF specification there are some +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. These components are -shown in \fref{fig:sgfModule}. +information and properties such as rank of players or komi. -\begin{figure}[h] - \begin{center} - \includegraphics[width=\textwidth]{diagrams/sgfModule.png} - \caption{Components of the SGF file parsing module.}\label{fig:sgfModule} - \end{center} -\end{figure} +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} |