\section{Introduction}

\begin{displayquote}
	Go is an ancient game which, from its forgotten origins in China, spread first
	to the rest of East Asia, and then to the entire world. How ancient? Historians
	aren't sure; it has a definite history of over 3000 years, but according to
	tradition Go was invented more than 4000 years ago. The English name comes from
	the Japanese name Igo, which means ``surrounding boardgame''.

	In this game, each player tries to use threats of death, capture, or isolation
	to assert control over more of the board than his opponent. An abstract strategy
	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}
\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 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}