1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
\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}
|
