diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/Makefile | 4 | ||||
| -rw-r--r-- | doc/diagrams/analysisClasses.puml | 27 | ||||
| -rw-r--r-- | doc/diagrams/modules.puml | 2 | ||||
| -rw-r--r-- | doc/diagrams/planificationWorkPlanEngine.puml | 30 | ||||
| -rw-r--r-- | doc/diagrams/planificationWorkPlanGame.puml | 18 | ||||
| -rw-r--r-- | doc/diagrams/skinparamsGantt.puml | 14 | ||||
| -rw-r--r-- | doc/diagrams/useCases.puml | 18 | ||||
| -rw-r--r-- | doc/tex/biber.bib | 22 | ||||
| -rw-r--r-- | doc/tex/planification.tex | 162 | ||||
| -rw-r--r-- | doc/tex/previousWorks.tex | 24 | ||||
| -rw-r--r-- | doc/tex/systemAnalysis.tex | 200 | ||||
| -rw-r--r-- | doc/tex/tfg.tex | 74 |
12 files changed, 569 insertions, 26 deletions
diff --git a/doc/Makefile b/doc/Makefile index 954ae3c..a631921 100644 --- a/doc/Makefile +++ b/doc/Makefile @@ -3,8 +3,8 @@ docName = tfg outputFolder = out -texFiles = tex/tfg.tex tex/introduction.tex tex/previousWorks.tex tex/interface.tex tex/implementation.tex -diagramImgs = diagrams/gameRepresentation.png diagrams/modules.png diagrams/sgfModule.png diagrams/gtpEngine.png +texFiles = tex/tfg.tex tex/introduction.tex tex/planification.tex tex/interface.tex tex/implementation.tex tex/systemAnalysis.tex tex/biber.bib +diagramImgs = diagrams/gameRepresentation.png diagrams/gtpEngine.png diagrams/modules.png diagrams/planificationWorkPlanEngine.png diagrams/planificationWorkPlanGame.png diagrams/sgfModule.png diagrams/useCases.png diagrams/analysisClasses.png all: $(docName).pdf diff --git a/doc/diagrams/analysisClasses.puml b/doc/diagrams/analysisClasses.puml new file mode 100644 index 0000000..5f1ccde --- /dev/null +++ b/doc/diagrams/analysisClasses.puml @@ -0,0 +1,27 @@ +@startuml + +!include skinparams.puml + +package GameModule { + class GameIO + class GameTree + class GameMove +} + +GameIO -> GameTree +GameTree -> GameMove + +package EngineModule { + class EngineIO + class EngineLogic + interface DecisionAlgorithm + class DecisionAlgorithm1 + class DecisionAlgorithm2 +} + +EngineIO -> EngineLogic +EngineLogic -> DecisionAlgorithm +DecisionAlgorithm <|.. DecisionAlgorithm1 +DecisionAlgorithm <|.. DecisionAlgorithm2 + +@enduml diff --git a/doc/diagrams/modules.puml b/doc/diagrams/modules.puml index 064be1d..5b8d78c 100644 --- a/doc/diagrams/modules.puml +++ b/doc/diagrams/modules.puml @@ -1,6 +1,6 @@ @startuml -!include ./skinparams.puml +!include skinparams.puml !include GameState.pumlc !include SGF.pumlc diff --git a/doc/diagrams/planificationWorkPlanEngine.puml b/doc/diagrams/planificationWorkPlanEngine.puml new file mode 100644 index 0000000..53bd5ea --- /dev/null +++ b/doc/diagrams/planificationWorkPlanEngine.puml @@ -0,0 +1,30 @@ +@startgantt + +!include skinparams.puml +!include skinparamsGantt.puml + +'printscale weekly +Sunday are closed + +Project starts 2021-01-04 + +-- Engine Implementation -- +[Engine modelling] as [EM] starts 2021-01-04 +[Engine modelling] as [EM] lasts 1 week +[Engine implementation] as [EI] lasts 5 weeks +[Engine testing] as [ET] lasts 5 weeks + +-- Algorithms Implementations -- +[Algorithm research] as [AR] lasts 1 week +[Monte Carlo implementation] as [MCI] lasts 3 weeks +[Extra algorithms research] as [EAR] lasts 2 weeks +[Extra algorithms implementation] as [EAI] lasts 4 weeks + +[EM] -> [AR] +[AR] -> [MCI] +[AR] -> [EI] +[AR] -> [ET] +[EI] -> [EAR] +[EAR] -> [EAI] + +@endgantt diff --git a/doc/diagrams/planificationWorkPlanGame.puml b/doc/diagrams/planificationWorkPlanGame.puml new file mode 100644 index 0000000..427564a --- /dev/null +++ b/doc/diagrams/planificationWorkPlanGame.puml @@ -0,0 +1,18 @@ +@startgantt + +!include skinparams.puml +!include skinparamsGantt.puml + +'printscale weekly +Sunday are closed + +Project starts 2020-11-02 + +-- Game Implementation -- +[Domain modelling] as [DM] lasts 6 days +[Domain implementation] as [DI] lasts 30 days +[Domain testing] as [DT] lasts 30 days +[DM] -> [DI] +[DM] -> [DT] + +@endgantt diff --git a/doc/diagrams/skinparamsGantt.puml b/doc/diagrams/skinparamsGantt.puml new file mode 100644 index 0000000..5355d5f --- /dev/null +++ b/doc/diagrams/skinparamsGantt.puml @@ -0,0 +1,14 @@ +@startuml + +<style> +ganttDiagram { + task { + FontSize 15 + } + separator { + FontSize 20 + } +} +</style> + +@enduml diff --git a/doc/diagrams/useCases.puml b/doc/diagrams/useCases.puml new file mode 100644 index 0000000..e3da3f8 --- /dev/null +++ b/doc/diagrams/useCases.puml @@ -0,0 +1,18 @@ +@startuml + +!include skinparams.puml + +actor "Human Player" as player +actor "Human User" as user +actor "GUI Program" as gui + +usecase "Play a match" as play +usecase "Generate a move" as genMove +usecase "Use as backend for machine player" as backend + +player --> play +user --> genMove +gui --> genMove +gui --> backend + +@enduml diff --git a/doc/tex/biber.bib b/doc/tex/biber.bib new file mode 100644 index 0000000..ddebe23 --- /dev/null +++ b/doc/tex/biber.bib @@ -0,0 +1,22 @@ +@online{sl_go, + title = {Go}, + organization = {Sensei's Library}, + date = {2019}, + urldate = {2021}, + url = {https://senseis.xmp.net/?go} +} + +@article{natureAlphaGo2016, + author = {David Silver and Aja Huang and Chris J. Maddison and Arthur Guez and Laurent Sifre and George van den Driessche and Julian Schrittwieser and Ioannis Antonoglou and Veda Panneershelvam and Marc Lanctot and Sander Dieleman and Dominik Grewe and John Nham and Nal Kalchbrenner and Ilya Sutskever and Timothy Lillicrap and Madeleine Leach and Koray Kavukcuoglu and Thore Graepel and Demis Hassabis}, + title = {Mastering the game of Go with deep neural networks and tree search}, + journaltitle = {Nature}, + date = {2016-01-27}, + url = {https://www.nature.com/articles/nature16961} +} + +@online{plantillaRedondo, + author = {J. M. Redondo}, + title = {Documentos-modelo para Trabajos de Fin de Grado/Master de la Escuela de Informática de Oviedo}, + date = {2019-06-17}, + url = {https://www.researchgate.net/publication/327882831_Plantilla_de_Proyectos_de_Fin_de_Carrera_de_la_Escuela_de_Informatica_de_Oviedo} +} diff --git a/doc/tex/planification.tex b/doc/tex/planification.tex new file mode 100644 index 0000000..9a95e8b --- /dev/null +++ b/doc/tex/planification.tex @@ -0,0 +1,162 @@ +\section{Planning} + +\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 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. + \item Either a GUI specifically developed for the project or an + implementation of an existing protocol so the engine can be used with + existing tools and GUIs. +\end{itemize} + +\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 superko rule, no suicide moves). + +\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 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 duration. + +\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 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 +Saturday. Gantt diagrams for the planned working schedule are shown as +Fig.~\ref{fig:planificationWorkPlanGame} and +Fig.~\ref{fig:planificationWorkPlanEngine}. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/planificationWorkPlanGame.png} + \caption{Initial work plan for implementing the game. + }\label{fig:planificationWorkPlanGame} + \end{center} +\end{figure} + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/planificationWorkPlanEngine.png} + \caption{Initial work plan for implementing the engine and algorithms. + }\label{fig:planificationWorkPlanEngine} + \end{center} +\end{figure} + +\subsection{Previous works} + +\subsubsection{Existing engines} + +\paragraph{AlphaGo} + +AlphaGo is a Go play and analysis engine 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 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 \parencite{natureAlphaGo2016} written by the team and +published on Nature is available on +https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf. + +The unprecedented success of AlphaGo served as inspiration for many AI projects, +including this one. + +\paragraph{KataGo} + +KataGo is an open source project 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. + +\paragraph{GnuGo} + +GnuGo is a software capable of playing Go part of the GNU project. Although not +a strong engine anymore, it is interesting for historic reasons as the free +software engine for which the GTP protocol was first defined. + +\subsubsection{GTP} + +GTP (\textit{Go Text Protocol}) is a text based protocol for communication with +computer go programs. [ref https://www.lysator.liu.se/~gunnar/gtp/] It is the +protocol used by GNU Go and the more modern and powerful KataGo. By supporting +GTP the engine developed for this project can be used with existing GUIs and +other programs, making it easier to use it with the tools users are already +familiar with. + +\subsubsection{Sabaki} + +Sabaki is a go board software compatible with GTP engines. It can serve as a GUI +for the engine developed in this project and as an example of the advantages of +following a standardized protocol. + +\subsection{Technological Infrastructure} + +\subsubsection{Programming language} + +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, for various reasons: + +\begin{itemize} + + \item Has established a reputation on scientific fields and more + specifically on AI research and development. + \item Interpreters are available for many platforms, which allows the most + people possible to access the product. + \item Although not too deeply, it has been used by the developer student + during its degree including in 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 engine, +since GTP is a text based protocol for programs using text interfaces. +Independent programs compatible with this interface can be used as a GUI. diff --git a/doc/tex/previousWorks.tex b/doc/tex/previousWorks.tex index 6e503a3..bff0c82 100644 --- a/doc/tex/previousWorks.tex +++ b/doc/tex/previousWorks.tex @@ -1,17 +1,17 @@ \section{Previous works} -\subsection{SGF} - -SGF (\textit{Smart Go Format} or, in a more general context, \textit{Smart Game -Format}) is a text file format specification for records of games or collections -of them. It was devised for Go but it supports other games with similar -turn-based structure. It supports move variations, annotations, setups and game -metadata. By supporting SGF our application can be used to analyse existing -games registered by other applications, such as those played on online Go -servers. - -The SGF specification can be found at -\url{https://www.red-bean.com/sgf/user_guide/index.html} +%\subsection{SGF} +% +%SGF (\textit{Smart Go Format} or, in a more general context, \textit{Smart Game +%Format}) is a text file format specification for records of games or collections +%of them. It was devised for Go but it supports other games with similar +%turn-based structure. It supports move variations, annotations, setups and game +%metadata. By supporting SGF our application can be used to analyse existing +%games registered by other applications, such as those played on online Go +%servers. +% +%The SGF specification can be found at +%\url{https://www.red-bean.com/sgf/user_guide/index.html} \subsection{GTP} diff --git a/doc/tex/systemAnalysis.tex b/doc/tex/systemAnalysis.tex new file mode 100644 index 0000000..d92f537 --- /dev/null +++ b/doc/tex/systemAnalysis.tex @@ -0,0 +1,200 @@ +\section{System Analysis} + +%\subsection{System reach determination} + +\subsection{System Requirements} + +The requirements for the system are expressed here in a nested list way, each of +them with a textual and numeric reference so they are traceable. The functional +requirements are exposed first, followed by the other kinds of requisites needed +for the system. + +\setlist[enumerate,2]{label*=\arabic*.} +\setlist[enumerate,3]{label*=\arabic*.} + +\subsubsection{Functional Requirements} + +\paragraph{Game Requirements} + +\setlist[enumerate,1]{label=FRG \arabic*.} + +\begin{enumerate} + + \item The state of the board can be shown to the user. + \begin{enumerate} + \item A text representation of each cell is printed. + \begin{enumerate} + \item A different character is used for each different state + of a cell. + \end{enumerate} + \item The coordinates system is shown around the board. + \begin{enumerate} + \item Columns are shown as capital letters left to right + starting with ``A'' and skipping ``I''. + \item Rows are shown as numbers starting with 1 on the + lowest row and increasing upwards. + \end{enumerate} + \end{enumerate} + + \item Movements can be introduced to be played on the board. + \begin{enumerate} + \item A move is introduced as the textual representation of the + 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)} + \item If the move is not valid, it must be notified to the + user and another move asked for. + \end{enumerate} + \end{enumerate} + + \item The board will behave according to the Japanese rules of Go. + +\end{enumerate} + +\paragraph{Engine Requirements} + +\setlist[enumerate,1]{label=FRE \arabic*.} + +\begin{enumerate} + + \item Coordinates of the board representing valid moves must be printed. + +\end{enumerate} + +%\subsubsection{Security Requirements} +% +%\setlist[enumerate,1]{label=SR \arabic*.} + +\subsubsection{Usability Requirements} + +\setlist[enumerate,1]{label=UR \arabic*.} + +\begin{enumerate} + + \item The engine executable will include a help option with the different + modes of execution. + +\end{enumerate} + +\subsubsection{User Requirements} + +\setlist[enumerate,1]{label=USR \arabic*.} + +\begin{enumerate} + + \item For understanding the workings of the application the user needs to be + familiar with the basics of the game of Go. + + \item For directly using the engine the user needs to be familiar with + command line interfaces. + +\end{enumerate} + +\subsubsection{Technological Requirements} + +\setlist[enumerate,1]{label=TR \arabic*.} + +\begin{enumerate} + + \item The game program will be a python file able to be executed by the + python interpreter. + + \item The program will make use of standard input and standard output for + communication. + \begin{enumerate} + \item Standard input will be used for reading moves. + \item Standard output will be used for showing the board and for + messages directed to the user. + \end{enumerate} + +\end{enumerate} + +\subsubsection{Response Time Requirements} + +\setlist[enumerate,1]{label=RTR \arabic*.} + +\begin{enumerate} + + \item The maximum thinking time of the engine will be configurable. + \begin{enumerate} + \item It will be possible to pass the maximum time as a launch + argument. + \item It will be possible to store the maximum time as a setting + in a configuration file + \end{enumerate} + +\end{enumerate} + + +\setlist[enumerate,1]{label=\arabic*.} + +\subsection{System Actors} + +There are various actors who will interact with the system, both human and +non-human. + +\begin{itemize} + + \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. + +\end{itemize} + +\subsection{Use Cases} + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/useCases.png} + \caption{Use cases.}\label{fig:useCases} + \end{center} +\end{figure} + +The different actors and use cases are represented on \fref{fig:useCases}. Each +use case is explained next. + +\paragraph{Play a match} + +The game interface reads the moves presented by the player and shows their +result on the board. + +\paragraph{Generate moves} + +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. + +\paragraph{Use as backend for machine player} + +The engine is used as the backend for generating moves for a machine player. + +\subsection{Subsystems} + +\subsubsection{Subsystems description} + +There will be two main subsystems. + +% TODO: Are there really two different subsystems? They look very coupled, since +% the engine will use some classes of the game. This section is more suited for +% independently run systems which communicate through some common interface. + +The first, called the Game System, will be in charge of storing all the state +information regarding a Go match, such as the history of moves, the possible +variations, the state of the board at any given time or the current number of +captured stones. + +The second, called the Engine System, will implement the GTP interface and use +the Game System to analyze positions and generate moves via decision algorithms. + +\subsection{Class analysis} + +The classes resulting from the analysis phase are shown in +\fref{fig:analysisClasses}. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{diagrams/analysisClasses.png} + \caption{General classes obtained from the analysis + phase.}\label{fig:analysisClasses} + \end{center} +\end{figure} diff --git a/doc/tex/tfg.tex b/doc/tex/tfg.tex index a14708d..9bf2189 100644 --- a/doc/tex/tfg.tex +++ b/doc/tex/tfg.tex @@ -5,27 +5,24 @@ \usepackage{booktabs} \usepackage{hyperref} \usepackage{csquotes} +\usepackage{enumitem} \usepackage[backend=biber, style=numeric-comp]{biblatex} -\addbibresource{/home/taamas/docs/biber.bib} +\addbibresource{tex/biber.bib} \geometry{left=4.5cm,top=2cm,bottom=2cm,right=4.5cm} -\hypersetup{colorlinks=true, +\hypersetup{colorlinks=false, linkcolor=black, - filecolor=magenta, + filecolor=black, urlcolor=black, bookmarks=true } \urlstyle{mono} -%\renewcommand{\contentsname}{Contenidos} -%\renewcommand{\figurename}{Figura} - \newcommand{\program}{Imago} -\newcommand{\inputtex}[1]{\input{tex/#1}} \newcommand{\fref}[1]{Fig.~\ref{#1}} %\newcommand{\uurl}[1]{\underline{\url{#1}}} @@ -45,15 +42,70 @@ This is the abstract. \end{abstract} +\clearpage + +\section*{Acknowledgements} + +TODO: Acknowledgements + +To Vicente García Díaz, for directing me in this project. + +To José Manuel Redondo López\cite{plantillaRedondo}, for making a very +complete template on which the structure of this documentation is extensively +based. + +\clearpage + +\section*{Copyright notice} + +\begin{displayquote} + + Copyright (C) 2021 \textbf{ÍÑIGO GUTIÉRREZ FERNÁNDEZ}. + + \textit{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 the + Copyright notice as an Invariant Section, 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{displayquote} + +Although this document uses the GNU Free Documentation License to keep its +contained information free, bear in mind that it isn't software documentation or +a manual or guide of any kind, and serves just as the documentation for the +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. + +\begin{displayquote} + + Copyright (C) 2019 \textbf{JOSÉ MANUEL REDONDO 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 + 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{displayquote} + +\clearpage + \tableofcontents -\inputtex{introduction.tex} +\input{tex/introduction.tex} + +\input{tex/planification.tex} -\inputtex{previousWorks.tex} +\input{tex/systemAnalysis.tex} -\inputtex{interface.tex} +%\input{tex/interface.tex} -\inputtex{implementation.tex} +%\input{tex/implementation.tex} \printbibliography{} |