tex: PCA-style r-table
[gostyle.git] / tex / gostyle.tex
blobd5559f92a214923e8f99b934923fd820257beb4b
1 \documentclass[journal]{IEEEtran}
3 \usepackage{cite}
4 % cite.sty was written by Donald Arseneau
5 % V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
6 % \cite{} output to follow that of IEEE. Loading the cite package will
7 % result in citation numbers being automatically sorted and properly
8 % "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
9 % cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
10 % \cite will automatically add leading space, if needed. Use cite.sty's
11 % noadjust option (cite.sty V3.8 and later) if you want to turn this off.
12 % cite.sty is already installed on most LaTeX systems. Be sure and use
13 % version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
14 % not currently provide for hyperlinked citations.
15 % The latest version can be obtained at:
16 % http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
17 % The documentation is contained in the cite.sty file itself.
20 % *** GRAPHICS RELATED PACKAGES ***
22 \ifCLASSINFOpdf
23 % \usepackage[pdftex]{graphicx}
24 % declare the path(s) where your graphic files are
25 % \graphicspath{{../pdf/}{../jpeg/}}
26 % and their extensions so you won't have to specify these with
27 % every instance of \includegraphics
28 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
29 \else
30 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
31 % will default to the driver specified in the system graphics.cfg if no
32 % driver is specified.
33 % \usepackage[dvips]{graphicx}
34 \usepackage{graphicx}
35 % declare the path(s) where your graphic files are
36 % \graphicspath{{../eps/}}
37 % and their extensions so you won't have to specify these with
38 % every instance of \includegraphics
39 % \DeclareGraphicsExtensions{.eps}
40 \fi
42 \usepackage{threeparttable}
44 \usepackage{algorithm}
45 \usepackage{algorithmic}
46 %\usepackage{algpseudocode}
47 % WICKED: nefunguje ani jedno???
48 % algorithmic.sty can be obtained at:
49 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
50 % There is also a support site at:
51 % http://algorithms.berlios.de/index.html
52 % Also of interest may be the (relatively newer and more customizable)
53 % algorithmicx.sty package by Szasz Janos:
54 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
56 % *** ALIGNMENT PACKAGES ***
58 %\usepackage{array}
59 % http://www.ctan.org/tex-archive/macros/latex/required/tools/
62 \usepackage{amsmath}
63 %\usepackage{mdwtab}
64 % http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
67 % IEEEtran contains the IEEEeqnarray family of commands that can be used to
68 % generate multiline equations as well as matrices, tables, etc., of high
69 % quality.
71 %\usepackage{eqparbox}
72 % Also of notable interest is Scott Pakin's eqparbox package for creating
73 % (automatically sized) equal width boxes - aka "natural width parboxes".
74 % Available at:
75 % http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
79 % *** SUBFIGURE PACKAGES ***
80 %\usepackage[tight,footnotesize]{subfigure}
81 % subfigure.sty was written by Steven Douglas Cochran. This package makes it
82 % easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
83 % work, it is a good idea to load it with the tight package option to reduce
84 % the amount of white space around the subfigures. subfigure.sty is already
85 % installed on most LaTeX systems. The latest version and documentation can
86 % be obtained at:
87 % http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
88 % subfigure.sty has been superceeded by subfig.sty.
92 %\usepackage[caption=false]{caption}
93 %\usepackage[font=footnotesize]{subfig}
94 % subfig.sty, also written by Steven Douglas Cochran, is the modern
95 % replacement for subfigure.sty. However, subfig.sty requires and
96 % automatically loads Axel Sommerfeldt's caption.sty which will override
97 % IEEEtran.cls handling of captions and this will result in nonIEEE style
98 % figure/table captions. To prevent this problem, be sure and preload
99 % caption.sty with its "caption=false" package option. This is will preserve
100 % IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
101 % (recommended due to many improvements over 1.2) of subfig.sty supports
102 % the caption=false option directly:
103 %\usepackage[caption=false,font=footnotesize]{subfig}
105 % The latest version and documentation can be obtained at:
106 % http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
107 % The latest version and documentation of caption.sty can be obtained at:
108 % http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
112 % *** FLOAT PACKAGES ***
114 %\usepackage{fixltx2e}
115 % fixltx2e, the successor to the earlier fix2col.sty, was written by
116 % Frank Mittelbach and David Carlisle. This package corrects a few problems
117 % in the LaTeX2e kernel, the most notable of which is that in current
118 % LaTeX2e releases, the ordering of single and double column floats is not
119 % guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
120 % single column figure to be placed prior to an earlier double column
121 % figure. The latest version and documentation can be found at:
122 % http://www.ctan.org/tex-archive/macros/latex/base/
126 %\usepackage{stfloats}
127 % stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
128 % the ability to do double column floats at the bottom of the page as well
129 % as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
130 % LaTeX2e). It also provides a command:
131 %\fnbelowfloat
132 % to enable the placement of footnotes below bottom floats (the standard
133 % LaTeX2e kernel puts them above bottom floats). This is an invasive package
134 % which rewrites many portions of the LaTeX2e float routines. It may not work
135 % with other packages that modify the LaTeX2e float routines. The latest
136 % version and documentation can be obtained at:
137 % http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
138 % Documentation is contained in the stfloats.sty comments as well as in the
139 % presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
140 % does not allow \baselineskip to stretch. Authors submitting work to the
141 % IEEE should note that IEEE rarely uses double column equations and
142 % that authors should try to avoid such use. Do not be tempted to use the
143 % cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
144 % not format its papers in such ways.
147 %\ifCLASSOPTIONcaptionsoff
148 % \usepackage[nomarkers]{endfloat}
149 % \let\MYoriglatexcaption\caption
150 % \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
151 %\fi
152 % endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
153 % This package may be useful when used in conjunction with IEEEtran.cls'
154 % captionsoff option. Some IEEE journals/societies require that submissions
155 % have lists of figures/tables at the end of the paper and that
156 % figures/tables without any captions are placed on a page by themselves at
157 % the end of the document. If needed, the draftcls IEEEtran class option or
158 % \CLASSINPUTbaselinestretch interface can be used to increase the line
159 % spacing as well. Be sure and use the nomarkers option of endfloat to
160 % prevent endfloat from "marking" where the figures would have been placed
161 % in the text. The two hack lines of code above are a slight modification of
162 % that suggested by in the endfloat docs (section 8.3.1) to ensure that
163 % the full captions always appear in the list of figures/tables - even if
164 % the user used the short optional argument of \caption[]{}.
165 % IEEE papers do not typically make use of \caption[]'s optional argument,
166 % so this should not be an issue. A similar trick can be used to disable
167 % captions of packages such as subfig.sty that lack options to turn off
168 % the subcaptions:
169 % For subfig.sty:
170 % \let\MYorigsubfloat\subfloat
171 % \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
172 % For subfigure.sty:
173 % \let\MYorigsubfigure\subfigure
174 % \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
175 % However, the above trick will not work if both optional arguments of
176 % the \subfloat/subfig command are used. Furthermore, there needs to be a
177 % description of each subfigure *somewhere* and endfloat does not add
178 % subfigure captions to its list of figures. Thus, the best approach is to
179 % avoid the use of subfigure captions (many IEEE journals avoid them anyway)
180 % and instead reference/explain all the subfigures within the main caption.
181 % The latest version of endfloat.sty and its documentation can obtained at:
182 % http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
184 % The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
185 % later in the document, say, to conditionally put the References on a
186 % page by themselves.
188 % *** PDF, URL AND HYPERLINK PACKAGES ***
190 \usepackage{url}
191 % url.sty was written by Donald Arseneau. It provides better support for
192 % handling and breaking URLs. url.sty is already installed on most LaTeX
193 % systems. The latest version can be obtained at:
194 % http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
195 % Read the url.sty source comments for usage information. Basically,
196 % \url{my_url_here}.
199 % *** Do not adjust lengths that control margins, column widths, etc. ***
200 % *** Do not use packages that alter fonts (such as pslatex). ***
201 % There should be no need to do such things with IEEEtran.cls V1.6 and later.
202 % (Unless specifically asked to do so by the journal or conference you plan
203 % to submit to, of course. )
205 % correct bad hyphenation here
206 \hyphenation{op-tical net-works semi-conduc-tor know-ledge}
209 \begin{document}
211 % paper title
212 % can use linebreaks \\ within to get better formatting as desired
213 \title{On Move Pattern Trends\\in Large Go Games Corpus}
215 % use \thanks{} to gain access to the first footnote area
216 % a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
217 % was not built to handle multiple paragraphs
218 \author{Petr~Baudi\v{s},~Josef~Moud\v{r}\'{i}k% <-this % stops a space
219 \thanks{P. Baudi\v{s} 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
220 \thanks{J. Moud\v{r}\'{i}k is student at the Faculty of Math and Physics, Charles University, Prague, CZ.}}
222 % note the % following the last \IEEEmembership and also \thanks -
223 % these prevent an unwanted space from occurring between the last author name
224 % and the end of the author line. i.e., if you had this:
226 % \author{....lastname \thanks{...} \thanks{...} }
227 % ^------------^------------^----Do not want these spaces!
229 % a space would be appended to the last name and could cause every name on that
230 % line to be shifted left slightly. This is one of those "LaTeX things". For
231 % instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
232 % "AB" then you have to do: "\textbf{A}\textbf{B}"
233 % \thanks is no different in this regard, so shield the last } of each \thanks
234 % that ends a line with a % and do not let a space in before the next \thanks.
235 % Spaces after \IEEEmembership other than the last one are OK (and needed) as
236 % you are supposed to have spaces between the names. For what it is worth,
237 % this is a minor point as most people would not even notice if the said evil
238 % space somehow managed to creep in.
241 % The paper headers
242 \markboth{Transactions on Computational Intelligence and AI in Games}%
243 {On Pattern Feature Trends in Large Go Game Corpus}
244 % The only time the second header will appear is for the odd numbered pages
245 % after the title page when using the twoside option.
247 % *** Note that you probably will NOT want to include the author's ***
248 % *** name in the headers of peer review papers. ***
249 % You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
250 % you desire.
255 % If you want to put a publisher's ID mark on the page you can do it like
256 % this:
257 %\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
258 % Remember, if you use this you must call \IEEEpubidadjcol in the second
259 % column for its text to clear the IEEEpubid mark.
263 % use for special paper notices
264 %\IEEEspecialpapernotice{(Invited Paper)}
269 % make the title area
270 \maketitle
273 \begin{abstract}
274 %\boldmath
276 We process a~large corpus of game records of the board game of Go and
277 propose a~way to extract per-player summary information on played moves.
278 We then apply several basic data-mining methods on the summary
279 information to identify the most differentiating features within the
280 summary information, and discuss their correspondence with traditional
281 Go knowledge. We show mappings of the features to player attributes
282 like playing strength or informally perceived ``playing style'' (such as
283 territoriality or aggressivity), and propose applications including
284 seeding real-work ranks of internet players, aiding in Go study, or
285 contribution to discussion within Go theory on the scope of ``playing
286 style''.
288 \end{abstract}
289 % IEEEtran.cls defaults to using nonbold math in the Abstract.
290 % This preserves the distinction between vectors and scalars. However,
291 % if the journal you are submitting to favors bold math in the abstract,
292 % then you can use LaTeX's standard command \boldmath at the very start
293 % of the abstract to achieve this. Many IEEE journals frown on math
294 % in the abstract anyway.
296 % Note that keywords are not normally used for peerreview papers.
297 \begin{IEEEkeywords}
298 board games, go, data mining, pattern recongition, player strength, playing style
299 \end{IEEEkeywords}
306 % For peer review papers, you can put extra information on the cover
307 % page as needed:
308 % \ifCLASSOPTIONpeerreview
309 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
310 % \fi
312 % For peerreview papers, this IEEEtran command inserts a page break and
313 % creates the second title. It will be ignored for other modes.
314 \IEEEpeerreviewmaketitle
318 \section{Introduction}
319 % The very first letter is a 2 line initial drop letter followed
320 % by the rest of the first word in caps.
322 % form to use if the first word consists of a single letter:
323 % \IEEEPARstart{A}{demo} file is ....
325 % form to use if you need the single drop letter followed by
326 % normal text (unknown if ever used by IEEE):
327 % \IEEEPARstart{A}{}demo file is ....
329 % Some journals put the first two words in caps:
330 % \IEEEPARstart{T}{his demo} file is ....
332 % Here we have the typical use of a "T" for an initial drop letter
333 % and "HIS" in caps to complete the first word.
334 \IEEEPARstart{T}{he} field of Computer Go usually focuses on the problem
335 of creating a~program to play the game, finding the best move from a~given
336 board position. We will make use of one method developed in the course
337 of such research and apply it to the analysis of existing game records
338 with the aim of helping humans to play the game better instead.
340 Go is a~two-player full-information board game played
341 on a~square grid (usually $19\times19$ lines) with black and white
342 stones; the goal of the game is to surround the most territory and
343 capture enemy stones. We assume basic familiarity with the game.
345 Many Go players are eager to play using computers (usually over
346 the internet) and review games played by others on computers as well.
347 This means that large amounts of game records are collected and digitally
348 stored, enabling easy processing of such collections. However, so far
349 only little has been done with the available data --- we are aware
350 only of uses for simple win/loss statistics (TODO: KGS Stats, KGS Analytics,
351 Pro Go Rating) and ''next move'' statistics on a~specific position (TODO:
352 Kombilo, Moyo Go Studio).
354 We present a~more in-depth approach --- from all played moves, we devise
355 a~compact evaluation of each player. We then explore correlations between
356 evaluations of various players in light of externally given information.
357 This way, we can discover similarity between moves characteristics of
358 players with the same playing strength, or discuss the meaning of the
359 "playing style" concept on the assumption that similar playing styles
360 should yield similar moves characteristics.
363 \section{Data Extraction}
364 \label{pattern-vectors}
366 As the input of our analysis, we use large collections of game records\footnote{We
367 use the SGF format (TODO) in our implementation.} organized by player names.
368 In order to generate the required compact description of most frequently played moves,
369 we construct a set of $n$ most occuring patterns (\emph{top patterns})
370 across all players and games from the database.\footnote{We use $n=500$ in our analysis.}
372 For each player, we then count how many times was each of those $n$ patterns played
373 during all his games and finally assign him a~{\em pattern vector} $\vec p$ of dimension $n$, with each
374 dimension corresponding to the relative number of occurences of a given pattern
375 (relative with respect to player's most played \emph{top pattern}). Using relative numbers of occurences ensures that
376 each dimension of player's \emph{pattern vector} is scaled to range $[0,1]$ and
377 therefore even players with different number of games in the database have comparable \emph{pattern vectors}.
379 \subsection{Pattern Features}
380 We need to define how to compose the patterns we use to describe moves.
381 However, there are some tradeoffs -- overly general descriptions carry too few
382 information to discern various player attributes; too specific descriptions
383 gather too few specimen over the games sample and the vector differences are
384 not statistically significant.
386 We have chosen an intuitive and simple approach inspired by pattern features
387 used when computing ELO ratings for candidate patterns in Computer Go play.
388 \cite{ELO} Each pattern is a~combination of several {\em pattern features}
389 (name--value pairs) matched at the position of the played move.
390 We use these features:
392 \begin{itemize}
393 \item capture move flag
394 \item atari move flag
395 \item atari escape flag
396 \item contiguity-to-last flag --- whether the move has been played in one of 8 neighbors of the last move
397 \item contiguity-to-second-last flag
398 \item board edge distance --- only up to distance 4
399 \item spatial pattern --- configuration of stones around the played move
400 \end{itemize}
402 The spatial patterns are normalized (using a dictionary) to be always
403 black-to-play and maintain translational and rotational symmetry.
404 Configurations of radius between 2 and 9 in the gridcular metric%
405 \footnote{The {\em gridcular} metric
406 $d(x,y) = |\delta x| + |\delta y| + \max(|\delta x|, |\delta y|)$ defines
407 a circle-like structure on the Go board square grid. \cite{SpatPat} }
408 are matched.
410 \subsection{Implementation}
412 We have implemented the data extraction by making use of the pattern
413 features matching implementation within the Pachi go-playing program
414 (TODO). We extract information on players by converting the SGF game
415 records to GTP (TODO) stream that feeds Pachi's {\tt patternscan}
416 engine which outputs a~single {\em patternspec} (string representation
417 of the particular pattern features combination) per move.
419 %We can then gather all patternspecs played by a~given player and summarize
420 %them; the $\vec p$ vector then consists of normalized counts of
421 %the given $n$ most frequent patternspecs.
423 \section{Data Mining}
424 \label{data-mining}
426 To assess the properties of gathered \emph{pattern vectors}
427 and their influence on playing styles,
428 we have processes the data using a~few basic data minining techniques.
430 The first two methods ({\em analytic}) rely purely on data gathered
431 from the game collection
432 and serve to show internal structure and correlations within the data set.
434 Principal component analysis finds orthogonal vector components that
435 have the largest variance.
436 Reversing the process can indicate which patterns correlate with each component.
437 Additionally, PCA can be used as a vector-preprocessing for methods
438 that are (negatively) sensitive to \emph{pattern vector} component correlations.
440 A~second method -- Kohonen maps -- is based on the theory of self-organizing maps
441 of abstract units (neurons) that
442 compete against each other for the representation of the input space.
443 Because neurons in the network are organized in a two-dimensional plane,
444 the trained network virtually spreads vectors to the 2D plane,
445 allowing for simple visualization of clusters of players with similar ``properties''.
448 Furthermore, we have used two \emph{classification} methods that assign
449 each \emph{pattern vector} $\vec P$ some additional data (\emph{output vector} $\vec O$),
450 representing e.g.~information about styles, player's strength or even a country of origin.
451 Initially, the methods must be nonetheless calibrated (trained) on some expert or prior knowledge,
452 usually in the form of pairs of \emph{reference pattern vectors} and their \emph{output vectors}.
454 Moreover, the reference set can be divided into training and testing pairs
455 and the methods can be compared by the square error on testing data set (difference of
456 \emph{output vectors} approximated by the method and their real desired value).
458 %\footnote{However, note that dicrete characteristics such as country of origin are
459 %not very feasible to use here, since WHAT??? is that even true?? }
461 $k$-Nearest Neighbor \cite{CoverHart1967} classifier (the first method)
462 approximates $\vec O$ by composing the \emph{output vectors}
463 of $k$ \emph{reference pattern vectors} closest to $\vec P$.
465 The other classifier is based on a~multi-layer feed-forward Artificial Neural Network:
466 the neural network can learn correlations between input and output vectors
467 and generalize the ``knowledge'' to unknown vectors; it can be more flexible
468 in the interpretation of different pattern vector elements and discern more
469 complex relations than the kNN classifier, but e.g.~requires larger training sample.
471 \subsection{Principal Component Analysis}
472 \label{data-mining}
473 We use Principal Component Analysis \emph{PCA} \cite{Jolliffe1986}
474 to reduce the dimensions of the \emph{pattern vectors} while preserving
475 as much information as possible.
477 Briefly, PCA is an eigenvalue decomposition of a~covariance matrix of centered \emph{pattern vectors},
478 producing a~linear mapping $o$ from $n$-dimensional vector space
479 to a~reduced $m$-dimensional vector space.
480 The $m$ eigenvectors of the original vectors' covariance matrix
481 with the largest eigenvalues are used as the base of the reduced vector space;
482 the eigenvectors form the transformation matrix $W$.
484 For each original \emph{pattern vector} $\vec p_i$,
485 we obtain its new representation $\vec r_i$ in the PCA base
486 as shown in the following equation:
487 \begin{equation}
488 \vec r_i = W \cdot \vec p_i
489 \end{equation}
491 The whole process is described in the Algorithm \ref{alg:pca}.
493 \begin{algorithm}
494 \caption{PCA -- Principal Component Analysis}
495 \begin{algorithmic}
496 \label{alg:pca}
497 \REQUIRE{$m > 0$, set of players $R$ with \emph{pattern vectors} $p_r$}
498 \STATE $\vec \mu \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_r}$
499 \FOR{ $r \in R$}
500 \STATE $\vec p_r \leftarrow \vec p_r - \vec \mu$
501 \ENDFOR
502 \FOR{ $(i,j) \in \{1,... ,n\} \times \{1,... ,n\}$}
503 \STATE $\mathit{Cov}[i,j] \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_{ri} \cdot \vec p_{rj}}$
504 \ENDFOR
505 \STATE Compute Eigenvalue Decomposition of $\mathit{Cov}$ matrix
506 \STATE Get $m$ largest eigenvalues
507 \STATE Most significant eigenvectors ordered by decreasing eigenvalues form the rows of matrix $W$
508 \FOR{ $r \in R$}
509 \STATE $\vec r_r\leftarrow W \vec p_r$
510 \ENDFOR
511 \end{algorithmic}
512 \end{algorithm}
514 \label{pearson}
515 We will want to find correlations between PCA dimensions and
516 some prior knowledge (player rank, style vector).
517 We compute the well-known {\em Pearson product-moment correlation coefficient} \cite{Pearson}
518 values for this purpose, measuring the strength of the linear dependence%
519 \footnote{A desirable property of PMCC is that it is invariant to translations and rescaling
520 of the vectors.}
521 between the dimensions:
523 $$ r_{X,Y} = {{\rm cov}(X,Y) \over \sigma_X \sigma_Y} $$
525 \subsection{Kohonen Maps}
526 \label{koh}
527 Kohonen map is a self-organizing network with neurons organized in a~two-dimensional plane.
528 Neurons in the map compete for representation of portions of the input vector space.
529 Each neuron $\vec n$ represents a vector and the network is trained so that the neurons
530 that are topologically close tend to represent vectors that are close as well.
532 First, a~randomly initialized network is sequentially trained;
533 in each iteration, we choose a~random training vector $\vec t$
534 and find the neuron $\vec w$ that is closest to $\vec t$ in Euclidean metric
535 (we call $\vec w$ a~\emph{winner}).
537 We then adapt neurons $n$ from the neighbourhood of $\vec w$ employing an equation:
538 \begin{equation}
539 \vec n = \vec n + \alpha \cdot \mathit{Influence}(\vec w, \vec n) \cdot (\vec t - \vec n)
540 \end{equation}
541 where $\alpha$ is a learning parameter, usually decreasing in time.
542 $Influence()$ is a function that forces neurons to spread.
543 Such function is usually realised using a mexican hat function or a difference-of-gaussians
544 (see \cite{TODO} for details).
545 The state of the network can be evaluated by calculating mean square difference
546 between each $\vec t \in T$ and its corresponding \emph{winner neuron} $\vec w_t$:
547 \begin{equation}
548 \mathit{Error}(N,T) = \sum_{\vec t \in T}{|\vec w_t - \vec t|}
549 \end{equation}
552 \begin{algorithm}
553 \caption{Kohonen maps -- training}
554 \begin{algorithmic}
555 \label{alg:koh}
556 \REQUIRE{Set of training vectors $T$, input dimension $D$}
557 \REQUIRE{max number of iterations $M$, desired error $E$}
558 \STATE $N \leftarrow \{\vec n | \vec n$ random, $\mathit{dim}(\vec n) = D\}$
559 \REPEAT
560 \STATE $\mathit{It} \leftarrow \mathit{It} + 1$
561 \STATE $\vec t \leftarrow \mathit{PickRandom}(T)$
562 \FORALL{$\vec n \in N$}
563 \STATE $D[\vec n] \leftarrow \mathit{EuclideanDistance}(\vec n, \vec t)$
564 \ENDFOR
565 \STATE Find $ \vec w \in N$ so that $D[\vec w] <= D[\vec m], \forall \vec m \in N$
566 \FORALL{$\vec n \in \mathit{TopologicalNeigbors}(N, \vec w)$}
567 \STATE $\vec n \leftarrow \vec n + \alpha(It) \cdot \mathit{Influence}(\vec w, \vec n) \cdot ( \vec t - \vec n ) $
568 \ENDFOR
569 \UNTIL{$\mathit{Error}(N, T) < E$ or $ \mathit{It} > M$}
570 \end{algorithmic}
571 \end{algorithm}
574 \subsection{k-nearest Neighbors Classifier}
575 \label{knn}
576 Our goal is to approximate player's \emph{output vector} $\vec O$; we know his \emph{pattern vector} $\vec P$.
577 We further assume that similarities in players' \emph{pattern vectors}
578 uniformly correlate with similarities in players' \emph{output vectors}.
580 We require a set of reference players $R$ with known \emph{pattern vectors} $\vec p_r$
581 and \emph{output vectors} $\vec o_r$.
583 $\vec O$ is approximated as a~weighted average of \emph{output vectors}
584 $\vec o_i$ of $k$ players with \emph{pattern vectors} $\vec p_i$ closest to $\vec P$.
585 This is illustrated in the Algorithm \ref{alg:knn}.
586 Note that the weight is a function of distance and it is not explicitly defined in Algorithm \ref{alg:knn}.
587 During our research, exponentially decreasing weight has proven to be sufficient.
589 \begin{algorithm}
590 \caption{k-Nearest Neighbors}
591 \begin{algorithmic}
592 \label{alg:knn}
593 \REQUIRE{pattern vector $\vec P$, $k > 0$, set of reference players $R$}
594 \FORALL{$r \in R$ }
595 \STATE $D[r] \leftarrow \mathit{EuclideanDistance}(\vec p_r, \vec P)$
596 \ENDFOR
597 \STATE $N \leftarrow \mathit{SelectSmallest}(k, R, D)$
598 \STATE $\vec O \leftarrow \vec 0$
599 \FORALL{$r \in N $}
600 \STATE $\vec O \leftarrow \vec O + \mathit{Weight}(D[r]) \cdot \vec o_r $
601 \ENDFOR
602 \end{algorithmic}
603 \end{algorithm}
605 \subsection{Neural Network Classifier}
606 \label{neural-net}
608 Feedforward neural networks \cite{TODO} are known for their ability to generalize
609 and find correlations and patterns between input and output data, working as a classifier.
611 Before use, the network is iteratively trained on the training data
612 (again consisting of pairs of \emph{pattern vectors} as input and \emph{output vectors})
613 until the error on the training set is reasonably small.
615 %Neural network is an adaptive system that must undergo a training
616 %period similarly to the requirement
617 %of reference vectors for the k-Nearest Neighbors algorithm above.
619 \subsubsection{Computation and activation of the NN}
620 Technically, the neural network is a network of interconnected computational units called neurons.
621 A feedforward neural network has a layered topology;
622 it usually has one \emph{input layer}, one \emph{output layer}
623 and an arbitrary number of \emph{hidden layers} between.
625 Each neuron $i$ is connected to all neurons in the previous layer and each connection has its weight $w_{ij}$
627 The computation proceeds in discrete time steps.
628 In the first step, the neurons in the \emph{input layer}
629 are \emph{activated} according to the \emph{input vector}.
630 Then, we iteratively compute output of each neuron in the next layer
631 until the output layer is reached.
632 The activity of output layer is then presented as the result.
634 The activation $y_i$ of neuron $i$ from the layer $I$ is computed as
635 \begin{equation}
636 y_i = f\left(\sum_{j \in J}{w_{ij} y_j}\right)
637 \end{equation}
638 where $J$ is the previous layer, while $y_j$ is the activation for neurons from $J$ layer.
639 Function $f()$ is a~so-called \emph{activation function}
640 and its purpose is to bound the outputs of neurons.
641 A typical example of an activation function is the sigmoid function.%
642 \footnote{A special case of the logistic function, defined by the formula
643 $\sigma(x)=\frac{1}{1+e^{-(rx+k)}}$; parameters control the growth rate ($r$)
644 and the x-position ($k$).}
646 \subsubsection{Training}
647 The training of the feed-forward neural network usually involves some
648 modification of supervised Backpropagation learning algorithm. \cite{TODO}
649 We use first-order optimization algorithm called RPROP \cite{Riedmiller1993}.
651 %Because the \emph{reference set} is usually not very large,
652 %we have devised a simple method for its extension.
653 %This enhancement is based upon adding random linear combinations
654 %of \emph{style and pattern vectors} to the training set.
656 As outlined above, the training set $T$ consists of pairs of
657 input vectors (\emph{pattern vectors} $\vec p_i)$ and
658 desired \emph{output vectors} $\vec o_i$.
660 The training algorithm is shown in Algorithm \ref{alg:tnn}.
662 \begin{algorithm}
663 \caption{Training Neural Network}
664 \begin{algorithmic}
665 \label{alg:tnn}
666 \REQUIRE{Train set $T$, desired error $e$, max iterations $M$}
667 \STATE $N \leftarrow \mathit{RandomlyInitializedNetwork}()$
668 \STATE $\mathit{It} \leftarrow 0$
669 \REPEAT
670 \STATE $\mathit{It} \leftarrow \mathit{It} + 1$
671 \STATE $\Delta \vec w \leftarrow \vec 0$
672 \STATE $\mathit{TotalError} \leftarrow 0$
673 %\FORALL{$(\overrightarrow{Input}, \overrightarrow{DesiredOutput}) \in T$}
674 %\STATE $\overrightarrow{Output} \leftarrow Result(N, \overrightarrow{Input})$
675 %\STATE $E \leftarrow |\overrightarrow{DesiredOutput} - \overrightarrow{Output}|$
676 \FORALL{$(\mathit{Input}, \mathit{DesiredOutput}) \in T$}
677 \STATE $\mathit{Output} \leftarrow \mathit{Result}(N, \mathit{Input})$
678 \STATE $\mathit{Error} \leftarrow |\mathit{DesiredOutput} - \mathit{Output}|$
679 \STATE $\Delta \vec w \leftarrow \Delta \vec w + \mathit{WeightUpdate}(N,\mathit{Error})$
680 \STATE $\mathit{TotalError} \leftarrow \mathit{TotalError} + \mathit{Error}$
681 \ENDFOR
682 \STATE $N \leftarrow \mathit{ModifyWeights}(N, \Delta \vec w)$
683 \UNTIL{$\mathit{TotalError} < e$ or $ \mathit{It} > M$}
684 \end{algorithmic}
685 \end{algorithm}
687 \subsubsection{Architecture details}
688 TODO num layers, num neurons, ..
689 TODO patri to vubec sem, spise ne
691 \subsection{Implementation}
693 We have implemented the data mining methods as an open-source framework ``gostyle'' \cite{TODO},
694 made available under the GNU GPL licence.
695 The majority of our basic processing and the analysis parts are implemented in the Python \cite{Python2005} programming language.
697 Nonetheless, we use a number of external libraries, such as the MDP library \cite{MDP} (used for PCA analysis),
698 Kohonen library \cite{KohonenPy}.
700 The neural network part of the project is written using the excellent libfann C library\cite{Nissen2003}.
703 \section{Strength Estimator}
705 \begin{figure*}[!t]
706 \centering
707 \includegraphics[width=7in]{strength-pca}
708 \caption{PCA of by-strength vectors}
709 \label{fig:strength_pca}
710 \end{figure*}
712 First, we have used our framework to analyse correlations of pattern vectors
713 and playing strength. Like in other competitively played board games, Go players
714 receive real-world rating based on tournament games, and rank based on their
715 rating.\footnote{Elo-like rating system \cite{GoR} is usually used,
716 corresponding to even win chances for game of two players with the same rank,
717 and about 2:3 win chance for stronger in case of one rank difference.}%
718 \footnote{Professional ranks and dan ranks in some Asia countries may
719 be assigned differently.} The amateur ranks range from 30kyu (beginner) to
720 1kyu (intermediate) and then follows 1dan to 7dan (9dan in some systems;
721 top-level player). Multiple independent real-world ranking scales exist
722 (geographically based) and online servers maintain their own user ranking;
723 the difference can be up to several stones.
725 As the source game collection, we use Go Teaching Ladder
726 reviews\footnote{The reviews contain comments and variations --- we consider only the actual played game.}
727 \cite{GTL} --- this collection contains 7700 games of players with strength ranging
728 from 30k to 4d; we consider only even games with clear rank information, and then
729 randomly separate 770 games as a testing set. Since the rank information is provided
730 by the users and may not be consistent, we are forced to take a simplified look
731 at the ranks, discarding the differences between various systems and thus increasing
732 error in our model.\footnote{Since
733 our results seem satisfying, we did not pursue to try another collection}
735 First, we have created a single pattern vector for each rank, from 30k to 4d;
736 we have performed PCA analysis on the pattern vectors, achieving near-perfect
737 rank correspondence in the first PCA dimension%
738 \footnote{The eigenvalue of the second dimension was four times smaller,
739 with no discernable structure revealed within the lower-order eigenvectors.}
740 (figure \ref{fig:strength_pca}).
742 We measure the accuracy of strength approximation by the first dimension
743 using Pearson's $r$ (see \ref{pearson}), yielding satisfying value $r=0.979$.
744 Using the eigenvector position directly for classification
745 of players within the test group yields MSE TODO, thus providing
746 reasonably satisfying accuracy.
748 To further enhance the strength estimator accuracy,
749 we have tried to train a NN classifier on our train set, consisting
750 of one $(\vec p, {\rm rank})$ pair per player --- we use the pattern vector
751 for activation of input neurons and rank number as result of the output
752 neuron. We then proceeded to test the NN on per-player pattern vectors built
753 from the games in the test set, yielding MSE of TODO with TODO games per player
754 on average.
757 \section{Style Estimator}
759 As a second case study for our pattern analysis, we investigate pattern vectors $\vec p$
760 of various well-known players, their relationships and correlations to prior
761 knowledge to explore its correlaction with extracted patterns. We look for
762 relationship between pattern vectors and perceived ``playing style'' and
763 attempt to use our classifiers to transform pattern vector $\vec p$ to style vector $\vec s$.
765 The source game collection is GoGoD Winter 2008 \cite{GoGoD} containing 55000
766 professional games, dating from the early Go history 1500 years ago to the present.
767 We consider only games of a small subset of players (fig. \ref{fig:style_marks});
768 we have chosen these for being well-known within the players community,
769 having large number of played games in our collection and not playing too long
770 ago.\footnote{Over time, many commonly used sequences get altered, adopted and
771 dismissed; usual playing conditions can also differ significantly.}
773 \subsection{Expert-based knowledge}
774 \label{style-vectors}
775 In order to provide a reference frame for our style analysis,
776 we have gathered some expert-based information about various
777 traditionally perceived style aspects.
778 This expert-based knowledge allows us to predict styles of unknown players based on
779 the similarity of their pattern vectors, as well as discover correlations between
780 styles and proportions of played patterns.
782 Experts were asked to mark each style aspect of the given players
783 on the scale from 1 to 10. The style aspects are defined as shown:
785 \vspace{4mm}
786 \noindent
787 %\begin{table}
788 \begin{center}
789 %\caption{Styles}
790 \begin{tabular}{|c|c|c|}
791 \hline
792 \multicolumn{3}{|c|}{Styles} \\ \hline
793 Style & 1 & 10\\ \hline
794 Territoriality $\tau$ & Moyo & Territorial \\
795 Orthodoxity $\omega$ & Classic & Novel \\
796 Aggressivity $\alpha$ & Calm & Figting \\
797 Thickness $\theta$ & Safe & Shinogi \\ \hline
798 \end{tabular}
799 \end{center}
800 %\end{table}
801 \vspace{4mm}
803 Averaging this expert based evaluation yields
804 \emph{reference style vector} $\vec s_r$ (of dimension $4$) for each player $r$
805 from the set of \emph{reference players} $R$.
807 Three high-level Go players (Alexander Dinerstein 3-pro, Motoki Noguchi
808 7-dan and V\'{i}t Brunner 4-dan) have judged style of the reference
809 players.
810 Mean standard deviation of the answers is 0.952,
811 making the data reasonably reliable,
812 though much larger sample would of course be more desirable.
813 The complete list of answers is in table \ref{fig:style_marks}.
815 \begin{table}[!t]
816 % increase table row spacing, adjust to taste
817 \renewcommand{\arraystretch}{1.3}
818 \begin{threeparttable}
819 \caption{Expert-Based Style Aspects of Selected Professionals\tnote{1} \tnote{2}}
820 \label{fig:style_marks}
821 \centering
822 % Some packages, such as MDW tools, offer better commands for making tables
823 % than the plain LaTeX2e tabular which is used here.
824 \begin{tabular}{|c||c||c||c||c|}
825 \hline
826 Player & $\tau$ & $\omega$ & $\alpha$ & $\theta$ \\
827 \hline
828 Go Seigen\tnote{3} & $6.0 \pm 2.0$ & $9.0 \pm 1.0$ & $8.0 \pm 1.0$ & $5.0 \pm 1.0$ \\
829 Ishida Yoshio\tnote{4}&$8.0 \pm 1.4$ & $5.0 \pm 1.4$ & $3.3 \pm 1.2$ & $5.3 \pm 0.5$ \\
830 Miyazawa Goro & $1.5 \pm 0.5$ & $10 \pm 0 $ & $9.5 \pm 0.5$ & $4.0 \pm 1.0$ \\
831 Yi Ch'ang-ho\tnote{5}& $7.0 \pm 0.8$ & $5.0 \pm 1.4$ & $2.6 \pm 0.9$ & $2.6 \pm 1.2$ \\
832 Sakata Eio & $7.6 \pm 1.7$ & $4.6 \pm 0.5$ & $7.3 \pm 0.9$ & $8.0 \pm 1.6$ \\
833 Fujisawa Hideyuki & $3.5 \pm 0.5$ & $9.0 \pm 1.0$ & $7.0 \pm 0.0$ & $4.0 \pm 0.0$ \\
834 Otake Hideo & $4.3 \pm 0.5$ & $3.0 \pm 0.0$ & $4.6 \pm 1.2$ & $3.6 \pm 0.9$ \\
835 Kato Masao & $2.5 \pm 0.5$ & $4.5 \pm 1.5$ & $9.5 \pm 0.5$ & $4.0 \pm 0.0$ \\
836 Takemiya Masaki & $1.3 \pm 0.5$ & $6.3 \pm 2.1$ & $7.0 \pm 0.8$ & $1.3 \pm 0.5$ \\
837 Kobayashi Koichi & $9.0 \pm 1.0$ & $2.5 \pm 0.5$ & $2.5 \pm 0.5$ & $5.5 \pm 0.5$ \\
838 Cho Chikun & $9.0 \pm 0.8$ & $7.6 \pm 0.9$ & $6.6 \pm 1.2$ & $9.0 \pm 0.8$ \\
839 Ma Xiaochun & $8.0 \pm 2.2$ & $6.3 \pm 0.5$ & $5.6 \pm 1.9$ & $8.0 \pm 0.8$ \\
840 Yoda Norimoto & $6.3 \pm 1.7$ & $4.3 \pm 2.1$ & $4.3 \pm 2.1$ & $3.3 \pm 1.2$ \\
841 Luo Xihe & $7.3 \pm 0.9$ & $7.3 \pm 2.5$ & $7.6 \pm 0.9$ & $6.0 \pm 1.4$ \\
842 O Meien & $2.6 \pm 1.2$ & $9.6 \pm 0.5$ & $8.3 \pm 1.7$ & $3.6 \pm 1.2$ \\
843 Rui Naiwei & $4.6 \pm 1.2$ & $5.6 \pm 0.5$ & $9.0 \pm 0.8$ & $3.3 \pm 1.2$ \\
844 Yuki Satoshi & $3.0 \pm 1.0$ & $8.5 \pm 0.5$ & $9.0 \pm 1.0$ & $4.5 \pm 0.5$ \\
845 Hane Naoki & $7.5 \pm 0.5$ & $2.5 \pm 0.5$ & $4.0 \pm 0.0$ & $4.5 \pm 1.5$ \\
846 Takao Shinji & $5.0 \pm 1.0$ & $3.5 \pm 0.5$ & $5.5 \pm 1.5$ & $4.5 \pm 0.5$ \\
847 Yi Se-tol & $5.3 \pm 0.5$ & $6.6 \pm 2.5$ & $9.3 \pm 0.5$ & $6.6 \pm 1.2$ \\
848 Yamashita Keigo\tnote{4}&$2.0\pm 0.0$& $9.0 \pm 1.0$ & $9.5 \pm 0.5$ & $3.0 \pm 1.0$ \\
849 Cho U & $7.3 \pm 2.4$ & $6.0 \pm 0.8$ & $5.3 \pm 1.7$ & $6.3 \pm 1.7$ \\
850 Gu Li & $5.6 \pm 0.9$ & $7.0 \pm 0.8$ & $9.0 \pm 0.8$ & $4.0 \pm 0.8$ \\
851 Chen Yaoye & $6.0 \pm 1.0$ & $4.0 \pm 1.0$ & $6.0 \pm 1.0$ & $5.5 \pm 0.5$ \\
852 \hline
853 \end{tabular}
854 \begin{tablenotes}
855 \item [1] Including standard deviation. Only players where we got at least two out of tree answers are included.
856 \item [2] We consider era as one of factors when finding correlations with pattern vectors; we quantify era by taking median year over all games played by the player. Since this quantity does not fit to the table, we at least sort the players ascending by their median year.
857 \item [3] We do not consider games of Go Seigen due to him playing across several distinct Go-playing eras and thus specifically high diversity of patterns.
858 \item [4] We do not consider games of Ishida Yoshio and Yamashita Keigo for the PCA analysis since they are significant outliers, making high-order dimensions much like purely ``similarity to this player''. Takemiya Masaki has the similar effect for the first dimension, but this corresponds to common knowledge of him being an extreme proponent of anti-territorial (``moyo'') style.
859 \item [5] We consider games only up to year 2004, since Yi Ch'ang-ho was prominent representative of a balanced, careful player until then, but is regarded to have altered his style significantly afterwards.
860 \end{tablenotes}
861 \end{threeparttable}
862 \end{table}
864 \subsection{Style Components Analysis}
866 \begin{figure}[!t]
867 \centering
868 \includegraphics[width=3.75in]{style-pca}
869 \caption{PCA of per-player vectors}
870 \label{fig:style_pca}
871 \end{figure}
873 We have looked at the five most significant dimensions of the pattern data
874 yielded by the PCA analysis of the reference player set%
875 \footnote{We also tried to observe PCA effect of removing outlying Takemiya
876 Masaki. This second dimension strongly
877 correlated to territoriality and third dimension strongly correlacted to era,
878 however the first dimension remained mysteriously uncorrelated and with no
879 obvious interpretation.}
880 (fig. \ref{fig:style_pca} shows three).
881 We have again computed the Pearson's $r$ for all combinations of PCA dimensions
882 and dimensions of the prior knowledge style vectors to find correlations.
884 \begin{table}[!t]
885 % increase table row spacing, adjust to taste
886 \renewcommand{\arraystretch}{1.3}
887 \caption{Covariance Measure of Patterns and Prior Information}
888 \label{fig:style_r}
889 \centering
890 % Some packages, such as MDW tools, offer better commands for making tables
891 % than the plain LaTeX2e tabular which is used here.
892 \begin{tabular}{|c||c||c||c||c||c|}
893 \hline
894 Eigenval. & $\tau$ & $\omega$ & $\alpha$ & $\theta$ & Year \\
895 \hline
896 0.447 & {\bf -0.530} & 0.323 & 0.298 & {\bf -0.554} & 0.090 \\
897 0.194 & {\bf -0.547} & 0.215 & 0.249 & -0.293 & {\bf -0.630} \\
898 0.046 & 0.131 & -0.002 & -0.128 & 0.242 & {\bf -0.630} \\
899 0.028 & -0.011 & 0.225 & 0.186 & 0.131 & 0.067 \\
900 0.024 & -0.181 & 0.174 & -0.032 & -0.216 & 0.352 \\
901 \hline
902 \end{tabular}
903 \end{table}
905 It is immediately
906 obvious both from the measured $r$ and visual observation
907 that by far the most significant vector corresponds very well
908 to the player territoriality,\footnote{Cho Chikun, perhaps the best-known
909 super-territorial player, is not well visible in the cluster, but he is
910 positioned around $-0.8$ on the first dimension.}
911 confirming the intuitive notion that this aspect of style
912 is the one easiest to pin-point and also
913 most obvious in the played shapes and sequences
914 (that can obviously aim directly at taking secure territory
915 or building center-oriented framework). Thick (solid) play also plays
916 a role, but these two style dimensions have been already shown
917 to be correlated in prior data.
919 In other PCA dimensions correspond well to to identify and name, but there
920 certainly is some influence of the styles on the patterns;
921 the found correlations are presented in table \ref{fig:style_r}.
922 (Larger absolute value means better linear correspondence.)
923 We also list the characteristic spatial patterns of the PCA dimension
924 extremes (table \ref{fig:style_patterns}).
926 We have not found significant correspondence for the style aspects
927 representing aggressiveness and novelty of play; this means either
928 these are not as well defined, the prior information do not represent
929 them accurately, or we cannot capture them well with our chosen pattern
930 extraction techniques.
932 We believe that the next step
933 in interpreting our results will be more refined prior information input
934 and precise analysis by Go experts.
936 Kohonen map view.
938 \subsection{Style Classification}
940 We then tried to apply the NN classifier with linear output function on the dataset
941 and that yielded Y (see fig. Z), with MSE abcd.
944 \section{Proposed Applications}
946 We believe that our findings might be useful for many applications
947 in the area of Go support software as well as Go-playing computer engines.
949 The style analysis can be an excellent teaching aid --- classifying style
950 dimensions based on player's pattern vector, many study recommendations
951 can be given, e.g. about the professional games to replay, the goal being
952 balancing understanding of various styles to achieve well-rounded skill set.
953 This was also our original aim when starting the research and a user-friendly
954 tool based on our work is now being created.
956 We hope that more strong players will look into the style dimensions found
957 by our statistical analysis --- analysis of most played patterns of prospective
958 opponents might prepare for the game, but we especially hope that new insights
959 on strategic purposes of various shapes and general human understanding
960 of the game might be achieved by investigating the style-specific patterns.
962 Classifying playing strength of a pattern vector of a player can be used
963 e.g. to help determine initial real-world rating of a player before their
964 first tournament based on games played on the internet; some players especially
965 in less populated areas could get fairly strong before playing their first
966 real tournament.
968 Analysis of pattern vectors extracted from games of Go-playing programs
969 in light of the shown strength and style distributions might help to
970 highlight some weaknesses and room for improvements. (However, since
971 correlation does not imply causation, simply optimizing Go-playing programs
972 according to these vectors is unlikely to yield good results.)
973 Another interesting applications in Go-playing programs might be strength
974 adjustment; the program can classify the player's level based on the pattern
975 vector from its previous games and auto-adjust its difficulty settings
976 accordingly to provide more even games for beginners.
979 % An example of a floating figure using the graphicx package.
980 % Note that \label must occur AFTER (or within) \caption.
981 % For figures, \caption should occur after the \includegraphics.
982 % Note that IEEEtran v1.7 and later has special internal code that
983 % is designed to preserve the operation of \label within \caption
984 % even when the captionsoff option is in effect. However, because
985 % of issues like this, it may be the safest practice to put all your
986 % \label just after \caption rather than within \caption{}.
988 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
989 % option should be used if it is desired that the figures are to be
990 % displayed while in draft mode.
992 %\begin{figure}[!t]
993 %\centering
994 %\includegraphics[width=2.5in]{myfigure}
995 % where an .eps filename suffix will be assumed under latex,
996 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
997 % via \DeclareGraphicsExtensions.
998 %\caption{Simulation Results}
999 %\label{fig_sim}
1000 %\end{figure}
1002 % Note that IEEE typically puts floats only at the top, even when this
1003 % results in a large percentage of a column being occupied by floats.
1006 % An example of a double column floating figure using two subfigures.
1007 % (The subfig.sty package must be loaded for this to work.)
1008 % The subfigure \label commands are set within each subfloat command, the
1009 % \label for the overall figure must come after \caption.
1010 % \hfil must be used as a separator to get equal spacing.
1011 % The subfigure.sty package works much the same way, except \subfigure is
1012 % used instead of \subfloat.
1014 %\begin{figure*}[!t]
1015 %\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
1016 %\label{fig_first_case}}
1017 %\hfil
1018 %\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
1019 %\label{fig_second_case}}}
1020 %\caption{Simulation results}
1021 %\label{fig_sim}
1022 %\end{figure*}
1024 % Note that often IEEE papers with subfigures do not employ subfigure
1025 % captions (using the optional argument to \subfloat), but instead will
1026 % reference/describe all of them (a), (b), etc., within the main caption.
1029 % An example of a floating table. Note that, for IEEE style tables, the
1030 % \caption command should come BEFORE the table. Table text will default to
1031 % \footnotesize as IEEE normally uses this smaller font for tables.
1032 % The \label must come after \caption as always.
1034 %\begin{table}[!t]
1035 %% increase table row spacing, adjust to taste
1036 %\renewcommand{\arraystretch}{1.3}
1037 % if using array.sty, it might be a good idea to tweak the value of
1038 % \extrarowheight as needed to properly center the text within the cells
1039 %\caption{An Example of a Table}
1040 %\label{table_example}
1041 %\centering
1042 %% Some packages, such as MDW tools, offer better commands for making tables
1043 %% than the plain LaTeX2e tabular which is used here.
1044 %\begin{tabular}{|c||c|}
1045 %\hline
1046 %One & Two\\
1047 %\hline
1048 %Three & Four\\
1049 %\hline
1050 %\end{tabular}
1051 %\end{table}
1054 % Note that IEEE does not put floats in the very first column - or typically
1055 % anywhere on the first page for that matter. Also, in-text middle ("here")
1056 % positioning is not used. Most IEEE journals use top floats exclusively.
1057 % Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
1058 % floats. This can be corrected via the \fnbelowfloat command of the
1059 % stfloats package.
1063 \section{Conclusion}
1064 The conclusion goes here.
1065 We have shown brm and proposed brm.
1067 Since we are not aware of any previous research on this topic and we
1068 are limited by space and time constraints, plenty of research remains
1069 to be done. There is plenty of room for further research in all parts
1070 of our analysis --- different methods of generating the $\vec p$ vectors
1071 can be explored; other data mining methods could be tried.
1072 It can be argued that many players adjust their style by game conditions
1073 (Go development era, handicap, komi and color, time limits, opponent)
1074 or styles might express differently in various game stages.
1075 More professional players could be consulted on the findings
1076 and for style scales calibration. Impact of handicap games on by-strength
1077 $\vec p$ distribution should be investigated.
1079 TODO: Future research --- Sparse PCA
1084 % if have a single appendix:
1085 %\appendix[Proof of the Zonklar Equations]
1086 % or
1087 %\appendix % for no appendix heading
1088 % do not use \section anymore after \appendix, only \section*
1089 % is possibly needed
1091 % use appendices with more than one appendix
1092 % then use \section to start each appendix
1093 % you must declare a \section before using any
1094 % \subsection or using \label (\appendices by itself
1095 % starts a section numbered zero.)
1099 %\appendices
1100 %\section{Proof of the First Zonklar Equation}
1101 %Appendix one text goes here.
1103 %% you can choose not to have a title for an appendix
1104 %% if you want by leaving the argument blank
1105 %\section{}
1106 %Appendix two text goes here.
1109 % use section* for acknowledgement
1110 \section*{Acknowledgment}
1111 \label{acknowledgement}
1113 We would like to thank Radka ``chidori'' Hane\v{c}kov\'{a} for the original research idea
1114 and X for reviewing our paper.
1115 We appreciate helpful comments on our general methodology
1116 by John Fairbairn, T. M. Hall, Robert Jasiek, Franti\v{s}ek Mr\'{a}z
1117 and several GoDiscussions.com users. \cite{GoDiscThread}
1118 Finally, we are very grateful for detailed input on specific go styles
1119 by Alexander Dinerstein, Motoki Noguchi and V\'{i}t Brunner.
1122 % Can use something like this to put references on a page
1123 % by themselves when using endfloat and the captionsoff option.
1124 \ifCLASSOPTIONcaptionsoff
1125 \newpage
1130 % trigger a \newpage just before the given reference
1131 % number - used to balance the columns on the last page
1132 % adjust value as needed - may need to be readjusted if
1133 % the document is modified later
1134 %\IEEEtriggeratref{8}
1135 % The "triggered" command can be changed if desired:
1136 %\IEEEtriggercmd{\enlargethispage{-5in}}
1138 % references section
1140 % can use a bibliography generated by BibTeX as a .bbl file
1141 % BibTeX documentation can be easily obtained at:
1142 % http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
1143 % The IEEEtran BibTeX style support page is at:
1144 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1145 \bibliographystyle{IEEEtran}
1146 % argument is your BibTeX string definitions and bibliography database(s)
1147 \bibliography{gostyle}
1149 % <OR> manually copy in the resultant .bbl file
1150 % set second argument of \begin to the number of references
1151 % (used to reserve space for the reference number labels box)
1152 %\begin{thebibliography}{1}
1154 %\bibitem{MasterMCTS}
1156 %\end{thebibliography}
1158 % biography section
1160 % If you have an EPS/PDF photo (graphicx package needed) extra braces are
1161 % needed around the contents of the optional argument to biography to prevent
1162 % the LaTeX parser from getting confused when it sees the complicated
1163 % \includegraphics command within an optional argument. (You could create
1164 % your own custom macro containing the \includegraphics command to make things
1165 % simpler here.)
1166 %\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
1167 % or if you just want to reserve a space for a photo:
1169 \begin{IEEEbiography}{Michael Shell}
1170 Biography text here.
1171 \end{IEEEbiography}
1173 % if you will not have a photo at all:
1174 \begin{IEEEbiographynophoto}{John Doe}
1175 Biography text here.
1176 \end{IEEEbiographynophoto}
1178 % insert where needed to balance the two columns on the last page with
1179 % biographies
1180 %\newpage
1182 \begin{IEEEbiographynophoto}{Jane Doe}
1183 Biography text here.
1184 \end{IEEEbiographynophoto}
1186 % You can push biographies down or up by placing
1187 % a \vfill before or after them. The appropriate
1188 % use of \vfill depends on what kind of text is
1189 % on the last page and whether or not the columns
1190 % are being equalized.
1192 %\vfill
1194 % Can be used to pull up biographies so that the bottom of the last one
1195 % is flush with the other column.
1196 %\enlargethispage{-5in}
1200 % that's all folks
1201 \end{document}