\chapter{Introduction}
\label{ch:intro}
In this chapter we will give a short overview about GO, and what kind of  work
has already be done. It exists in main parts as a summary of \cite{97paper}.

\section{Playing GO - Basics}
For a computer GO is really hard to learn, and the best networks are still weaker as an
average human player. There exists a number of reasons for this, just too name a few:
the games is pattern oriented, the branching factor is prohibitively large and there are
multiple interacting goals. Probably evolving new methods and networks can solve
these ( and many other problems connected to this subject ) problems.
\subsection{GO, the original game}
Although the word GO is taken from the Japanese word for the game, it seems to be
coming from China about 3000 years ago. It is a simple board based strategy games,
but is appears simple in comparison to chess or similair board-strategy games.
The main goal is to reach more points than your opponennt. To do so, you can
playe stones, black or white, on a square rid with 19 intersections across. Two players,
black and white, place alternate on stone of their respective colors on an intersection.
The games end when both players pass or no more space for placing stones is left.
It is very easy to even the opponent levels. If a player has more experience, he
allows his oppenent a number of free moves. You say he ranks x stones higher. ( x
is the number of allowed free stones )
\subsubsection{How to gain points}
Each player tries to catch stones of the opponent. To do so, he has to place them
around the opponent stones. If stones got "captured" in such way, they are removed
from the board. At the end of the game the remaining stones are counted. In a normal
even game, white can add 5.5 points, offsetting the fact of black's first move. The player
with the highest score wins.
\subsection{Computers and GO}
Although the rule set is relatively simple, computers are still not able to play against
good players and win. A game of GO can be divided into three general phases: the
opening, the midgame and the endgame. Computer's success in each of this stages
varies and we have to take a deeper look in what can and what can not be achieved
with computational methods.
\subsubsection{The Opening}
The opening game is referred to as the fuseki. Specified combinations of stones in the
beginning are referred to as joseki. Good GO programms contain databases with 5000 to
50000 moves, and they have no difficults to play a good beginning with them. But because
evolving a good strategy is still a bigger goal, improvements were not made yet in this stage
of the game.
\subsubsection{The Midgame}
This stage of a game contains the bigger problems for computer. Because of the sheer size of
a average board (19x19), between 200 to 300 moves are possible on a first sight in a typical
midgame position. Therefore brute force searching would result in much too big trees.
Techniques which are used contain pattern libraries, tactical analysis and rule-based expert
systems. The system first evaluates candidate moves, using one or some of the named
techniques and analysis them. \\
There are several problems with the current midgame techniques. They tend to be difficult
to apply and error-prone, and because most of them are static, it is difficult to achieve general
play and advance must be made by a human.
\subsubsection{The Endgame}
The endgame of GO is simplier for computers, but normally there are less points to achieve.
The board is full, patterns are set and positions taken. Although computers play very well in
this stage, they achieve less points compared to what could be taken out of the midgame.
So the most important and difficult part of playing GO is in the midgame where the traditional
techniques are the weakest.

\section{Neural Networks and Go}
The main factor, that is holding back computer GO programs, is the largely pattern oriented
game strategies that need to be incorporated for successfully playing GO. As neural networks
are known to be exceptionally good at pattern transformation tasks, employing this relatively
new technique seems like a very promising approach.

\subsection{SANE}
\label{ch:intro:sane}
SANE (Symbiotic Adaptive Neuro-Evolution) is a specific form of  neural network that does
not depend on backpropagation as training method which cannot be effectively applied on
the intended purpose. It maintains a large pool of neurons, structured as a classic
three-layer feedforward network, and additionally a population of blueprints which can be
thought of as a selection of neurons specifying an individual neural network. This ensures
the evolution of a wide variety of assemblages to compensate for the rather long evaluation
intervals. A neuron's activation is defined by the transfer function
$ \sigma(x) = \frac{1}{1+e^{-x}} $. During the process of evolution SANE evaluates each
blueprint's performance and calculates a fitness value for every neuron in the pool based
on the performance of  the networks in which it participates. In the so called reproduction
phase, the top 25\% in the neuron pool and top 15\% in the blueprint population are
randomly mated making use of a one-point crossover procedure to obtain new individuals
replacing the least fittest ones. On the blueprint level, each link to a breeding neuron is
altered to its offspring with a 50\% probability.
Additionally a conservative mutaion rate of 1\% is applied to both populations.

\subsection{Applying SANE to Go}
SANE evolves common three-layer feed-forward networks with input layers
of two units (Boolean value) and output layers of only one unit (float value)
per board position. Positive output results indicate good and negative results bad moves.
The neurones generated are 312 bits long and represent a set of 12 weights.
Each generation 200 networks were formed with a mutation rate of 0.1\% and
25-30\% of the population allowed to breed, which has given good results during
experimentation. It showed to be rather difficult to determine the end of a game, to
remove dead stones and to check for repetition of entire board positions. Solutions
for all these problems were found. An upper bound was placed on the number of
moves in order to ban excessively long games. The fitness level for the networks
was produced by summing the difference in score between SANE and its
opponent over a certain number of games.

\subsection{Results}
SANE was tested with board sizes of 5x5, 7x7 and 9x9, where it was able to
beat its opponent program wally after an acceptable number of generations.
Larger boards could not be tested due to lack of CPU power. Several
experiments showed, that SANE managed to beat deterministic opponents very
rapidly, whereas it did not learn to play against more randomly acting
players. When trained with a more non-deterministic wally the network developed
tricks instead of only being able to win against only one certain player.
In order to train the networks at a higher level the GO handicapping mechanism
was used to simulate stronger opponents.

\subsection{Strategies Evolved}
An interesting question is, what kind of strategies did the networks evolve because they
start with no prior knowledge on how to play the game. Important for the network is the
training partner, who is the only source of information for the network. A network with only
one specific training partner can work out strategies to take advantage of the opponents
weakness. For that reason it is better to use a variety of opponents. The networks outputs
are random at the beginning but after a few generations they start to make simple living
groups. The evolution system discovered good GO playing strategies without prior
knowledge entirely on its own, based on what moves led to wins and losses

\subsection{Future Work}
Future Work will focus on scaling up to larger boards. In the future they plan to play on any
board size because now the networks can only play on the board on which they were
developed. There are two possibilities to solve this problem:

\begin{enumerate}
        \item to design a representation that is independent of board size
        \item to work out solutions that only consider a portion of the board at a time, but by
                this method the result is a weaker play.
        \item enhancing the network architecture.
\end{enumerate}

There are several ways to make the architecture more effective, including preprogrammed
feature detectors and hierarchies of networks. The networks are forced to discover
useful features themselves because they are not given any prior knowledge about what
features are relevant to playing GO. A pre-defined feature space instead of looking at the
raw board might make the assignment easier and might allow the network to learn faster
and deal with more complex patterns. and evolving against stronger opponents.
A variety of stronger opponents is necessary to achieve truly high levels of  play. The
stronger player can be simulated by using handicaps but handicap games alone are not
enough. A problem is that strong opponents tend to take longer to generate moves than
weaker programs. In future it would be necessary to work out networks against human
players. This way perhaps GO-playing could finally be evolved that were able to compete
with the best humans.
%
%\subsection{Conclusions}
New techniques based on pattern  recognition and learning like SANE will be required to
build GO programs that would be competitive at high levels of play because the traditional
methods have been insufficient.