path: root/doc/tex/planning.tex

\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}