clanek: normality of errors

[gostyle.git] / PAPERS / clanek_go_congress / clanek.tex

\documentclass[12pt,a4paper,notitlepage]{article}

\usepackage[a4paper,vmargin={20mm,20mm},hmargin={20mm,20mm}]{geometry}

%% Použité kódování znaků: obvykle latin2, cp1250 nebo utf8:
\usepackage[utf8]{inputenc}

%% Ostatní balíčky
\usepackage[titletoc]{appendix}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{color}
\usepackage[multiple]{footmisc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{threeparttable}
\usepackage{longtable}
\usepackage{tabularx}
\usepackage{amsfonts}
\usepackage{caption}
\usepackage[lined, ruled, boxed, linesnumbered]{algorithm2e}

\usepackage[round]{natbib}             % sazba pouzite literatury

\usepackage{psfrag}

\usepackage{psgo,array}
\usepackage{url}                % sazba URL

\usepackage[ps2pdf,unicode]{hyperref}   % Musí být za všemi ostatními balíčky
\usepackage{breakurl}


%\hypersetup{pdftitle=Meta-learning methods for analyzing Go playing trends}
%\hypersetup{pdfauthor=Josef Moudřík}

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
%\title{On Move Pattern Trends\\in  Large Go Games Corpus}
\title{Evaluating Go Game Records\\for Prediction of Player Attributes }

% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
\author{Josef~Moud\v{r}\'{i}k%
\thanks{J. Moud\v{r}\'{i}k is student at the Faculty of Math and Physics, Charles University, Prague, CZ.},~Petr~Baudi\v{s}%
\thanks{P. Baudi\v{s} is an independent researcher. Part of his work
in this area has been supported by the SUSE Labs and the Department
of Applied Mathematics, Faculty of Mathematics and Physics, Charles University.}}
\maketitle

\begin{abstract}
We propose a~way of extracting and aggrgating per-move evaluations from sets of Go game records.
The evaluations capture different aspects of the games such as the played patterns
or statistics of sente/gote sequences (among others); using machine learning
algorithms, they can be used to predict arbitrary relevant target variables.
We apply this methodology to predict strength and playing style (e.g.
territoriality or aggressivity) of a player and make our predictor
available as an online tool, a part of the GoStyle project.
%% No, na tohle neni v clanku misto, pze to ma mit jen 8 stranek
% navic bych tyhle veci chtel zverejnit i samy o sobe, nejak dukladnejc,
% 
%By inspecting the dependencies between the evaluations and the target variable,
%we are able to tell which patterns are bad or good (in case of strength as the
%target variable), or which moves e.g. constitute the territorial style of play.
%%
We propose a number of possible applications including seeding real-work ranks
of internet players, aiding in Go study and tuning of Go-playing programs, or
a contribution to Go-theoretical discussion on the scope of ``playing style''.
\end{abstract}


\section{Introduction}
The field of Computer Go usually focuses on the problem
of creating a~program to play the game by finding the best move from a~given
board position \citep{GellySilver2008}. We focus on analyzing existing game
records with the aim of helping humans to play and understand the game better
instead.

Go is a~two-player full-information board game played
on a~square grid (usually $19\times19$ lines) with black and white
stones; the goal of the game is to surround the most territory and
capture enemy stones. We assume basic familiarity with the game.

Since the game has a worldwide popularity, large collections
of Go game records have been compiled, covering both amateur and professional games,
e.g. \citep{KGS,GoGoD}. 
So far, not much has been done to analyze these records using computers.
There are programs that serve as tools to study the opening phase of the game
by giving simple statistics of next move candidates based on professional
games~\citep{Kombilo,MoyoGo}.
The professional games have also been used in computer Go;
patterns from the professional games
are used as a heuristic to improve the tree
search, e.g.~\citep{PatElo}. Apart from these, we are not aware of
any principially different usage.

Following up on our initial research \citep{GoStyleArxiv},
we present a deeper approach. We extract different
kinds of information from the records to create a complex
evaluation of the game sample. The \emph{evaluation} is a vector
composed of independent features -- each of the features
captures different aspect of the sample. For example,
we use statistics of most frequent
local patterns played, statistics of high and low plays
in different game stages, etc.

Using machine learning, the evaluation of the sample
can be used to predict relevant variables. In this work
for instance,
the sample consists of the games of a player
and we predict his strength or playing style.

This paper is organized as follows. Section~\ref{sec:feat}
presents the features comprising the evaluation.
Section~\ref{sec:mach} gives details about the machine
learning method we have used.
In Section~\ref{sec:expe} we give details about our
datasets -- for prediction of strength and style -- and
show how precisely can the prediction be conducted.
Section~\ref{sec:disc} discusses applications and future work.

\section{Feature Extraction}
\label{sec:feat}
This section presents the methods for extracting the evaluation 
vector (we call it $ev$) from a set of games. Because we aggregate
data by player, each game in the set is accompanied by the color
which specifies our player of interest.
The sample is therefore regarded as a \emph{set
of colored games}, $GC = \{ (game_1, color_1), \ldots\}$.

The evaluation vector $ev$ is composed by concatenating several
sub-vectors we call \emph{features} -- examples include the
aforementioned local patterns or statistics of sente and gote
sequences. These will be detailed in the rest of this section.
Some of the details are edited for brevity,
please see \citep{Moudrik13} for an extended description.

\subsection{Raw Game Processing}
The games\footnote{
    We use the standard \emph{.sgf} file format as input, \citep{SGF}.
} are processed by the Pachi Go
Engine~\citep{Pachi} which exports a variety of analytical data
about each move in the game.
For each move,
Pachi outputs a list of key-value pairs regarding the current move:

\begin{itemize}
    \item \textbf{atari flag} --- whether the move put enemy stones in atari,
    \item \textbf{atari escape flag} --- whether the move saved own stones from atari,
    \item \textbf{capture} --- number of enemy stones the move captured,
    \item \textbf{contiguity to last move} --- the gridcular
        distance\footnotemark[2] from the last move,
    \item \textbf{board edge distance} --- the distance from
        the nearest edge of the board,
    \item \textbf{spatial pattern} --- configuration of stones around the played move.
\end{itemize}

We use this information to compute the higher level features given below.
The spatial pattern pictures positions of stones around the current move up to
a certain distance.\footnote{
    \label{grid}
    The distance is given by the {\em gridcular} metric
$d(x,y) = |\delta x| + |\delta y| + \max(|\delta x|, |\delta y|)$, which produces
a circle-like structure on the Go board square grid \citep{SpatPat}.
Spatial patterns of sizes 2 to 6 are regarded.
}

\subsection{Patterns}
The first feature collects a statistics of $N = 400$ most frequently ocurring
spatial patterns (together with both atari flags). The list of the $N$ most frequently
played patterns is computed beforehand from the whole database of games. The patterns
are normalized to be black to play and are invariant under rotation and mirroring.

Given a set of colored games $GC$ we then count how many times was each of the $N$
patterns played -- thus obtaining a vector $\vec c$ of counts ($|\vec c| = 400$).
With simple occurence count however, particular counts $c_i$ increase proportionally to 
number of games in $GC$. To maintain invariancy under the number of games in the sample,
a normalization is needed. We do this by dividing the $\vec c$ by $|GC|$, though other schemes
are possible, see \citep{Moudrik13}.

\subsection{$\omega$-local Sente and Gote Sequences}
Because the concept of sente and gote is very important in real games, we devised
a statistics which tries to capture distribution of sente and gote plays in the games
from the sample. Because deciding what moves are sente or gote can be hard even
for human players, we restricted ourselves to what we call $\omega$-local (sente
and gote) sequences. We say that a move is $\omega$-local (with respect
to the previous move) if its gridcular distance from previous move
is smaller than a fixed number $\omega$; in this work, we used $\omega=10$.
The simplification has a clear assumption -- the responses to
a sente move are always local.
Of course, this assumption might not always hold, but
the feature proves to be useful nonetheless.

We then partition each game into $\omega$-local sequences (that is, each move in the
sequence is $\omega$-local with respect to its directly previous move) and observe
whether the player who started the sequence is different from the player who ended it.
If it is so, the $\omega$-local sequence is said to be sente for the player who started it
because he gets to play somewhere else first (tenuki). Similarly if the player who 
started the sequence had to respond last we say that the sequence is gote for him.
Based on this partitioning, we can count the average number of sente and gote
sequences per game from the sample $GC$. These two numbers, along with their difference,
form the second feature.

\subsection{Border Distance}
The third feature is a two dimensional histogram counting the average number of moves
in the sample played low or high in different game stages. The original idea was to help
to distinguish between territorial and influence based moves in the opening.

The first dimension is specified by the move's border distance,
the second one by the number of the current move from the beginning of the game.
The granularity of each dimension is given by intervals dividing the domains.
We use the
$$ByDist = \{ \langle1, 2\rangle, \langle 3 \rangle, \langle4\rangle, \langle 5, \infty)\}$$
division for the border distance dimension
(distinguishing between the first 2 lines, 3rd line of territory, 4th line of influence and
higher plays for the rest).
The move number division is given by
$$ByMoves = \{ \langle1, 10\rangle, \langle 11, 64\rangle, \langle 65,200\rangle, \langle 201, \infty)\}$$ 
with the motivation to (very roughly) distinguish
between the opening (say first ten moves), early middle game (moves 11-64), middle game
and endgame.

If we use the $ByMoves$ and $ByDist$ intervals to divide the domains, we obtain a histogram
of total $|ByMoves| \times |ByDist| = 16$ fields. For each move in the games $GC$,
we increase the count in the
appropriate histogram field. In the end, the whole histogram is normalized
to establish invariancy under the number of games scanned by dividing the 
histogram elements by $|GC|$. These 16 numbers form the third feature.

\subsection{Captured Stones}
Apart from the border distance feature, we also maintain a two-dimensional histogram
which counts the numbers of captured stones in different game stages. The motivation is
simple -- especially beginners tend to capture stones because ``they could'' instead of
because it is the ``best move''. For example, such a capture might
be a grave mistake in the opening.

As before, one of the dimensions is given by the intervals 
$$ByMoves = \{ \langle1, 60\rangle, \langle 61, 240\rangle, \langle 241, \infty)\}$$
which try to specify the game stages (roughly: opening, middle game, endgame).\footnote{
    The division into game stages is coarser than for the previous
    feature because captures occur relatively infrequently. Finer graining
    would require more data.
}
The second dimension has a fixed size of three bins. Along the number of captives
of the player of interest (the first bin), we also count the number of his
opponent's captives (the second bin) and a difference between the two numbers
(the third bin). Together, we obtain a histogram of $|ByMoves| \times 3 = 9$ elements.

Again, the colored games $GC$ are processed move by move by increasing
the counts of captivated stones (or 0) in the appropriate field.
The 9 numbers (again normalized by dividing by $|GC|$) are the output of the fourth
feature.

\subsection{Win/Loss Statistics}
Finally, we used a simple feature that keeps statistics of
wins and losses and whether they were by points or by resignation\footnote{
    We disregard forfeited, unfinished or jigo games in this feature
    because the frequency of these events is so small it would
    require a very large dataset to utilize them reliably.
}. 
For example, many weak players continue playing games that are already lost
until the end, mainly because their counting is not very good (they do not
know there is no way to win), while professionals do not hesitate to resign 
if they think that nothing can be done.

In the colored games of $GC$, we count how many times did the player of interest:
\begin{itemize}
    \item win by counting,
    \item win by resignation,
    \item lost by counting,
    \item and lost by resignation.
\end{itemize}
Again, we divide these four numbers by $|GC|$ to maintain the invariancy under the number of games
in $GC$. Furthermore, for the games won or lost in counting we count the average
size of the win or loss in points. The six numbers form the last feature.

\section{Machine Learning}
\label{sec:mach}
So far, we have considered how we can turn a set of coloured games $GC$ into
an evaluation vector. Now, we are going to show how to utilize the evaluation.
To predict various player attributes, we start with an input dataset $D$ consisting
of pairs $D=\{ (GC_i, y_i), \dots\}$, where $GC_i$
corresponds to a set of colored games of $i$-th player and $y_i$ is the
target attribute. The $y_i$ might be fairly arbitrary, as long as it has
\emph{some} relation to the $GC_i$. For example, $y_i$ might be $i$'s strength.

Now, let's denote our evaluation process we presented before as $eval$ and
let $ev_i$ be evaluation of $i$-th player, $ev_i = eval(GC_i)$. Then,
we can transform $D$ into $D_{ev} = \{(ev_i, y_i), \dots\}$, which forms
our training dataset.

The task of our machine learning algorithm is to generalize the knowledge
from the dataset $D_{ev}$ to predict correct $y_X$ even for previously unseen $GC_X$.
In the case of strength, we might therefore be able to predict strength $y_X$
of an unknown player $X$ given a set of his games $GC_X$ (from which we can
compute the evaluation $ev_X$).

After testing multiple approaches, we have settled on using a bagged artificial neural network
as the predictor.
Neural networks are a standard technique in machine learning. The network is
composed of simple computational units which are organized in a layered topology,
as described e.g. in monograph by \citet{haykin_nn}.
We have used a simple feedforward neural network with 20~hidden units, trained
using the RPROP algorithm \citep{Riedmiller1993} for at most 100~iterations.

The bagging \citep{breimanbag96} is a method that combines an ensemble of
$N$ models (trained on differently sampled data) to improve their
performance and robustness. In this work, we used a bag of $N=20$ neural networks.

\subsection{Measuring the Performance}

To assess the efficiency of our method and give estimates of its precision for
unseen inputs, we measure the performance of our algorithm given a dataset $D_{ev}$.
A standard way to do this is to divide the $D_{ev}$ into training
and testing parts and compute the error of the method on the testing part.

A commonly used measure is the mean square error ($MSE$) which estimates variance of
the error distribution. We use its square root ($RMSE$) which is an estimate of
standard deviation of the predictions,
$$ RMSE = \sqrt{\frac{1}{|T_s|} \sum_{(ev, y) \in T_s}{ (predict(ev) - y)^2}} $$
where the machine learning model $predict$ is trained on the
training data $T_r$ and $T_s$ denotes the testing data.

\subsubsection*{Cross-Validation}

For the error estimation to be robust, we use the method of cross-validation \citep{crossval},
which is a standard statistical technique for robust estimation of parameters.
We split the data into $k$ disjunct subsets (called \emph{folds}) and then
iteratively compose the training and testing sets and measure errors.
%In each of the $k$ iterations, $k$-th fold is chosen as the testing data, and
%all the remaining $k-1$ folds form the training data. The division into the folds is
%done randomly, and so that the folds have approximately the
%same size.
In this work, we have used 5-fold cross validation.

\section{Experiments and Results}
\label{sec:expe}

\subsection{Strength}
One of the two major domains we have tested our framework on is the prediction of player
strength.

\subsubsection*{Dataset}
We have collected a large sample of games from the public
archives of the Kiseido Go server~\citep{KGSArchives}.
The sample consists of over 100 000 records of games in the \emph{.sgf} format~\citep{SGF}.

For each rank $r$ in the range of 6-dan to 20-kyu, we gathered a
list of players $P_r$ of the particular rank. To avoid biases caused by
different strategies, the sample only consists of games played on $19 \times 19$ board without
handicap stones.
The set of colored games $GC_p$ for a~player $p \in P_r$ consists of the games player $p$
played when he had the rank $r$. We only use the $GC_p$ if the number of
games is not smaller than 10 games; if the sample is larger than 50 games, we 
randomly choose a subset of the sample (the size of subset is uniformly randomly
chosen from interval $\langle 10, 50\rangle$).\footnote{
   By cutting the number of games to a fixed number (say 50) for large
   samples, we would create an artificial disproportion in sizes of $GC_p$,
   which could introduce bias into the process.
}

For each of the 26 ranks, we gathered 120 such $GC_p$'s.
The target variable $y$ to learn from directly corresponds to the ranks:
$y=20$ for rank of 20-kyu, $y=1$ for 1-kyu, $y=0$ for 1-dan, $y=-5$
for 6-dan, other values similarly. (With increasing strength, the $y$
decreases.)

\subsubsection*{Results}

The performance of the prediction of strength is given in Table~\ref{tab:str_reg_res}.
The table compares the performance of the Bagged neural network (Section~\ref{sec:mach}),
with simple reference method of Mean regression, which just constantly 
predicts average of the strengths in the dataset regardless of the evaluation vector.

The results show that the prediction of strength has standard deviation $\sigma$
(estimated by the $RMSE$ error) of approximately $2.7$ rank.
Because the errors are normally distributed, 
we can say that 68\% of predictions fall within distance of
$\sigma$ from the real strength and 95\% of predictions are within $2\sigma$.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\textbf{Machine learning method} & $\mathbf{RMSE}$ error\\

\hline
Mean regression & 7.507 \\ \hline
Bagged NN & 2.712 \\

\hline
\end{tabular}
\end{center}
\caption{
    $RMSE$ performance of the strength prediction. The mean regression is 
    a reference model which predicts constant value (average of the
    strengths in the dataset) regardless of the set of games. The results
    are computed by 5-fold cross-validation.
} 
\label{tab:str_reg_res}
\end{table}

\subsection{Style}

The second domain is the prediction of different aspects of player styles.

\subsubsection*{Dataset}
The collection of games in this dataset comes from the Games of Go on Disk database by \citet{GoGoD}.
This database contains more than 70 000 professional games, spanning from the ancient times
to the present.

We chose 25 popular professional players (mainly from the 20th century) and
asked several experts (professional and strong amateur players)
to evaluate these players using a questionnaire. The experts (Alexander
Dinerchtein 3-pro, Motoki Noguchi 7-dan,
Vladimír Daněk 5-dan, Lukáš Podpěra 5-dan and Vít Brunner 4-dan)
were asked to assess the players on four scales, each ranging from 1 to 10.

%\begin{table}[h!]
\begin{center}
%\caption{Styles}
\begin{tabular}{|c|c|c|}
\hline
\textbf{Style} & \textbf{1} & \textbf{10}\\ \hline
Territoriality & Moyo & Territory \\
Orthodoxity & Classic & Novel \\
Aggressivity& Calm & Fighting \\
Thickness & Safe & Shinogi \\ \hline
\end{tabular}
\end{center}
%\caption[Definition of the style scales]{
%The definition of the style scales.
%}
%\label{tab:style_def}
%\end{table}

The scales try to reflect
some of the traditionally perceived playing styles.\footnote{
    Refer also to~\citet{GoGoD:styles}, or~\citet{senseis:styles} regarding Go playing styles.
}
For example, the first scale (\emph{territoriality})
stresses whether a player prefers safe, yet inherently smaller territory (number 10 on the scale),
or roughly sketched large territory (\emph{moyo}, 1 on the scale), which is however insecure. 


For each of the selected professionals, we took 192 of his games from the GoGoD database
at random. We divided these games (at random) into 12 colored sets $GC$ of 16 games.
The target variable (for each of the four styles) $y$ is given by average of the answers of
the experts. Results of the questionnaire are published online in~\citep{style_quest}.

\subsubsection*{Results}

The results of style prediction are given in Table~\ref{tab:sty_reg_res}. 
Given that the style scales have range of 1 to 10, we consider the average 
standard deviation from correct answers of around 1.6 to be a good precision.

We should note that the mean regression has very small $RMSE$
for the scale of thickness.
This stems from the fact that the experts' answers from the questionnaire 
have themselves very little variance --- our conclusion is that the scale of
thickness was not chosen well. Refer to~\citep{style_quest} for further discussion.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
&
\multicolumn{4}{|c|}{ $\mathbf{RMSE}$ error } \\
\hline
\textbf{Method} & Territoriality & Orthodoxity & Aggressivity & Thickness \\


\hline
Mean regression & 2.403 & 2.421 & 2.179 & 1.682 \\
Bagged NN & 1.527 & 1.734 & 1.548 & 1.572  \\
\hline
\end{tabular}
\end{center}
\caption{
    $RMSE$ performance for prediction of different styles. The mean regression is 
    a reference model which predicts constant value (average of the
    values of each particular style) regardless of the set of games. The results
    are computed by 5-fold cross-validation.
}
\label{tab:sty_reg_res}
\end{table}


\section{Discussion}
\label{sec:disc}

The results in both domains have shown that our evaluations are useful in predicting
different kinds of player attributes. This can have a number of possible applications.

So far, we have utilized some of our findings in an online web
application\footnote{\url{http://gostyle.j2m.cz/webapp.html}}. Based on data submitted
by the users, it evaluates their games and predicts their playing style
and recommends relevant professional players to review. Of course,
our methods for style estimation are trained on very strong players and they might
not thus be fully generalizable to ordinary players. Weak players might not have a consistent
style or the whole concept of style might not be even applicable for them. Estimating this 
effect is however not easily possible, since we do not have data about weak players' styles.
Our webapp allows the users to submit their own opinion about their style, therefore we should
be able to consider this effect in the future research.

Other possible applications include helping the ranking algorithms to converge faster ---
usually, the ranking of a player is determined from his opponents' ranking by looking
at the numbers of wins and losses (e.g. by computing an Elo rating). Our methods might improve this
by including the domain knowledge.
Similarly, a computer Go program can quickly classify the level of its
human opponent based on the evaluation from their previous games
and auto-adjust its difficulty settings accordingly
to provide more even games for beginners.

It is also possible to study dependencies between single elements of the evaluation vector
and the target variable $y$ directly. By pinpointing e.g. the patterns
of the strongest correlation with bad strength (players who play them are weak), we can 
warn the users not to play these. We have made some initial research into this in~\citep{Moudrik13},
we do not present these results here because of space constraints.

\section{Conclusion}
\label{sec:conc}
We presented a method for evaluating players based on a sample of their games.
These summary evaluations turn out to be useful in many cases --- they allow us to predict
different player attributes (such as strength or playing style) with reasonable accuracy.
We believe that the applications of these findings can help to improve both human and computer
understanding in the game of Go.

\section{Implementation}
\label{sec:impl}

The code used in this work
is released online as a part of GoStyle project~\citep{GoStyleWeb}.
The majority of the source code is implemented in
the Python programming language~\citep{Python27}.

The machine learning was implemented using the
Orange Datamining suite~\citep{curk05} and
the Fast Artificial Neural Network library FANN~\citep{Nissen2003}.
We used the Pachi Go engine~\citep{Pachi} for the raw game processing.

\bibliographystyle{abbrvnat}
\bibliography{clanek}

\end{document}