Merge branch 'master' of git+ssh://repo.or.cz/srv/git/gostyle

[gostyle.git] / tex / gostyle.tex

\documentclass[journal]{IEEEtran}

\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.


% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi

\usepackage{algorithm}
\usepackage{algorithmic}
%\usepackage{algpseudocode}
% WICKED: nefunguje ani jedno???
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/

% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


\usepackage{amsmath}
%\usepackage{mdwtab}
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.

%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/



% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/



% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.


%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
% This package may be useful when used in conjunction with IEEEtran.cls'
% captionsoff option. Some IEEE journals/societies require that submissions
% have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.3.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% For subfigure.sty:
% \let\MYorigsubfigure\subfigure
% \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat/subfig command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.

% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.


% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{On Pattern Feature Trends in Large Go Game Corpus}

% 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{Petr~Baudis,~Josef~Moudrik% <-this % stops a space
\thanks{P. Baudis is student at the Faculty of Math and Physics, Charles University, Prague, CZ, and also does some of his Computer Go research as an employee of SUSE Labs Prague, Novell CZ.}% <-this % stops a space
\thanks{J. Moudrik is student at the Faculty of Math and Physics, Charles University, Prague, CZ.}}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.


% The paper headers
\markboth{Transactions on Computational Intelligence and AI in Games}%
{On Pattern Feature Trends in Large Go Game Corpus}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.




% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark.



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle


\begin{abstract}
%\boldmath

We process a~large corpus of game records of the board game of Go and
propose a~way to extract per-player summary information on played moves.
We then apply several basic data-mining methods on the summary
information to identify the most differentiating features within the
summary information, and discuss their correspondence with traditional
Go knowledge. We show mappings of the features to player attributes
like playing strength or informally perceived "playing style" (such as
territoriality or aggressivity), and propose applications including
seeding real-work ranks of internet players, aiding in Go study, or
contribution to discussion within Go theory on the scope of "playing
style".

\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the journal you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals frown on math
% in the abstract anyway.

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
board games, go, data mining, player strength, playing style
\end{IEEEkeywords}






% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps.
% 
% form to use if the first word consists of a single letter:
% \IEEEPARstart{A}{demo} file is ....
% 
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by IEEE):
% \IEEEPARstart{A}{}demo file is ....
% 
% Some journals put the first two words in caps:
% \IEEEPARstart{T}{his demo} file is ....
% 
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
\IEEEPARstart{T}{he} field of Computer Go usually focuses on the problem
of creating a~program to play the game, finding the best move from a~given
board position. We will make use of one method developed in the course
of such research and apply it to the analysis of existing game records
with the aim of helping humans to play 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.

Many Go players are eager to play using computers (usually over
the internet) and review games played by others on computers as well.
This means that large amounts of game records are collected and digitally
stored, enabling easy processing of such collections. However, so far
only little has been done with the available data --- we are aware
only of uses for simple win/loss statistics (TODO: KGS Stats, KGS Analytics,
Pro Go Rating) and ''next move'' statistics on a~specific position (TODO:
Kombilo, Moyo Go Studio).

We present a~more in-depth approach --- from all played moves, we devise
a~compact evaluation of each player. We then explore correlations between
evaluations of various players in light of externally given information.
This way, we can discover similarity between moves characteristics of
players with the same playing strength, or discuss the meaning of the
"playing style" concept on the assumption that similar playing styles
should yield similar moves characteristics.


\section{Expert-based knowledge}
\label{style-vectors}
In order to provide a reference frame for our style analysis,
we have gathered some expert-based information about various
traditionally perceived style aspects.
Three high-level Go players (Alexander Dinerstein 3-pro, Motoki Noguchi
7-dan and Vit Brunner 4-dan) have judged style of several Go
professionals -- we call them \emph{reference playerse} -- chosen for both
being well-known within the community and having large number of played games in our collection.

This expert-based knowledge allows us to predict styles of unknown players based on
the similarity of their pattern vectors, as well as discover correlations between
styles and proportions of played patterns.

Experts were asked to assign each of player's style a number
on a scale from 1 to 10. These are interpreted
as shown in the table below.

\vspace{4mm}
\noindent
%\begin{table}
\begin{center}
%\caption{Styles}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{Styles} \\ \hline
Style & 1 & 10\\ \hline
Territoriality & Moyo & Territorial \\
Orthodoxity & Classic & Novel \\
Aggressivity & Calm & Figting \\
Thickness & Safe & Shinogi \\ \hline
\end{tabular}
\end{center}
%\end{table}
\vspace{4mm}

Averaging this expert based evaluation yields
\emph{reference style vector} $\vec s_r$ (of dimension $4$) for each player $r$
from the set of \emph{reference players} $R$.

%-- each with a \emph{pattern vector} $\vec p_i$ and \emph{style vector} $\vec s_i$.

\section{Data Extraction}
\label{pattern-vectors}
In addition to the explicit expert knowledge, we use the data obtained by...

TODO rozvest uvod, nemuze se zacinat jenom As the input...

As the input, we assume a~collection of game records\footnote{We
use the SGF format (TODO) in our implementation.} organized by player names.
We use two collections; the first one is GoGoD Winter 2009 (TODO) containing 42000 (TODO)
professional games, dating from the early Go history 1500 years ago to the present.
We use this collection for style analysis and detailed correlation analysis
of well-known Go professionals.
The other source is Go Teaching Ladder reviews (TODO). These include 7600 games
of players spanning over all strength levels; we use this collection
for finding correlations between moves of players of the same strength rank.

In order to generate the required compact description of most frequently played moves,
we construct a set of $n$ most occuring patterns (\emph{top patterns})
across all players and games from the database\footnote{We use $n=500$ in our analysis.}.
For each player, we then count how many times was each of those $n$ patterns played
during all his games and finally assign him a~{\em pattern vector} $\vec p$ of dimension $n$, with each
dimension corresponding to the relative number of occurences of a given pattern
(with respect to player's most played \emph{top pattern}). Using relative numbers of occurences ensures that
each dimension of player's \emph{pattern vector} is scaled to range $[0,1]$ and
therefore even players with different number of games in the database have comparable \emph{pattern vectors}.

\subsection{Pattern Features}
We need to define how to compose the patterns we use to describe moves.
There are some tradeoffs in play - overly general descriptions carry too few
information to discern various player attributes; too specific descriptions
gather too few specimen over the games sample and the vector differences are
not statistically significant.

We have chosen an intuitive and simple approach inspired by pattern features
used when computing ELO ratings for candidate patterns in Computer Go play.
\cite{ELO} Each pattern is a~combination of several {\em pattern features}
(name-value pairs) matched at the position of the played move.
We use these features:

\begin{itemize}
\item capture move flag
\item atari move flag
\item atari escape flag
\item contiguity-to-last flag --- whether the move has been played in one of 8 neighbors of the last move
\item contiguity-to-second-last flag
\item board edge distance --- only up to distance 4
\item spatial pattern --- configuration of stones around the played move
\end{itemize}

The spatial patterns are normalized (using a dictionary) to be always
black-to-play and maintain translational and rotational symmetry.
Configurations with diameter between 2 and 9 in the gridcular metric%
\footnote{The {\em gridcular} metric
$d(x,y) = |\delta x| + |\delta y| + \max(|\delta x|, |\delta y|)$ defines
a circle-like structure on the Go board square grid. \cite{SpatPat} }
are matched.

\subsection{Implementation}

We have implemented the data extraction by making use of the pattern
features matching implementation within the Pachi go-playing program
(TODO). We extract information on players by converting the SGF game
records to GTP (TODO) stream that feeds Pachi's {\tt patternscan}
engine which outputs a~single patternspec per move. We can then gather
all encountered patternspecs belonging to a~given player and summarize
them; the $\vec p$ vector then consists of normalized counts of
the given $n$ most frequent patternspecs.


\section{Data Mining}
\label{data-mining}

To assess the properties of gathered \emph{pattern vectors} and their influence on playing styles,
we have analysed the data by a~few basic data minining techniques.

First two methods rely purely on data gathered from the GoGoD database. Principal component
analysis finds orthogonal vector components that have biggest variance. Reversing the process then
indicates which patterns correlate with each style. Additionally, PCA can be used as a vector-preprocessing
for methods that are negatively sensitive to \emph{pattern vector} component correlations.

A~second method -- Kohonen's networks -- is based on the theory of self-organizing maps of neurons that
compete against each other for representation of the input space. Because neurons in the network are
organized in a two-dimensional plane, the trained network virtually spreads vectors to the 2D plane,
allowing for simple visualization.

In addition to methods operating just upon the set of \emph{pattern vectors}, we have used and compared two methods
that approximate an unknown \emph{style vector} $\vec S$ of a player with known \emph{pattern vector} $\vec P$.

First of them is called $k$-Nearest Neighbor (kNN) classification.
Simpy said kNN approximates $\vec S$ by the ``average'' of \emph{style vectors} of $k$ nearest \emph{pattern vectors}.
The last method is based on the theory of Neural Networks -- networks of artificial neurons, that are used
for their generalization abilities. Neural network can learn correlations between input and output vectors and
generalize the ``knowledge'' to unknown vectors sufficiently good.

TODO rozdelit na algo/results?? 

\subsection{Principal Component Analysis}
\label{data-mining}
Principal Component Analysis \emph{PCA} \cite{Jolliffe1986} is a~method we use to reduce the dimensions of
\emph{pattern vectors} while preserving as much information as possible.

Shortly, PCA is an eigenvalue decomposition of a~covariance matrix of centered \emph{pattern vectors}.
It can be thought of as a~mapping $o$ from $n$-dimensional vector space to a~reduced $m$-dimensional vector space.
The base of this reduced vector space comprises $m$ eigenvectors of original vectors' covariance matrix.
We choose them to be the eigenvectors with biggest eigenvalues. 
Ordered by decreasing eigenvalues, the eigenvectors form rows of the transformation matrix $W$.

Finally, we represent reduced \emph{pattern vectors} as a vector of coeficients of this eigenvector-base.
For each original \emph{pattern vector} $\vec p_i$, we obtain its new representation $\vec r_i$ as shown
in the following equation:
\begin{equation}
\vec r_i = W \cdot \vec p_i
\end{equation}

The whole process is described in the Algorithm \ref{alg:pca}.

\begin{algorithm}
\caption{PCA -- Principal Component analysis}
\begin{algorithmic}
\label{alg:pca}
\REQUIRE{$m > 0$, set of players $R$ with \emph{pattern vectors} $p_r$}
\STATE $\vec \mu \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_r}$
\FOR{ $r \in R$}
\STATE $\vec p_r \leftarrow \vec p_r - \vec \mu$
\ENDFOR
\FOR{ $(i,j) \in \{1,... ,n\} \times \{1,... ,n\}$}
\STATE $\mathit{Cov}[i,j] \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_{ri} \cdot \vec p_{rj}}$
\ENDFOR
\STATE Compute Eigenvalue Decomposition of $\mathit{Cov}$ matrix
\STATE Get $m$ biggest eigenvalues 
\STATE According eigenvectors ordered by decreasing eigenvalues form rows of matrix $W$ 
\FOR{ $r \in R$}
\STATE $\vec r_r\leftarrow W \vec p_r$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Kohonen Maps}
\label{koh}
Kohonen map is a self-organizing network with neurons organized in a two-dimensional plane.
Neurons in the map compete for representation of input vector space. Each neuron $\vec n$ represents a vector
and the network is trained so that the neurons that are topologically close tend to represent vectors that
are close as well. That is realised as follows. Initially random network is sequentially trained;
in each iterations we choose a random training vector $\vec t$ and find neuron $\vec w$ that is closest
to $\vec t$ in Euclidean metric (we call $\vec w$ a \emph{winner neuron}).

We then adapt neurons from the neighbourhood of $\vec w$ employing an equation:
\begin{equation}
\vec n = \vec n + \alpha \cdot \mathit{Influence}(\vec w, \vec n) \cdot (\vec t - \vec n) 
\end{equation}
where $\alpha$ is a learning parameter, usually decreasing in time. $Influence()$ is a function that forces neurons
to spread. Such function is usually realised using a mexican hat function or a difference-of-gaussians (see \cite{TODO}
for details). A state of the network can be valued by calculating mean square difference between each $\vec t \in T$
and its corresponding \emph{winner neuron} $\vec w_t$:
\begin{equation}
\mathit{Error}(N,T) = \sum_{\vec t \in T}{|\vec w_t - \vec t|}
\end{equation}


\begin{algorithm}
\caption{Kohonen maps -- training}
\begin{algorithmic}
\label{alg:koh}
\REQUIRE{Set of training vectors $T$, input dimension $D$}
\REQUIRE{max number of iterations $M$, desired error $E$}
\STATE $N \leftarrow \{\vec n | \vec n$ random, $\mathit{dim}(\vec n) = D\}$
\REPEAT
\STATE $\mathit{It} \leftarrow \mathit{It} + 1$
\STATE $\vec t \leftarrow \mathit{PickRandom}(T)$
\FORALL{$\vec n \in N$}
\STATE $D[\vec n] \leftarrow \mathit{EuclideanDistance}(\vec n, \vec t)$
\ENDFOR
\STATE Find $ \vec w \in N$ so that $D[\vec w] <= D[\vec m], \forall \vec m \in N$
\FORALL{$\vec n \in \mathit{TopologicalNeigbors}(N, \vec w)$}
\STATE $\vec n \leftarrow \vec n + \alpha(It) \cdot \mathit{Influence}(\vec w, \vec n) \cdot ( \vec t - \vec n ) $
\ENDFOR
\UNTIL{$\mathit{Error}(N, T) < E$ or $ \mathit{It} > M$}
\end{algorithmic}
\end{algorithm}


\subsection{k-nearest Neighbors Classifier}
\label{knn}
K-nearest neigbors is an essential classification technique.
We use it to approximate player's \emph{style vector} $\vec S$, assuming that his \emph{pattern vector} $\vec P$ is known.
To achieve this, we utilize \emph{reference style vectors} (see section \ref{style-vectors}).

The idea is based on a assumption that similarities in players' \emph{pattern vectors}
correlate with similarities in players' \emph{style vectors}. We try to approximate $\vec S$
as a weighted average of \emph{style vectors}
$\vec s_i$ of $k$ players with \emph{pattern vectors} $\vec p_i$ closest to $\vec P$.
This is illustrated in the Algorithm \ref{alg:knn}.
Note that the weight is a function of distance and it is not explicitly defined in Algorithm \ref{alg:knn}.
During our research, exponentialy decreasing weight has proven to be sufficient.

\begin{algorithm}
\caption{k-Nearest Neighbors}
\begin{algorithmic}
\label{alg:knn}
\REQUIRE{pattern vector $\vec P$, $k > 0$, set of reference players $R$}
\FORALL{$r \in R$ }
\STATE $D[r] \leftarrow \mathit{EuclideanDistance}(\vec p_r, \vec P)$
\ENDFOR
\STATE $N \leftarrow \mathit{SelectSmallest}(k, R, D)$
\STATE $\vec S \leftarrow \vec 0$
\FORALL{$r \in N $}
\STATE $\vec S \leftarrow \vec S + \mathit{Weight}(D[r]) \cdot \vec s_r $
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Neural Network Classifier}
\label{neural-net}

As an alternative to the k-Nearest Neigbors algorithm (section \ref{knn}), we have used 
a classificator based on feed-forward artificial neural networks \cite{TODO}.
Neural networks (NN) are known for their ability to generalize and find correlations and patterns between
input and output data. Neural network is an adaptive system and it 
must undergo a certain training before it can be reasonably used. Basically, we use
information for \emph{reference players} (for which either \emph{pattern vectors} and
\emph{style vectors} are known) as training data.

\subsubsection{Computation and activation of the NN}
Technically, neural network is a network of interconnected computational units called neurons.
A feedforward neural network has a layered topology; it usually has one \emph{input layer}, one \emph{output
layer} and an arbitrary number of \emph{hidden layers} between.

Each neuron $i$ is connected to all neurons in the previous layer and each connection has its weight $w_{ij}$

The computation proceeds in a discrete time steps.
In the first step, \emph{activation} of neurons in the \emph{input layer} is set according to the \emph{input vector}.
Then, we iteratively compute output of each neuron in next layer until the output layer is reached. The activity of
output layer is then presented as a result.

The activation $y_i$ of neuron $i$ from the layer $I$ is computed using the following equation:
\begin{equation}
y_i = f(\sum_{j \in J}{w_{ij} y_j})
\end{equation}
where $J$ is a previous layer, while $y_j$ is the activation for neurons from $J$ layer. Function $f()$ is
called \emph{activation function} and its purpose is to bound outputs of neurons. A typical example of an activation
function is a sigmoid function.\footnote{The sigmoid function is a special case of the logistic function; it is defined by the formula
$\sigma(x)=\frac{1}{1+e^{-(rx+k)}}$, parameters control the growth rate ($r$) and the x-position ($k$).}

\subsubsection{Training}
The training of the feedforward neural network usually involves some
modification of supervised Backpropagation learning algorithm. \cite{TODO}
We use first-order optimization algorithm called RPROP \cite{Riedmiller1993}.

Because the \emph{reference set} is not usually very large, we have devised a simple method for its extension.
This enhancement is based upon adding random linear combinations of \emph{style and pattern vectors} to the training set.

As insinuated above, the training set consist of pairs of input vectors (\emph{pattern vectors}) and
desired output vectors (\emph{style vectors}). The training set $T$ is then enlarged by adding linear combinations:
\begin{equation}
T_\mathit{base} = \{(\vec p_r, \vec s_r) | r \in R\}\\
\end{equation}
\begin{equation}
T_\mathit{ext} = \{(\vec p, \vec s) | \exists D \subseteq R : \vec p = \sum_{d \in D}{g_d \vec p_d}, \vec s = \sum_{d \in D}{g_d \vec s_d}\}
\end{equation}
TODO zabudovat $g_d$ dovnitr?
where $g_d, d \in D$ are random coeficients, so that $\sum_{d \in D}{g_d} = 1$. The training set
is then constructed as:
\begin{equation}
T = T_\mathit{base} \cup \mathit{SomeFiniteSubset}(T_\mathit{ext})
\end{equation}

The network is trained as shown in Algorithm \ref{alg:tnn}.

\begin{algorithm}
\caption{Training Neural Network}
\begin{algorithmic}
\label{alg:tnn}
\REQUIRE{Train set $T$, desired error $e$, max iterations $M$}
\STATE $N \leftarrow \mathit{RandomlyInitializedNetwork}()$
\STATE $\mathit{It} \leftarrow 0$
\REPEAT
\STATE $\mathit{It} \leftarrow \mathit{It} + 1$
\STATE $\Delta \vec w \leftarrow \vec 0$
\STATE $\mathit{TotalError} \leftarrow 0$
%\FORALL{$(\overrightarrow{Input}, \overrightarrow{DesiredOutput}) \in T$}
%\STATE $\overrightarrow{Output} \leftarrow Result(N, \overrightarrow{Input})$
%\STATE $E \leftarrow |\overrightarrow{DesiredOutput} - \overrightarrow{Output}|$
\FORALL{$(\mathit{Input}, \mathit{DesiredOutput}) \in T$}
\STATE $\mathit{Output} \leftarrow \mathit{Result}(N, \mathit{Input})$
\STATE $\mathit{Error} \leftarrow |\mathit{DesiredOutput} - \mathit{Output}|$
\STATE $\Delta \vec w \leftarrow \Delta \vec w + \mathit{WeightUpdate}(N,\mathit{Error})$
\STATE $\mathit{TotalError} \leftarrow \mathit{TotalError} + \mathit{Error}$
\ENDFOR
\STATE $N \leftarrow \mathit{ModifyWeights}(N, \Delta \vec w)$
\UNTIL{$\mathit{TotalError} < e$ or $ \mathit{It} > M$}
\end{algorithmic}
\end{algorithm}


\subsubsection{Architecture details}
TODO num layers, num neurons, ..


\subsection{Implementation}

We have implemented the data mining methods as an open-source project ``gostyle'' \cite{TODO},
licensed under GNU GPL.
PCA: In our implementation, we use a~library called MDP \cite{MDP}.
TODO libfann


\section{Strength Estimation Analysis}

PCA analysis yielded X, chi-square test blabla...

We then tried to apply the NN classifier with linear output function on the dataset
and that yielded Y (see fig. Z), with MSE abcd.


\section{Style Components Analysis}

PCA analysis yielded X, chi-square test...

We then tried to apply the NN classifier with linear output function on the dataset
and that yielded Y (see fig. Z), with MSE abcd.


\section{Proposed Applications}

.


% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex, 
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}

% Note that IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command, the
% \label for the overall figure must come after \caption.
% \hfil must be used as a separator to get equal spacing.
% The subfigure.sty package works much the same way, except \subfigure is
% used instead of \subfloat.
%
%\begin{figure*}[!t]
%\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.


% An example of a floating table. Note that, for IEEE style tables, the 
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals use top floats exclusively.
% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
% floats. This can be corrected via the \fnbelowfloat command of the
% stfloats package.



\section{Conclusion}
The conclusion goes here.
We have shown brm and proposed brm.

Since we are not aware of any previous research on this topic and we
are limited by space and time constraints, plenty of research remains
to be done. There is plenty of room for further research in all parts
of our analysis --- different methods of generating the $\vec p$ vectors
can be explored; other data mining methods could be tried.
It can be argued that many players adjust their style by game conditions
(Go development era, handicap, komi and color, time limits, opponent)
or styles might express differently in various game stages.
Finally, more professional players could be consulted on the findings
and for style scales calibration.

TODO: Future research --- Sparse PCA




% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%


%\appendices
%\section{Proof of the First Zonklar Equation}
%Appendix one text goes here.
%
%% you can choose not to have a title for an appendix
%% if you want by leaving the argument blank
%\section{}
%Appendix two text goes here.


% use section* for acknowledgement
\section*{Acknowledgment}
\label{acknowledgement}


We would like to thank X for reviewing our paper.
We appreciate helpful comments on our general methodology
by John Fairbairn, T. M. Hall, Robert Jasiek
and several GoDiscussions.com users. \cite{GoDiscThread}
Finally, we are very grateful for ranking of go styles of selected professionals
by Alexander Dinerstein 3-pro, Motoki Noguchi 7-dan and Vit Brunner 4-dan.


% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
\bibliography{gostyle}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
%\begin{thebibliography}{1}
%
%\bibitem{MasterMCTS}
%
%\end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

\begin{IEEEbiography}{Michael Shell}
Biography text here.
\end{IEEEbiography}

% if you will not have a photo at all:
\begin{IEEEbiographynophoto}{John Doe}
Biography text here.
\end{IEEEbiographynophoto}

% insert where needed to balance the two columns on the last page with
% biographies
%\newpage

\begin{IEEEbiographynophoto}{Jane Doe}
Biography text here.
\end{IEEEbiographynophoto}

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}