diff options
51 files changed, 3485 insertions, 632 deletions
@@ -1,8 +1,10 @@ *.sgf # images +img/ *.png *.jpg +*.svg *.xcf # doc diff --git a/doc/Makefile b/doc/Makefile index 284000e..472de8e 100644 --- a/doc/Makefile +++ b/doc/Makefile @@ -3,13 +3,13 @@ docName = imago outputFolder = out -texFiles = tex/$(docName).tex tex/introduction.tex tex/planification.tex tex/systemAnalysis.tex tex/systemDesign.tex tex/implementation.tex tex/results.tex tex/conclusions.tex tex/biber.bib +texFiles = tex/$(docName).tex tex/introduction.tex tex/planning.tex tex/systemAnalysis.tex tex/systemDesign.tex tex/implementation.tex tex/results.tex tex/appendixes.tex tex/conclusions.tex tex/glossary.tex tex/license.tex tex/biber.bib -diagramImgs = diagrams/planificationWorkPlanEngine.png diagrams/planificationWorkPlanGame.png diagrams/useCases.png diagrams/analysisClasses.png diagrams/useCase_generateAMove.png diagrams/useCase_useAsBackend.png diagrams/useCase_playAMatch.png diagrams/interfaces.png diagrams/gameModule.png diagrams/engineModule.png diagrams/trainingModule.png diagrams/modules.png diagrams/fullClasses.png +diagramImgs = diagrams/planningWorkPlanEngine.png diagrams/planningWorkPlanGame.png diagrams/useCases.png diagrams/analysisClasses.png diagrams/useCase_generateAMove.png diagrams/useCase_useAsBackend.png diagrams/useCase_trainTheEngine.png diagrams/useCase_playAMatch.png diagrams/interfaces.png diagrams/gameModule.png diagrams/engineModule.png diagrams/trainingModule.png diagrams/modules.png diagrams/fullClasses.png imgs = img/imago.jpg img/models/denseModel.png img/models/convModel.png -listings = listings/denseModel.txt listings/convModel.txt listings/denseTraining.txt listings/convTraining.txt listings/trainCommand.sh +listings = listings/denseModel.txt listings/convModel.txt listings/denseTraining.txt listings/convTraining.txt listings/trainCommand.sh listings/testOutput.txt all: $(docName).pdf @@ -17,6 +17,7 @@ $(docName).pdf: $(texFiles) $(diagramImgs) $(imgs) $(listings) Makefile [ -d $(outputFolder) ] || mkdir $(outputFolder) xelatex -shell-escape -output-directory $(outputFolder) tex/$(docName).tex biber $(outputFolder)/$(docName) + makeglossaries -d $(outputFolder) $(docName) xelatex -shell-escape -output-directory $(outputFolder) tex/$(docName).tex mv $(outputFolder)/$(docName).pdf . diff --git a/doc/diagrams/planningWorkPlanEngine.puml b/doc/diagrams/planningWorkPlanEngine.puml new file mode 100644 index 0000000..9caad40 --- /dev/null +++ b/doc/diagrams/planningWorkPlanEngine.puml @@ -0,0 +1,46 @@ +@startgantt + +!include skinparams.puml +!include skinparamsGantt.puml + +printscale weekly +Saturday are closed +Sunday are closed + +Project starts 2021-01-11 + +-- Preliminary research -- +[Previous works research] as [PWR] lasts 1 week +[Algorithms research] as [AR] lasts 2 weeks + +-- Engine Implementation -- +[Engine modelling] as [EM] lasts 1 week +[Engine implementation] as [EI] lasts 4 weeks + +-- Algorithms Implementations -- +[Monte Carlo implementation] as [MCI] lasts 4 weeks +[Neural networks research] as [NNR] lasts 2 weeks +[Neural networks implementation] as [NNI] lasts 3 weeks + +-- Testing -- +[Engine unit testing] as [EUT] lasts 4 weeks +[System testing] as [ST] lasts 1 week + +-- Analysis -- +[Algorithms comparison] as [AC] lasts 2 weeks + +[PWR] -> [AR] +[AR] -> [EM] + +[EM] -> [MCI] +[EM] -> [EI] +[EM] -> [EUT] + +[MCI] -> [NNR] +[NNR] -> [NNI] + +[NNI] -> [ST] + +[ST] -> [AC] + +@endgantt diff --git a/doc/diagrams/planningWorkPlanGame.puml b/doc/diagrams/planningWorkPlanGame.puml new file mode 100644 index 0000000..ffaf72c --- /dev/null +++ b/doc/diagrams/planningWorkPlanGame.puml @@ -0,0 +1,30 @@ +@startgantt + +!include skinparams.puml +!include skinparamsGantt.puml + +printscale weekly zoom 2 +Saturday are closed +Sunday are closed + +Project starts 2020-11-02 + +-- Preliminary research -- +[Previous works research] as [PWR] lasts 1 week + +-- Game Implementation -- +[Domain modelling] as [DM] lasts 1 week +[Domain implementation] as [DI] lasts 6 weeks + +-- Testing -- +[Unit testing] as [UT] lasts 6 weeks +[System testing] as [ST] lasts 1 week + +[PWR] -> [DM] + +[DM] -> [DI] +[DM] -> [UT] + +[DI] -> [ST] + +@endgantt diff --git a/doc/diagrams/useCase_trainTheEngine.puml b/doc/diagrams/useCase_trainTheEngine.puml new file mode 100644 index 0000000..5ae5e1e --- /dev/null +++ b/doc/diagrams/useCase_trainTheEngine.puml @@ -0,0 +1,24 @@ +@startuml + +!include skinparams.puml + +actor "Human user" as user + +boundary "Training CLI" as cli +control "Read files" as read +control "Create initial model" as initial +entity "Neural network" as nn +control "Train network" as train +boundary "Model file" as model + +user -> cli : provide input files +cli -> read +read -> initial +initial -> nn +loop until final epoch reached + train <- nn : expose to training + train -> nn : update +end +nn -> model : save neural network model + +@enduml diff --git a/doc/diagrams/useCases.puml b/doc/diagrams/useCases.puml index 8d4aa71..42cb471 100644 --- a/doc/diagrams/useCases.puml +++ b/doc/diagrams/useCases.puml @@ -9,10 +9,12 @@ actor "Human User" as user usecase "Play a match" as play usecase "Use as backend for machine player" as backend usecase "Generate a move" as genMove +usecase "Train the engine" as train player --> play gui --> backend user --> genMove gui --> genMove +user --> train @enduml diff --git a/doc/listings/goInterface/01-start.txt b/doc/listings/goInterface/01-start.txt new file mode 100644 index 0000000..0aa8dfd --- /dev/null +++ b/doc/listings/goInterface/01-start.txt @@ -0,0 +1,11 @@ + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): diff --git a/doc/listings/goInterface/02-firstMove.txt b/doc/listings/goInterface/02-firstMove.txt new file mode 100644 index 0000000..3fb46d6 --- /dev/null +++ b/doc/listings/goInterface/02-firstMove.txt @@ -0,0 +1,23 @@ + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): e6 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (W): diff --git a/doc/listings/goInterface/03-fullGame.txt b/doc/listings/goInterface/03-fullGame.txt new file mode 100644 index 0000000..4e01b75 --- /dev/null +++ b/doc/listings/goInterface/03-fullGame.txt @@ -0,0 +1,96 @@ + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): e6 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (W): e4 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · · · · · · · · +4 · · · · W · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): g5 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · · · · · B · · +4 · · · · W · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (W): c5 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · W · · · B · · +4 · · · · W · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): g3 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · W · · · B · · +4 · · · · W · · · · +3 · · · · · · B · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (W): g7 + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · W · · +6 · · · · B · · · · +5 · · W · · · B · · +4 · · · · W · · · · +3 · · · · · · B · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (B): pass + + A B C D E F G H J +9 · · · · · · · · · +8 · · · · · · · · · +7 · · · · · · W · · +6 · · · · B · · · · +5 · · W · · · B · · +4 · · · · W · · · · +3 · · · · · · B · · +2 · · · · · · · · · +1 · · · · · · · · · +Move (W): pass +Both players passed: end of the game. diff --git a/doc/listings/goInterface/04-ko.txt b/doc/listings/goInterface/04-ko.txt new file mode 100644 index 0000000..f1ef2dd --- /dev/null +++ b/doc/listings/goInterface/04-ko.txt @@ -0,0 +1,75 @@ + A B C D E F G H J +9 B · B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (W): b9 + + A B C D E F G H J +9 · W B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (B): a9 +Invalid Move. Illegal by ko rule. + + A B C D E F G H J +9 · W B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (B): z9 +Invalid move syntax. Example of move: A1 + + A B C D E F G H J +9 · W B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (B): a0 +Invalid move syntax. Example of move: A1 + + A B C D E F G H J +9 · W B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (B): a10 +Invalid move syntax. Example of move: A1 + + A B C D E F G H J +9 · W B · · · · · · +8 W B · · · · · · · +7 · · · · · · · · · +6 · · · · · · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · W +Move (B): diff --git a/doc/listings/imagocliInterface/01-start.txt b/doc/listings/imagocliInterface/01-start.txt new file mode 100644 index 0000000..b1c72f0 --- /dev/null +++ b/doc/listings/imagocliInterface/01-start.txt @@ -0,0 +1,40 @@ +name += Imago + +version += 0.0.0 + +protocol_version += 2 + +known_command nonexistentcommand += false + +known_command name += true + +nonexistentcommand +? unknown command + +play b e6 += + +genmove w += C8 + +showboard += + A B C D E F G H J +9 · · · · · · · · · +8 · · W · · · · · · +7 · · · · · · · · · +6 · · · · B · · · · +5 · · · · · · · · · +4 · · · · · · · · · +3 · · · · · · · · · +2 · · · · · · · · · +1 · · · · · · · · · + +quit += + diff --git a/doc/listings/test.sh b/doc/listings/test.sh new file mode 100644 index 0000000..b929249 --- /dev/null +++ b/doc/listings/test.sh @@ -0,0 +1,2 @@ +#!/bin/sh +coverage run --source=imago -m unittest discover tests/ && coverage report -m --skip-empty diff --git a/doc/listings/testOutput.txt b/doc/listings/testOutput.txt new file mode 100644 index 0000000..e6fb2d6 --- /dev/null +++ b/doc/listings/testOutput.txt @@ -0,0 +1,24 @@ +Name Stmts Miss Cover Missing +------------------------------------------------------------------------ +imago/data/enums.py 17 0 100% +imago/engine/core.py 39 7 82% 43, 50-52, 60-62 +imago/engine/createDecisionAlgorithm.py 11 5 55% 13-21 +imago/engine/decisionAlgorithm.py 9 4 56% 6, 10, 14, 18 +imago/engine/imagoIO.py 107 9 92% 76-77, 189-196, 208 +imago/engine/keras/convNeuralNetwork.py 11 0 100% +imago/engine/keras/denseNeuralNetwork.py 11 0 100% +imago/engine/keras/keras.py 30 3 90% 48-49, 53 +imago/engine/keras/neuralNetwork.py 137 1 99% 141 +imago/engine/monteCarlo.py 110 7 94% 128, 181-188, 194-195 +imago/engine/parseHelpers.py 48 0 100% +imago/gameLogic/gameBoard.py 205 7 97% 116, 180, 205, 272, 284, 306, 312 +imago/gameLogic/gameMove.py 95 9 91% 21, 27, 34, 138-142, 146 +imago/gameLogic/gameState.py 41 0 100% +imago/scripts/monteCarloSimulation.py 17 17 0% 3-25 +imago/sgfParser/astNode.py 70 7 90% 10, 14, 22, 45, 59, 67, 157 +imago/sgfParser/parsetab.py 18 0 100% +imago/sgfParser/sgf.py 6 0 100% +imago/sgfParser/sgflex.py 31 9 71% 37-38, 42-43, 47-48, 64-65, 71 +imago/sgfParser/sgfyacc.py 41 14 66% 35-36, 51, 59-68, 71 +------------------------------------------------------------------------ +TOTAL 1054 99 91% diff --git a/doc/tex/appendixes.tex b/doc/tex/appendixes.tex new file mode 100644 index 0000000..b4533d6 --- /dev/null +++ b/doc/tex/appendixes.tex @@ -0,0 +1,399 @@ +\section{Appendixes} + +Additional information is included here, after the main sections regarding the +project. + +\subsection{User manual} + +This manual explains to the end user how to use the software. + +\subsubsection{The game: the \texttt{go.py} interface} + +\texttt{go.py} is a simple executable to interact with the Game system of this +project. It makes use of no artificial intelligence whatsoever, its aim just +being allowing for human play. It can be executed in a shell as: + +{ + \centering + \begin{minipage}{0.4\textwidth} + \texttt{python go.py} + \end{minipage} + \par +} + +or by any other means of executing a python file with access to its input and +output streams. The executable receives no arguments and has no options. + +When executed the user is presented with the following interface: + +{ + \centering + \begin{minipage}{0.4\textwidth} + \inputminted{text}{listings/goInterface/01-start.txt} + \end{minipage} + \par +} + +The state of the board (empty for now) is shown and the user is prompted for a +move. The color to make the move is marked between brackets: \texttt{B} for +Black, \texttt{W} for White. + +A move can now be provided for the Black player, such as \texttt{e6}. + +{ + \centering + \begin{minipage}{0.4\textwidth} + \inputminted{text}{listings/goInterface/02-firstMove.txt} + \end{minipage} + \par +} + +The interface shows again the state of the board. The game can continue until +the move ``pass'' is provided for both players. + +{ + \centering + \begin{minipage}{\textwidth} + \begin{multicols}{2} + \inputminted[fontsize=\small]{text}{listings/goInterface/03-fullGame.txt} + \end{multicols} + \end{minipage} + \par +} + +The game will also show captured stones and notify illegal moves, such as wrong +input or because of the \gls{ko} rule. + +{ + \centering + \begin{minipage}{\textwidth} + \begin{multicols}{2} + \inputminted[fontsize=\small]{text}{listings/goInterface/04-ko.txt} + \end{multicols} + \end{minipage} + \par +} + +\subsubsection{The engine: the \texttt{imagocli.py} interface} + +\texttt{imagocli.py} is a text interface which follows the \acrfull{gtp} +specification. It can be executed in a shell as: + +{ + \centering + \begin{minipage}{0.4\textwidth} + \texttt{python imagocli.py} + \end{minipage} + \par +} + +If desired, the \acrshort{ai} to be run can be passed as an argument to the +\texttt{-e} option, but it is not necessary. The available arguments are: + +\begin{itemize} + + \item \texttt{montecarlo}: The Monte Carlo Tree Search algorithm is used. + \item \texttt{keras}: The default Keras neural network, the convolutional + one, is used. + \item \texttt{dense}: The dense neural network is used. + \item \texttt{conv}: The convolutional neural network is used. + +\end{itemize} + +So, if for example the dense neural network is the one to use, the program would +be executed as: + +{ + \centering + \begin{minipage}{0.4\textwidth} + \texttt{python imagocli.py -e dense} + \end{minipage} + \par +} + +If no arguments are provided the default configuration is to use the Monte Carlo +Tree Search algorithm. + +When executed interactively and before any input is provided it just waits for +input with no prompt whatsoever. This is in compliance with the \acrshort{gtp} +specification. + +These are the commands that the program knows and a short description of what +each does: + +\begin{itemize} + + \item \texttt{list\_commands}: Shows a list of the commands the engine + knows. + \item \texttt{known\_command}: Receives an argument and tells whether it is + a known command or not. + \item \texttt{name}: Shows the name of the program. + \item \texttt{version}: Shows the version of the program. + \item \texttt{protocol\_version}: Shows the implemented \acrshort{gtp} + version number. + \item \texttt{boardsize}: Changes the size of the board. Results in an + arbitrary internal state unless \texttt{clear\_board} is called after + it. + \item \texttt{clear\_board}: The board is cleared of stones, the record of + captured stones resets to zero and the move history resets to empty. + \item \texttt{komi}: Sets the value for \gls{komi}. + \item \texttt{fixed\_handicap}: The given number of handicap stones are + placed following the protocol specification, which follows traditional + placement of handicap. + \item \texttt{place\_free\_handicap}: The given number of handicap stones + are placed following the AI criteria. + \item \texttt{set\_free\_handicap}: The given number of handicap stones are + placed on the requested vertices. + \item \texttt{play}: A stone of the requested color is played at the + requested vertex. + \item \texttt{genmove}: A stone of the requested color is played following + the AI criteria. The played move is printed. + \item \texttt{undo}: The state is restored to before the last move, which is + removed from the move history. + \item \texttt{showboard}: Prints a text representation of the board state. + +\end{itemize} + +Here is an example of a session. + +{ + \centering + \begin{minipage}{\textwidth} + \begin{multicols}{2} + \inputminted[fontsize=\small]{text}{listings/imagocliInterface/01-start.txt} + \end{multicols} + \end{minipage} + \par +} + +Note how responses from the program begin with an equals symbol and a space but +with a question mark replacing the space to mark errors, like when providing an +unknown command (exemplified here with \texttt{nonexistentcommand} in line 16). + +This session consists first of some information asked to the engine: its name, +its version and the version of \acrshort{gtp} it implements. Then exemplifies +how to check if a command is implemented and an error answer. Then, the main +commands to interact with the game and the \acrshort{ai} are executed: +\texttt{play}, to provide an initial explicit move, and \texttt{genmove}, to +obtain an \acrshort{ai}-generated move. Finally, a representation of the board +state after these two moves is obtained with \texttt{showboard} and the engine +is closed with \texttt{quit}. + +\subsubsection{Example of \acrshort{gui} use: configuring Sabaki} + +Since the main aim of implementing a \acrshort{gtp} interface is having it be +compatible with existing tools, an explanation of how to use it in conjunction +with one such established tool is provided. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/01-initialScreen.jpg} + \caption{Sabaki after being started. + }\label{fig:sabakiStart} + \end{center} +\end{figure} + +Sabaki \cite{sabaki} is a Go board software compatible with \acrshort{gtp} +engines. It can be downloaded from \texttt{https://sabaki.yichuanshen.de/}. When +started, it shows a screen such as the one in \fref{fig:sabakiStart}. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/02-examplePlaying.jpg} + \caption{Playing some moves on the default board. + }\label{fig:sabakiExampleMoves} + \end{center} +\end{figure} + +This initial screen contains a 19x19 board ready to be played on by local human +players. The stones can be placed by clicking on the desired vertices of the +board and, as would be expected, the interface swaps between players after each +move. An example of the screen after some initial moves can be seen on +\fref{fig:sabakiExampleMoves}. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/03-enginesSidebar.jpg} + \caption{Opened the engines sidebar (on the left). + }\label{fig:sabakiEnginesSidebar} + \end{center} +\end{figure} + +To set Sabaki to work with \texttt{imagocli.py} first open the engines sidebar +by clicking on ``Engines'', then ``Show Engines Sidebar''. The window should now +look like the one shown on \fref{fig:sabakiEnginesSidebar}, with the engines +sidebar open at the left but with nothing shown on it yet. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/04-engineManagement.jpg} + \caption{The engine management window. + }\label{fig:sabakiEngineManagement} + \end{center} +\end{figure} + +Click on the symbol on the top left of the engines sidebar, the one with a +triangle inside of a circle (the play button), and on ``Manage Engines...'' on +the opened floating dialog. The engine management window will open, as shown on +\fref{fig:sabakiEngineManagement}. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/05-configuredEngine.jpg} + \caption{\texttt{imagocli.py} configured as engine. + }\label{fig:sabakiConfiguredEngine} + \end{center} +\end{figure} + +Engines are listed on the big box at the center of the window, but if none has +yet been configured nothing will be shown there. Click ``Add'' to create the +first engine entry. Give it a name by writing on the first line of the newly +created entry, then write the path to the \texttt{imagocli.py} executable +besides the folder symbol, at the text box prompting for the path to the engine. +Alternatively, click on the folder symbol and a file explorer will open where it +will be possible to graphically select the executable file. Arguments and +initial commands to provide to the engine can be configured here, but none of +them will be needed for the default configuration of \program{}. An example of +the configured engine is shown on \fref{fig:sabakiConfiguredEngine}. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/06-configuringAMatch.jpg} + \caption{Configuring a match against the engine. + }\label{fig:sabakiConfiguringAMatch} + \end{center} +\end{figure} + +The engine management window can now be closed by clicking on ``Close'' at its +bottom right. Click again on the play button, the one on the top left of the +engines sidebar, and select the newly created engine entry. The engine will now +be started. By default, Sabaki will provide it the \texttt{name}, +\texttt{version}, \texttt{protocol\_version} and \texttt{list\_commands} +commands, and the text interface will be shown on the engines sidebar. To play +against the engine, click on ``File'', then ``New'', or just use the keyboard +shortcut Ctrl+N. A window will be shown where a new game can be configured. The +most important settings are making the engine be one (or both) of the players +and setting the board size to 9x9, since this is where the engine plays best. +For example, to set the engine as the white player, click on the arrow next to +the white player's name and select the engine, represented by the name given to +it before, on the floating menu. The size of the board can be set on the ``Board +Size'' setting. Other options allow to set a name for the other player, a name +for the match, the \gls{komi} and the handicap stones, if any. When ready, click +``Ok'' on the bottom right of the window. An example configuration can be seen +on \fref{fig:sabakiConfiguringAMatch}. If the engine doesn't respond to the +moves, which should be clear since its status is shown on the engines sidebar, +try adding it to the match by clicking on ``Attach Engine'' and then on its name +on the new match window, instead of directly on its name. This creates a new +entry for the engine on the engines sidebar. Multiple instances of the same or +different engines can be running at the same time; to remove one, just right +click on its name and click on ``Detach'' on the floating menu. + +\begin{figure}[p] + \begin{center} + \includegraphics[width=0.8\textwidth]{img/sabakiManual/07-playingAgainstImago.png} + \caption{Playing some moves against \program{}. + }\label{fig:sabakiAgainstTheEngine} + \end{center} +\end{figure} + +The engine can now be played against: when black (the human) makes a move, it +will respond as white. Some initial moves against it can be seen on +\fref{fig:sabakiAgainstTheEngine}. Note the interaction between Sabaki and the +\acrshort{gtp} interface on the engines sidebar. + +\clearpage + +\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 & 95 & 1900 \\ + \midrule + Game unit testing & 90 & 1800 \\ + \midrule + Game system testing & 15 & 300 \\ + \midrule + Engine preliminary research & 15 & 300 \\ + \midrule + Engine implementation & 75 & 1500 \\ + \midrule + Algorithms implementations & 135 & 2700 \\ + \midrule + Engine testing & 75 & 1500 \\ + \midrule + Results analysis & 30 & 600 \\ + \midrule + \textbf{Total} & \textbf{545} & \textbf{10900} \\ + \bottomrule + \end{tabular} + } +\end{table} + +\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} + +\begin{table}[H] + \makebox[\linewidth]{ + \begin{tabular}{l r} + \toprule + \textbf{Category} & \textbf{Cost (€)} \\ + \midrule + Work & 10900 \\ + \midrule + Materials & 600 \\ + \midrule + \textbf{Total} & \textbf{11500} \\ + \bottomrule + \end{tabular} + } +\end{table} + +\subsubsection{Budget for the client} + +\begin{table}[H] + \makebox[\linewidth]{ + \begin{tabular}{l r} + \toprule + \textbf{Task} & \textbf{Cost (€)} \\ + \midrule + Game system development & 2200 \\ + \midrule + Engine development & 4500 \\ + \midrule + Testing & 3600 \\ + \midrule + Result analysis & 600 \\ + \midrule + Materials & 600 \\ + \midrule + \textbf{Total} & \textbf{11500} \\ + \bottomrule + \end{tabular} + } +\end{table} diff --git a/doc/tex/biber.bib b/doc/tex/biber.bib index d0a714e..a058686 100644 --- a/doc/tex/biber.bib +++ b/doc/tex/biber.bib @@ -7,27 +7,35 @@ } @online{gtp, - author = {Gunnar Farnebäck}, - title = {GTP --- Go Text Protocol}, - date = {2002}, - urldate = {2021}, - url = {https://www.lysator.liu.se/~gunnar/gtp} + author = {Gunnar Farnebäck}, + title = {GTP --- Go Text Protocol}, + date = {2002}, + urldate = {2021}, + url = {https://www.lysator.liu.se/~gunnar/gtp} } @online{sgf, - author = {Arno Hollosi}, - title = {SGF File Format FF[4]}, - date = {2021}, - urldate = {2022}, - url = {https://www.red-bean.com/sgf} + author = {Arno Hollosi}, + title = {SGF File Format FF[4]}, + date = {2021}, + urldate = {2022}, + url = {https://www.red-bean.com/sgf} +} + +@online{alphaGo, + author = {DeepMind}, + title = {AlphaGo}, + date = {2022}, + urldate = {2022}, + url = {https://www.deepmind.com/research/highlighted-research/alphago} } @online{katago, - author = {David J Wu ("lightvector")}, - title = {KataGo}, - date = {2021}, - urldate = {2021}, - url = {https://github.com/lightvector/KataGo} + author = {David J Wu ("lightvector")}, + title = {KataGo}, + date = {2021}, + urldate = {2021}, + url = {https://github.com/lightvector/KataGo} } @online{gnugo, @@ -39,17 +47,23 @@ } @online{sabaki, - author = {Yichuan Shen}, - title = {Sabaki --- An elegant Go board and SGF editor for a more civilized age.}, - date = {2019}, - urldate = {2021}, - url = {https://sabaki.yichuanshen.de} + author = {Yichuan Shen}, + title = {Sabaki --- An elegant Go board and SGF editor for a more civilized age.}, + date = {2019}, + urldate = {2021}, + url = {https://sabaki.yichuanshen.de} +} + +@online{tensorflow, + title = {TensorFlow}, + urldate = {2023}, + url = {https://www.tensorflow.org/} } @online{keras, - title = {Keras: the Python deep learning API}, - urldate = {2022}, - url = {https://keras.io} + title = {Keras: the Python deep learning API}, + urldate = {2022}, + url = {https://keras.io} } @online{sl_go, @@ -68,89 +82,109 @@ } @online{python_unittest, - title = {unittest --- Unit testing framework}, - urldate = {2021}, - url = {https://docs.python.org/3/library/unittest.html} + title = {unittest --- Unit testing framework}, + urldate = {2021}, + url = {https://docs.python.org/3/library/unittest.html} } @online{python_coverage, - title = {Coverage.py}, - urldate = {2021}, - url = {https://coverage.readthedocs.io} + title = {Coverage.py}, + urldate = {2021}, + url = {https://coverage.readthedocs.io} } @online{matplotlib_heatmaps, - title = {Creating annotated heatmaps — Matplotlib 3.5.2 documentation}, - urldate = {2022}, - url = {https://matplotlib.org/stable/gallery/images_contours_and_fields/image_annotated_heatmap.html} + title = {Creating annotated heatmaps — Matplotlib 3.5.2 documentation}, + urldate = {2022}, + url = {https://matplotlib.org/stable/gallery/images_contours_and_fields/image_annotated_heatmap.html} } @online{python, - title = {Welcome to Python.org}, - urldate = {2022}, - url = {https://www.python.org} + title = {Welcome to Python.org}, + urldate = {2022}, + url = {https://www.python.org} } @online{numpy, - title = {NumPy}, - urldate = {2022}, - url = {https://numpy.org} + title = {NumPy}, + urldate = {2022}, + url = {https://numpy.org} } @online{matplotlib, - title = {Matplotlib — Visualization with Python}, - urldate = {2022}, - url = {https://matplotlib.org} + title = {Matplotlib — Visualization with Python}, + urldate = {2022}, + url = {https://matplotlib.org} } @online{ply, - title = {PLY (Python Lex-Yacc)}, - urldate = {2022}, - url = {http://www.dabeaz.com/ply} + title = {PLY (Python Lex-Yacc)}, + urldate = {2022}, + url = {http://www.dabeaz.com/ply} +} + +@online{git, + title = {Git}, + urldate = {2023}, + url = {https://git-scm.com/} } @online{vim, - title = {welcome home : vim online}, - urldate = {2022}, - url = {https://www.vim.org} + title = {welcome home : vim online}, + urldate = {2022}, + url = {https://www.vim.org} } @online{neovim, - title = {Home - Neovim}, - urldate = {2022}, - url = {http://neovim.io} + title = {Home - Neovim}, + urldate = {2022}, + url = {http://neovim.io} } @online{latex, - title = {LaTeX - A document preparation system}, - urldate = {2022}, - url = {https://www.latex-project.org} + title = {LaTeX - A document preparation system}, + urldate = {2022}, + url = {https://www.latex-project.org} } @online{puml, - title = {Open-source tool that uses simple textual descriptions to draw beautiful UML diagrams.}, - urldate = {2022}, - url = {https://plantuml.com} + title = {Open-source tool that uses simple textual descriptions to draw beautiful UML diagrams.}, + urldate = {2022}, + url = {https://plantuml.com} } @online{sl_sword, - title = {9x9 Tengen Openings at Sensei's Library}, - urldate = {2022}, - url = {https://senseis.xmp.net/?9x9TengenOpenings} + title = {9x9 Tengen Openings at Sensei's Library}, + urldate = {2022}, + url = {https://senseis.xmp.net/?9x9TengenOpenings} +} + +@book{choLifeAndDeath, + author = {Cho Chikun}, + title = {Cho Chikun Life and Death Dictionary}, + year = {1996}, + editor = {Nihon Ki-in (the Japanese Go Association)} } @online{ogsLifeAndDeath, - author = {sunspark}, - title = {Cho Chikun's Encyclopedia of Life and Death - Elementary: 1 / 900}, - date = {2016}, - urldate = {2022}, - url = {https://online-go.com/puzzle/2824} + author = {sunspark}, + title = {Cho Chikun's Encyclopedia of Life and Death - Elementary: 1 / 900}, + date = {2016}, + urldate = {2022}, + url = {https://online-go.com/puzzle/2824} } @online{fsf_free, - author = {Free Software Foundation}, - title = {What is Free Software? - GNU Project - Free Software Foundation}, - date = {2022}, - urldate = {2022}, - url = {https://www.gnu.org/philosophy/free-sw.html} + author = {Free Software Foundation}, + title = {What is Free Software? - GNU Project - Free Software Foundation}, + date = {2022}, + urldate = {2022}, + url = {https://www.gnu.org/philosophy/free-sw.html} +} + +@online{arch, + title = {Arch Linux}, + date = {2023}, + urldate = {2023}, + url = {https://archlinux.org/} } diff --git a/doc/tex/conclusions.tex b/doc/tex/conclusions.tex index ebbf7fd..a6bc434 100644 --- a/doc/tex/conclusions.tex +++ b/doc/tex/conclusions.tex @@ -6,22 +6,22 @@ could be done in the future to improve the system are discussed here. \subsection{Problems with the Implementation of the Game} While Go has a simple set of rules, they lead to many borderline cases which -must be specifically addressed. For example, the ko rule obliges to check the -previous board positions after each move so no boards are repeated. +must be specifically addressed. As an example, the \gls{ko} rule obliges to +check the previous board positions after each move so no boards are repeated. These problems have been solved by designing the tree of moves of a match so each move stores the full board layout after it has been played. This of course increases the memory needed to run the application, but has been chosen over the alternative of having to recreate the board parsing the tree backwards for each -move to check if ko is occurring, if a move makes a capture and which stones +move to check if \gls{ko} is occurring, if a move makes a capture and which stones have already been captured, etc. It is the old problem of memory versus processing, which in this case has been answered with memory. Which one would be the best solution would require a deep analysis out of the scope of the project. \subsection{Problems with the Monte Carlo Tree Search Algorithm} -The implementation Monte Carlo Tree Search algorithm was not precise by itself -when asked for moves. This could be attributed to various factors: +The implemented Monte Carlo Tree Search algorithm was not precise by itself when +asked for moves. This could be attributed to various factors: \begin{itemize} @@ -31,7 +31,7 @@ when asked for moves. This could be attributed to various factors: are not precise on analyzing the result since the moves in them are played at random. - \item The configuration used, 5 explorations with 10 simulations each for + \item The configuration used, 5 explorations with 10 simulations each per cycle, does not allow for many good moves to be found. \end{itemize} @@ -48,7 +48,7 @@ on this section. \subsubsection{Finding the correct design} -When approaching neural networks design with a basic understanding of their +When approaching neural networks design with just basic understanding of their inner workings it is easy to get lost in all the different factors that can be tuned. The number and variant of layers, their number of nodes, their activation function, the learning rate; they can all be tweaked and doing so in the favour @@ -84,7 +84,7 @@ for evaluation. \subsubsection{Mistakes on Networks' Play Patterns} One notable mistake made by the networks, specially the convolutional network, -was passing to much. Passing is considered just another move, so the networks +was passing too much. Passing is considered just another move, so the networks have no grasp that they should not pass until there are no more valuable moves to be made. A new design problem could be to create a specific passing policy. @@ -93,7 +93,8 @@ make reasonable decisions at the start of the game, with some interesting variations. But as the game progresses their moves make less sense. This could be because they have seen many examples of starting moves but complications at the middle and end game are much more diverse and the networks had not been -trained on similar situations. +trained on similar situations. These stages of the game are probably where a +strong Monte Carlo Tree Search algorithm would help the most. \subsection{Viable Extensions} @@ -109,8 +110,8 @@ simpler. The logical next step would be to join both: the network could select the best moves to be made, and the tree search algorithm could explore them to select the best and grow its explored tree in meaningful directions. -This is also what was done by AlphaGo. By seeing the results obtained in this -project it makes sense they made that decision. +This is also what was done by AlphaGo. Going by the results obtained in this +project it makes sense they went with that design. \subsubsection{Train the Engine by Itself} diff --git a/doc/tex/glossary.tex b/doc/tex/glossary.tex new file mode 100644 index 0000000..25c0488 --- /dev/null +++ b/doc/tex/glossary.tex @@ -0,0 +1,54 @@ +\newglossaryentry{ko} +{ + name=ko, + description={A rule forbidding plays that would repeat the previous board + position} +} + +\newglossaryentry{superko} +{ + name=superko, + description={A modification to the ko rule forbidding plays that would + repeat any previous board position and not just the last one} +} + +\newglossaryentry{komi} +{ + name=komi, + description={Points given to the white player to compensate for playing + second} +} + +\newglossaryentry{suicide} +{ + name=suicide move, + description={A typically prohibited move which doesn't capture any stone + and results in the player's group having zero liberties} +} + +\newglossaryentry{tsumego} +{ + name=tsumego, + description={A Go problem} +} + +\newglossaryentry{criticalPoint} +{ + name=critical point, + description={A position on the board which makes a group either live or die + depending on who plays there first} +} + +\newglossaryentry{eye} +{ + name=eye, + description={An area surrounded by a group. If a group has at least two eyes + it can never be captured, since the opponent would have to play in all the + eyes simultaneously to capture it} +} + +\newacronym{ai}{AI}{Artificial Intelligence} +\newacronym{ast}{AST}{Annotated Syntax Tree} +\newacronym{gtp}{GTP}{Go Text Protocol} +\newacronym{gui}{GUI}{Graphical User Interface} +\newacronym{sgf}{SGF}{Smart Game Format} diff --git a/doc/tex/imago.tex b/doc/tex/imago.tex index cc77673..ca72c7a 100644 --- a/doc/tex/imago.tex +++ b/doc/tex/imago.tex @@ -8,6 +8,7 @@ \usepackage{enumitem} \usepackage[indent=20pt]{parskip} % Space between paragraphs \usepackage{indentfirst} % Indent first paragraph of sections +\usepackage{multicol} % Multiple columns \geometry{left=3cm,top=2cm,bottom=2cm,right=3cm} @@ -28,10 +29,14 @@ \usepackage{minted} % Code importing and formatting \setminted{linenos, breaklines} +\usepackage[acronym, toc]{glossaries} +\makeglossaries +\input{tex/glossary.tex} + \newcommand{\program}{Imago} \newcommand{\fref}[1]{Fig.~\ref{#1}} -\newcommand{\flist}[1]{Listing~\ref{#1}} +\newcommand{\lref}[1]{Listing~\ref{#1}} %\newcommand{\uurl}[1]{\underline{\url{#1}}} \newcommand{\tabitem}{~~\llap{\textbullet}~~} @@ -46,12 +51,13 @@ \includegraphics[width=0.3\textwidth]{img/logoEII.png} \end{center}~\\[10pt] \program\\ - \large An AI player of the game of Go + \large An AI player of the game of Go\\ + \large (Juego Go basado en inteligencia artificial)\\ } \author{Íñigo Gutiérrez Fernández} -\date{} +\date{Oviedo, June 2023} \maketitle @@ -66,12 +72,20 @@ \clearpage \begin{abstract} - The game of Go presents a complex problem for machine learning by virtue of - containing a very wide and deep decision tree. This project has tried to - tackle the problem by using different decision algorithms and also provides - a full implementation of the game. These tools could be used by players and - developers as a foundation for other machine learning projects or to simply - keep studying the game. + With a history of more than 3000 years, the game of Go presents a complex + problem for machine learning by virtue of containing a very wide and deep + decision tree. Finally, in 2016, computer scientists from DeepMind were able + to create an artificial intelligence capable of defeating profesional + players of the game with a combination of old and new strategies. This + project has tried to follow their steps and tackle the problem by using + different decision algorithms, such as Monte Carlo Tree Search and neural + networks, and also provides a full implementation of the game, playable on + its own or available as a library for the engine developed for this project + and potentially others to come. The resulting strength of the developed + algorithms is no match to that of a profesional player, but it shows the + possibilities achievable just with the limited resources employed on this + project. These tools could be used by players and developers as a foundation + for other machine learning projects or to simply keep studying the game. \end{abstract} \clearpage @@ -81,7 +95,7 @@ To Vicente García Díaz, for helping me learning to program on my first year at the school and directing me in this project on my last. -To José Manuel Redondo López\cite{plantillaRedondo}, for making an extensive +To José Manuel Redondo López \cite{plantillaRedondo}, for making an extensive template on which the structure of this documentation is extensively based. To all the people who have provided their time, support, ideas and company, all @@ -111,12 +125,12 @@ author's Degree's Final Project. This document is based on a template by José Manuel Redondo López, associate professor of the University of Oviedo. The copyright notice he asks for -inclusion to use this template is included here. +inclusion of to use this template is included here. \begin{displayquote} Copyright (C) 2019 \textbf{JOSÉ MANUEL REDONDO - LÓPEZ}.\cite{plantillaRedondo} + LÓPEZ}. \cite{plantillaRedondo} \textit{Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 @@ -150,7 +164,7 @@ inclusion to use this template is included here. \input{tex/introduction.tex} \clearpage -\input{tex/planification.tex} +\input{tex/planning.tex} \clearpage \input{tex/systemAnalysis.tex} @@ -165,14 +179,32 @@ inclusion to use this template is included here. \input{tex/results.tex} \clearpage +\input{tex/appendixes.tex} +\clearpage + \input{tex/conclusions.tex} \clearpage +% Glossary and acronyms + +\printglossary[title=Glossary of Go Terminology] +\makeatletter +\def\@currentlabelname{\@glotype@main@title} +\label{glossary} +\makeatother + +\printglossary[type=\acronymtype] +\makeatletter +\def\@currentlabelname{\@glotype@acronymtype@title} +\label{acronyms} +\makeatother + +\clearpage + % References (bibliography) +\printbibliography[heading=bibintoc]{} +\clearpage -\setcounter{secnumdepth}{0} -\section{References} -\printbibliography[type=article,title={Cited articles},heading=subbibintoc]{} -\printbibliography[type=online,title={Online resources},heading=subbibintoc]{} +\input{tex/license.tex} \end{document} diff --git a/doc/tex/implementation.tex b/doc/tex/implementation.tex index d46e805..d3cd0c3 100644 --- a/doc/tex/implementation.tex +++ b/doc/tex/implementation.tex @@ -1,8 +1,11 @@ \section{Implementation} +This section is about the specific tools and process used to implement +\program{}. + \subsection{Development Hardware} -The development and evaluation machine is a Satellite L50-C laptop. Its +The development and evaluation machine is a Toshiba Satellite L50-C laptop. Its specifications are shown as a list for readability. \begin{itemize} @@ -15,71 +18,71 @@ specifications are shown as a list for readability. \subsection{Development Software} The tools selected for the development of the project and the documentation are -listed and explained on this section. All the tools used are either -free\cite{fsf_free} or open source software. The development machine runs 64 -bits Arch Linux as its operating system. +listed and explained on this section. All the tools used are either free +\cite{fsf_free} or open source software. The development machine runs 64 bits +Arch Linux \cite{arch} as its operating system. \subsubsection{Language} -The programming language of choice is Python\cite{python}. The rationale behind +The programming language of choice is Python \cite{python}. The rationale behind this decision has been stated on Section \ref{sec:programmingLanguage}. It also allows easy use of the Keras library for implementing neural networks. -Various python libraries have been used to easy the development process or +Various Python libraries have been used to easy the development process or assist in the analysis of results. These are: -\paragraph{Keras/Tensorflow\cite{keras}} +\paragraph{Keras/TensorFlow} -Tensorflow is a platform for machine learning which provides a diverse range of -tools, one of which is a python library for machine learning. +TensorFlow \cite{tensorflow} is a platform for machine learning which provides a +diverse range of tools, one of which is a Python library for machine learning. -Keras is a high-level API for Tensorflow allowing for the easy definition of -neural networks. It permits easily testing and comparing different network -layouts. +Keras \cite{keras} is a high-level API for TensorFlow allowing for the easy +definition of neural networks. It permits easily testing and comparing different +network layouts. -\paragraph{NumPy\cite{numpy}} +\paragraph{NumPy} -A scientific package for python providing a lot of mathematical tools. The most -interesting for this project are its capabilities to create and transform -matrices. +A scientific package for Python providing a lot of mathematical tools +\cite{numpy}. The most interesting for this project are its capabilities to +create and transform matrices. -\paragraph{Matplotlib\cite{matplotlib}} +\paragraph{Matplotlib} -A python library for creating graphs and other visualizations. It is used to -show the likelihood of moves the neural networks of the project create from a -board configuration. +A Python library for creating graphs and other visualizations \cite{matplotlib}. +It is used to show the likelihood of moves the neural networks of the project +create from a board configuration. -\paragraph{PLY\cite{ply}} +\paragraph{PLY} -A tool for generating compilers in Python. It is an implementation of the lex -and yacc utilities, allowing to create lexers and parsers. It is used in the -project to create the SGF parser which transform SGF files to internal -representations of Go matches. +A tool for generating compilers in Python \cite{ply}. It is an implementation of +the lex and yacc utilities, allowing to create lexers and parsers. It is used in +the project to create the \acrshort{sgf} parser which transform \acrshort{sgf} +files to internal representations of Go matches. \paragraph{Other utility libraries} -These are some utility libraries commonly used for frequent programming tasks: +These are some utility libraries commonly used for frequent programming tasks. \begin{itemize} - \item \textbf{sys}: to stop the execution of the program or access system info such + \item \textbf{sys}: To stop the execution of the program or access system info such as primitives maximum values. - \item \textbf{os}: to interact with files. - \item \textbf{re}: to check strings with regular expressions. - \item \textbf{random}: to get random values, for example to obtain a random - item from a list. - \item \textbf{copy}: to obtain deep copies of multidimensional arrays. + \item \textbf{os}: To interact with files. + \item \textbf{re}: To check strings with regular expressions. + \item \textbf{random}: For randomness, for example to obtain a random item + from a list. + \item \textbf{copy}: To obtain deep copies of multidimensional arrays. \end{itemize} \subsubsection{Development Tools} -\paragraph{Neovim\cite{neovim}} +\paragraph{Neovim} -A text editor based on Vim\cite{vim}, providing its same functionality with -useful additions and defaults for modern computers and terminal emulators. With -some extensions and configuration it can become a powerful development -environment with a very fluid usage experience. That, and the fact that the -developer considers Vim's modal editing the best writing experience possible on -a computer, have made Neovim the editor of choice. +A text editor based on Vim \cite{vim}, providing its same functionality with +useful additions and defaults for modern computers and terminal emulators +\cite{neovim}. With some extensions and configuration it becomes a powerful +development environment with a very fluid usage experience. That, and the +preference of the developer of Vim's modal editing as the best writing +experience possible on a computer, have made Neovim the editor of choice. %TODO: Write about neovim extensions %\begin{itemize} @@ -88,21 +91,31 @@ a computer, have made Neovim the editor of choice. % %\end{itemize} +\paragraph{Git} + +A version control tool widely used in software development environments +\cite{git}. If the reader is not already familiar with it, it suffices to say it +allows to store and manage snapshots of a project, navigate through them and +diverge into different development branches, among other useful features. + +The source code of this document and of the rest of the project is publicly +available at \url{https://git.taamas.xyz/Taamas/imago}. + \subsubsection{Documentation Tools} -\paragraph{\LaTeX\cite{latex}} +\paragraph{\LaTeX} -A typesetting system widely used in the investigation field, among others. It -allows for documentation like this text to be written in plain text and then -compiled to PDF or other formats, which permits keeping the source files of the -documentation small and organized plus other benefits of plain text such as -being able to use version control. +A typesetting system widely used in the investigation field, among others +\cite{latex}. It allows for documentation like this text to be written in plain +text and then compiled to PDF or other formats, which permits keeping the source +files of the documentation small and organized plus other benefits of plain text +such as being able to be used in conjunction with version control tools. -\paragraph{PlantUML\cite{puml}} +\paragraph{PlantUML} -A program which creates diagrams from plain text files. PlantUML supports syntax -for many different sorts of diagrams, mainly but not only UML. It has been used -to generate the diagrams used in this text. +A program which creates diagrams from plain text files \cite{puml}. PlantUML +supports syntax for many different sorts of diagrams, mainly but not only UML. +It has been used to generate the diagrams used in this text. \paragraph{Make} @@ -113,9 +126,280 @@ updates them if they already exist but their source files are newer than them. It has been used to generate this text from \LaTeX{} and PlantUML source files. The contents of the Makefile with which this document has been compiled are -shown in \flist{code:makefile}. +shown in \lref{code:makefile}. -\begin{listing}[h] +\begin{listing}[p] \inputminted{make}{Makefile} \caption{Documentation Makefile}\label{code:makefile} \end{listing} + +\subsection{Execution of the Testing Plan} + +Part of the implementation process is to execute the testing plan. The results +of this execution are provided in this section. + +\subsubsection{Execution of the Unitary Testing} + +The script used to run the tests is shown on \lref{lst:test} and its output on +\lref{lst:testOutput}. + +\begin{listing}[p] + \inputminted{bash}{listings/test.sh} + \caption{Script to run the tests and list the result.} + \label{lst:test} +\end{listing} + +\begin{listing}[p] + \inputminted[fontsize=\footnotesize]{text}{listings/testOutput.txt} + \caption{Unitary testing output.} + \label{lst:testOutput} +\end{listing} + +\subsubsection{Execution of the Integration Testing} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.2\linewidth}p{0.3\linewidth}p{0.4\linewidth}} + \toprule + \multicolumn{3}{c}{\textbf{Engine and Game modules}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} & \textbf{Results} \\ + \midrule + The GTP interface of the engine is used to play a match & + The module handles the game and can show its state. & + The engine runs correctly and is capable of keeping track of and showing the + state of a match, which shows it is making good use of the Game module. \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.2\linewidth}p{0.3\linewidth}p{0.4\linewidth}} + \toprule + \multicolumn{3}{c}{\textbf{Training and Engine module}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} & \textbf{Results} \\ + \midrule + The training process is started & + The training uses the network defined on the Engine module. & + The training output shows the network in training follows the design defined + on the Engine module. \\ + \bottomrule +\end{tabular} + +\subsubsection{Execution of the System Testing} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.2\linewidth}p{0.3\linewidth}p{0.4\linewidth}} + \toprule + \multicolumn{3}{c}{\textbf{Game interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} & \textbf{Results} \\ + \midrule + Play a game of Go with no engine & + The game can be played until the end. & + The interface continues asking for moves until both players pass + consecutively, which ends the game and the execution. \\ + \midrule + Provide a wrong move & + The interface shows it is wrong and the game continues without a change of + state. & + As expected, the interface shows a message signaling that the move is wrong + and showing an example of a move. \\ + \midrule + Close the game & + The interface closes. & + A message is shown signaling that the game is ending and the engine closes. + \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.2\linewidth}p{0.3\linewidth}p{0.4\linewidth}} + \toprule + \multicolumn{3}{c}{\textbf{Engine interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} & \textbf{Results} \\ + \midrule + Ask for the available commands & + The interface outputs the available commands. & + The list of available commands is printed one per line. \\ + \midrule + Provide a move & + The state of the engine updates with the new move. & + No output is given, but after providing the \texttt{showboard} command it is + shown that the move has been registered. \\ + \midrule + Ask for a move & + The engine suggests a move without changing the state of the current game. & + After the necessary time for generating the move, it is printed. The + \texttt{showboard} is then used to check the state of the game has not + changed. \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.2\linewidth}p{0.3\linewidth}p{0.4\linewidth}} + \toprule + \multicolumn{3}{c}{\textbf{Training interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} & \textbf{Results} \\ + \midrule + Provide some games to train on & + A neural network model is created. & + First, all the training files used are printed, and then, as expected, the + training process commences. A model is created or updated in the + \texttt{models} folder. \\ + \midrule + Start the training without providing games & + An error message is shown and the execution terminated. & + As expected, a message is shown asking for SGF files to be provided as + arguments and the execution is terminated.\\ + \bottomrule +\end{tabular} + +\subsubsection{Usability Testing} + +Two human users were asked to interact with the interfaces of \program{} and +presented with a questionary. + +The profile of the first user is of someone who has played some Go matches and +knows the fundamentals of the game but is a beginner, and who has little +experience with computers outside of their usage as office tools and internet +browsers. Here are their answers. + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against a human}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes. \\ + \midrule + How hard was the interface of the game to understand? & + It was easy and intuitive because you just entered the command to start and + then you only had to tell it where you wanted to play the stones. It felt + easy to me.\\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against the engine}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes. \\ + \midrule + How hard was the interface of the game to understand? & + It was easy to understand because it just was enering the commands and the + application did what it had to do, but it was more difficult than the + previous one because I'm not used to do these things with commands. It is + less intuitive than the previous one regarding playing against the machine + because you don't see each move as you write it, having to ask it to show + them instead.\\ + \midrule + How strong did you find the engine? & + It was not so aggresive as playing against a human who knows the game. It + doesn't play to harm its opponent.\\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against the interface through a + third-party}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes. \\ + \midrule + Did you find any problems when setting up the engine? & + No, it was well explained step by step, although the images could be better + lined up with the text. Anyway, the explanations were clear and easy to + follow.\\ + \midrule + Do you think this tool has value for studying Go? & + Yes.\\ + \bottomrule +\end{tabular} + +The profile of the second user is of someone who has experience with computers +and works as a software developer, but who has just the bare minimum knowledge +of the game of Go. Here are their answers. + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against a human}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes, I was able to. \\ + \midrule + How hard was the interface of the game to understand? & + I think six out of ten. Some people won't understand what a command is and + without a visual interface they could feel confused about it.\\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against the engine}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes, I was. \\ + \midrule + How hard was the interface of the game to understand? & + I think seven out of ten. I was expecting to follow some steps so I could + execute it at the same time I was reading the manual, but in the end the + most practical thing was read everything before execute commands.\\ + \midrule + How strong did you find the engine? & + It followed good paths to win the game, I didn't feel random moves during + the game by its side.\\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Playing against the interface through a + third-party}} \\ + \midrule + \textbf{Question} & \textbf{Answer} \\ + \midrule + Were you able to start the interface? & + Yes, I was. \\ + \midrule + Did you find any problems when setting up the engine? & + No, I didn't.\\ + \midrule + Do you think this tool has value for studying Go? & + I think it is a good tool for a group of players, so they can practise and + even train the AI if they want to.\\ + \bottomrule +\end{tabular} + +The results of these usability tests were useful mostly to update the manual and +make it easier to understand and follow and also to address some problems with +the interfaces that raised up during the testing. diff --git a/doc/tex/introduction.tex b/doc/tex/introduction.tex index fe5c205..c50d700 100644 --- a/doc/tex/introduction.tex +++ b/doc/tex/introduction.tex @@ -12,11 +12,74 @@ game at heart, Go has nonetheless been interpreted as a stylized representation of fighting a war, settling a frontier, cornering a market, thrashing out an argument, or even of fortune-telling and prophecy. Go has always been one of the - most played games in the world.\cite{sl_go} + most played games in the world. \cite{sl_go} \end{displayquote} As old and deep as Go is it has recently lived a revolution by the appearance of artificial intelligences with superhuman strength. While not expecting to achieve what a full team of developers and computer scientists at Google did, -this project aims to evaluate how an engine able to play the game of Go could be +this project aims to analyze how an engine able to play the game of Go could be created, implement such an engine and evaluate the results of the whole process. + +\subsection{Driving Needs} + +As one of the deepest and most studied games in the world, Go presents a very +interesting problem for artificial intelligence. Implementing not only the +game's simple but subtle rules, but a system capable of playing it with a +satisfying level of skill, is a task worth of pursuing as an exercise on +software design, algorithmics and \acrfull{ai} research. + +On the practical level, this project can be a foundation for the development of +different Go analysis algorithms by providing an existing engine to house them, +which can be of interest to Go players and software scientists alike. + +\subsection{Reach} + +Presented here are the ideal targets of the project. + +\begin{itemize} + \item An implementation of the game of Go, that is, a system for holding the + moves and variants of a match (a tree of moves) and the logic for the + game's rules. + \item An engine capable of analyzing board positions and generating strong + moves via various decision algorithms. + \item An interface compatible with existing \acrshort{gui}s. + \item A way for processing existing records of games, which are usually + recorded in the \acrfull{sgf}. +\end{itemize} + +\subsection{Rules of Go} + +Some understanding of the basics of the game is necessary to process this +document. Luckily for the reader, the rules of Go are pretty simple. If the +reader prefers, there is an interactive tutorial at +\texttt{https://online-go.com/learn-to-play-go/} going over the fundamentals and +introducing basic strategy for managing the stones which is already useful and +needed for the first games. Either way, the rules are sumarized as follows: + +\begin{itemize} + +\item There are two players. One plays as black, the other as white. Black plays + first. + +\item The player with the biggest score when the game ends wins. The score + consists of surrounded territory and captured enemy stones. Surrounded + territory is defined as the areas of empty space connected orthogonally + only to stones of one color. Each empty space on a surrounded area and each + captured enemy stone score one point. + +\item As their turn, a player can either place a stone of their color in an + empty space of the board or pass. The game ends when both players pass + consecutively. + +\item Stones of the same color orthogonally adjacent to one another are + considered connected. When one group of connected stones has no more + orthogonally adjacent empty spaces it is considered as captured and its + stones are removed from the board. + +\item Additionally, to prevent endlessly repeating plays, it is forbidden to + make a move which resets the board to the previous position. This is called + the \Gls{ko} rule, is of strategic relevance outside the scope of a basic + introduction to the game, and doesn't always come up. + +\end{itemize} diff --git a/doc/tex/license.tex b/doc/tex/license.tex new file mode 100644 index 0000000..d0e8c3a --- /dev/null +++ b/doc/tex/license.tex @@ -0,0 +1,535 @@ +\begin{center} + \section{GNU Free Documentation License} +\end{center} + + \begin{center} + + Version 1.3, 3 November 2008 + + + Copyright \copyright{} 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc. + + \bigskip + + \texttt{<https://fsf.org/>} + + \bigskip + + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. +\end{center} + + +\begin{center} +{\bf\large Preamble} +\end{center} + +The purpose of this License is to make a manual, textbook, or other +functional and useful document ``free'' in the sense of freedom: to +assure everyone the effective freedom to copy and redistribute it, +with or without modifying it, either commercially or noncommercially. +Secondarily, this License preserves for the author and publisher a way +to get credit for their work, while not being considered responsible +for modifications made by others. + +This License is a kind of ``copyleft'', which means that derivative +works of the document must themselves be free in the same sense. It +complements the GNU General Public License, which is a copyleft +license designed for free software. + +We have designed this License in order to use it for manuals for free +software, because free software needs free documentation: a free +program should come with manuals providing the same freedoms that the +software does. But this License is not limited to software manuals; +it can be used for any textual work, regardless of subject matter or +whether it is published as a printed book. We recommend this License +principally for works whose purpose is instruction or reference. + + +\begin{center} +{\Large\textbf{1. APPLICABILITY AND DEFINITIONS}} +\end{center} + +This License applies to any manual or other work, in any medium, that +contains a notice placed by the copyright holder saying it can be +distributed under the terms of this License. Such a notice grants a +world-wide, royalty-free license, unlimited in duration, to use that +work under the conditions stated herein. The ``\textbf{Document}'', below, +refers to any such manual or work. Any member of the public is a +licensee, and is addressed as ``\textbf{you}''. You accept the license if you +copy, modify or distribute the work in a way requiring permission +under copyright law. + +A ``\textbf{Modified Version}'' of the Document means any work containing the +Document or a portion of it, either copied verbatim, or with +modifications and/or translated into another language. + +A ``\textbf{Secondary Section}'' is a named appendix or a front-matter section of +the Document that deals exclusively with the relationship of the +publishers or authors of the Document to the Document's overall subject +(or to related matters) and contains nothing that could fall directly +within that overall subject. (Thus, if the Document is in part a +textbook of mathematics, a Secondary Section may not explain any +mathematics.) The relationship could be a matter of historical +connection with the subject or with related matters, or of legal, +commercial, philosophical, ethical or political position regarding +them. + +The ``\textbf{Invariant Sections}'' are certain Secondary Sections whose titles +are designated, as being those of Invariant Sections, in the notice +that says that the Document is released under this License. If a +section does not fit the above definition of Secondary then it is not +allowed to be designated as Invariant. The Document may contain zero +Invariant Sections. If the Document does not identify any Invariant +Sections then there are none. + +The ``\textbf{Cover Texts}'' are certain short passages of text that are listed, +as Front-Cover Texts or Back-Cover Texts, in the notice that says that +the Document is released under this License. A Front-Cover Text may +be at most 5 words, and a Back-Cover Text may be at most 25 words. + +A ``\textbf{Transparent}'' copy of the Document means a machine-readable copy, +represented in a format whose specification is available to the +general public, that is suitable for revising the document +straightforwardly with generic text editors or (for images composed of +pixels) generic paint programs or (for drawings) some widely available +drawing editor, and that is suitable for input to text formatters or +for automatic translation to a variety of formats suitable for input +to text formatters. A copy made in an otherwise Transparent file +format whose markup, or absence of markup, has been arranged to thwart +or discourage subsequent modification by readers is not Transparent. +An image format is not Transparent if used for any substantial amount +of text. A copy that is not ``Transparent'' is called ``\textbf{Opaque}''. + +Examples of suitable formats for Transparent copies include plain +ASCII without markup, Texinfo input format, LaTeX input format, SGML +or XML using a publicly available DTD, and standard-conforming simple +HTML, PostScript or PDF designed for human modification. Examples of +transparent image formats include PNG, XCF and JPG. Opaque formats +include proprietary formats that can be read and edited only by +proprietary word processors, SGML or XML for which the DTD and/or +processing tools are not generally available, and the +machine-generated HTML, PostScript or PDF produced by some word +processors for output purposes only. + +The ``\textbf{Title Page}'' means, for a printed book, the title page itself, +plus such following pages as are needed to hold, legibly, the material +this License requires to appear in the title page. For works in +formats which do not have any title page as such, ``Title Page'' means +the text near the most prominent appearance of the work's title, +preceding the beginning of the body of the text. + +The ``\textbf{publisher}'' means any person or entity that distributes +copies of the Document to the public. + +A section ``\textbf{Entitled XYZ}'' means a named subunit of the Document whose +title either is precisely XYZ or contains XYZ in parentheses following +text that translates XYZ in another language. (Here XYZ stands for a +specific section name mentioned below, such as ``\textbf{Acknowledgements}'', +``\textbf{Dedications}'', ``\textbf{Endorsements}'', or ``\textbf{History}''.) +To ``\textbf{Preserve the Title}'' +of such a section when you modify the Document means that it remains a +section ``Entitled XYZ'' according to this definition. + +The Document may include Warranty Disclaimers next to the notice which +states that this License applies to the Document. These Warranty +Disclaimers are considered to be included by reference in this +License, but only as regards disclaiming warranties: any other +implication that these Warranty Disclaimers may have is void and has +no effect on the meaning of this License. + + +\begin{center} +{\Large\bf 2. VERBATIM COPYING\par} +\end{center} + +You may copy and distribute the Document in any medium, either +commercially or noncommercially, provided that this License, the +copyright notices, and the license notice saying this License applies +to the Document are reproduced in all copies, and that you add no other +conditions whatsoever to those of this License. You may not use +technical measures to obstruct or control the reading or further +copying of the copies you make or distribute. However, you may accept +compensation in exchange for copies. If you distribute a large enough +number of copies you must also follow the conditions in section~3. + +You may also lend copies, under the same conditions stated above, and +you may publicly display copies. + + +\begin{center} +{\Large\bf 3. COPYING IN QUANTITY\par} +\end{center} + + +If you publish printed copies (or copies in media that commonly have +printed covers) of the Document, numbering more than 100, and the +Document's license notice requires Cover Texts, you must enclose the +copies in covers that carry, clearly and legibly, all these Cover +Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on +the back cover. Both covers must also clearly and legibly identify +you as the publisher of these copies. The front cover must present +the full title with all words of the title equally prominent and +visible. You may add other material on the covers in addition. +Copying with changes limited to the covers, as long as they preserve +the title of the Document and satisfy these conditions, can be treated +as verbatim copying in other respects. + +If the required texts for either cover are too voluminous to fit +legibly, you should put the first ones listed (as many as fit +reasonably) on the actual cover, and continue the rest onto adjacent +pages. + +If you publish or distribute Opaque copies of the Document numbering +more than 100, you must either include a machine-readable Transparent +copy along with each Opaque copy, or state in or with each Opaque copy +a computer-network location from which the general network-using +public has access to download using public-standard network protocols +a complete Transparent copy of the Document, free of added material. +If you use the latter option, you must take reasonably prudent steps, +when you begin distribution of Opaque copies in quantity, to ensure +that this Transparent copy will remain thus accessible at the stated +location until at least one year after the last time you distribute an +Opaque copy (directly or through your agents or retailers) of that +edition to the public. + +It is requested, but not required, that you contact the authors of the +Document well before redistributing any large number of copies, to give +them a chance to provide you with an updated version of the Document. + + +\begin{center} +{\Large\bf 4. MODIFICATIONS\par} +\end{center} + +You may copy and distribute a Modified Version of the Document under +the conditions of sections 2 and 3 above, provided that you release +the Modified Version under precisely this License, with the Modified +Version filling the role of the Document, thus licensing distribution +and modification of the Modified Version to whoever possesses a copy +of it. In addition, you must do these things in the Modified Version: + +\begin{itemize} +\item[A.] + Use in the Title Page (and on the covers, if any) a title distinct + from that of the Document, and from those of previous versions + (which should, if there were any, be listed in the History section + of the Document). You may use the same title as a previous version + if the original publisher of that version gives permission. + +\item[B.] + List on the Title Page, as authors, one or more persons or entities + responsible for authorship of the modifications in the Modified + Version, together with at least five of the principal authors of the + Document (all of its principal authors, if it has fewer than five), + unless they release you from this requirement. + +\item[C.] + State on the Title page the name of the publisher of the + Modified Version, as the publisher. + +\item[D.] + Preserve all the copyright notices of the Document. + +\item[E.] + Add an appropriate copyright notice for your modifications + adjacent to the other copyright notices. + +\item[F.] + Include, immediately after the copyright notices, a license notice + giving the public permission to use the Modified Version under the + terms of this License, in the form shown in the Addendum below. + +\item[G.] + Preserve in that license notice the full lists of Invariant Sections + and required Cover Texts given in the Document's license notice. + +\item[H.] + Include an unaltered copy of this License. + +\item[I.] + Preserve the section Entitled ``History'', Preserve its Title, and add + to it an item stating at least the title, year, new authors, and + publisher of the Modified Version as given on the Title Page. If + there is no section Entitled ``History'' in the Document, create one + stating the title, year, authors, and publisher of the Document as + given on its Title Page, then add an item describing the Modified + Version as stated in the previous sentence. + +\item[J.] + Preserve the network location, if any, given in the Document for + public access to a Transparent copy of the Document, and likewise + the network locations given in the Document for previous versions + it was based on. These may be placed in the ``History'' section. + You may omit a network location for a work that was published at + least four years before the Document itself, or if the original + publisher of the version it refers to gives permission. + +\item[K.] + For any section Entitled ``Acknowledgements'' or ``Dedications'', + Preserve the Title of the section, and preserve in the section all + the substance and tone of each of the contributor acknowledgements + and/or dedications given therein. + +\item[L.] + Preserve all the Invariant Sections of the Document, + unaltered in their text and in their titles. Section numbers + or the equivalent are not considered part of the section titles. + +\item[M.] + Delete any section Entitled ``Endorsements''. Such a section + may not be included in the Modified Version. + +\item[N.] + Do not retitle any existing section to be Entitled ``Endorsements'' + or to conflict in title with any Invariant Section. + +\item[O.] + Preserve any Warranty Disclaimers. +\end{itemize} + +If the Modified Version includes new front-matter sections or +appendices that qualify as Secondary Sections and contain no material +copied from the Document, you may at your option designate some or all +of these sections as invariant. To do this, add their titles to the +list of Invariant Sections in the Modified Version's license notice. +These titles must be distinct from any other section titles. + +You may add a section Entitled ``Endorsements'', provided it contains +nothing but endorsements of your Modified Version by various +parties---for example, statements of peer review or that the text has +been approved by an organization as the authoritative definition of a +standard. + +You may add a passage of up to five words as a Front-Cover Text, and a +passage of up to 25 words as a Back-Cover Text, to the end of the list +of Cover Texts in the Modified Version. Only one passage of +Front-Cover Text and one of Back-Cover Text may be added by (or +through arrangements made by) any one entity. If the Document already +includes a cover text for the same cover, previously added by you or +by arrangement made by the same entity you are acting on behalf of, +you may not add another; but you may replace the old one, on explicit +permission from the previous publisher that added the old one. + +The author(s) and publisher(s) of the Document do not by this License +give permission to use their names for publicity for or to assert or +imply endorsement of any Modified Version. + + +\begin{center} +{\Large\bf 5. COMBINING DOCUMENTS\par} +\end{center} + + +You may combine the Document with other documents released under this +License, under the terms defined in section~4 above for modified +versions, provided that you include in the combination all of the +Invariant Sections of all of the original documents, unmodified, and +list them all as Invariant Sections of your combined work in its +license notice, and that you preserve all their Warranty Disclaimers. + +The combined work need only contain one copy of this License, and +multiple identical Invariant Sections may be replaced with a single +copy. If there are multiple Invariant Sections with the same name but +different contents, make the title of each such section unique by +adding at the end of it, in parentheses, the name of the original +author or publisher of that section if known, or else a unique number. +Make the same adjustment to the section titles in the list of +Invariant Sections in the license notice of the combined work. + +In the combination, you must combine any sections Entitled ``History'' +in the various original documents, forming one section Entitled +``History''; likewise combine any sections Entitled ``Acknowledgements'', +and any sections Entitled ``Dedications''. You must delete all sections +Entitled ``Endorsements''. + +\begin{center} +{\Large\bf 6. COLLECTIONS OF DOCUMENTS\par} +\end{center} + +You may make a collection consisting of the Document and other documents +released under this License, and replace the individual copies of this +License in the various documents with a single copy that is included in +the collection, provided that you follow the rules of this License for +verbatim copying of each of the documents in all other respects. + +You may extract a single document from such a collection, and distribute +it individually under this License, provided you insert a copy of this +License into the extracted document, and follow this License in all +other respects regarding verbatim copying of that document. + + +\begin{center} +{\Large\bf 7. AGGREGATION WITH INDEPENDENT WORKS\par} +\end{center} + + +A compilation of the Document or its derivatives with other separate +and independent documents or works, in or on a volume of a storage or +distribution medium, is called an ``aggregate'' if the copyright +resulting from the compilation is not used to limit the legal rights +of the compilation's users beyond what the individual works permit. +When the Document is included in an aggregate, this License does not +apply to the other works in the aggregate which are not themselves +derivative works of the Document. + +If the Cover Text requirement of section~3 is applicable to these +copies of the Document, then if the Document is less than one half of +the entire aggregate, the Document's Cover Texts may be placed on +covers that bracket the Document within the aggregate, or the +electronic equivalent of covers if the Document is in electronic form. +Otherwise they must appear on printed covers that bracket the whole +aggregate. + + +\begin{center} +{\Large\bf 8. TRANSLATION\par} +\end{center} + + +Translation is considered a kind of modification, so you may +distribute translations of the Document under the terms of section~4. +Replacing Invariant Sections with translations requires special +permission from their copyright holders, but you may include +translations of some or all Invariant Sections in addition to the +original versions of these Invariant Sections. You may include a +translation of this License, and all the license notices in the +Document, and any Warranty Disclaimers, provided that you also include +the original English version of this License and the original versions +of those notices and disclaimers. In case of a disagreement between +the translation and the original version of this License or a notice +or disclaimer, the original version will prevail. + +If a section in the Document is Entitled ``Acknowledgements'', +``Dedications'', or ``History'', the requirement (section~4) to Preserve +its Title (section~1) will typically require changing the actual +title. + + +\begin{center} +{\Large\bf 9. TERMINATION\par} +\end{center} + + +You may not copy, modify, sublicense, or distribute the Document +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense, or distribute it is void, and +will automatically terminate your rights under this License. + +However, if you cease all violation of this License, then your license +from a particular copyright holder is reinstated (a) provisionally, +unless and until the copyright holder explicitly and finally +terminates your license, and (b) permanently, if the copyright holder +fails to notify you of the violation by some reasonable means prior to +60 days after the cessation. + +Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + +Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, receipt of a copy of some or all of the same material does +not give you any rights to use it. + + +\begin{center} +{\Large\bf 10. FUTURE REVISIONS OF THIS LICENSE\par} +\end{center} + + +The Free Software Foundation may publish new, revised versions +of the GNU Free Documentation License from time to time. Such new +versions will be similar in spirit to the present version, but may +differ in detail to address new problems or concerns. See +\texttt{https://www.gnu.org/licenses/}. + +Each version of the License is given a distinguishing version number. +If the Document specifies that a particular numbered version of this +License ``or any later version'' applies to it, you have the option of +following the terms and conditions either of that specified version or +of any later version that has been published (not as a draft) by the +Free Software Foundation. If the Document does not specify a version +number of this License, you may choose any version ever published (not +as a draft) by the Free Software Foundation. If the Document +specifies that a proxy can decide which future versions of this +License can be used, that proxy's public statement of acceptance of a +version permanently authorizes you to choose that version for the +Document. + + +\begin{center} +{\Large\bf 11. RELICENSING\par} +\end{center} + + +``Massive Multiauthor Collaboration Site'' (or ``MMC Site'') means any +World Wide Web server that publishes copyrightable works and also +provides prominent facilities for anybody to edit those works. A +public wiki that anybody can edit is an example of such a server. A +``Massive Multiauthor Collaboration'' (or ``MMC'') contained in the +site means any set of copyrightable works thus published on the MMC +site. + +``CC-BY-SA'' means the Creative Commons Attribution-Share Alike 3.0 +license published by Creative Commons Corporation, a not-for-profit +corporation with a principal place of business in San Francisco, +California, as well as future copyleft versions of that license +published by that same organization. + +``Incorporate'' means to publish or republish a Document, in whole or +in part, as part of another Document. + +An MMC is ``eligible for relicensing'' if it is licensed under this +License, and if all works that were first published under this License +somewhere other than this MMC, and subsequently incorporated in whole +or in part into the MMC, (1) had no cover texts or invariant sections, +and (2) were thus incorporated prior to November 1, 2008. + +The operator of an MMC Site may republish an MMC contained in the site +under CC-BY-SA on the same site at any time before August 1, 2009, +provided the MMC is eligible for relicensing. + + +\begin{center} +{\Large\bf ADDENDUM: How to use this License for your documents\par} +\end{center} + +To use this License in a document you have written, include a copy of +the License in the document and put the following copyright and +license notices just after the title page: + +\bigskip +\begin{quote} + Copyright \copyright{} YEAR YOUR NAME. + Permission is granted to copy, distribute and/or modify this document + under the terms of the GNU Free Documentation License, Version 1.3 + or any later version published by the Free Software Foundation; + with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. + A copy of the license is included in the section entitled ``GNU + Free Documentation License''. +\end{quote} +\bigskip + +If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts, +replace the ``with \dots\ Texts.''\ line with this: + +\bigskip +\begin{quote} + with the Invariant Sections being LIST THEIR TITLES, with the + Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST. +\end{quote} +\bigskip + +If you have Invariant Sections without Cover Texts, or some other +combination of the three, merge those two alternatives to suit the +situation. + +If your document contains nontrivial examples of program code, we +recommend releasing these examples in parallel under your choice of +free software license, such as the GNU General Public License, +to permit their use in free software. diff --git a/doc/tex/planning.tex b/doc/tex/planning.tex new file mode 100644 index 0000000..790a988 --- /dev/null +++ b/doc/tex/planning.tex @@ -0,0 +1,264 @@ +\section{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} + +The project will be organized in several stages based on the different +components and needs. + +\subsubsection{Game Implementation} + +The rules of the game must be implemented, ideally in a way they can be tested +by direct human play. This system will at its bare minimum represent the +Japanese Go rules (area scoring, no \gls{superko} rule, no \gls{suicide} moves. +These terms are explained in the \nameref{glossary} of this document). + +\subsubsection{Engine Implementation} + +The key of this project is to create some kind of system able to generate strong +moves based on any given board configuration: this will be such system. It will +implement an existing protocol so it can be used with other compatible tools. It +has to be able to receive game updates and configuration and to output moves for +either player. It should also be modular enough so different algorithms can be +selected and tested against each other as an experimental search for the best of +them. + +\subsubsection{Artificial Intelligence Algorithms} + +Different algorithms for the engine to use should be implemented and tested. The +results of this development and testing process should be presented as part of +the final version of the project. + +\subsection{Logistics} + +The project will be developed by Íñigo Gutiérrez Fernández, student of the +Computer Software Engineering Degree at the University of Oviedo, with +supervision from Vicente García Díaz, Associate Professor in the Department of +Computer Science at the University of Oviedo. + +The used material consists of a development and testing machine owned by the +student with specifications stated later on the project plan. + +\subsection{Work Plan} + +The sole developer will be the student, who is currently working as a Junior +Software Engineer on a 35 hour per week schedule and with no university +responsibilities other than this project. Taking this into account, a sensible +initial assumption is that he will be able to work 3 hours a day, Monday to +Friday. Gantt diagrams for the planned working schedule are shown as +\fref{fig:planningWorkPlanGame} and +\fref{fig:planningWorkPlanEngine}. This planning predicts 6 months of +development, from November 2020 to April 2021. With the planned schedule of 3 +hours a day on weekdays this amounts to 375 hours. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/planningWorkPlanGame.png} + \caption{Initial work plan for implementing the game. + }\label{fig:planningWorkPlanGame} + \end{center} +\end{figure} + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/planningWorkPlanEngine.png} + \caption{Initial work plan for implementing the engine and algorithms. + }\label{fig:planningWorkPlanEngine} + \end{center} +\end{figure} + +\subsection{Previous Works} + +This section lists and describes the existing projects which inspired and can be +of use in the development of \program{}. + +\subsubsection{Existing Engines} + +\begin{figure}[h] + \begin{center} + \includegraphics[width=0.5\textwidth]{img/Alphago_logo_Reversed.jpg} + \caption{AlphaGo logo. By Google DeepMind - Google DeepMind AlphaGo + Logo, Public Domain, + https://commons.wikimedia.org/w/index.php?curid=47169369 + }\label{fig:alphaGoLogo} + \end{center} +\end{figure} + +\paragraph{AlphaGo} + +A Go play and analysis engine \cite{alphaGo} developed by DeepMind Technologies, +a company owned by Google. It revolutionized the world of Go in 2015 and 2016 +when it respectively became the first \acrshort{ai} to win against a +professional Go player and then won against Lee Sedol, a Korean player of the +highest professional rank and one of the strongest players in the world at the +time. Its source code is closed, but a paper written by the team has been +published on Nature \cite{natureAlphaGo2016}. The logo of the project is shown +on \fref{fig:alphaGoLogo}. + +The unprecedented success of AlphaGo served as inspiration for many +\acrshort{ai} projects, including this one. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=0.5\textwidth]{img/katago.png} + \caption{KataGo logo. + https://katagotraining.org/static/images/katago.png + }\label{fig:kataGoLogo} + \end{center} +\end{figure} + +\paragraph{KataGo} + +An open source project \cite{katago} based on the AlphaGo paper that also +achieved superhuman strength of play. The availability of its implementation and +documentation presents a great resource for this project. The logo of the +project is shown on \fref{fig:kataGoLogo}. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=0.5\textwidth]{img/gnuGoLogo.jpg} + \caption{GnuGo logo. + https://www.gnu.org/software/gnugo/logo-36.jpg + }\label{fig:gnuGoLogo} + \end{center} +\end{figure} + +\paragraph{GnuGo} + +A software \cite{gnugo} 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}} + +The \acrfull{gtp} \cite{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 \acrshort{gui}s and other programs, making it easier to +be used with the tools target users are already familiar with. + +%TODO +%\begin{listing}[h] +% \inputminted{text}{listings/gtpExample.sgf} +% \caption{\acrshort{gtp} session example.} +% \label{lst:gtpExample} +%\end{listing} + +\paragraph{\acrshort{sgf}} + +The \acrfull{sgf} \cite{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} +\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 the two + continuations described in the \acrshort{sgf} file are marked 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 + }\label{fig:sabaki} + \end{center} +\end{figure} + +\subsubsection{Sabaki} + +Sabaki \cite{sabaki} is a Go board software compatible with \acrshort{gtp} +engines. It can serve as a \acrshort{gui} for the engine developed in this project and as +an example of the advantages of following a standardized protocol. Part of its +graphical interface is shown on \fref{fig:sabaki}. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=0.5\textwidth]{img/kerasLogo.jpg} + \caption{Keras logo. + https://keras.io/img/logo.png + }\label{fig:kerasLogo} + \end{center} +\end{figure} + +\subsubsection{Keras} + +Keras \cite{keras} is a deep learning API for Python allowing for the high-level +definition of neural networks. This permits easily testing and comparing +different network layouts. The logo of the project is shown on +\fref{fig:kerasLogo}. + +\subsubsection{PLY} + +PLY \cite{ply} is a Python implementation of the compiler construction tools lex +and yacc. It will be useful for implementing the \acrshort{sgf} parser needed to +process records of Go matches. + +\subsection{Technological Infrastructure} + +This section establishes the technological needs of the project and proposes +solutions to them. + +\subsubsection{Programming Language}\label{sec:programmingLanguage} + +The resulting product of this project will be one or more pieces of software +able to be run locally on a personal computer. The programming language of +choice is Python \cite{python}, for various reasons: + +\begin{itemize} + + \item It has established a reputation on scientific fields and more + specifically on \acrshort{ai} research and development. + \item Interpreters are available for many platforms, which allows the most + people possible to access the product. + \item Although not very deeply, it has been used by the developer student + during its degree including in \acrshort{ai} and game theory contexts. + +\end{itemize} + +\subsubsection{Interface} + +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 will be able to +be used in conjunction with this engine, for example to serve as a \acrshort{gui}. + +There is also the need of an interface with \acrshort{sgf} files so existing +games can be processed by the trainer. + +Both the engine and the trainer will need to interface with the files storing +the neural network models. + +The systems' interfaces are shown in \fref{fig:interfaces}. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/interfaces.png} + \caption{Interfaces of the three components of the project.} + \label{fig:interfaces} + \end{center} +\end{figure} diff --git a/doc/tex/results.tex b/doc/tex/results.tex index 3c586e4..e166873 100644 --- a/doc/tex/results.tex +++ b/doc/tex/results.tex @@ -30,13 +30,16 @@ \section{Results} +This section shows an analysis of the successes and failures of the final +product and the strength of play of its various algorithms. + \subsection{Monte Carlo Tree Search Evaluation} The Monte Carlo Algorithm tries to explore the tree of possibilities as efficiently as possible. With this approach, it can be expected to fail when -alone on a problem such big as the game of Go. Nonetheless, there are some areas -where it can be useful. It will be evaluated by its capabilities while playing -games but also when presented with go problems. +alone on a problem such as big as the game of Go. Nonetheless, there are some +areas where it can be useful. It will be evaluated by its capabilities while +playing games but also when presented with Go problems. The Monte Carlo algorithm has been set to do 5 explorations with 10 simulations each when it is asked for a move. In the hardware used this makes it think for @@ -57,7 +60,8 @@ Some moves could be debated as sensible, but many of them are on the second or fist line, which so early on the game are the two worst places to play at. It seems clear that this algorithm, at least with this specific configuration, -can't handle the size of an empty Go board, even on the 9x9 size. +can't handle the tree of possibilities of an empty Go board even at the 9x9 +size. A record of the game is shown in \fref{fig:mctsVSmcts}. @@ -72,56 +76,63 @@ A record of the game is shown in \fref{fig:mctsVSmcts}. Since tree exploration on smaller boards or advanced games with little empty spaces should be easier the algorithm has also been tested on some Go problems. -A Go problem or tsumego is a predefined layout of the board, or of a section of -the board, for which the player must find some beneficial move. Life and death -problems are a subset of tsumegos in which the survival of a group depends on -finding the correct sequence to save or kill the group. One collection of such -tsumegos is \textit{Cho Chikun's Encyclopedia of Life and Death}, part of which -are available on OGS\cite{ogsLifeAndDeath}, an online go server. +A Go problem or \gls{tsumego} is a predefined layout of the board, or of a +section of the board, for which the player must find some beneficial move. Life +and death problems are a subset of \gls{tsumego}s in which the aim is to find +the correct sequence to save or kill a group. One collection of such +\gls{tsumego}s is \textit{Cho Chikun Life and Death Dictionary} +\cite{choLifeAndDeath}, part of which are available on OGS +\cite{ogsLifeAndDeath}, an online Go server. The first of these problems and what the algorithm suggested as moves is shown in \fref{fig:mctsProblem01}. Black makes the first move, which means the solution is to find some favorable outcome for black, which in this case is killing the white group. The white -group has a critical point on B1. If white plays on B1 they make two eyes and -live, but if black plays there first white can't make two eyes and dies, so B1 -is the solution to the tsumego. This is one of the easiest Go problems. +group has a \gls{criticalPoint} on B1. If white plays on B1 they make two +\glspl{eye} and live, but if black plays there first white can't make two +\glspl{eye} and dies, so B1 is the solution to the \gls{tsumego}. This is one of +the easiest Go problems. The algorithm neglects this solution. While asked five times to generate a move for the starting position it suggested B1 only once. But notably, after making another move, it consistently suggested B1 for white, -which is the solution now that white has to play. So in the end it was able to -solve the tsumego, probably because after making a move it had already explored -part of the tree but it was difficult that it explored the solution for the -first move. +which is now the correct move for white. So in the end it was able to solve the +\gls{tsumego}, probably because after making a move it had already explored part +of the tree but it was difficult that it explored the solution for the first +move, that is, in its first exploration cycle. -The engine was tested against other tsumegos but it was not able to solve them, -so no more are shown here. +The engine was tested against other \gls{tsumego}s but it was not able to solve +them, so no more are shown here. This was the one simple enough for an engine of +this characteristics and running on the testing hardware to solve. \subsection{Neural Network Training} -Each network has been training by receiving batches of SGF files which are first -converted to lists of moves by the Training System and then provided to the -train function of the networks. This has been executed with the following -command: +Each network has been training by receiving batches of \acrshort{sgf} files +which are first converted to lists of moves by the Training System and then +provided to the train function of the networks. This has been executed with the +following command: \inputminted[fontsize=\small]{bash}{listings/trainCommand.sh} -Which lists the contents of a folder containing multiple SGF files, shuffles the -list, takes some of them and passes them to train.py as arguments. The combined -list of game positions and moves made from them in all the games selected make -up the sample of the training. The number of files selected can of course be -adapted to the situation. +Which lists the contents of a folder containing multiple \acrshort{sgf} files, +shuffles the list, takes some of them and passes them to train.py as arguments. +The combined list of game positions and moves made from them in all the games +selected make up the sample of the training. The number of files selected can of +course be adapted to the situation. The networks were configured to train for 20 epochs, that is, processing the full batch and updating the weights on the network 20 times. 10\% of the sample -were used as validation. This means they were not used for training but to -check the accuracy and loss of the network after training with the rest of -the batch. This technique of validation can help detect overfitting, which -happens when a network does a very good job on the population it has been -trained on but it fails when receiving unseen data. +was used as validation. This means they were not used for training but to check +the accuracy and loss of the network after training with the rest of the batch. +This technique of validation can help detect overfitting, which happens when a +network does a very good job on the population it has been trained on but it +fails when receiving unseen data. + +The outputs from this training process can be seen on \lref{code:denseTraining} +and \lref{code:convTraining} for the dense network and the convolutional +network respectively. The training shows loss decrementing and accuracy incrementing on each epoch for both training and validation samples, which suggests there is learning happening @@ -134,10 +145,6 @@ as with batches of 10 games an epoch of training could be completed in one minute, in three minutes batches of 20 games, and in up to an hour with batches of 100 games. -The outputs from this training process can be seen on \flist{code:denseTraining} -and \flist{code:convTraining} for the dense network and the convolutional -network respectively. - \begin{listing}[h] \inputminted[fontsize=\scriptsize]{text}{listings/denseTraining.txt} \caption{Dense neural network training log.} @@ -163,8 +170,8 @@ of predicting human moves through the training epochs. Another way is to make the network play either against itself, another network, or a human player, and analyze the score it provides to each possible play. The -output of the network is a vector with the likelihood of making each move, so -we can take this values as how strongly the engine suggests each of them. +output of the network is a vector with the likelihood of making each move, so we +can take these values as how strongly the engine suggests each of them. \subsection{Neural Networks Against Themselves} @@ -184,11 +191,11 @@ move), can be seen on Figs.~\ref{fig:denseVSdense01}, \ref{fig:denseVSdense02}, The dense network starts on the center of the board, which is one of the standard openings in the 9x9 board. It starts on a very good track, but we must -acknowledge that the empty board is a position present on every go match it has -trained on and so it should know it well. It probably means the center was the -most played opening in the sample. It is interesting to check the heatmap of -this move, since the selected move has only a score of 0.27. Other common -openings on the 9x9 are represented on the vertices with some significant score. +acknowledge that the empty board is a position present on every Go match it has +trained on, so it should know it well. It probably means the center was the most +played opening in the sample. It is interesting to check the heatmap of this +move, since the selected move has only a score of 0.27. Other common openings on +the 9x9 are represented on the vertices with some significant score. The heatmap of the response to the center play is also interesting. The four highest scored moves are equivalent, since the first move has not broken any @@ -201,12 +208,13 @@ second black move is suggested with more likelihood than the previous one. This is also a very common sequence of play. The following moves are a white attack followed by black's sensible response, -and a strong white extension (arguably to the wrong side, but the minutia of why +and a strong white extension (arguably to the wrong side, but the details of why the other side would be better is probably not grasped by the engine). The -following moves could be called looking for complication, which is a strategy. +following moves could be classified as ``looking for complication'', which is a +strategy. -Overall some moves could be criticised but the engine is showing at least a -basic knowledge of the game's strategy. +Overall some moves can be criticised but the engine is showing at least a basic +knowledge of the game's strategy. \subsubsection{Convolutional Network Against Itself} @@ -219,21 +227,21 @@ more certain of the move than the dense network. Its next two plays are also the same, but the match starts to diverge from the fourth move. Instead of attacking the black stone on the side, white plays directly under at -B5, keeping the edge of symmetry. This is strategically important because while -symmetry is present playing on either side makes no difference, while playing -after the opponent has broken symmetry gives the opportunity to respond and -capitalize on the now better side to play. +B5, keeping the edge of symmetry. This is strategically important because as +long as symmetry is present playing on either side makes no difference, while +playing after the opponent has broken symmetry gives the opportunity to respond +and capitalize on the now better side to play. Black responds to the white stone by attacking it at B4 and white then extends to the more open side with F7. The match up to this point is discussed on Sensei's Library as an interesting -sequence deriving from the center first stone\cite{sl_sword}. The discussion +sequence deriving from the center first stone \cite{sl_sword}. The discussion there states that white should have extended to the other side. The following moves are some sensible continuations, with approaches and responses on each side. They are probably not the best moves, but the idea -behind them can be read from the board. +behind them can be grasped from the board. \subsubsection{Dense Network Against Convolutional} diff --git a/doc/tex/systemAnalysis.tex b/doc/tex/systemAnalysis.tex index c3c6aa8..1f0c997 100644 --- a/doc/tex/systemAnalysis.tex +++ b/doc/tex/systemAnalysis.tex @@ -1,5 +1,9 @@ \section{System Analysis} +This section provides a preliminary analysis of the needs of the project, such +as its requirements, components and use cases. It also includes the +specification of the testing plan. + \subsection{System Reach Determination} These are the main goals the final product must reach. @@ -7,19 +11,19 @@ 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 decision algorithms to keep the state of the game and can also be used - in an interactive application for a user to play the game and test the - code. + in an interactive application for a human user to play the game and test + the code. \item An engine program as a way of presenting an interface for using these - algorithms. The engine will use the GTP so it can be used with an - existing GUI or other tools. + algorithms. The engine will use the \acrshort{gtp} so it can be used with an + existing \acrshort{gui} or other tools. - \item A parser for SGF files so they can be processed in the training of + \item A parser for \acrshort{sgf} files so they can be processed in the training of neural networks. \end{enumerate} @@ -50,7 +54,7 @@ requisites needed for the system. coordinates of the vertex to play on or as ``pass''. \begin{enumerate} \item The text introduced for the move must follow the - regular expression \texttt{([A-Z][0-9]+|pass)} + regular expression \texttt{([A-HJ-Z][0-9]+)|(pass)} \item If the move is not valid it must be notified to the user and another move asked for. \end{enumerate} @@ -84,15 +88,14 @@ requisites needed for the system. \item The engine program is interactive. - \item The engine implements the GTP (\textit{Go Text Protocol}) for its - interface. + \item The engine implements the \acrfull{gtp} for its interface. \begin{enumerate} \item Commands are read from standard input. \item Responses are provided via standard output. \item There exist commands to set up the conditions of the match. \begin{enumerate} \item The size of the board can be set. - \item The komi can be set. + \item The \gls{komi} can be set. \end{enumerate} \item There exist commands to manipulate the internal representation of the match. @@ -149,9 +152,9 @@ requisites needed for the system. \item The trainer can import existing games. \begin{enumerate} - \item Records of games stored as SGF can be imported. - \item Files containing records of games are provided as arguments to - the trainer. + \item Records of games stored as \acrshort{sgf} can be imported. + \item Files containing records of games can be provided as arguments + to the trainer. \end{enumerate} \end{enumerate} @@ -179,13 +182,13 @@ requisites needed for the system. \begin{enumerate} \item For understanding the workings of the application the user needs to be - familiar with the basics of the game of Go. + familiar with the rules of the game of Go. \item For directly using the engine the user needs to be familiar with command line interfaces. - \item For directly using the trainer the user needs to know the different - network models available. + \item For directly using the trainer the user needs to know about the + different network models available. \end{enumerate} @@ -195,8 +198,8 @@ requisites needed for the system. \begin{enumerate} - \item The game program will be a python file able to be executed by the - python interpreter. + \item The game program will be a Python script able to be executed by the + Python interpreter. \item The game program will make use of standard input and standard output for communication. @@ -206,8 +209,8 @@ requisites needed for the system. \item Standard output will be used for messages directed to the user. \end{enumerate} - \item The engine program will be a python file able to be executed by the - python interpreter. + \item The engine program will be a Python script able to be executed by the + Python interpreter. \item The engine program will make use of standard input and standard output for communication. @@ -217,11 +220,11 @@ requisites needed for the system. commands. \end{enumerate} - \item The trainer program will be a python file able to be executed by the - python interpreter. + \item The trainer program will be a Python script able to be executed by the + Python interpreter. - \item The engine program will make use of standard input and standard output - for communication. + \item The trainer program will make use of standard input and standard + output for communication. \begin{enumerate} \item Standard input will be used for reading commands. \item Standard output will be used for showing the result of @@ -264,37 +267,41 @@ between human players to show and test its capabilities. \subsubsection{Engine System} -The Engine System will implement the GTP interface and use the Game System to +The Engine System will implement the \acrshort{gtp} interface and use the Game System to analyse positions and generate moves via decision algorithms. This system can be directly called to manually set up game states and ask for -moves or can be called by other programs which use GTP to be used as backend for +moves or can be called by other programs which use \acrshort{gtp} to be used as backend for playing matches against a computer player. \subsubsection{Training System} -The Training System will process SGF files storing records of games, train the +The Training System will process \acrshort{sgf} files storing records of games, train the neural network models over those games and store the result. These models can 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 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} +This section describes the needed classes expected as a result of the analysis +of the project. + \subsubsection{Class Diagram} The classes resulting from the analysis phase are shown in \fref{fig:analysisClasses}. -\begin{figure}[h] +\begin{figure}[p] \begin{center} \includegraphics[width=\textwidth]{diagrams/analysisClasses.png} \caption{General classes obtained from the analysis @@ -416,7 +423,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.} \\ @@ -431,7 +438,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 @@ -446,17 +453,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 @@ -478,10 +485,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 @@ -654,8 +661,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} @@ -666,12 +673,13 @@ The classes resulting from the analysis phase are shown in \textbf{Parser} \\ \midrule \textbf{Description} \\ - Reads 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 SGF files.} \\ - \tabitem{Convert the content of the SGF files to a tree of GameMove.} \\ + \tabitem{Read \acrshort{sgf} files.} \\ + \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 @@ -688,19 +696,19 @@ The classes resulting from the analysis phase are shown in \textbf{ASTNode} \\ \midrule \textbf{Description} \\ - Makes up the tree resulting from the parsing of an SGF file.\\ + 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.} \\ - \tabitem{\textbf{props}: The properties of the tree read from an SGF file.} + \tabitem{\textbf{props}: The properties of the tree read from an \acrshort{sgf} file.} \\ \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} @@ -715,13 +723,14 @@ non-human. \item The human player who interacts with the playing interface. \item The human user who interacts with the engine. - \item A GUI software which uses the engine to generate moves. + \item The human user who starts the training. + \item A \acrshort{gui} software which uses the engine to generate moves. \end{itemize} \subsection{Use Cases} -\begin{figure}[h] +\begin{figure}[p] \begin{center} \includegraphics[width=\textwidth]{diagrams/useCases.png} \caption{Use cases.} @@ -737,20 +746,25 @@ use case is explained next. The game interface reads the moves presented by the player and shows their result on the board. +\paragraph{Generate a move} + +The engine interface reads the input for generating a move as stated by the +\acrshort{gtp} protocol and outputs the coordinates of the board to play. + +\paragraph{Train the engine} + +The training system is started to process matches stored as \acrshort{sgf} files +and to train a neural network. + \paragraph{Use as backend for machine player} The engine is used as the backend for generating moves for a machine player, -this is, for automated play, either against a human who is using the GUI or +this is, for automated play, either against a human who is using the \acrshort{gui} or against another machine player. -\paragraph{Generate a move} - -The engine interface reads the input for generating a move as stated by the -GTP protocol and outputs the coordinates of the board to play. - \subsection{Use Case Analysis and Scenarios} -\begin{figure}[h] +\begin{figure}[p] \begin{center} \includegraphics[width=0.8\textwidth]{diagrams/useCase_playAMatch.png} \caption{Use case: Play a match.} @@ -758,6 +772,8 @@ GTP protocol and outputs the coordinates of the board to play. \end{center} \end{figure} +\vspace{\interclassSpace} + \begin{tabular}{lp{0.6\linewidth}} \toprule \multicolumn{2}{c}{\textbf{Play a match}} \\ @@ -783,7 +799,7 @@ GTP protocol and outputs the coordinates of the board to play. main scenario. \\ \midrule \textbf{Notes} & - This scenario does not pretend to be a complete recreation of a go match. It + This scenario does not pretend to be a complete recreation of a Go match. It will be playable, but its main purpose is to see the Game implementation in action.\newline A robustness diagram for this scenario is shown in @@ -793,7 +809,7 @@ GTP protocol and outputs the coordinates of the board to play. \vspace{\interclassSpace} -\begin{figure}[h] +\begin{figure}[p] \begin{center} \includegraphics[width=\textwidth]{diagrams/useCase_generateAMove.png} \caption{Use case: Generate a move.} @@ -810,7 +826,7 @@ GTP protocol and outputs the coordinates of the board to play. \midrule \textbf{Postconditions} & A move is suggested via the engine output. \\ \midrule - \textbf{Actors} & Human user and GUI program. \\ + \textbf{Actors} & Human user and \acrshort{gui} program. \\ \midrule \textbf{Description} & 1. The user or program enters the player to generate the move @@ -835,7 +851,49 @@ GTP protocol and outputs the coordinates of the board to play. \vspace{\interclassSpace} -\begin{figure}[h] +\begin{figure}[p] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/useCase_trainTheEngine.png} + \caption{Use case: Train the engine.} + \label{fig:useCase_trainTheEngine} + \end{center} +\end{figure} + +\begin{tabular}{lp{0.6\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Train the engine}} \\ + \midrule + \textbf{Preconditions} & Some SGF files have been acquired to be used as + training games. \\ + \midrule + \textbf{Postconditions} & A neural network model has been created or updated. \\ + \midrule + \textbf{Actors} & Human user. \\ + \midrule + \textbf{Description} & + 1. The user starts the trainer.\newline + 2. The trainer processes the input files.\newline + 3. The trainer trains a model with the games described in the input + files. \\ + \midrule + \textbf{Secondary scenarios} & + --- \\ + \midrule + \textbf{Exceptions} & + \textbf{No input provided}: An error message is shown. Go back to step 1 of + main scenario. \newline + \textbf{The input is not formatted properly}: An error message is shown. Go + back to step 1 of main scenario. \\ + \midrule + \textbf{Notes} & + A robustness diagram for this scenario is shown in + \fref{fig:useCase_trainTheEngine}.\\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{figure}[p] \begin{center} \includegraphics[width=\textwidth]{diagrams/useCase_useAsBackend.png} \caption{Use case: Use as backend for machine player.} @@ -852,7 +910,7 @@ GTP protocol and outputs the coordinates of the board to play. \midrule \textbf{Postconditions} & A match has been played against the engine. \\ \midrule - \textbf{Actors} & GUI program. \\ + \textbf{Actors} & \acrshort{gui} program. \\ \midrule \textbf{Description} & 1. The program gives commands to the engine to set up the game. The @@ -879,14 +937,50 @@ GTP protocol and outputs the coordinates of the board to play. \subsection{Testing Plan Specification} +The Testing Plan will include four types of tests: + +\begin{itemize} + + \item Unitary Testing: for isolated code elements. + \item Integration Testing: for the collaboration between components. + \item System Testing: for the product as a whole. + \item Usability Testing: for the experience of users with the product. + +\end{itemize} + \subsubsection{Unitary Testing} -Tests for the python code are developed using the unittest\cite{python_unittest} -testing framework. It has been chosen by virtue of being thoroughly documented -and widely used. +A unitary testing suite provides test coverage at a base level, checking the +correct behaviour of each specific code piece. + +\subsubsection{Integration Testing} + +The interaction between components will be tested to check their correct +behaviour on the various situations where they have to work together: + +\begin{itemize} +\item The Engine module is able to use the Game module to handle a match. +\item The Training module is able to use the Engine module and its definitions + of neural networks. +\end{itemize} + +\subsubsection{System Testing} + +The working of the system as a whole has to be tested. Mainly: + +\begin{itemize} + + \item A game of Go can be played by a human by using the Game module. + \item A game of Go can be played against the computer by using the + \acrshort{gtp} interface of the Engine module. + \item The \acrshort{gtp} interface is compatible with at least one existing + \acrshort{gui} that claims compatibility with this protocol. + \item A training session can be started and it produces some results to be + evaluated independent of this test step. + +\end{itemize} -The coverage of unit testing is checked with Coverage.py\cite{python_coverage}, -which can by itself run the unittest tests and generate coverage reports based -on the results. +\subsubsection{Usability Testing} -% Maybe put an example report here? +Some people representing the final user will be confronted with the interfaces +of the system to test its usability. diff --git a/doc/tex/systemDesign.tex b/doc/tex/systemDesign.tex index 80a2ccb..e166955 100644 --- a/doc/tex/systemDesign.tex +++ b/doc/tex/systemDesign.tex @@ -1,5 +1,8 @@ \section{System Design} +This section explains the design of the component systems of \program{}, the +algorithms used and how they are to be implemented. + \subsection{Class Diagram} The full class diagram is shown in \fref{fig:fullClasses}. @@ -15,7 +18,7 @@ The full class diagram is shown in \fref{fig:fullClasses}. \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 +along with diagrams for each subsystem, since the full class diagram can be too big to be comfortably analyzed. \subsection{Game} @@ -30,24 +33,24 @@ too big to be comfortably analyzed. \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 +exploration of variants 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. +\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}. @@ -58,15 +61,15 @@ These classes and their relationships can be seen in \fref{fig:game}. \begin{figure}[h] \begin{center} \includegraphics[width=0.8\textwidth]{diagrams/engineModule.png} - \caption{Design of the GTP engine.}\label{fig:engine} + \caption{Design of the \acrshort{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: +This will be an implementation of \acrshort{gtp}, that is, the piece of software +which offers the \acrshort{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} @@ -74,63 +77,68 @@ 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 \acrshort{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}. \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}. +decision trees. It has a history of use in Go engines, not being able to reach +strong levels of play until it was paired with neural networks by AlphaGo 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 algorithm assigns a score to each explored node of the game tree 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{Selection}: The most promising move with at least one + 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. + different matches from it. How this matches are played varies: they can + be totally random, but here is where AlphaGo introduces one of its + neural networks so these simulation matches are more valuable. - \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. + \item \textbf{Backpropagation}: The scores of the new move and its previous + moves up to the root of the tree are 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. +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 +available children from a node or to simulate random games. \subsubsection{Neural Networks Explained} @@ -154,13 +162,13 @@ Several kinds of layers have been used in this project: \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 + \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. + or more complex shapes, so they are used a lot on image processing. 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 @@ -176,19 +184,19 @@ Several kinds of layers have been used in this project: 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. +purpose and baseline 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. +approach used on image processing to the more general one and study 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 -and for the analysis of results while keeping able to support meaningful -matches. +and for the analysis of results while still being big enough to support +meaningful matches. Both networks have the same design for their input and output. @@ -224,7 +232,7 @@ 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 +The design of this network is shown in \lref{code:denseModel} and \fref{fig:denseNN} as provided by Keras' summary and plot\_model functions respectively. @@ -249,7 +257,7 @@ 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 +The design of this network is shown in \lref{code:convModel} and \fref{fig:convNN} as provided by Keras' summary and plot\_model functions respectively. @@ -257,8 +265,8 @@ respectively. \begin{figure}[h] \begin{center} - \includegraphics[width=\textwidth]{diagrams/trainingModule.png} - \caption{Components of the SGF file parsing module.} + \includegraphics[width=0.7\textwidth]{diagrams/trainingModule.png} + \caption{Components of the \acrshort{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, @@ -267,19 +275,20 @@ respectively. \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. +trained first so they can provide meaningful results. For a Go \acrshort{ai} it +makes sense to have its algorithms trained on Go games. There exists a common +text format to store Go games: \acrshort{sgf}. If the system is able to process +\acrshort{sgf} files, it can provide 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 +\cite{ply}. The result of the parsing is an \acrfull{ast} 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 @@ -287,24 +296,25 @@ 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{\texttt{\acrshort{sgf}}}: Provides a high-level method to convert a path to a \acrshort{sgf} + file to a \texttt{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{\texttt{sgfyacc}}: The implementation of a \acrshort{sgf} parser using PLY. Takes + the tokens generated by \texttt{sgflex} and creates an \texttt{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{\texttt{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 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{\texttt{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{\texttt{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}. @@ -313,7 +323,7 @@ The training can be started with the executable \texttt{train.py}. %\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 +%moves. One module to read and write \acrshort{sgf} files. Modules are shown in %\fref{fig:modules}. % %\begin{figure}[h] @@ -322,3 +332,136 @@ 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} + +This section lists and explains the exact testing plan. + +\subsubsection{Unitary Testing} + +Tests for the Python code will be developed using the unittest +\cite{python_unittest} testing framework. It has been chosen by virtue of being +thoroughly documented and widely used. + +The coverage of unit testing will be checked with Coverage.py +\cite{python_coverage}, which can by itself run the unittest tests and generate +coverage reports based on the results. + +\subsubsection{Integration Testing} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.5\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Engine and Game modules}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} \\ + \midrule + The GTP interface of the engine is used to play a match & The module handles + the game and can show its state. \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.5\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Training and Engine module}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} \\ + \midrule + The training process is started & The training uses the network defined on + the Engine module. \\ + \bottomrule +\end{tabular} + +\subsubsection{System Testing} + +These are the tests to check the correct working of the system as a whole. The +tests are grouped by the interface they are run against. + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.5\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Game interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} \\ + \midrule + Play a game of Go with no engine & The game can be played until the end. \\ + \midrule + Provide a wrong move & The interface shows it is wrong and the game + continues without a change of state. \\ + \midrule + Close the game & The interface closes. \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.5\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Engine interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} \\ + \midrule + Ask for the available commands & The interface outputs the available + commands. \\ + \midrule + Provide a move & The state of the engine updates with the new move. \\ + \midrule + Ask for a move & The engine suggests a move without changing the state of + the current game. \\ + \bottomrule +\end{tabular} + +\vspace{\interclassSpace} + +\begin{tabular}{p{0.4\linewidth}p{0.5\linewidth}} + \toprule + \multicolumn{2}{c}{\textbf{Training interface}} \\ + \midrule + \textbf{Test} & \textbf{Expected behaviour} \\ + \midrule + Provide some games to train on & A neural network model is created. \\ + \midrule + Start the training without providing games & An error message is shown and + the execution terminated. \\ + \bottomrule +\end{tabular} + +\subsubsection{Usability Testing} + +Two different human users will be exposed to the interfaces of the project and +asked to answer a questionary about their experience. The aim of this process is +to identify and address any problems end users could have when using the +system. + +As the training of the neural networks is part of the preparation of the system, +its usability will not be tested for end users. + +These are the questions provided to the testers. + +\begin{itemize} + + \item Playing against a human: + \begin{itemize} + \item Were you able to start the interface? + \item How hard was the interface of the game to understand? + \end{itemize} + + \item Playing against the engine: + \begin{itemize} + \item Were you able to start the interface? + \item How hard was the interface of the game to understand? + \item How strong did you find the engine? + \end{itemize} + + \item Playing against the interface through a third-party \acrshort{gui}: + \begin{itemize} + \item Were you able to start the interface? + \item Did you find any problems when setting up the engine? + \item Do you think this tool has value for studying Go? + \end{itemize} + +\end{itemize} @@ -2,14 +2,17 @@ """Play Go!""" +import sys + from imago.engine.parseHelpers import parseVertex from imago.gameLogic.gameState import GameState -if __name__ == "__main__": +def runGame(): GAMESTATE = GameState(9) + gameEnded = False - while True: + while not gameEnded: GAMESTATE.getBoard().printBoard() @@ -19,11 +22,32 @@ if __name__ == "__main__": move = parseVertex(move, GAMESTATE.size) except Exception as err: print("Invalid move syntax. Example of move: A1") + print() continue + if move == "pass": + + GAMESTATE.playPass() + if GAMESTATE.lastMove.previousMove.isPass: + print("Both players passed: end of the game.") + gameEnded = True + + else: + moveRow = move[0] + moveCol = move[1] + try: + GAMESTATE.playMove(moveRow, moveCol) + except Exception as err: + print(err) + print() - moveRow = move[0] - moveCol = move[1] +if __name__ == "__main__": - GAMESTATE.playMove(moveRow, moveCol) + try: + runGame() + except KeyboardInterrupt as err: + print() + print("Quitting: End of the game.") + print() + sys.exit(0) diff --git a/imago/engine/core.py b/imago/engine/core.py index 2bf7d5a..0f88dfd 100644 --- a/imago/engine/core.py +++ b/imago/engine/core.py @@ -4,14 +4,16 @@ from imago.data.enums import DecisionAlgorithms from imago.engine.createDecisionAlgorithm import create as createDA from imago.gameLogic.gameState import GameState + DEF_SIZE = 9 DEF_KOMI = 5.5 DEF_ALGORITHM = DecisionAlgorithms.KERAS + class GameEngine: """Plays the game of Go.""" - def __init__(self, decisionAlgorithmId = DEF_ALGORITHM): + def __init__(self, decisionAlgorithmId=DEF_ALGORITHM): self.komi = DEF_KOMI self.gameState = GameState(DEF_SIZE) self.daId = decisionAlgorithmId diff --git a/imago/engine/imagoIO.py b/imago/engine/imagoIO.py index 9b3e367..75a1a99 100644 --- a/imago/engine/imagoIO.py +++ b/imago/engine/imagoIO.py @@ -5,40 +5,23 @@ import sys from imago.engine import parseHelpers from imago.engine.core import GameEngine -def _response(text=""): - print("= %s" % text) - print() - -def _responseError(text=""): - print("? %s" % text) - print() - -def protocol_version(_): - """Version of the GTP Protocol""" - _response("2") - -def name(_): - """Name of the engine""" - _response("Imago") - -def version(_): - """Version of the engine""" - _response("0.0.0") def getCoordsText(row, col): """Returns a string representation of row and col. In GTP A1 is bottom left corner. """ - return "%s%d" % (chr(65+row), col+1) + return "%s%d" % (chr(65 + row), col + 1) + class ImagoIO: """Recieves and handles commands.""" - def __init__(self, decisionAlgorithmId = None): + + def __init__(self, decisionAlgorithmId=None, outputStream=sys.stdout): self.commands_set = { - protocol_version, - name, - version, + self.protocol_version, + self.name, + self.version, self.known_command, self.list_commands, self.boardsize, @@ -49,9 +32,22 @@ class ImagoIO: self.set_free_handicap, self.play, self.genmove, - self.undo + self.undo, + self.showboard } self.gameEngine = GameEngine(decisionAlgorithmId) + self.outputStream = outputStream + + + def _response(self, text=""): + print("= %s" % text, file=self.outputStream) + print(file=self.outputStream) + + + def _responseError(self, text=""): + print("? %s" % text.replace('\n', '\n? '), file=self.outputStream) + print(file=self.outputStream) + def start(self): """Starts reading commands interactively.""" @@ -63,7 +59,8 @@ class ImagoIO: continue if input_tokens[0] == "quit": - sys.exit(0) + self._response() + break command = None for comm in self.commands_set: @@ -72,109 +69,139 @@ class ImagoIO: if command is not None: arguments = input_tokens[1:] - #print("[DEBUG]:Selected command: %s; args: %s" % (command, arguments)) command(arguments) else: - _responseError("unknown command") + self._responseError("unknown command") except Exception as err: - _responseError("An uncontrolled error ocurred. The error was: %s" % err) + self._responseError("Error: %s" % err) + def known_command(self, args): - """True if command is known, false otherwise""" + """True if command is known, false otherwise.""" if len(args) != 1: - _responseError("Wrong number of arguments.") - _responseError("Usage: known_command COMMAND_NAME") + self._responseError("Wrong number of arguments\n" + + "Usage: known_command COMMAND_NAME") return out = "false" for c in self.commands_set: if c.__name__ == args[0]: out = "true" - _response(out) + self._response(out) + def list_commands(self, _): - """List of commands, one per row""" + """List of commands, one per row.""" output = "" for c in self.commands_set: output += ("%s - %s\n" % (c.__name__, c.__doc__)) - _response(output) + output = output[:-1] # Remove last newline character + self._response(output) + + + def protocol_version(self, _): + """Version of the GTP Protocol.""" + self._response("2") + + + def name(self, _): + """Name of the engine.""" + self._response("Imago") + + + def version(self, _): + """Version of the engine.""" + self._response("0.0.0") + def boardsize(self, args): """Changes the size of the board. Board state, number of stones and move history become arbitrary. - It is wise to call clear_board after this command. - """ + It is wise to call clear_board after this command.""" if len(args) != 1: - _responseError("Wrong number of arguments") - _responseError("Usag. boardsize <newSize>") + self._responseError("Wrong number of arguments\n" + + "Usage: boardsize <newSize>") return size = int(args[0]) self.gameEngine.setBoardsize(size) - _response() + self._response() + def clear_board(self, _): """The board is cleared, the number of captured stones reset to zero and the move - history reset to empty. - """ + history reset to empty.""" self.gameEngine.clearBoard() - _response() + self._response() + def komi(self, args): """Sets a new value of komi.""" if len(args) != 1: - _responseError("Wrong number of arguments") - _responseError("Usage: komi <newKomi>") + self._responseError("Wrong number of arguments\n" + + "Usage: komi <newKomi>") return komi = float(args[0]) self.gameEngine.setKomi(komi) - _response() + self._response() + def fixed_handicap(self, args): """Handicap stones are placed on the board on standard vertices. - These vertices follow the GTP specification. - """ + These vertices follow the GTP specification.""" if len(args) != 1: - _responseError("Wrong number of arguments") - _responseError("Usage: fixed_handicap <count>") + self._responseError("Wrong number of arguments\n" + + "Usage: fixed_handicap <count>") return stones = float(args[0]) vertices = self.gameEngine.setFixedHandicap(stones) out = getCoordsText(vertices[0][0], vertices[0][1]) for vertex in vertices[1:]: out += " " + getCoordsText(vertex[0], vertex[1]) - _response(out) + self._response(out) + def place_free_handicap(self, args): """Handicap stones are placed on the board by the AI criteria.""" #TODO + def set_free_handicap(self, args): """Handicap stones are placed on the board as requested.""" #TODO + def play(self, args): """A stone of the requested color is played at the requested vertex.""" if len(args) != 2: - _responseError("Wrong number of arguments.") - _responseError("Usage: play <color> <vertex>") + self._responseError("Wrong number of arguments\n" + + "Usage: play <color> <vertex>") return - move = parseHelpers.parseMove(args, self.gameEngine.gameState.size) - self.gameEngine.play(move.color, move.vertex) - _response() + try: + move = parseHelpers.parseMove(args, self.gameEngine.gameState.size) + self.gameEngine.play(move.color, move.vertex) + self._response() + except Exception as err: + self._responseError("Invalid move: %s" % err) + def genmove(self, args): """A stone of the requested color is played where the engine chooses.""" if len(args) != 1: - _responseError("Wrong number of arguments.") - _responseError("Usage: genmove <color>") + self._responseError("Wrong number of arguments\n" + + "Usage: genmove <color>") return color = parseHelpers.parseColor(args[0]) output = parseHelpers.vertexToString(self.gameEngine.genmove(color), - self.gameEngine.gameState.size) - _response(output) - self.gameEngine.gameState.getBoard().printBoard() + self.gameEngine.gameState.size) + self._response(output) + def undo(self, _): """The board configuration and number of captured stones are reset to the state - before the last move, which is removed from the move history. - """ + before the last move, which is removed from the move history.""" self.gameEngine.undo() + self._response() + + + def showboard(self, _): + """Prints a representation of the board state.""" + self._response('\n%s' % self.gameEngine.gameState.getBoard().toString()) diff --git a/imago/engine/keras/convNeuralNetwork.py b/imago/engine/keras/convNeuralNetwork.py index 638e2fe..7e6e63c 100644 --- a/imago/engine/keras/convNeuralNetwork.py +++ b/imago/engine/keras/convNeuralNetwork.py @@ -43,7 +43,7 @@ class ConvNeuralNetwork(NeuralNetwork): ), ]) - model.summary() + #model.summary() model.compile( optimizer=Adam(learning_rate=0.0001), diff --git a/imago/engine/keras/denseNeuralNetwork.py b/imago/engine/keras/denseNeuralNetwork.py index 6a350f7..4b4c0e0 100644 --- a/imago/engine/keras/denseNeuralNetwork.py +++ b/imago/engine/keras/denseNeuralNetwork.py @@ -29,7 +29,7 @@ class DenseNeuralNetwork(NeuralNetwork): ), ]) - model.summary() + #model.summary() model.compile( optimizer=Adam(learning_rate=0.0001), diff --git a/imago/engine/keras/keras.py b/imago/engine/keras/keras.py index 871f4a0..b3061e8 100644 --- a/imago/engine/keras/keras.py +++ b/imago/engine/keras/keras.py @@ -34,7 +34,7 @@ class Keras(DecisionAlgorithm): if coords == "pass": self.currentMove = self.currentMove.addPass() else: - self.currentMove = self.currentMove.addMoveByCoords(coords) + self.currentMove = self.currentMove.addMove(coords) def pickMove(self): """Returns a move to play.""" @@ -47,3 +47,7 @@ class Keras(DecisionAlgorithm): """Empties move history.""" boardSize = self.currentMove.board.getBoardHeight() self.currentMove = GameMove(GameBoard(boardSize, boardSize)) + + +if __name__ == '__main__': + unittest.main() diff --git a/imago/engine/keras/neuralNetwork.py b/imago/engine/keras/neuralNetwork.py index c414a78..9d0b853 100644 --- a/imago/engine/keras/neuralNetwork.py +++ b/imago/engine/keras/neuralNetwork.py @@ -7,6 +7,9 @@ import os.path import numpy from matplotlib import pyplot +# Disable TensorFlow importing warnings +os.environ['TF_CPP_MIN_LOG_LEVEL'] = '3' + from tensorflow.keras.models import load_model from tensorflow.keras.utils import plot_model @@ -28,12 +31,12 @@ class NeuralNetwork: self.model = self._loadModel(self.path) except FileNotFoundError: self.model = self._initModel(boardSize) - self.saveModelPlot("model.png") + #self.saveModelPlot("model.png") def _initModel(self, boardSize=DEF_BOARD_SIZE): raise NotImplementedError("Tried to directly use NeuralNetwork class. Use one of the subclasses instead.") - def trainModel(self, games): + def trainModel(self, games, epochs=20, verbose=2): trainMoves = [] targets = [] for game in games: @@ -48,14 +51,14 @@ class NeuralNetwork: y=targets, validation_split=0.1, batch_size=1, - epochs=20, + epochs=epochs, shuffle=False, - verbose=2 + verbose=verbose ) def _loadModel(self, modelPath): # Load model - if os.path.isfile(modelPath): + if os.path.isfile(modelPath) or os.path.isdir(modelPath): return load_model(modelPath) else: raise FileNotFoundError("Keras neural network model file not found at %s" @@ -145,7 +148,7 @@ class NeuralNetwork: return self.model.predict( x = sampleBoards, batch_size = 1, - verbose = 2) + verbose = 0) def _saveHeatmap(self, data, passChance): rows = len(data) diff --git a/imago/engine/monteCarlo.py b/imago/engine/monteCarlo.py index baaaba8..ee8380a 100644 --- a/imago/engine/monteCarlo.py +++ b/imago/engine/monteCarlo.py @@ -11,26 +11,30 @@ class MCTS(DecisionAlgorithm): def __init__(self, move): self.root = MCTSNode(move, None) + self.expansions = 5 + self.simulationsPerExpansion = 10 + self.debug = False - def forceNextMove(self, coords): + def forceNextMove(self, coords: tuple): """Selects given move as next move.""" - if coords == "pass": - raise NotImplementedError("Pass not implemented for MCTS algorithm.") for node in self.root.children: - if (node.move.getRow() == coords[0] - and node.move.getCol() == coords[1]): + if (node.move.isPass and coords == "pass" or + node.move.getRow() == coords[0] + and node.move.getCol() == coords[1]): self.root = node return self.root = self.root.expansionForCoords(coords) def pickMove(self): """ - Performs an exploratory cycle, updates the root to the best node and returns its - corresponding move.""" + Performs an exploratory cycle and returns the coordinates of the picked move.""" #NOTE: with only one selection-expansion the match is # completely random - for _ in range(5): - self.root.selection().expansion().simulation(10, 20) + for _ in range(self.expansions): + self.root\ + .selection()\ + .expansion()\ + .simulation(self.simulationsPerExpansion, 20, self.debug) selectedNode = self._selectBestNextNode() return selectedNode.move.coords @@ -63,6 +67,7 @@ class MCTSNode: self.parent = parent self.children = set() self.unexploredVertices = move.getPlayableVertices() + self.unexploredVertices.add("pass") def ucbForPlayer(self): """ @@ -133,17 +138,17 @@ class MCTSNode: """ Adds a move for the given coordinates as a new node to the children of this node.""" - newMove = self.move.addMove(coords[0], coords[1]) + newMove = self.move.addMove(coords) newNode = MCTSNode(newMove, self) self.children.add(newNode) - self.unexploredVertices.remove((coords[0], coords[1])) + self.unexploredVertices.remove(coords) return newNode - def simulation(self, nMatches, scoreDiffHeur): + def simulation(self, nMatches, scoreDiffHeur, debug=False): """Play random matches to accumulate reward information on the node.""" scoreAcc = 0 for _ in range(nMatches): - result = self._randomMatch(scoreDiffHeur) + result = self._randomMatch(scoreDiffHeur, debug) self.visits += 1 scoreDiff = result[0]-result[1] if scoreDiff != 0: @@ -155,10 +160,10 @@ class MCTSNode: node.visits += nMatches node = node.parent - def _randomMatch(self, scoreDiffHeur): + def _randomMatch(self, scoreDiffHeur, debug=False): """Play a random match and return the resulting score.""" - #IMPORTANT: the score heuristic doesn't work for the first move of the game, since - #the black player holds all except for one vertex! + #NOTE: IMPORTANT: the score heuristic doesn't work for the first move of the game, + # since the black player holds all except for one vertex! currentMove = self.move score = currentMove.board.score() while currentMove.getGameLength() < 5 or abs(score[0] - score[1]) < scoreDiffHeur: @@ -169,16 +174,19 @@ class MCTSNode: currentMove = currentMove.addPass() else: selectedMove = random.choice(list(sensibleMoves)) - currentMove = currentMove.addMoveByCoords(selectedMove) + currentMove = currentMove.addMove(selectedMove) score = currentMove.board.score() - print("Current move: %s" % (str(currentMove))) - print("Current move game length: ", currentMove.getGameLength()) - print("Score of the board: %d, %d (%d)" - % (score[0], - score[1], - score[0]-score[1]) - ) - currentMove.printBoard() + + if debug: + print("Current move: %s" % (str(currentMove))) + print("Current move game length: ", currentMove.getGameLength()) + print("Score of the board: %d, %d (%d)" + % (score[0], + score[1], + score[0]-score[1]) + ) + currentMove.printBoard() + return score def _printBoardInfo(self): diff --git a/imago/engine/parseHelpers.py b/imago/engine/parseHelpers.py index fc42845..64342d3 100644 --- a/imago/engine/parseHelpers.py +++ b/imago/engine/parseHelpers.py @@ -19,7 +19,7 @@ def parseMove(args, boardsize): """Converts the textual representation of a move to a move instance.""" if len(args) != 2: raise RuntimeError( - "Unable to transform string %s to move: Wrong format." + "Unable to transform string [%s] to move: Wrong format." % args) color = parseColor(args[0]) vertex = parseVertex(args[1], boardsize) @@ -32,7 +32,7 @@ def parseColor(text): return Player.WHITE if textUpper in VALID_BLACK_STRINGS: return Player.BLACK - raise RuntimeError("Unknown color %s." % text) + raise RuntimeError("Unknown color [%s]." % text) def parseVertex(text, boardSize): """Returns row and column of a vertex given its input string. A vertex can also be the @@ -47,7 +47,7 @@ def parseVertex(text, boardSize): if text == "PASS": return "pass" raise RuntimeError( - "Unable to transform string %s to vertex. Wrong format." + "Unable to transform string [%s] to vertex. Wrong format." % text) vertexCol = ord(text[0]) @@ -61,10 +61,10 @@ def parseVertex(text, boardSize): if (vertexCol < 0 or vertexRow < 0 or vertexCol >= boardSize or vertexRow >= boardSize): raise RuntimeError( - "Unable to transform string %s to vertex. Maps to [%d, %d], which is out of board bounds (size %d)" + "Unable to transform string [%s] to vertex. Maps to [%d, %d], which is out of board bounds (size [%d])" % (text, vertexCol, vertexRow, boardSize)) - return [vertexRow, vertexCol] + return (vertexRow, vertexCol) def vertexToString(vertex, boardSize): """Returns a string representing the vertex. @@ -76,11 +76,11 @@ def vertexToString(vertex, boardSize): return "pass" if len(vertex) != 2: raise RuntimeError( - "Unable to transform vertex %s to string. Too many elements." + "Unable to transform vertex [%s] to string. Too many elements." % str(vertex)) if vertex[0] >= boardSize or vertex[1] >= boardSize or vertex[0] < 0 or vertex[1] < 0: raise RuntimeError( - "Unable to transform vertex %s to string. Vertex out of board bounds (size %d)" + "Unable to transform vertex [%s] to string. Vertex out of board bounds (size [%d])" % (str(vertex), boardSize)) vertexRow = boardSize - vertex[0] diff --git a/imago/gameLogic/gameBoard.py b/imago/gameLogic/gameBoard.py index 611c4cb..d0e22a6 100644 --- a/imago/gameLogic/gameBoard.py +++ b/imago/gameLogic/gameBoard.py @@ -110,9 +110,12 @@ class GameBoard: containing the vertices where stones were captured. """ - if (row < 0 or row >= self.getBoardHeight() - or col < 0 or col >= self.getBoardWidth()): - raise RuntimeError("[ERROR] Move and capture: out of bounds (%d, %d)" % (row, col)) + try: + if (row < 0 or row >= self.getBoardHeight() + or col < 0 or col >= self.getBoardWidth()): + raise RuntimeError("[ERROR] Move and capture: out of bounds (%d, %d)" % (row, col)) + except Exception as err: + raise RuntimeError("[ERROR] Move and capture: Wrong input: %s" % err) self.board[row][col] = player @@ -273,8 +276,8 @@ class GameBoard: return False return True - def printBoard(self): - """Print the board.""" + def toString(self): + """Returns a representation of the state of the board as a string.""" colTitle = 'A' rowTitlePadding = 2 if self.getBoardHeight() >= 10: @@ -289,7 +292,7 @@ class GameBoard: colTitle = chr(ord(colTitle)+1) if colTitle == "I": # Skip I colTitle = "J" - print(rowText) + output = rowText # Print rows rowTitle = self.getBoardHeight() @@ -297,11 +300,17 @@ class GameBoard: rowText = "" for col in row: rowText += cellToString(col) + " " - print(str(rowTitle) + " " * rowTitlePadding + rowText) + output += '\n%d%s%s' % (rowTitle, " " * rowTitlePadding, rowText) rowTitle -= 1 if rowTitle == 9: rowTitlePadding += 1 + return output + + def printBoard(self): + """Print the board.""" + print(self.toString()) + def cellToString(code): """Returns the text representation of a cell.""" if code == Player.WHITE: diff --git a/imago/gameLogic/gameData.old b/imago/gameLogic/gameData.old new file mode 100644 index 0000000..f23723f --- /dev/null +++ b/imago/gameLogic/gameData.old @@ -0,0 +1,52 @@ +"""Invariable data pertaining a match.""" + +#class GameData: + """Invariable data pertaining a match.""" + +# Obsolete method of storing properties +# def __init__(self, +# name = None, +# size = 19, +# annotator = None, +# date = None, +# blackRank = "?", +# whiteRank = "?", +# blackName = None, +# whiteName = None, +# blackTeam = None, +# whiteTeam = None, +# copyrightInfo = None, +# event = None, +# gameComment = None, +# openingInfo = None, +# timeInfo = None, +# overtimeInfo = None, +# placeInfo = None, +# result = "?", +# roundInfo = None, +# rules = None, +# source = None, +# user = None +# ): +# self.name = name +# self.size = size +# self.annotator = annotator +# self.date = date +# self.blackRank = blackRank +# self.whiteRank = whiteRank +# self.blackName = blackName +# self.whiteName = whiteName +# self.blackTeam = blackTeam +# self.whiteTeam = whiteTeam +# self.copyrightInfo = copyrightInfo +# self.event = event +# self.gameComment = gameComment +# self.openingInfo = openingInfo +# self.timeInfo = timeInfo +# self.overtimeInfo = overtimeInfo +# self.placeInfo = placeInfo +# self.result = result +# self.roundInfo = roundInfo +# self.rules = rules +# self.source = source +# self.user = user diff --git a/imago/gameLogic/gameData.py b/imago/gameLogic/gameData.py deleted file mode 100644 index 6cc4d7e..0000000 --- a/imago/gameLogic/gameData.py +++ /dev/null @@ -1,51 +0,0 @@ -"""Invariable data pertaining a match.""" - -class GameData: - """Invariable data pertaining a match.""" - - def __init__(self, - name = None, - size = 19, - annotator = None, - date = None, - blackRank = "?", - whiteRank = "?", - blackName = None, - whiteName = None, - blackTeam = None, - whiteTeam = None, - copyrightInfo = None, - event = None, - gameComment = None, - openingInfo = None, - timeInfo = None, - overtimeInfo = None, - placeInfo = None, - result = "?", - roundInfo = None, - rules = None, - source = None, - user = None - ): - self.name = name - self.size = size - self.annotator = annotator - self.date = date - self.blackRank = blackRank - self.whiteRank = whiteRank - self.blackName = blackName - self.whiteName = whiteName - self.blackTeam = blackTeam - self.whiteTeam = whiteTeam - self.copyrightInfo = copyrightInfo - self.event = event - self.gameComment = gameComment - self.openingInfo = openingInfo - self.timeInfo = timeInfo - self.overtimeInfo = overtimeInfo - self.placeInfo = placeInfo - self.result = result - self.roundInfo = roundInfo - self.rules = rules - self.source = source - self.user = user diff --git a/imago/gameLogic/gameMove.py b/imago/gameLogic/gameMove.py index c1c7a05..b6f2947 100644 --- a/imago/gameLogic/gameMove.py +++ b/imago/gameLogic/gameMove.py @@ -84,14 +84,15 @@ class GameMove: vertices.add((row, col)) return vertices - def addMoveByCoords(self, coords): + def addMove(self, coords): """Adds a move to the next moves list creating its board from this move's board plus a new stone at the specified coordinates. """ - return self.addMove(coords[0], coords[1]) + if coords == "pass": + return self.addPass() + return self.addMoveByCoords(coords[0], coords[1]) - - def addMove(self, row, col): + def addMoveByCoords(self, row, col): """Adds a move to the next moves list creating its board from this move's board plus a new stone at the specified row and column. """ diff --git a/imago/gameLogic/gameState.py b/imago/gameLogic/gameState.py index 72b91b4..c577713 100644 --- a/imago/gameLogic/gameState.py +++ b/imago/gameLogic/gameState.py @@ -40,32 +40,31 @@ class GameState: def playMoveForPlayer(self, row, col, player): """Execute a move on the board for the given player.""" + # Check a last move already exists + if self.lastMove is None: + raise RuntimeError("Last move of the GameState is None.") + prevBoards = self.lastMove.getThisAndPrevBoards() playable, message = self.lastMove.board.isPlayable(row, col, player, prevBoards) if playable: self._addMove(player, row, col) return True - print("Invalid Move! %s" % message) + raise Exception("Invalid Move. %s" % message) return False def playPass(self): """Passes the turn for the player who should make a move.""" - self.lastMove.addPass() + self.lastMove = self.lastMove.addPass() def passForPlayer(self, player): """Passes the turn for the given player.""" - self.lastMove.addPassForPlayer(player) + self.lastMove = self.lastMove.addPassForPlayer(player) def undo(self): """Sets the move before the last move as the new last move.""" self.lastMove = self.lastMove.previousMove def _addMove(self, player, row, col): - - # Check a last move already exists - if self.lastMove is None: - raise RuntimeError("Last move of the GameState is None.") - # Add and return the new move self.lastMove = self.lastMove.addMoveForPlayer(row, col, player) return self.lastMove diff --git a/imago/sgfParser/astNode.py b/imago/sgfParser/astNode.py index 41629ce..5071483 100644 --- a/imago/sgfParser/astNode.py +++ b/imago/sgfParser/astNode.py @@ -1,4 +1,4 @@ -from imago.gameLogic.gameData import GameData +#from imago.gameLogic.gameData import GameData from imago.gameLogic.gameMove import GameMove from imago.gameLogic.gameBoard import GameBoard from imago.data.enums import Player @@ -22,64 +22,6 @@ class ASTNode: children = children[0].children children.append(move) - def toGameTree(self): - """Converts this node and its subtree into a GameTree""" - gameData = GameData() - for prop in self.props: - if prop.name == "GM": # Type of game, 1 is Go - if prop.value != 1: - print("ERROR") # TODO: Error handling - if prop.name == "SZ": # Size of board. [19] for squared, [10:12] for rect. - gameData.size = prop.value - if prop.name == "AN": # Annotator - gameData.annotator = prop.value - if prop.name == "BR": # Rank of black player - gameData.blackRank = prop.value - if prop.name == "WR": # Rank of white player - gameData.whiteRank = prop.value - if prop.name == "PB": # Name of black player - gameData.blackName = prop.value - if prop.name == "PW": # Name of white player - gameData.whiteName = prop.value - if prop.name == "BT": # Name of black team - gameData.blackTeam = prop.value - if prop.name == "WT": # Name of white team - gameData.whiteTeam = prop.value - if prop.name == "CP": # Copyright information - gameData.copyright = prop.value - if prop.name == "DT": # Date - gameData.date = prop.value - if prop.name == "EV": # Event information - gameData.event = prop.value - if prop.name == "GN": # Game nae - gameData.name = prop.value - if prop.name == "GC": # Extra game comment - gameData.gameComment = prop.value - if prop.name == "ON": # Description of opening played - gameData.openingInfo = prop.value - if prop.name == "OT": # Overtime method - gameData.overtimeInfo = prop.value - if prop.name == "PC": # Place where the game took place - gameData.place = prop.value - if prop.name == "RE": # Result of the game - gameData.result = prop.value - if prop.name == "RO": # Round number and type - gameData.roundInfo = prop.value - if prop.name == "RU": # Rules used for the game - gameData.rules = prop.value - if prop.name == "SO": # Source of the game - gameData.source = prop.source - if prop.name == "TM": # Time limit in seconds - gameData.timeInfo = prop.source - if prop.name == "US": # User or program which entered the game - gameData.user = prop.source - - firstMoves = [] - for child in self.children: - firstMoves.append(child.toGameMoveTree(size)) - - return GameTree(firstMoves, gameData) - def toGameMoveTree(self, previousMove=None): if previousMove is None: # Game root node @@ -138,6 +80,65 @@ def textToCoords(text): # Poner en PropertyMove, subclase de Property row = ord(text[1]) - ord('a') return [row, col] + # Obsolete method of storing properties + #def toGameTree(self): + # """Converts this node and its subtree into a GameTree""" + # gameData = GameData() + # for prop in self.props: + # if prop.name == "GM": # Type of game, 1 is Go + # if prop.value != 1: + # print("ERROR") # TODO: Error handling + # if prop.name == "SZ": # Size of board, [19] for squared, [10:12] for rect. + # gameData.size = prop.value + # if prop.name == "AN": # Annotator + # gameData.annotator = prop.value + # if prop.name == "BR": # Rank of black player + # gameData.blackRank = prop.value + # if prop.name == "WR": # Rank of white player + # gameData.whiteRank = prop.value + # if prop.name == "PB": # Name of black player + # gameData.blackName = prop.value + # if prop.name == "PW": # Name of white player + # gameData.whiteName = prop.value + # if prop.name == "BT": # Name of black team + # gameData.blackTeam = prop.value + # if prop.name == "WT": # Name of white team + # gameData.whiteTeam = prop.value + # if prop.name == "CP": # Copyright information + # gameData.copyright = prop.value + # if prop.name == "DT": # Date + # gameData.date = prop.value + # if prop.name == "EV": # Event information + # gameData.event = prop.value + # if prop.name == "GN": # Game nae + # gameData.name = prop.value + # if prop.name == "GC": # Extra game comment + # gameData.gameComment = prop.value + # if prop.name == "ON": # Description of opening played + # gameData.openingInfo = prop.value + # if prop.name == "OT": # Overtime method + # gameData.overtimeInfo = prop.value + # if prop.name == "PC": # Place where the game took place + # gameData.place = prop.value + # if prop.name == "RE": # Result of the game + # gameData.result = prop.value + # if prop.name == "RO": # Round number and type + # gameData.roundInfo = prop.value + # if prop.name == "RU": # Rules used for the game + # gameData.rules = prop.value + # if prop.name == "SO": # Source of the game + # gameData.source = prop.source + # if prop.name == "TM": # Time limit in seconds + # gameData.timeInfo = prop.source + # if prop.name == "US": # User or program which entered the game + # gameData.user = prop.source + # + # firstMoves = [] + # for child in self.children: + # firstMoves.append(child.toGameMoveTree()) + # + # return GameTree(firstMoves, gameData) + class Property: """Property of a Node""" diff --git a/imagocli.py b/imagocli.py index 5f14380..d660195 100755 --- a/imagocli.py +++ b/imagocli.py @@ -14,12 +14,15 @@ if __name__ == "__main__": if sys.argv[1] == "-e": if sys.argv[2] == "montecarlo": decisionAlgorithm = DecisionAlgorithms.MONTECARLO - if sys.argv[2] == "keras": + elif sys.argv[2] == "keras": decisionAlgorithm = DecisionAlgorithms.KERAS - if sys.argv[2] == "dense": + elif sys.argv[2] == "dense": decisionAlgorithm = DecisionAlgorithms.DENSE - if sys.argv[2] == "conv": + elif sys.argv[2] == "conv": decisionAlgorithm = DecisionAlgorithms.CONV + else: + print('Invalid algorithm "%s"' % sys.argv[2]) + sys.exit(1) if decisionAlgorithm is None: io = ImagoIO() diff --git a/tests/test_enums.py b/tests/test_enums.py index 73f4009..21b2057 100644 --- a/tests/test_enums.py +++ b/tests/test_enums.py @@ -5,7 +5,7 @@ import unittest from imago.data.enums import Player class TestEnums(unittest.TestCase): - """Test parseHelpers module.""" + """Test enums module.""" def testOtherPlayer(self): """Test method to get the other player""" diff --git a/tests/test_gameBoard.py b/tests/test_gameBoard.py index 8a7b127..c7808ac 100644 --- a/tests/test_gameBoard.py +++ b/tests/test_gameBoard.py @@ -114,5 +114,33 @@ class TestGameBoard(unittest.TestCase): board.board[9][0] = Player.WHITE self.assertEqual((9, 21), board.score()) + def testToString(self): + """Test formatting of the board as a string.""" + + board = GameBoard(9, 9) + self.assertEqual(' A B C D E F G H J \n\ +9 · · · · · · · · · \n\ +8 · · · · · · · · · \n\ +7 · · · · · · · · · \n\ +6 · · · · · · · · · \n\ +5 · · · · · · · · · \n\ +4 · · · · · · · · · \n\ +3 · · · · · · · · · \n\ +2 · · · · · · · · · \n\ +1 · · · · · · · · · ', board.toString()) + + board.moveAndCapture(2, 6, Player.BLACK) + board.moveAndCapture(5, 4, Player.WHITE) + self.assertEqual(' A B C D E F G H J \n\ +9 · · · · · · · · · \n\ +8 · · · · · · · · · \n\ +7 · · · · · · B · · \n\ +6 · · · · · · · · · \n\ +5 · · · · · · · · · \n\ +4 · · · · W · · · · \n\ +3 · · · · · · · · · \n\ +2 · · · · · · · · · \n\ +1 · · · · · · · · · ', board.toString()) + if __name__ == '__main__': unittest.main() diff --git a/tests/test_gameMove.py b/tests/test_gameMove.py index 6569c5b..a7edfab 100644 --- a/tests/test_gameMove.py +++ b/tests/test_gameMove.py @@ -18,13 +18,13 @@ class TestGameMove(unittest.TestCase): self.assertIsNone(firstMove.coords) - secondMove = firstMove.addMove(1, 2) + secondMove = firstMove.addMoveByCoords(1, 2) self.assertIsNone(firstMove.coords) self.assertEqual(secondMove.coords[0], 1) self.assertEqual(secondMove.coords[1], 2) - thirdMove = secondMove.addMove(5, 7) + thirdMove = secondMove.addMoveByCoords(5, 7) self.assertIsNone(firstMove.coords) self.assertIsNone(thirdMove.previousMove.previousMove.coords) @@ -66,7 +66,7 @@ class TestGameMove(unittest.TestCase): (2,0), (2,1), (2,2))) ) - secondMove = firstMove.addMove(1, 2) + secondMove = firstMove.addMoveByCoords(1, 2) self.assertSetEqual( secondMove.getPlayableVertices(), set(((0,0), (0,1), (0,2), diff --git a/tests/test_gameState.py b/tests/test_gameState.py new file mode 100644 index 0000000..1c6b997 --- /dev/null +++ b/tests/test_gameState.py @@ -0,0 +1,89 @@ +"""Tests for the input/output component.""" + +import unittest + +from imago.data.enums import Player +from imago.gameLogic.gameState import GameState + +class TestGameState(unittest.TestCase): + """Test GameState component.""" + + def testCurrentPlayer(self): + """Test simple commands.""" + size = 9 + state = GameState(size) + + self.assertEqual(state.getCurrentPlayer(), Player.BLACK) + self.assertEqual(state.getPlayerCode(), 'B') + + state.playMove(0, 0) + self.assertEqual(state.getCurrentPlayer(), Player.WHITE) + self.assertEqual(state.getPlayerCode(), 'W') + + def testPlays(self): + """Test simple commands.""" + size = 3 + state = GameState(size) + + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.playMove(1, 1) + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.BLACK, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.playPass() + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.BLACK, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.undo() + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.BLACK, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.undo() + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.passForPlayer(Player.WHITE) + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + + self.assertRaises(Exception, state.playMove, -1, -1) + self.assertEqual(state.getBoard().getBoard(), + [ + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY], + [Player.EMPTY, Player.EMPTY, Player.EMPTY] + ]) + + state.lastMove = None + self.assertEqual(state.getCurrentPlayer(), Player.BLACK) + self.assertRaises(RuntimeError, state.playMove, 0, 0) + +if __name__ == '__main__': + unittest.main() diff --git a/tests/test_imagoIO.py b/tests/test_imagoIO.py new file mode 100644 index 0000000..499fdb2 --- /dev/null +++ b/tests/test_imagoIO.py @@ -0,0 +1,201 @@ +"""Tests for the input/output component.""" + +import unittest + +import io +import sys + +from imago.data.enums import DecisionAlgorithms +from imago.engine.imagoIO import ImagoIO +from imago.engine.parseHelpers import parseVertex + +class TestImagoIO(unittest.TestCase): + """Test ImagoIO component.""" + + @unittest.mock.patch('imago.engine.imagoIO.input', create=True) + def testSimpleCommands(self, mocked_input): + """Test simple commands.""" + + self.maxDiff = None + + mocked_input.side_effect = [ + '\n', + 'name\n', + 'version\n', + 'protocol_version\n', + 'clear_board\n', + '\n', + 'known_command\n', + 'known_command name\n', + 'known_command version\n', + 'known_command wrongcommand\n', + '\n', + 'boardsize\n', + 'boardsize 10\n', + '\n', + 'komi\n', + 'komi 5.5\n', + '\n', + 'play\n', + 'play 1\n', + 'play 1 2\n', + 'play b a1\n', + '\n', + 'undo\n', + 'undo\n', + '\n', + 'wrongcommand\n', + '\n', + 'quit\n' + ] + + testout = io.StringIO() + imagoIO = ImagoIO( + decisionAlgorithmId=DecisionAlgorithms.MONTECARLO, + outputStream=testout + ) + + imagoIO.start() + value = testout.getvalue() + self.assertEqual( + '= Imago\n\n' + + '= 0.0.0\n\n' + + '= 2\n\n' + + '= \n\n' + + '? Wrong number of arguments\n' + + '? Usage: known_command COMMAND_NAME\n\n' + + '= true\n\n' + + '= true\n\n' + + '= false\n\n' + + '? Wrong number of arguments\n' + + '? Usage: boardsize <newSize>\n\n' + + '= \n\n' + + '? Wrong number of arguments\n' + + '? Usage: komi <newKomi>\n\n' + + '= \n\n' + + '? Wrong number of arguments\n' + + '? Usage: play <color> <vertex>\n\n' + + '? Wrong number of arguments\n' + + '? Usage: play <color> <vertex>\n\n' + + '? Invalid move: Unknown color [1].\n\n' + + '= \n\n' + + '= \n\n' + + '= \n\n' + + '? unknown command\n\n' + + '= \n\n', + value + ) + + testout.close() + + + @unittest.mock.patch('imago.engine.imagoIO.input', create=True) + def testListsCommands(self, mocked_input): + """Test command for listing all commands.""" + + mocked_input.side_effect = [ + 'list_commands\n', + 'quit\n' + ] + + testout = io.StringIO() + imagoIO = ImagoIO( + decisionAlgorithmId=DecisionAlgorithms.MONTECARLO, + outputStream=testout + ) + + commandsString = "\n".join(list(map( + lambda cmd: "%s - %s" % (cmd.__name__, cmd.__doc__), + imagoIO.commands_set))) + + imagoIO.start() + value = testout.getvalue() + self.assertEqual( + '= ' + + commandsString + + '\n\n' + + '= \n\n', + value + ) + + testout.close() + + + @unittest.mock.patch('imago.engine.imagoIO.input', create=True) + def testFixedHandicap(self, mocked_input): + """Test command for setting fixed handicap stones.""" + + mocked_input.side_effect = [ + 'fixed_handicap\n', + 'fixed_handicap 2\n', + 'quit\n' + ] + + testout = io.StringIO() + imagoIO = ImagoIO( + decisionAlgorithmId=DecisionAlgorithms.MONTECARLO, + outputStream=testout + ) + + imagoIO.start() + value = testout.getvalue() + self.assertEqual( + '? Wrong number of arguments\n' + + '? Usage: fixed_handicap <count>\n\n' + + '= A1 A2\n\n' + + '= \n\n', + value + ) + + testout.close() + + +# @unittest.mock.patch('imago.engine.imagoIO.input', create=True) +# def testGenmove(self, mocked_input): +# """Test command for generating a move.""" +# +# mocked_input.side_effect = [ +# 'genmove\n', +# 'genmove w w\n', +# 'genmove 2\n', +# 'quit\n' +# ] +# +# testout = io.StringIO() +# imagoIO = ImagoIO( +# decisionAlgorithmId=DecisionAlgorithms.MONTECARLO, +# outputStream=testout +# ) +# +# imagoIO.start() +# value = testout.getvalue() +# self.assertEqual( +# '? Wrong number of arguments\n' + +# '? Usage: genmove <color>\n\n' + +# '? Wrong number of arguments\n' + +# '? Usage: genmove <color>\n\n' + +# '? Error: Unknown color [2].\n\n', +# value +# ) +# +# mocked_input.side_effect = [ +# 'genmove w\n', +# 'quit\n'] +# +# testout = io.StringIO() +# imagoIO = ImagoIO( +# decisionAlgorithmId=DecisionAlgorithms.MONTECARLO, +# outputStream=testout +# ) +# imagoIO.start() +# value = testout.getvalue() +# vertexValue = value.split(' ')[1].split('\n')[0] +# +# # Test parsing vertex does not raise an error +# parseVertex(vertexValue, imagoIO.gameEngine.gameState.size) +# +# testout.close() + + +if __name__ == '__main__': + unittest.main() diff --git a/tests/test_monteCarlo.py b/tests/test_monteCarlo.py index b217cf9..9d1fcfc 100644 --- a/tests/test_monteCarlo.py +++ b/tests/test_monteCarlo.py @@ -2,6 +2,7 @@ import unittest +from imago.engine.decisionAlgorithm import DecisionAlgorithm from imago.gameLogic.gameState import GameState from imago.engine.monteCarlo import MCTS from imago.engine.monteCarlo import MCTSNode @@ -17,8 +18,55 @@ class TestMonteCarlo(unittest.TestCase): tree = MCTS(state.lastMove) #print(tree.pickMove().toString()) + def testForceNextMove(self): + """Test forcing next move.""" + + # Next move before expansion (no children nodes) + state = GameState(TEST_BOARD_SIZE) + tree = MCTS(state.lastMove) + self.assertEqual(set(), tree.root.children) + tree.forceNextMove((0, 1)) + self.assertEqual(set(), tree.root.children) + + # Next move after expansion (with children nodes) + tree.expansions = 2 + tree.simulationsPerExpansion = 2 + tree.pickMove() + self.assertEqual(tree.expansions, len(tree.root.children)) + nextMoveCoords = list(tree.root.children)[0].move.coords + tree.forceNextMove(nextMoveCoords) + + def testPass(self): + """Test passing as next move.""" + state = GameState(TEST_BOARD_SIZE) + tree = MCTS(state.lastMove) + self.assertFalse(tree.root.move.isPass) + tree.forceNextMove("pass") + self.assertTrue(tree.root.move.isPass) + + def testClearBoard(self): + """Test clearing board returns root to original and retains information.""" + state = GameState(TEST_BOARD_SIZE) + tree = MCTS(state.lastMove) + + firstMoveCoords = (0,0) + secondMoveCoords = (1,0) + thirdMoveCoords = (0,1) + + tree.forceNextMove(firstMoveCoords) + tree.forceNextMove(secondMoveCoords) + tree.forceNextMove(thirdMoveCoords) + tree.clearBoard() + + nextNode = list(tree.root.children)[0] + self.assertEqual(firstMoveCoords, nextNode.move.coords) + nextNode = list(nextNode.children)[0] + self.assertEqual(secondMoveCoords, nextNode.move.coords) + nextNode = list(nextNode.children)[0] + self.assertEqual(thirdMoveCoords, nextNode.move.coords) + #def testSimulation(self): - # """Test calculation of group liberties.""" + # """Test Monte Carlo simulation.""" # board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) # move = GameMove(board) # node = MCTSNode(move, None) diff --git a/tests/test_neuralNetwork.py b/tests/test_neuralNetwork.py new file mode 100644 index 0000000..42ba4a1 --- /dev/null +++ b/tests/test_neuralNetwork.py @@ -0,0 +1,83 @@ +"""Tests for neural network module.""" + +import os +import shutil +import unittest + +from imago.data.enums import DecisionAlgorithms +from imago.sgfParser.sgf import loadGameTree +from imago.gameLogic.gameState import GameState +from imago.engine.keras.neuralNetwork import NeuralNetwork +from imago.engine.keras.denseNeuralNetwork import DenseNeuralNetwork +from imago.engine.keras.convNeuralNetwork import ConvNeuralNetwork +from imago.engine.keras.keras import Keras + +class TestNeuralNetwork(unittest.TestCase): + """Test neural network module.""" + + def testLoadBaseClass(self): + """Test error when creating model with the base NeuralNetwork class""" + + self.assertRaises(NotImplementedError, + NeuralNetwork, + "non/existing/file") + + def testNetworks(self): + """Test creation of initial model for dense neural network""" + + testModel = 'testModel' + testModelPlot = 'testModelPlot' + + games = [] + for file in [ + '../collections/minigo/matches/1.sgf', + '../collections/minigo/matches/2.sgf', + '../collections/minigo/matches/3.sgf' + ]: + games.append(loadGameTree(file)) + matches = [game.getMainLineOfPlay() for game in games] + + nn = DenseNeuralNetwork(modelPath=testModel, boardSize=9) + nn.trainModel(matches, epochs=1, verbose=0) + + game = GameState(9) + nn.pickMove(game.lastMove, game.getCurrentPlayer()) + + nn.saveModel(testModel) + self.assertTrue(os.path.isdir(testModel)) + shutil.rmtree(testModel, ignore_errors=True) + + nn.saveModel() + self.assertTrue(os.path.isdir(testModel)) + nn = DenseNeuralNetwork(modelPath=testModel, boardSize=9) + + nn.saveModelPlot(testModelPlot) + self.assertTrue(os.path.isfile(testModelPlot)) + + shutil.rmtree(testModel, ignore_errors=True) + os.remove(testModelPlot) + + nn = ConvNeuralNetwork(testModel, boardSize=9) + + def testKeras(self): + """Test keras model loading.""" + + gameState = GameState(9) + move = gameState.lastMove + + keras = Keras(move) + keras.forceNextMove("pass") + + keras = Keras(move, DecisionAlgorithms.DENSE) + keras.forceNextMove((3,3)) + + keras = Keras(move, DecisionAlgorithms.CONV) + self.assertRaises(RuntimeError, keras.forceNextMove, "wrongmove") + pickedCoords = keras.pickMove() + self.assertTrue(len(pickedCoords) == 2 or pickedCoords == "pass") + + self.assertRaises(RuntimeError, Keras, move, DecisionAlgorithms.MONTECARLO) + + +if __name__ == '__main__': + unittest.main() diff --git a/tests/test_parseHelpers.py b/tests/test_parseHelpers.py index 7bbf152..c1405fb 100644 --- a/tests/test_parseHelpers.py +++ b/tests/test_parseHelpers.py @@ -26,7 +26,7 @@ class TestParseHelpers(unittest.TestCase): ) parsedMove = parseHelpers.parseMove(["B", "t1"], TEST_BOARD_SIZE) - targetMove = parseHelpers.GtpMove(Player.BLACK, [18, 18]) + targetMove = parseHelpers.GtpMove(Player.BLACK, (18, 18)) self.assertEqual(parsedMove.color, targetMove.color) self.assertEqual(parsedMove.vertex, targetMove.vertex) @@ -54,26 +54,26 @@ class TestParseHelpers(unittest.TestCase): """Test correct inputs and their resulting coordinates for parseVertex.""" self.assertEqual(parseHelpers.parseVertex( "a1", TEST_BOARD_SIZE), - [18,0]) + (18,0)) self.assertEqual(parseHelpers.parseVertex( "b1", TEST_BOARD_SIZE), - [18,1]) + (18,1)) self.assertEqual(parseHelpers.parseVertex( "a2", TEST_BOARD_SIZE), - [17,0]) + (17,0)) self.assertEqual(parseHelpers.parseVertex( "b2", TEST_BOARD_SIZE), - [17,1]) + (17,1)) self.assertEqual(parseHelpers.parseVertex( "T1", TEST_BOARD_SIZE), - [18,18]) + (18,18)) self.assertEqual(parseHelpers.parseVertex( "T19", TEST_BOARD_SIZE), - [0,18]) + (0,18)) self.assertEqual(parseHelpers.parseVertex( "A19", TEST_BOARD_SIZE), - [0,0]) + (0,0)) self.assertEqual(parseHelpers.parseVertex( "pass", TEST_BOARD_SIZE), @@ -81,10 +81,14 @@ class TestParseHelpers(unittest.TestCase): def testVertexToString(self): """Test converting vertices to strings.""" - self.assertEqual(parseHelpers.vertexToString([0,0], TEST_BOARD_SIZE), "A19") - self.assertEqual(parseHelpers.vertexToString([1,0], TEST_BOARD_SIZE), "A18") - self.assertEqual(parseHelpers.vertexToString([2,0], TEST_BOARD_SIZE), "A17") - self.assertEqual(parseHelpers.vertexToString([0,1], TEST_BOARD_SIZE), "B19") + + # Try with vertices as tuples + self.assertEqual(parseHelpers.vertexToString((0,0), TEST_BOARD_SIZE), "A19") + self.assertEqual(parseHelpers.vertexToString((1,0), TEST_BOARD_SIZE), "A18") + self.assertEqual(parseHelpers.vertexToString((2,0), TEST_BOARD_SIZE), "A17") + self.assertEqual(parseHelpers.vertexToString((0,1), TEST_BOARD_SIZE), "B19") + + # Try with vertices as arrays self.assertEqual(parseHelpers.vertexToString([0,2], TEST_BOARD_SIZE), "C19") self.assertEqual(parseHelpers.vertexToString([0,18], TEST_BOARD_SIZE), "T19") self.assertEqual(parseHelpers.vertexToString([18,0], TEST_BOARD_SIZE), "A1") @@ -93,10 +97,10 @@ class TestParseHelpers(unittest.TestCase): self.assertEqual(parseHelpers.vertexToString("pass", TEST_BOARD_SIZE), "pass") wrongVertices = [ - [-1,0], - [0,-1], - [-1,-1], - [19,0], + (-1,0), + (0,-1), + (-1,-1), + (19,0), [0,19], [19,19], [0], diff --git a/tests/test_sgf.py b/tests/test_sgf.py new file mode 100644 index 0000000..1266429 --- /dev/null +++ b/tests/test_sgf.py @@ -0,0 +1,27 @@ +"""Tests for processing of SGF files.""" + +import unittest + +from imago.sgfParser.sgfyacc import parser + +TESTING_SGF = 'tests/testingSGF.sgf' + +class TestSGF(unittest.TestCase): + """Test processing SGF files.""" + + def testToGameTree(self): + """Test converting file to GameTree""" + + file = open(TESTING_SGF, "r") + text = file.read() + file.close() + + astNode = parser.parse(text) + + astNode.toGameMoveTree() + + astNode.toString() + + +if __name__ == '__main__': + unittest.main() @@ -14,6 +14,10 @@ def main(): print(file) games.append(loadGameTree(file)) + if len(games) == 0: + print("Error: No game files provided. Provide some SGF files as arguments.") + sys.exit(0) + matches = [game.getMainLineOfPlay() for game in games] modelFile = "" |