diff options
Diffstat (limited to 'doc/tex')
| -rw-r--r-- | doc/tex/appendixes.tex | 51 | ||||
| -rw-r--r-- | doc/tex/glossary.tex | 8 | ||||
| -rw-r--r-- | doc/tex/imago.tex | 11 | ||||
| -rw-r--r-- | doc/tex/planning.tex | 57 | ||||
| -rw-r--r-- | doc/tex/systemAnalysis.tex | 58 | ||||
| -rw-r--r-- | doc/tex/systemDesign.tex | 88 |
6 files changed, 177 insertions, 96 deletions
diff --git a/doc/tex/appendixes.tex b/doc/tex/appendixes.tex new file mode 100644 index 0000000..89c413c --- /dev/null +++ b/doc/tex/appendixes.tex @@ -0,0 +1,51 @@ +\section{Appendixes} + +Additional information is included here, after the main sections regarding the +project. + +\subsection{Budget} + +Here are tables regarding the costs of resources and development for the +project. + +\subsubsection{Work resources} + +The costs are calculated based on a programmer salary of 20€/hour. + +\begin{table}[h] + \makebox[\linewidth]{ + \begin{tabular}{l r r} + \toprule + \textbf{Task} & \textbf{Time (hours)} & \textbf{Cost (€)} \\ + \midrule + Game preliminary research & 15 & 300 \\ + \midrule + Game implementation & 55 & 1100 \\ + \midrule + Game unit testing & 50 & 1000 \\ + \midrule + Game system testing & 5 & 100 \\ + \midrule + \textbf{Total} & \textbf{125} & \textbf{2500} \\ + \bottomrule + \end{tabular} + } +\end{table} + +%TODO: Finish budgets + +\subsubsection{Material resources} + +\begin{table}[h] + \makebox[\linewidth]{ + \begin{tabular}{l r} + \toprule + \textbf{Resource} & \textbf{Cost (€)} \\ + \midrule + Development computer & 600 \\ + \bottomrule + \end{tabular} + } +\end{table} + +\subsubsection{Totals} diff --git a/doc/tex/glossary.tex b/doc/tex/glossary.tex index 8b43e94..b1cea02 100644 --- a/doc/tex/glossary.tex +++ b/doc/tex/glossary.tex @@ -1,15 +1,15 @@ \newglossaryentry{ko} { name=ko, - description={A rule which prevents plays that would repeat the previous - board position} + description={A rule forbidding plays that would repeat the previous board + position} } \newglossaryentry{superko} { name=superko, - description={An extension to the ko rule to prevent any previous board - position and not just the last one} + description={A modification to the ko rule forbidding plays that would + repeat any previous board position and not just the last one} } \newglossaryentry{komi} diff --git a/doc/tex/imago.tex b/doc/tex/imago.tex index 8067043..0447d70 100644 --- a/doc/tex/imago.tex +++ b/doc/tex/imago.tex @@ -151,8 +151,8 @@ inclusion of to use this template is included here. \clearpage -\input{tex/introduction.tex} -\clearpage +%\input{tex/introduction.tex} +%\clearpage \input{tex/planning.tex} \clearpage @@ -169,8 +169,11 @@ inclusion of to use this template is included here. %\input{tex/results.tex} %\clearpage -\input{tex/conclusions.tex} -\clearpage +%\input{tex/appendixes.tex} +%\clearpage + +%\input{tex/conclusions.tex} +%\clearpage \printglossaries \clearpage diff --git a/doc/tex/planning.tex b/doc/tex/planning.tex index 5d73ec3..17d413f 100644 --- a/doc/tex/planning.tex +++ b/doc/tex/planning.tex @@ -1,7 +1,7 @@ \section{Planning} -This section explains the aim of the project, its reach, the existing work it is -based on and an initial planning. +This section explains the aim of the project, its reach and the existing work it +is based on, and presents an initial planning. \subsection{Project Stages} @@ -123,20 +123,20 @@ presents a great resource for this project. The logo of the project is shown on \paragraph{GnuGo \cite{gnugo}} -A software capable of playing Go part of the GNU project. Although not a strong -engine anymore, it is interesting for historic reasons as the free software -engine for which the \acrshort{gtp} protocol was first defined. The logo of the +A software capable of playing Go and part of the GNU project. Although not a +strong engine anymore, it is interesting for historic reasons as the free +software engine for which the \acrfull{gtp} was first defined. The logo of the project is shown on \fref{fig:gnuGoLogo}. \subsubsection{Existing Standards} \paragraph{\acrshort{gtp} \cite{gtp}} -\acrshort{gtp} (\textit{\acrlong{gtp}}) is a text based protocol for -communication with computer Go programs. It is the protocol used by GNU Go and -the more modern and powerful KataGo. By supporting \acrshort{gtp} the engine -developed for this project can be used with existing GUIs and other programs, -making it easier to use it with the tools users are already familiar with. +The \acrfull{gtp} is a text based protocol for communication with computer Go +programs. It is the protocol used by GNU Go and the more modern and powerful +KataGo. By supporting \acrshort{gtp} the engine developed for this project can +be used with existing GUIs and other programs, making it easier to be used with +the tools target users are already familiar with. %TODO %\begin{listing}[h] @@ -147,23 +147,36 @@ making it easier to use it with the tools users are already familiar with. \paragraph{\acrshort{sgf} \cite{sgf}} -\acrshort{sgf} (\textit{\acrlong{sgf}}) is a text format widely used for storing -records of Go matches which allows for variants, comments and other metadata. It -was devised for Go but it supports other games with similar turn-based -structure. Many popular playing tools use it. By supporting \acrshort{sgf} vast -existing collections of games, such as those played on online Go servers, can be -used to train the decision algorithms based on neural networks. An example of a -\acrshort{sgf} file can be seen on \lref{lst:sgfExample}. +The \acrfull{sgf} is a text format widely used for storing records of Go matches +which allows for variants, comments and other metadata. It was devised for Go +but it supports other games with similar turn-based structure. Many popular +playing tools use it. By supporting \acrshort{sgf} vast existing collections of +games, such as those played on online Go servers, can be used to train the +decision algorithms based on neural networks. An example of a \acrshort{sgf} +file can be seen on \lref{lst:sgfExample}. The game state described in this file +is shown visually in \fref{fig:sgfExample}. \begin{listing}[h] \inputminted[breakafter=\]]{text}{listings/sgfExample.sgf} - \caption{\acrshort{sgf} example. Describes a \gls{tsumego} (Go problem) setup and two - variants, one commented as "Correct" and other commented as "Incorrect".} - \label{lst:sgfExample} + \caption{\acrshort{sgf} example. Describes a \gls{tsumego} (Go problem) + setup and two variants, one commented as "Correct" and other commented as + "Incorrect". + }\label{lst:sgfExample} \end{listing} \begin{figure}[h] \begin{center} + \includegraphics[width=0.5\textwidth]{img/sgfExample.png} + \caption{Screenshot of Sabaki showing the \gls{tsumego} described in the + \acrshort{sgf} example from \lref{lst:sgfExample}. Note that Sabaki + marks the two continuations described in the \acrshort{sgf} file with + two transparent grey dots. + }\label{fig:sgfExample} + \end{center} +\end{figure} + +\begin{figure}[h] + \begin{center} \includegraphics[width=0.5\textwidth]{img/sabaki.jpg} \caption{Sabaki screenshot. https://sabaki.yichuanshen.de/img/screenshot.png @@ -217,8 +230,8 @@ choice is Python \cite{python}, for various reasons: Both the game and the engine will offer a text interface. For the game this allows for quick human testing. For the engine it is mandated by the protocol, since \acrshort{gtp} is a text based protocol for programs using text -interfaces. Independent programs compatible with this interface can be used as a -GUI. +interfaces. Independent programs compatible with this interface will be able to +be used in conjunction with this engine, for example to serve as a GUI. There is also the need of an interface with \acrshort{sgf} files so existing games can be processed by the trainer. diff --git a/doc/tex/systemAnalysis.tex b/doc/tex/systemAnalysis.tex index ba5fbf1..5263d1f 100644 --- a/doc/tex/systemAnalysis.tex +++ b/doc/tex/systemAnalysis.tex @@ -7,7 +7,7 @@ These are the main goals the final product must reach. \begin{enumerate} \item The implementation, analysis and comparison of different decision - algorithms for genarating moves. This is the main goal and the following + algorithms for generating moves. This is the main goal and the following ones are derived from the need of reaching it. \item A library for representing the game of Go. It can be used for the @@ -278,13 +278,14 @@ then be imported by the engine and be used to generate moves. \subsubsection{Interface Between Subsystems} -The Training System depends on the NeuralNetwork interface of the Engine System -and uses it to train and store the neural network models. +The Training System depends on the \texttt{NeuralNetwork} interface of the +Engine System and uses it to train and store the neural network models. -Both the Engine and Training systems depend on the GameMove class of the Game -System. The Engine System uses it to store the state of a game and provide it -to the decision algorithms. The Training System uses it to create the internal -representation of a game resulting from the processing of an \acrshort{sgf} file. +Both the Engine and Training systems depend on the \texttt{GameMove} class of +the Game System. The Engine System uses it to store the state of a game and +provide it to the decision algorithms. The Training System uses it to create the +internal representation of a game resulting from the processing of an +\acrshort{sgf} file. \subsection{Class Analysis} @@ -415,7 +416,7 @@ The classes resulting from the analysis phase are shown in \tabitem{\textbf{visits}: How many times the node has been visited.} \\ \tabitem{\textbf{score}: The number of explorations of the node resulting in victory.} \\ - \tabitem{\textbf{move}: A GameMove for accessing game state and logic.} \\ + \tabitem{\textbf{move}: A \texttt{GameMove} for accessing game state and logic.} \\ \tabitem{\textbf{parent}: This node's parent in the tree.} \\ \tabitem{\textbf{children}: The nodes following from this node in the tree.} \\ @@ -430,7 +431,7 @@ The classes resulting from the analysis phase are shown in Selects the most promising node which still has some unexplored children.} \\ \tabitem{\textbf{expansion()}: Monte Carlo Tree Search expansion step. Picks - an unexplored vertex from the node and adds it as a new MCTSNode.} \\ + an unexplored vertex from the node and adds it as a new \texttt{MCTSNode}.} \\ \tabitem{\textbf{expansionForCoords()}: Performs an expansion for the given coordinates. This represents forcing a move on the algorithm.} \\ \tabitem{\textbf{simulation()}: Play random matches to accumulate reward @@ -445,17 +446,17 @@ The classes resulting from the analysis phase are shown in \textbf{Keras} \\ \midrule \textbf{Description} \\ - Implements the DecisionAlgorithm interface to give access to a neural - network. \\ + Implements the \texttt{DecisionAlgorithm} interface to give access to a + neural network. \\ \midrule \textbf{Responsibilities} \\ \tabitem{Analyzing game states and generating moves.} \\ \midrule \textbf{Proposed attributes} \\ - \tabitem{\textbf{currentMove}: A GameMove for accessing game state and + \tabitem{\textbf{currentMove}: A \texttt{GameMove} for accessing game state and logic.} \\ - \tabitem{\textbf{neuralNetwork}: A NeuralNetwork instance for generating - moves.} \\ + \tabitem{\textbf{neuralNetwork}: A \texttt{NeuralNetwork} instance for + generating moves.} \\ \midrule \textbf{Proposed methods} \\ \decisionAlgorithmMethods @@ -477,10 +478,10 @@ The classes resulting from the analysis phase are shown in \tabitem{Loading a model file to use an existing trained neural network.} \\ \midrule \textbf{Proposed attributes} \\ - \tabitem{\textbf{currentMove}: A GameMove for accessing game state and + \tabitem{\textbf{currentMove}: A \texttt{GameMove} for accessing game state and logic.} \\ - \tabitem{\textbf{neuralNetwork}: A NeuralNetwork instance for generating - moves.} \\ + \tabitem{\textbf{neuralNetwork}: A \texttt{NeuralNetwork} instance for + generating moves.} \\ \midrule \textbf{Proposed methods} \\ \tabitem{\textbf{pickMove()}: Uses the current internal model to pick a move @@ -653,8 +654,8 @@ The classes resulting from the analysis phase are shown in %TODO: Explain why this is empty \midrule \textbf{Proposed methods} \\ - \tabitem{\textbf{loadGameTree()}: Reads a file and generates a GameMove tree - from its contents.} \\ + \tabitem{\textbf{loadGameTree()}: Reads a file and generates a + \texttt{GameMove} tree from its contents.} \\ \bottomrule \end{tabular} @@ -665,12 +666,13 @@ The classes resulting from the analysis phase are shown in \textbf{Parser} \\ \midrule \textbf{Description} \\ - Reads \acrshort{sgf} files and converts them to a tree of GameMove from the Game - System. \\ + Reads \acrshort{sgf} files and converts them to a tree of \texttt{GameMove} + from the Game System. \\ \midrule \textbf{Responsibilities} \\ \tabitem{Read \acrshort{sgf} files.} \\ - \tabitem{Convert the content of the \acrshort{sgf} files to a tree of GameMove.} \\ + \tabitem{Convert the content of the \acrshort{sgf} files to a tree of + \texttt{GameMove}.} \\ \midrule \textbf{Proposed attributes} \\ %TODO: Explain why this is empty @@ -690,7 +692,7 @@ The classes resulting from the analysis phase are shown in Makes up the tree resulting from the parsing of an \acrshort{sgf} file.\\ \midrule \textbf{Responsibilities} \\ - \tabitem{Obtain a GameMove tree from itself and its children.} \\ + \tabitem{Obtain a \texttt{GameMove} tree from itself and its children.} \\ \midrule \textbf{Proposed attributes} \\ \tabitem{\textbf{children}: The nodes following from itself.} \\ @@ -698,8 +700,8 @@ The classes resulting from the analysis phase are shown in \\ \midrule \textbf{Proposed methods} \\ - \tabitem{\textbf{toGameTree()}: Returns a GameMove tree corresponding to the - tree following from this node.} \\ + \tabitem{\textbf{toGameTree()}: Returns a \texttt{GameMove} tree + corresponding to the tree following from this node.} \\ \bottomrule \end{tabular} @@ -905,7 +907,7 @@ The script used to run the tests is shown on \lref{lst:test} and its output on % Maybe put an example report here? \begin{listing}[h] \inputminted{bash}{listings/test.sh} - \caption{Dense neural network model.} + \caption{Script to run the tests.} \label{lst:test} \end{listing} @@ -920,3 +922,7 @@ The script used to run the tests is shown on \lref{lst:test} and its output on \subsubsection{System Testing} \subsubsection{Usability Testing} + +% Game playing + +% Using the engine with an existing GUI diff --git a/doc/tex/systemDesign.tex b/doc/tex/systemDesign.tex index f0762e8..7a5db7b 100644 --- a/doc/tex/systemDesign.tex +++ b/doc/tex/systemDesign.tex @@ -34,20 +34,20 @@ 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 +\texttt{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. +\texttt{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. +these operations are implemented as the \texttt{GameBoard} class. A game can be started by the executable \texttt{go.py}. @@ -74,24 +74,26 @@ three components, each with a separate responsibility: 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 \texttt{GameEngine} contains the logic of the commands available + from the IO component. It uses a \texttt{GameState} to keep a record of + the game and uses a \texttt{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. + \item The \texttt{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). +Two implementations of \texttt{DecisionAlgorithm} have been made: one for the +Monte Carlo Tree Search algorithm (on the \texttt{MCTS} class) and the other for +neural networks (on the \texttt{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 \texttt{Keras} class also makes use of the \texttt{NeuralNetwork} class, +which offers functions for creating, training, saving and using neural network +models. The designs of the network are implemented in the subclasses +\texttt{DenseNeuralNetwork} and \texttt{ConvNeuralNetwork} as examples of dense +and convolutional networks, respectively. The engine can be started with the executable \texttt{imagocli.py}. @@ -128,9 +130,9 @@ The exploration of the tree has 4 steps: 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. +The implementation of the algorithm will use the existing \texttt{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} @@ -182,8 +184,8 @@ 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. +These networks have been implemented on the \texttt{DenseNeuralNetwork} and \\ +\texttt{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 @@ -273,13 +275,14 @@ store Go games: \acrshort{sgf}. If the system is able to process \acrshort{sgf} the games stored on them to the neural networks for training. And so the need for an \acrshort{sgf} parser arises. -To parse \acrshort{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 \acrshort{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 \gls{komi}. +To parse \acrshort{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 +\texttt{GameMove} tree. This is done for the root node, since from the +\acrshort{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 \gls{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 @@ -288,23 +291,24 @@ solved. These components are shown in \fref{fig:trainingModule}. \begin{itemize} \item \textbf{\acrshort{sgf}}: Provides a high-level method to convert a path to a \acrshort{sgf} - file to a GameMove tree. + file to a \texttt{GameMove} tree. \item \textbf{sgfyacc}: The implementation of a \acrshort{sgf} parser using PLY. Takes - the tokens generated by \textbf{sgflex} and creates an ASTNode tree from - them. + the tokens generated by \textbf{sgflex} and creates an \texttt{ASTNode} + tree from them. - \item \textbf{sgflex}: The implementation of a \acrshort{sgf} lexer using PLY.\@ Takes - text input and generates the tokens of the \acrshort{sgf} language from them. + \item \textbf{sgflex}: The implementation of a \acrshort{sgf} lexer using + PLY.\@ Takes text input and generates the tokens of the \acrshort{sgf} + language from them. - \item \textbf{ASTNode}: The AST resulting from the parsing of a \acrshort{sgf} file. - Has a method to convert it to a tree of GameMove and so obtain the - contents of the \acrshort{sgf} in the internal representation used by the project's - systems. + \item \textbf{ASTNode}: The AST resulting from the parsing of a + \acrshort{sgf} file. Has a method to convert it to a tree of + \texttt{GameMove} and so obtain the contents of the \acrshort{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. + \item \textbf{Property}: The representation of a property of an + \texttt{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}. @@ -322,3 +326,7 @@ The training can be started with the executable \texttt{train.py}. % \caption{Modules.}\label{fig:modules} % \end{center} %\end{figure} + +%\subsection{Technical Testing Plan Specification} + +%TODO |