tex: DRAFT3
[gostyle.git] / tex / gostyle.tex
blobfde2a1520bc4ac3c2101b6ff7cecf901f7f8a5d1
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{psgo}
45 \setgounit{0.4cm}
47 \usepackage{algorithm}
48 \usepackage{algorithmic}
49 %\usepackage{algpseudocode}
50 % WICKED: nefunguje ani jedno???
51 % algorithmic.sty can be obtained at:
52 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
53 % There is also a support site at:
54 % http://algorithms.berlios.de/index.html
55 % Also of interest may be the (relatively newer and more customizable)
56 % algorithmicx.sty package by Szasz Janos:
57 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
59 % *** ALIGNMENT PACKAGES ***
61 %\usepackage{array}
62 % http://www.ctan.org/tex-archive/macros/latex/required/tools/
65 \usepackage{amsmath}
66 %\usepackage{mdwtab}
67 % http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
70 % IEEEtran contains the IEEEeqnarray family of commands that can be used to
71 % generate multiline equations as well as matrices, tables, etc., of high
72 % quality.
74 %\usepackage{eqparbox}
75 % Also of notable interest is Scott Pakin's eqparbox package for creating
76 % (automatically sized) equal width boxes - aka "natural width parboxes".
77 % Available at:
78 % http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
82 % *** SUBFIGURE PACKAGES ***
83 %\usepackage[tight,footnotesize]{subfigure}
84 % subfigure.sty was written by Steven Douglas Cochran. This package makes it
85 % easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
86 % work, it is a good idea to load it with the tight package option to reduce
87 % the amount of white space around the subfigures. subfigure.sty is already
88 % installed on most LaTeX systems. The latest version and documentation can
89 % be obtained at:
90 % http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
91 % subfigure.sty has been superceeded by subfig.sty.
95 %\usepackage[caption=false]{caption}
96 %\usepackage[font=footnotesize]{subfig}
97 % subfig.sty, also written by Steven Douglas Cochran, is the modern
98 % replacement for subfigure.sty. However, subfig.sty requires and
99 % automatically loads Axel Sommerfeldt's caption.sty which will override
100 % IEEEtran.cls handling of captions and this will result in nonIEEE style
101 % figure/table captions. To prevent this problem, be sure and preload
102 % caption.sty with its "caption=false" package option. This is will preserve
103 % IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
104 % (recommended due to many improvements over 1.2) of subfig.sty supports
105 % the caption=false option directly:
106 %\usepackage[caption=false,font=footnotesize]{subfig}
108 % The latest version and documentation can be obtained at:
109 % http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
110 % The latest version and documentation of caption.sty can be obtained at:
111 % http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
115 % *** FLOAT PACKAGES ***
117 %\usepackage{fixltx2e}
118 % fixltx2e, the successor to the earlier fix2col.sty, was written by
119 % Frank Mittelbach and David Carlisle. This package corrects a few problems
120 % in the LaTeX2e kernel, the most notable of which is that in current
121 % LaTeX2e releases, the ordering of single and double column floats is not
122 % guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
123 % single column figure to be placed prior to an earlier double column
124 % figure. The latest version and documentation can be found at:
125 % http://www.ctan.org/tex-archive/macros/latex/base/
129 %\usepackage{stfloats}
130 % stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
131 % the ability to do double column floats at the bottom of the page as well
132 % as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
133 % LaTeX2e). It also provides a command:
134 %\fnbelowfloat
135 % to enable the placement of footnotes below bottom floats (the standard
136 % LaTeX2e kernel puts them above bottom floats). This is an invasive package
137 % which rewrites many portions of the LaTeX2e float routines. It may not work
138 % with other packages that modify the LaTeX2e float routines. The latest
139 % version and documentation can be obtained at:
140 % http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
141 % Documentation is contained in the stfloats.sty comments as well as in the
142 % presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
143 % does not allow \baselineskip to stretch. Authors submitting work to the
144 % IEEE should note that IEEE rarely uses double column equations and
145 % that authors should try to avoid such use. Do not be tempted to use the
146 % cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
147 % not format its papers in such ways.
150 %\ifCLASSOPTIONcaptionsoff
151 % \usepackage[nomarkers]{endfloat}
152 % \let\MYoriglatexcaption\caption
153 % \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
154 %\fi
155 % endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
156 % This package may be useful when used in conjunction with IEEEtran.cls'
157 % captionsoff option. Some IEEE journals/societies require that submissions
158 % have lists of figures/tables at the end of the paper and that
159 % figures/tables without any captions are placed on a page by themselves at
160 % the end of the document. If needed, the draftcls IEEEtran class option or
161 % \CLASSINPUTbaselinestretch interface can be used to increase the line
162 % spacing as well. Be sure and use the nomarkers option of endfloat to
163 % prevent endfloat from "marking" where the figures would have been placed
164 % in the text. The two hack lines of code above are a slight modification of
165 % that suggested by in the endfloat docs (section 8.3.1) to ensure that
166 % the full captions always appear in the list of figures/tables - even if
167 % the user used the short optional argument of \caption[]{}.
168 % IEEE papers do not typically make use of \caption[]'s optional argument,
169 % so this should not be an issue. A similar trick can be used to disable
170 % captions of packages such as subfig.sty that lack options to turn off
171 % the subcaptions:
172 % For subfig.sty:
173 % \let\MYorigsubfloat\subfloat
174 % \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
175 % For subfigure.sty:
176 % \let\MYorigsubfigure\subfigure
177 % \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
178 % However, the above trick will not work if both optional arguments of
179 % the \subfloat/subfig command are used. Furthermore, there needs to be a
180 % description of each subfigure *somewhere* and endfloat does not add
181 % subfigure captions to its list of figures. Thus, the best approach is to
182 % avoid the use of subfigure captions (many IEEE journals avoid them anyway)
183 % and instead reference/explain all the subfigures within the main caption.
184 % The latest version of endfloat.sty and its documentation can obtained at:
185 % http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
187 % The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
188 % later in the document, say, to conditionally put the References on a
189 % page by themselves.
191 % *** PDF, URL AND HYPERLINK PACKAGES ***
193 \usepackage{url}
194 % url.sty was written by Donald Arseneau. It provides better support for
195 % handling and breaking URLs. url.sty is already installed on most LaTeX
196 % systems. The latest version can be obtained at:
197 % http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
198 % Read the url.sty source comments for usage information. Basically,
199 % \url{my_url_here}.
202 % *** Do not adjust lengths that control margins, column widths, etc. ***
203 % *** Do not use packages that alter fonts (such as pslatex). ***
204 % There should be no need to do such things with IEEEtran.cls V1.6 and later.
205 % (Unless specifically asked to do so by the journal or conference you plan
206 % to submit to, of course. )
208 % correct bad hyphenation here
209 \hyphenation{op-tical net-works semi-conduc-tor know-ledge}
212 \begin{document}
214 % paper title
215 % can use linebreaks \\ within to get better formatting as desired
216 \title{On Move Pattern Trends\\in Large Go Games Corpus}
218 % use \thanks{} to gain access to the first footnote area
219 % a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
220 % was not built to handle multiple paragraphs
221 \author{Petr~Baudi\v{s},~Josef~Moud\v{r}\'{i}k% <-this % stops a space
222 \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
223 \thanks{J. Moud\v{r}\'{i}k is student at the Faculty of Math and Physics, Charles University, Prague, CZ.}}
225 % note the % following the last \IEEEmembership and also \thanks -
226 % these prevent an unwanted space from occurring between the last author name
227 % and the end of the author line. i.e., if you had this:
229 % \author{....lastname \thanks{...} \thanks{...} }
230 % ^------------^------------^----Do not want these spaces!
232 % a space would be appended to the last name and could cause every name on that
233 % line to be shifted left slightly. This is one of those "LaTeX things". For
234 % instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
235 % "AB" then you have to do: "\textbf{A}\textbf{B}"
236 % \thanks is no different in this regard, so shield the last } of each \thanks
237 % that ends a line with a % and do not let a space in before the next \thanks.
238 % Spaces after \IEEEmembership other than the last one are OK (and needed) as
239 % you are supposed to have spaces between the names. For what it is worth,
240 % this is a minor point as most people would not even notice if the said evil
241 % space somehow managed to creep in.
244 % The paper headers
245 \markboth{Transactions on Computational Intelligence and AI in Games --- DRAFT3}%
246 {On Pattern Feature Trends in Large Go Game Corpus --- DRAFT3}
247 % The only time the second header will appear is for the odd numbered pages
248 % after the title page when using the twoside option.
250 % *** Note that you probably will NOT want to include the author's ***
251 % *** name in the headers of peer review papers. ***
252 % You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
253 % you desire.
258 % If you want to put a publisher's ID mark on the page you can do it like
259 % this:
260 %\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
261 % Remember, if you use this you must call \IEEEpubidadjcol in the second
262 % column for its text to clear the IEEEpubid mark.
266 % use for special paper notices
267 %\IEEEspecialpapernotice{(Invited Paper)}
272 % make the title area
273 \maketitle
276 \begin{abstract}
277 %\boldmath
279 We process a~large corpus of game records of the board game of Go and
280 propose a~way to extract summary information on played moves.
281 We then apply several basic data-mining methods on the summary
282 information to identify the most differentiating features within the
283 summary information, and discuss their correspondence with traditional
284 Go knowledge. We show mappings of the features to player attributes
285 like playing strength or informally perceived ``playing style'' (such as
286 territoriality or aggressivity), and propose applications including
287 seeding real-work ranks of internet players, aiding in Go study, or
288 contribution to Go-theoretical discussion on the scope of ``playing
289 style''.
291 \end{abstract}
292 % IEEEtran.cls defaults to using nonbold math in the Abstract.
293 % This preserves the distinction between vectors and scalars. However,
294 % if the journal you are submitting to favors bold math in the abstract,
295 % then you can use LaTeX's standard command \boldmath at the very start
296 % of the abstract to achieve this. Many IEEE journals frown on math
297 % in the abstract anyway.
299 % Note that keywords are not normally used for peerreview papers.
300 \begin{IEEEkeywords}
301 board games, go, computer go, data mining, go theory,
302 pattern recongition, player strength, playing style,
303 neural networks, sociomaps, principal component analysis,
304 naive bayes classifier
305 \end{IEEEkeywords}
312 % For peer review papers, you can put extra information on the cover
313 % page as needed:
314 % \ifCLASSOPTIONpeerreview
315 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
316 % \fi
318 % For peerreview papers, this IEEEtran command inserts a page break and
319 % creates the second title. It will be ignored for other modes.
320 \IEEEpeerreviewmaketitle
324 \section{Introduction}
325 % The very first letter is a 2 line initial drop letter followed
326 % by the rest of the first word in caps.
328 % form to use if the first word consists of a single letter:
329 % \IEEEPARstart{A}{demo} file is ....
331 % form to use if you need the single drop letter followed by
332 % normal text (unknown if ever used by IEEE):
333 % \IEEEPARstart{A}{}demo file is ....
335 % Some journals put the first two words in caps:
336 % \IEEEPARstart{T}{his demo} file is ....
338 % Here we have the typical use of a "T" for an initial drop letter
339 % and "HIS" in caps to complete the first word.
340 \IEEEPARstart{T}{he} field of Computer Go usually focuses on the problem
341 of creating a~program to play the game, finding the best move from a~given
342 board position. \cite{GellySilver2008}
343 We will make use of one method developed in the course
344 of such research and apply it to the analysis of existing game records
345 with the aim of helping humans to play and understand the game better
346 instead.
348 Go is a~two-player full-information board game played
349 on a~square grid (usually $19\times19$ lines) with black and white
350 stones; the goal of the game is to surround the most territory and
351 capture enemy stones. We assume basic familiarity with the game.
353 Many Go players are eager to play using computers (usually over
354 the internet) and review games played by others on computers as well.
355 This means that large amounts of game records are collected and digitally
356 stored, enabling easy processing of such collections. However, so far
357 only little has been done with the available data --- we are aware
358 only of uses for simple win/loss statistics \cite{KGSAnalytics} \cite{ProGoR}
359 and ``next move'' statistics on a~specific position \cite{Kombilo} \cite{MoyoGo}.
361 We present a~more in-depth approach --- from all played moves, we devise
362 a~compact evaluation of each player. We then explore correlations between
363 evaluations of various players in light of externally given information.
364 This way, we can discover similarity between moves characteristics of
365 players with the same playing strength, or discuss the meaning of the
366 "playing style" concept on the assumption that similar playing styles
367 should yield similar moves characteristics.
370 \section{Data Extraction}
371 \label{pattern-vectors}
373 As the input of our analysis, we use large collections of game records%
374 \footnote{We use the SGF format \cite{SGF} in our implementation.}
375 grouped by the primary object of analysis (player name, player rank, etc.).
376 We process the games by object, generating a description for each
377 played move -- a {\em pattern}, being a combination of several
378 {\em pattern features} described below.
380 We keep track of the most
381 occuring patterns, finally composing $n$-dimensional {\em pattern vector}
382 $\vec p$ of per-pattern counts from the $n$ globally most frequent patterns%
383 \footnote{We use $n=500$ in our analysis.}
384 (the mapping from patterns to vector elements is common for all objects).
385 We can then process and compare just the pattern vectors.
387 \subsection{Pattern Features}
388 When deciding how to compose the patterns we use to describe moves,
389 we need to consider a specificity tradeoff --- overly general descriptions carry too few
390 information to discern various player attributes; too specific descriptions
391 gather too few specimen over the games sample and the vector differences are
392 not statistically significant.
394 We have chosen an intuitive and simple approach inspired by pattern features
395 used when computing Elo ratings for candidate patterns in Computer Go play.
396 \cite{PatElo} Each pattern is a~combination of several {\em pattern features}
397 (name--value pairs) matched at the position of the played move.
398 We use these features:
400 \begin{itemize}
401 \item capture move flag
402 \item atari move flag
403 \item atari escape flag
404 \item contiguity-to-last flag%
405 \footnote{We do not consider contiguity features in some cases when we are working
406 on small game samples and need to reduce pattern diversity.}
407 --- whether the move has been played in one of 8 neighbors of the last move
408 \item contiguity-to-second-last flag
409 \item board edge distance --- only up to distance 4
410 \item spatial pattern --- configuration of stones around the played move
411 \end{itemize}
413 The spatial patterns are normalized (using a dictionary) to be always
414 black-to-play and maintain translational and rotational symmetry.
415 Configurations of radius between 2 and 9 in the gridcular metric%
416 \footnote{The {\em gridcular} metric
417 $d(x,y) = |\delta x| + |\delta y| + \max(|\delta x|, |\delta y|)$ produces
418 a circle-like structure on the Go board square grid. \cite{SpatPat} }
419 are matched.
421 Pattern vectors representing these features contain information on
422 played shape as well as a basic representation of tactical dynamics
423 --- threats to capture stones, replying to last move, or ignoring
424 opponent's move elsewhere to return to an urgent local situation.
425 The shapes most frequently correspond to opening moves
426 (either in empty corners and sides, or as part of {\em joseki}
427 --- commonly played sequences) characteristic for a certain
428 strategic aim. In the opening, even a single-line difference
429 in the distance from the border can have dramatic impact on
430 further local and global development.
432 \subsection{Vector Rescaling}
434 The pattern vector elements can have diverse values since for each object,
435 we consider different number of games (and thus patterns).
436 Therefore, we normalize the values to range $[-1,1]$,
437 the most frequent pattern having the value of $1$ and the least occuring
438 one being $-1$.
439 Thus, we obtain vectors describing relative frequency of played patterns
440 independent on number of gathered patterns.
441 But there are multiple ways to approach the normalization.
443 \begin{figure}[!t]
444 \centering
445 \includegraphics{patcountdist}
446 \caption{Log-scaled number of pattern occurences
447 in the GoGoD games examined in sec. \ref{styleest}.}
448 \label{fig:patcountdist}
449 \end{figure}
451 \subsubsection{Linear Normalization}
453 One is simply to linearly re-scale the values using:
454 $$y_i = {x_i - x_{\rm min} \over x_{\rm max}}$$
455 This is the default approach; we have used data processed by only this
456 computation unless we note otherwise.
457 As shown on fig. \ref{fig:patcountdist}, most of the spectrum is covered
458 by the few most-occuring patterns (describing mostly large-diameter
459 shapes from the game opening). This means that most patterns will be
460 always represented by only very small values near the lower bound.
462 \subsubsection{Extended Normalization}
463 \label{xnorm}
465 To alleviate this problem, we have also tried to modify the linear
466 normalization by applying two steps --- {\em pre-processing}
467 the raw counts using
468 $$x_i' = \log (x_i + 1)$$
469 and {\em post-processing} the re-scaled values by the logistic function:
470 $$y_i' = {2 \over 1 + e^{-cy_i}}-1$$
471 However, we have found that this method is not universally beneficial.
472 In our styles case study (sec. \ref{styleest}), this normalization
473 produced PCA decomposition with significant dimensions corresponding
474 better to some of the prior knowledge and more instructive for manual
475 inspection, but ultimately worsened accuracy of our classifiers;
476 we conjecture from this that the most frequently occuring patterns are
477 also most important for classification of major style aspects.
479 \subsection{Implementation}
481 We have implemented the data extraction by making use of the pattern
482 features matching implementation%
483 \footnote{The pattern features matching was developed according
484 to the Elo-rating playing scheme. \cite{PatElo}}
485 within the Pachi go-playing program \cite{Pachi}.
486 We extract information on players by converting the SGF game
487 records to GTP stream \cite{GTP} that feeds Pachi's {\tt patternscan}
488 engine, outputting a~single {\em patternspec} (string representation
489 of the particular pattern features combination) per move. Of course,
490 only moves played by the appropriate color in the game are collected.
492 \section{Data Mining}
493 \label{data-mining}
495 To assess the properties of gathered pattern vectors
496 and their influence on playing styles,
497 we process the data by several basic data minining techniques.
499 The first two methods {\em (analytic)} rely purely on single data set
500 and serve to show internal structure and correlations within the data set.
502 Principal Component Analysis finds orthogonal vector components that
503 have the largest variance.
504 Reversing the process can indicate which patterns correlate with each component.
505 Additionally, PCA can be used as vector preprocessing for methods
506 that are negatively sensitive to pattern vector component correlations.
508 The~second method of Sociomaps creates spatial
509 representation of the data set elements (e.g. players) based on
510 similarity of their data set features; we can then project other
511 information on the map to illutrate its connection to the data set.
513 Furthermore, we test several \emph{classification} methods that assign
514 each pattern vector $\vec P$ an \emph{output vector} $\vec O$,
515 representing e.g.~information about styles, player's strength or even
516 meta-information like the player's era or a country of origin.
517 Initially, the methods must be calibrated (trained) on some prior knowledge,
518 usually in the form of \emph{reference pairs} of pattern vectors
519 and the associated output vectors.
521 Moreover, the reference set can be divided into training and testing pairs
522 and the methods can be compared by the mean square error on testing data set
523 (difference of output vectors approximated by the method and their real desired value).
525 %\footnote{However, note that dicrete characteristics such as country of origin are
526 %not very feasible to use here, since WHAT??? is that even true?? }
528 First, we test the $k$-Nearest Neighbors \cite{CoverHart1967} classifier
529 approximates $\vec O$ by composing the output vectors
530 of $k$ reference pattern vectors closest to $\vec P$.
532 Another classifier is a~multi-layer feed-forward Artificial Neural Network:
533 the neural network can learn correlations between input and output vectors
534 and generalize the ``knowledge'' to unknown vectors; it can be more flexible
535 in the interpretation of different pattern vector elements and discern more
536 complex relations than the kNN classifier,
537 but may not be as stable and requires larger training sample.
539 Finally, a commonly used classifier in statistical inference is
540 the Naive Bayes classifier; it can infer relative probability of membership
541 in various classes based on previous evidence (training patterns). \cite{Bayes}
543 \subsection{Statistical Methods}
544 We use couple of general statistical analysis together with the particular
545 techniques.
547 \label{pearson}
548 To find correlations within or between extracted data and
549 some prior knowledge (player rank, style vector), we compute the well-known
550 {\em Pearson product-moment correlation coefficient} \cite{Pearson},
551 measuring the strength of the linear dependence%
552 \footnote{A desirable property of PMCC is that it is invariant to translations and rescaling
553 of the vectors.}
554 between any two dimensions:
556 $$ r_{X,Y} = {{\rm cov}(X,Y) \over \sigma_X \sigma_Y} $$
558 To compare classifier performance on the reference data, we employ
559 {\em $k$-fold cross validation}:
560 we randomly divide the training set (organized by measured subjects, usually players)
561 into $k$ distinct segments of similar sizes and then iteratively
562 use each part as a~testing set as the other $k-1$ parts are used as a~training set.
563 We then average results over all iterations.
565 \subsection{Principal Component Analysis}
566 \label{PCA}
567 We use Principal Component Analysis \emph{PCA} \cite{Jolliffe1986}
568 to reduce the dimensions of the pattern vectors while preserving
569 as much information as possible, assuming inter-dependencies between
570 pattern vector dimensions are linear.
572 Briefly, PCA is an eigenvalue decomposition of a~covariance matrix of centered pattern vectors,
573 producing a~linear mapping $o$ from $n$-dimensional vector space
574 to a~reduced $m$-dimensional vector space.
575 The $m$ eigenvectors of the original vectors' covariance matrix
576 with the largest eigenvalues are used as the base of the reduced vector space;
577 the eigenvectors form projection matrix $W$.
579 For each original pattern vector $\vec p_i$,
580 we obtain its new representation $\vec r_i$ in the PCA base
581 as shown in the following equation:
582 \begin{equation}
583 \vec r_i = W \cdot \vec p_i
584 \end{equation}
586 The whole process is described in the Algorithm \ref{alg:pca}.
588 \begin{algorithm}
589 \caption{PCA -- Principal Component Analysis}
590 \begin{algorithmic}
591 \label{alg:pca}
592 \REQUIRE{$m > 0$, set of players $R$ with pattern vectors $p_r$}
593 \STATE $\vec \mu \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_r}$
594 \FOR{ $r \in R$}
595 \STATE $\vec p_r \leftarrow \vec p_r - \vec \mu$
596 \ENDFOR
597 \FOR{ $(i,j) \in \{1,... ,n\} \times \{1,... ,n\}$}
598 \STATE $\mathit{Cov}[i,j] \leftarrow 1/|R| \cdot \sum_{r \in R}{\vec p_{ri} \cdot \vec p_{rj}}$
599 \ENDFOR
600 \STATE Compute Eigenvalue Decomposition of $\mathit{Cov}$ matrix
601 \STATE Get $m$ largest eigenvalues
602 \STATE Most significant eigenvectors ordered by decreasing eigenvalues form the rows of matrix $W$
603 \FOR{ $r \in R$}
604 \STATE $\vec r_r\leftarrow W \vec p_r$
605 \ENDFOR
606 \end{algorithmic}
607 \end{algorithm}
609 \subsection{Sociomaps}
610 \label{soc}
611 Sociomaps are a general mechanism for visualising possibly assymetric
612 relationships on a 2D plane such that ordering of the maximum possible
613 subject distances in the dataset is preserved in distances on the plane.
615 In our particular case,%
616 \footnote{A special case of the {\em Subject-to-Object Relation Mapping (STORM)} indirect sociomap.}
617 we will consider a dataset $\vec S$ of small-dimensional
618 vectors $\vec s_i$. First, we estimate the significance of difference
619 between each two subjects.
620 Then, we determine projection $\varphi$ of all the $\vec s_i$
621 to spatial coordinates of an Euclidean plane, such that it reflects
622 the estimated difference significances.
624 To quantify the differences between the subjects ({\em team profiling} \cite{TeamProf})
625 into an $A$ matrix, for each two subjects $i, j$ we compute the scalar distance%
626 \footnote{We use the {\em Manhattan} metric $d(x,y) = \sum_i |x_i - y_i|$.}
627 of $s_i, s_j$ and then estimate the $A_{ij}$ probability of at least such distance
628 occuring in uniformly-distributed input. This probability expresses the significance
629 of the difference between the two subjects.
631 To visualize the quantified differences \cite{Sociomaps}, we need to find
632 the $\varphi$ projection such that it maximizes a {\em three-way ordering} criterion:
633 ordering of any three members within $A$ and on the plane
634 (by Euclidean metric) must be the same.
636 $$ \min_\varphi \sum_{i\ne j\ne k} \Phi(\varphi, i, j, k) $$
637 $$ \Phi(\varphi, i, j, k) = \begin{cases}
638 1 & \delta(1,A_{ij},A_{ik}) = \delta(\varphi(i),\varphi(j),\varphi(k)) \\
639 0 & \hbox{otherwise} \end{cases} $$
640 $$ \delta(a, b, c) = \begin{cases}
641 1 & |a-b| > |a-c| \\
642 0 & |a-b| = |a-c| \\
643 -1 & |a-b| < |a-c| \end{cases} $$
645 The $\varphi$ projection is then determined by randomly initializing
646 the position of each subject and then employing gradient descent methods.
648 \subsection{k-nearest Neighbors Classifier}
649 \label{knn}
650 Our goal is to approximate player's output vector $\vec O$;
651 we know his pattern vector $\vec P$.
652 We further assume that similarities in players' pattern vectors
653 uniformly correlate with similarities in players' output vectors.
655 We require a set of reference players $R$ with known \emph{pattern vectors} $\vec p_r$
656 and \emph{output vectors} $\vec o_r$.
658 $\vec O$ is approximated as a~weighted average of \emph{output vectors}
659 $\vec o_i$ of $k$ players with \emph{pattern vectors} $\vec p_i$ closest to $\vec P$.
660 This is illustrated in the Algorithm \ref{alg:knn}.
661 Note that the weight is a function of distance and is not explicitly defined in Algorithm \ref{alg:knn}.
662 During our research, exponentially decreasing weight has proven to be sufficient.
664 \begin{algorithm}
665 \caption{k-Nearest Neighbors}
666 \begin{algorithmic}
667 \label{alg:knn}
668 \REQUIRE{pattern vector $\vec P$, $k > 0$, set of reference players $R$}
669 \FORALL{$r \in R$ }
670 \STATE $D[r] \leftarrow \mathit{EuclideanDistance}(\vec p_r, \vec P)$
671 \ENDFOR
672 \STATE $N \leftarrow \mathit{SelectSmallest}(k, R, D)$
673 \STATE $\vec O \leftarrow \vec 0$
674 \FORALL{$r \in N $}
675 \STATE $\vec O \leftarrow \vec O + \mathit{Weight}(D[r]) \cdot \vec o_r $
676 \ENDFOR
677 \end{algorithmic}
678 \end{algorithm}
680 \subsection{Neural Network Classifier}
681 \label{neural-net}
683 Feed-forward neural networks are known for their ability to generalize
684 and find correlations between input patterns and output classifications.
685 Before use, the network is iteratively trained on the training data
686 until the error on the training set is reasonably small.
688 %Neural network is an adaptive system that must undergo a training
689 %period similarly to the requirement
690 %of reference vectors for the k-Nearest Neighbors algorithm above.
692 \subsubsection{Computation and activation of the NN}
693 Technically, the neural network is a network of interconnected
694 computational units called neurons.
695 A feedforward neural network has a layered topology;
696 it usually has one \emph{input layer}, one \emph{output layer}
697 and an arbitrary number of \emph{hidden layers} between.
699 Each neuron $i$ is connected to all neurons in the previous layer and each connection has its weight $w_{ij}$
701 The computation proceeds in discrete time steps.
702 In the first step, the neurons in the \emph{input layer}
703 are \emph{activated} according to the \emph{input vector}.
704 Then, we iteratively compute output of each neuron in the next layer
705 until the output layer is reached.
706 The activity of output layer is then presented as the result.
708 The activation $y_i$ of neuron $i$ from the layer $I$ is computed as
709 \begin{equation}
710 y_i = f\left(\sum_{j \in J}{w_{ij} y_j}\right)
711 \end{equation}
712 where $J$ is the previous layer, while $y_j$ is the activation for neurons from $J$ layer.
713 Function $f()$ is a~so-called \emph{activation function}
714 and its purpose is to bound the outputs of neurons.
715 A typical example of an activation function is the sigmoid function.%
716 \footnote{A special case of the logistic function $\sigma(x)=(1+e^{-(rx+k)})^{-1}$.
717 Parameters control the growth rate $r$ and the x-position $k$.}
719 \subsubsection{Training}
720 Training of the feed-forward neural network usually involves some
721 modification of supervised Backpropagation learning algorithm.
722 We use first-order optimization algorithm called RPROP. \cite{Riedmiller1993}
724 %Because the \emph{reference set} is usually not very large,
725 %we have devised a simple method for its extension.
726 %This enhancement is based upon adding random linear combinations
727 %of \emph{style and pattern vectors} to the training set.
729 As outlined above, the training set $T$ consists of
730 $(\vec p_i, \vec o_i)$ pairs.
731 The training algorithm is shown in Algorithm \ref{alg:tnn}.
733 \begin{algorithm}
734 \caption{Training Neural Network}
735 \begin{algorithmic}
736 \label{alg:tnn}
737 \REQUIRE{Train set $T$, desired error $e$, max iterations $M$}
738 \STATE $N \leftarrow \mathit{RandomlyInitializedNetwork}()$
739 \STATE $\mathit{It} \leftarrow 0$
740 \REPEAT
741 \STATE $\mathit{It} \leftarrow \mathit{It} + 1$
742 \STATE $\Delta \vec w \leftarrow \vec 0$
743 \STATE $\mathit{TotalError} \leftarrow 0$
744 %\FORALL{$(\overrightarrow{Input}, \overrightarrow{DesiredOutput}) \in T$}
745 %\STATE $\overrightarrow{Output} \leftarrow Result(N, \overrightarrow{Input})$
746 %\STATE $E \leftarrow |\overrightarrow{DesiredOutput} - \overrightarrow{Output}|$
747 \FORALL{$(\mathit{Input}, \mathit{DesiredOutput}) \in T$}
748 \STATE $\mathit{Output} \leftarrow \mathit{Result}(N, \mathit{Input})$
749 \STATE $\mathit{Error} \leftarrow |\mathit{DesiredOutput} - \mathit{Output}|$
750 \STATE $\Delta \vec w \leftarrow \Delta \vec w + \mathit{WeightUpdate}(N,\mathit{Error})$
751 \STATE $\mathit{TotalError} \leftarrow \mathit{TotalError} + \mathit{Error}$
752 \ENDFOR
753 \STATE $N \leftarrow \mathit{ModifyWeights}(N, \Delta \vec w)$
754 \UNTIL{$\mathit{TotalError} < e$ or $ \mathit{It} > M$}
755 \end{algorithmic}
756 \end{algorithm}
758 \subsection{Naive Bayes Classifier}
759 \label{naive-bayes}
761 Naive Bayes Classifier uses existing information to construct
762 probability model of likelihoods of given {\em feature variables}
763 based on a discrete-valued {\em class variable}.
764 Using the Bayes equation, we can then estimate the probability distribution
765 of class variable for particular values of the feature variables.
767 In order to approximate player's output vector $\vec O$ based on
768 pattern vector $\vec P$, we will compute each element of the
769 output vector separately, covering the output domain by several $k$-sized
770 discrete intervals (classes).
772 We will also in fact work on
773 PCA-represented input $\vec R$ (using the 10 most significant
774 dimensions), since smaller input dimension is more computationally
775 feasible and $\vec R$ also better fits the pre-requisites of the
776 classifier, the dimensions being more independent and
777 better approximating the normal distribution.
779 When training the classifier for $\vec O$ element $o_i$
780 of class $c = \lfloor o_i/k \rfloor$,
781 we assume the $\vec R$ elements are normally distributed and
782 feed the classifier information in the form
783 $$ \vec R \mid c $$
784 estimating the mean $\mu_c$ and standard deviation $\sigma_c$
785 of each $\vec R$ element for each encountered $c$.
786 Then, we can query the built probability model on
787 $$ \max_c P(c \mid \vec R) $$
788 obtaining the most probable class $i$ for an arbitrary $\vec R$.
789 Each probability is obtained using the normal distribution formula:
790 $$ P(c \mid x) = {1\over \sqrt{2\pi\sigma_c^2}}\exp{-(x-\mu_c)^2\over2\sigma_c^2} $$
792 \begin{algorithm}
793 \caption{Training Naive Bayes}
794 \begin{algorithmic}
795 \label{alg:tnb}
796 \REQUIRE{Train set $T = (\mathit{R, c})$}
797 \FORALL{$(R, c) \in T$}
798 \STATE $\mathit{RbyC}_c \leftarrow \{\mathit{RbyC}_c, R\}$
799 \ENDFOR
800 \FORALL{$c$}
801 \STATE $\mu_c \leftarrow {1 \over |\mathit{RbyC}_c|} \sum_{R \in \mathit{RbyC}_c} R$
802 \ENDFOR
803 \FORALL{$c$}
804 \STATE $\sigma_c \leftarrow {1 \over |\mathit{RbyC}_c|} \sum_{R \in \mathit{RbyC}_c} R-\mu_c $
805 \ENDFOR
806 \end{algorithmic}
807 \end{algorithm}
809 \subsection{Implementation}
811 We have implemented the data mining methods as the
812 ``gostyle'' open-source framework \cite{GoStyle},
813 made available under the GNU GPL licence.
815 The majority of our basic processing and the analysis parts
816 are implemented in the Python \cite{Python25} programming language.
817 We use several external libraries, most notably the MDP library \cite{MDP}.
818 The neural network part of the project is written using the libfann C library\cite{Nissen2003}.
820 The sociomap has been visualised using the Team Profile Analyzer \cite{TPA}
821 which is part of the Sociomap suite \cite{SociomapSite}.
824 \section{Strength Estimation}
826 \begin{figure*}[!t]
827 \centering
828 \includegraphics[width=7in]{strength-pca}
829 \caption{PCA of by-strength vectors}
830 \label{fig:strength_pca}
831 \end{figure*}
833 First, we have used our framework to analyse correlations of pattern vectors
834 and playing strength. Like in other competitively played board games, Go players
835 receive real-world {\em rating number} based on tournament games,
836 and {\em rank} based on their rating.%
837 \footnote{Elo-type rating system \cite{GoR} is usually used,
838 corresponding to even win chances for game of two players with the same rank,
839 and about 2:3 win chance for stronger in case of one rank difference.}%
840 \footnote{Professional ranks and dan ranks in some Asia countries may
841 be assigned differently.}
842 The amateur ranks range from 30-kyu (beginner) to 1-kyu (intermediate)
843 and then follows 1-dan to 7-dan\footnote{9-dan in some systems.} (top-level player).
844 Multiple independent real-world ranking scales exist
845 (geographically based), also online servers maintain their own user ranking;
846 the difference between scales can be up to several ranks and the rank
847 distributions also differ. \cite{RankComparison}
849 \subsection{Data used}
850 As the source game collection, we use Go Teaching Ladder reviews archive%
851 \footnote{The reviews contain comments and variations --- we consider only the main
852 variation with the actual played game.}
853 \cite{GTL} --- this collection contains 7700 games of players with strength ranging
854 from 30-kyu to 4-dan; we consider only even games with clear rank information.
855 Since the rank information is provided by the users and may not be consistent,
856 we are forced to take a simplified look at the ranks,
857 discarding the differences between various systems and thus somewhat
858 increasing error in our model.\footnote{Since our results seem satisfying,
859 we did not pursue to try another collection;
860 one could e.g. look at game archives of some Go server.}
862 \subsection{PCA analysis}
863 First, we have created a single pattern vector for each rank, from 30-kyu to 4-dan;
864 we have performed PCA analysis on the pattern vectors, achieving near-perfect
865 rank correspondence in the first PCA dimension%
866 \footnote{The eigenvalue of the second dimension was four times smaller,
867 with no discernable structure revealed within the lower-order eigenvectors.}
868 (figure \ref{fig:strength_pca}).
870 We measure the accuracy of strength approximation by the first dimension
871 using Pearson's $r$ (see \ref{pearson}), yielding quite satisfying value of $r=0.979$
872 implying extremely strong correlation.
873 \footnote{Extended vector normalization (sec. \ref{xnorm})
874 produced noticeably less clear-cut results.}
876 \subsection{Strength classification}
878 We have randomly separated $10\%$ of the game database as a testing set,
879 one $(\vec p, {\rm rank})$ pair per player. We then explore the influence
880 of game sample size%
881 \footnote{Arbitrary game numbers are approximated by pattern file sizes,
882 randomly selecting games of appropriate strength.}
883 on the accuracy of various classifiers.
884 In order to reduce the diversity of patterns (negatively impacting accuracy
885 on small samples), we do not consider the contiguity pattern features.
887 %Using the most significant PCA eigenvector position directly for classification
888 %of players within the test group yields MSE TODO, thus providing
889 %reasonably satisfying accuracy by itself.
891 %Using the Naive Bayes classifier yields MSE TODO.
893 %Using a random classifier yields MSE TODO.
895 Using the $4$-Nearest Neighbors classifier, we have achieved the results described
896 in the table \ref{table-str-class} --- overally obtaining quite impressive
897 accuracy even on rather small game sample sizes.
898 The error is listed as MSE (on rank rescaled to $[-1,1]$) and standard deviation
899 $\sigma$ in percentages (meaning the difference from the real rank on average).
901 \begin{table}[!t]
902 % increase table row spacing, adjust to taste
903 \renewcommand{\arraystretch}{1.3}
904 \caption{Strength Classifier Performance}
905 \label{table-str-class}
906 \centering
907 \begin{tabular}{|c|c|c|c|c|}
908 \hline
909 $\sim$ games & MSE & $\sigma \%$ \\ \hline
910 $85$& $0.007$ & $4\%$ \\
911 $43$& $0.029$ & $8\%$ \\
912 $17$& $0.081$ & $14\%$ \\
913 $9$& $0.131$ & $18\%$ \\
914 $2$& $0.187$ & $22\%$ \\\hline
915 \end{tabular}
916 \end{table}
918 Finally, we used $8$-fold cross validation on one-file-per-rank files,
919 yielding a MSE $0.085$ which is equivalent to standard deviation of $15\%$.
921 \section{Style Estimation}
922 \label{styleest}
924 As a~second case study for our pattern analysis,
925 we investigate pattern vectors $\vec p$ of various well-known players,
926 their relationships in-between and to prior knowledge
927 in order to explore the correlation of prior knowledge with extracted patterns.
928 We look for relationships between pattern vectors and perceived
929 ``playing style'' and attempt to use our classifiers to transform
930 pattern vector $\vec p$ to style vector $\vec s$.
932 The source game collection is GoGoD Winter 2008 \cite{GoGoD} containing 55000
933 professional games, dating from the early Go history 1500 years ago to the present.
934 We consider only games of a small subset of players (table \ref{fig:style_marks});
935 we have chosen them for being well-known within the players community,
936 having large number of played games in our collection and not playing too long
937 ago.\footnote{Over time, many commonly used sequences get altered, adopted and
938 dismissed; usual playing conditions can also differ significantly.}
940 \subsection{Expert-based knowledge}
941 \label{style-vectors}
942 In order to provide a reference frame for our style analysis,
943 we have gathered some expert-based information about various
944 traditionally perceived style aspects to use as a prior knowledge.
945 This expert-based knowledge allows us to predict styles of unknown players
946 based on the similarity of their pattern vectors,
947 as well as discover correlations between styles and proportions
948 of played patterns.
950 Experts were asked to mark four style aspects of each of the given players
951 on the scale from 1 to 10. The style aspects are defined as shown:
953 \vspace{4mm}
954 \noindent
955 %\begin{table}
956 \begin{center}
957 %\caption{Styles}
958 \begin{tabular}{|c|c|c|}
959 \hline
960 Style & 1 & 10\\ \hline
961 Territoriality $\tau$ & Moyo & Territory \\
962 Orthodoxity $\omega$ & Classic & Novel \\
963 Aggressivity $\alpha$ & Calm & Figting \\
964 Thickness $\theta$ & Safe & Shinogi \\ \hline
965 \end{tabular}
966 \end{center}
967 %\end{table}
968 \vspace{4mm}
970 We have devised these four style aspects based on our own Go experience
971 and consultations with other experts.
972 The used terminology has quite
973 clear meaning to any experienced Go player and there is not too much
974 room for confusion, except possibly in the case of ``thickness'' ---
975 but the concept is not easy to pin-point succintly and we also did not
976 add extra comments on the style aspects to the questionnaire deliberately
977 to accurately reflect any diversity in understanding of the terms.
979 Averaging this expert based evaluation yields \emph{reference style vector}
980 $\vec s_r$ (of dimension $4$) for each player $r$
981 from the set of \emph{reference players} $R$.
983 Throughout our research, we have experimentally found that playing era
984 is also a major factor differentiating between patterns. Thus, we have
985 further extended the $\vec s_r$ by median year over all games played
986 by the player.
988 \begin{table}[!t]
989 % increase table row spacing, adjust to taste
990 \renewcommand{\arraystretch}{1.3}
991 \caption{Covariance Measure of Prior Information Dimensions}
992 \label{fig:style_marks_r}
993 \centering
994 % Some packages, such as MDW tools, offer better commands for making tables
995 % than the plain LaTeX2e tabular which is used here.
996 \begin{tabular}{|r||r||r||r||r||r|}
997 \hline
998 & $\tau$ & $\omega$ & $\alpha$ & $\theta$ & year \\
999 \hline
1000 $\tau$ &$1.000$&$-0.438$&$-0.581$&$ 0.721$&$ 0.108$\\
1001 $\omega$& &$ 1.000$&$ 0.682$&$ 0.014$&$-0.021$\\
1002 $\alpha$& & &$ 1.000$&$-0.081$&$ 0.030$\\
1003 $\theta$& &\multicolumn{1}{c||}{---}
1004 & &$ 1.000$&$-0.073$\\
1005 y. & & & & &$ 1.000$\\
1006 \hline
1007 \end{tabular}
1008 \end{table}
1010 Three high-level Go players (Alexander Dinerstein 3-pro, Motoki Noguchi
1011 7-dan and V\'{i}t Brunner 4-dan) have judged style of the reference
1012 players.
1013 The complete list of answers is in table \ref{fig:style_marks}.
1014 Mean standard deviation of the answers is 0.952,
1015 making the data reasonably reliable,
1016 though much larger sample would of course be more desirable.
1017 We have also found significant correlation between the various
1018 style aspects, as shown by the Pearson's $r$ values
1019 in table \ref{fig:style_marks_r}.
1021 \begin{table}[!t]
1022 % increase table row spacing, adjust to taste
1023 \renewcommand{\arraystretch}{1.4}
1024 \begin{threeparttable}
1025 \caption{Expert-Based Style Aspects of Selected Professionals\tnote{1} \tnote{2}}
1026 \label{fig:style_marks}
1027 \centering
1028 % Some packages, such as MDW tools, offer better commands for making tables
1029 % than the plain LaTeX2e tabular which is used here.
1030 \begin{tabular}{|c||c||c||c||c|}
1031 \hline
1032 {Player} & $\tau$ & $\omega$ & $\alpha$ & $\theta$ \\
1033 \hline
1034 Go Seigen\tnote{3} & $6.0 \pm 2.0$ & $9.0 \pm 1.0$ & $8.0 \pm 1.0$ & $5.0 \pm 1.0$ \\
1035 Ishida Yoshio\tnote{4}&$8.0 \pm 1.4$ & $5.0 \pm 1.4$ & $3.3 \pm 1.2$ & $5.3 \pm 0.5$ \\
1036 Miyazawa Goro & $1.5 \pm 0.5$ & $10 \pm 0 $ & $9.5 \pm 0.5$ & $4.0 \pm 1.0$ \\
1037 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$ \\
1038 Sakata Eio & $7.6 \pm 1.7$ & $4.6 \pm 0.5$ & $7.3 \pm 0.9$ & $8.0 \pm 1.6$ \\
1039 Fujisawa Hideyuki & $3.5 \pm 0.5$ & $9.0 \pm 1.0$ & $7.0 \pm 0.0$ & $4.0 \pm 0.0$ \\
1040 Otake Hideo & $4.3 \pm 0.5$ & $3.0 \pm 0.0$ & $4.6 \pm 1.2$ & $3.6 \pm 0.9$ \\
1041 Kato Masao & $2.5 \pm 0.5$ & $4.5 \pm 1.5$ & $9.5 \pm 0.5$ & $4.0 \pm 0.0$ \\
1042 Takemiya Masaki\tnote{4}&$1.3\pm 0.5$& $6.3 \pm 2.1$ & $7.0 \pm 0.8$ & $1.3 \pm 0.5$ \\
1043 Kobayashi Koichi & $9.0 \pm 1.0$ & $2.5 \pm 0.5$ & $2.5 \pm 0.5$ & $5.5 \pm 0.5$ \\
1044 Cho Chikun & $9.0 \pm 0.8$ & $7.6 \pm 0.9$ & $6.6 \pm 1.2$ & $9.0 \pm 0.8$ \\
1045 Ma Xiaochun & $8.0 \pm 2.2$ & $6.3 \pm 0.5$ & $5.6 \pm 1.9$ & $8.0 \pm 0.8$ \\
1046 Yoda Norimoto & $6.3 \pm 1.7$ & $4.3 \pm 2.1$ & $4.3 \pm 2.1$ & $3.3 \pm 1.2$ \\
1047 Luo Xihe & $7.3 \pm 0.9$ & $7.3 \pm 2.5$ & $7.6 \pm 0.9$ & $6.0 \pm 1.4$ \\
1048 O Meien & $2.6 \pm 1.2$ & $9.6 \pm 0.5$ & $8.3 \pm 1.7$ & $3.6 \pm 1.2$ \\
1049 Rui Naiwei & $4.6 \pm 1.2$ & $5.6 \pm 0.5$ & $9.0 \pm 0.8$ & $3.3 \pm 1.2$ \\
1050 Yuki Satoshi & $3.0 \pm 1.0$ & $8.5 \pm 0.5$ & $9.0 \pm 1.0$ & $4.5 \pm 0.5$ \\
1051 Hane Naoki & $7.5 \pm 0.5$ & $2.5 \pm 0.5$ & $4.0 \pm 0.0$ & $4.5 \pm 1.5$ \\
1052 Takao Shinji & $5.0 \pm 1.0$ & $3.5 \pm 0.5$ & $5.5 \pm 1.5$ & $4.5 \pm 0.5$ \\
1053 Yi Se-tol & $5.3 \pm 0.5$ & $6.6 \pm 2.5$ & $9.3 \pm 0.5$ & $6.6 \pm 1.2$ \\
1054 Yamashita Keigo\tnote{4}&$2.0\pm 0.0$& $9.0 \pm 1.0$ & $9.5 \pm 0.5$ & $3.0 \pm 1.0$ \\
1055 Cho U & $7.3 \pm 2.4$ & $6.0 \pm 0.8$ & $5.3 \pm 1.7$ & $6.3 \pm 1.7$ \\
1056 Gu Li & $5.6 \pm 0.9$ & $7.0 \pm 0.8$ & $9.0 \pm 0.8$ & $4.0 \pm 0.8$ \\
1057 Chen Yaoye & $6.0 \pm 1.0$ & $4.0 \pm 1.0$ & $6.0 \pm 1.0$ & $5.5 \pm 0.5$ \\
1058 \hline
1059 \end{tabular}
1060 \begin{tablenotes}
1061 \item [1] Including standard deviation. Only players where we received at least two out of three answers are included.
1062 \item [2] Since the playing era column does not fit into the table, we at least sort the players ascending by their median year.
1063 \item [3] We do not consider games of Go Seigen due to him playing across several distinct eras and also being famous for radical opening experiments throughout the time, and thus featuring especially high diversity in patterns.
1064 \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 that case corresponds to common knowledge of him being an extreme proponent of anti-territorial (``moyo'') style.
1065 \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 and still has this reputation in minds of many players, but is regarded to have altered his style significantly afterwards.
1066 \end{tablenotes}
1067 \end{threeparttable}
1068 \end{table}
1070 \subsection{Style Components Analysis}
1072 \begin{figure}[!t]
1073 \centering
1074 \includegraphics[width=3.75in]{style-pca}
1075 \caption{PCA of per-player vectors}
1076 \label{fig:style_pca}
1077 \end{figure}
1079 We have looked at the ten most significant dimensions of the pattern data
1080 yielded by the PCA analysis of the reference player set%
1081 \footnote{We also tried to observe PCA effect of removing outlying Takemiya
1082 Masaki. That way, the second dimension strongly
1083 correlated to territoriality and third dimension strongly correlacted to era,
1084 however the first dimension remained mysteriously uncorrelated and with no
1085 obvious interpretation.}
1086 (fig. \ref{fig:style_pca} shows the first three).
1087 We have again computed the Pearson's $r$ for all combinations of PCA dimensions
1088 and dimensions of the prior knowledge style vectors to find correlations.
1090 \begin{table}[!t]
1091 % increase table row spacing, adjust to taste
1092 \renewcommand{\arraystretch}{1.4}
1093 \caption{Covariance Measure of PCA and Prior Information}
1094 \label{fig:style_r}
1095 \centering
1096 % Some packages, such as MDW tools, offer better commands for making tables
1097 % than the plain LaTeX2e tabular which is used here.
1098 \begin{tabular}{|c||r||r||r||r||r|}
1099 \hline
1100 Eigenval. & $\tau$ & $\omega$ & $\alpha$ & $\theta$ & Year \\
1101 \hline
1102 $0.4473697$ & $\mathbf{-0.530}$ & $ 0.323$ & $ 0.298$ & $\mathbf{-0.554}$ & $ 0.090$ \\
1103 $0.1941057$ & $\mathbf{-0.547}$ & $ 0.215$ & $ 0.249$ & $-0.293$ & $\mathbf{-0.630}$ \\
1104 $0.0463189$ & $ 0.131$ & $-0.002$ & $-0.128$ & $ 0.242$ & $\mathbf{-0.630}$ \\
1105 $0.0280301$ & $-0.011$ & $ 0.225$ & $ 0.186$ & $ 0.131$ & $ 0.067$ \\
1106 $0.0243231$ & $-0.181$ & $ 0.174$ & $-0.032$ & $-0.216$ & $ 0.352$ \\
1107 $0.0180875$ & $-0.364$ & $ 0.226$ & $ 0.339$ & $-0.136$ & $ 0.113$ \\
1108 $0.0138478$ & $-0.194$ & $-0.048$ & $-0.099$ & $-0.333$ & $ 0.055$ \\
1109 $0.0110575$ & $-0.040$ & $-0.254$ & $-0.154$ & $-0.054$ & $-0.089$ \\
1110 $0.0093587$ & $-0.199$ & $-0.115$ & $ 0.358$ & $-0.234$ & $-0.028$ \\
1111 $0.0084930$ & $ 0.046$ & $ 0.190$ & $ 0.305$ & $ 0.176$ & $ 0.089$ \\
1112 \hline
1113 \end{tabular}
1114 \end{table}
1116 \begin{table}[!t]
1117 % increase table row spacing, adjust to taste
1118 \renewcommand{\arraystretch}{1.6}
1119 \begin{threeparttable}
1120 \caption{Characteristic Patterns of PCA$_{1,2}$ Dimensions \tnote{1}}
1121 \label{fig:style_patterns}
1122 \centering
1123 % Some packages, such as MDW tools, offer better commands for making tables
1124 % than the plain LaTeX2e tabular which is used here.
1125 \begin{tabular}{|p{2.3cm}p{2.4cm}p{2.4cm}p{0cm}|}
1126 % The virtual last column is here because otherwise we get random syntax errors.
1128 \hline \multicolumn{4}{|c|}{PCA$_1$ --- Moyo-oriented, thin-playing player} \\
1129 \centering \begin{psgopartialboard*}{(8,1)(12,6)}
1130 \stone[\marktr]{black}{k}{4}
1131 \end{psgopartialboard*} &
1132 \centering \begin{psgopartialboard*}{(1,2)(5,6)}
1133 \stone{white}{d}{3}
1134 \stone[\marktr]{black}{d}{5}
1135 \end{psgopartialboard*} &
1136 \centering \begin{psgopartialboard*}{(5,1)(10,6)}
1137 \stone{white}{f}{3}
1138 \stone[\marktr]{black}{j}{4}
1139 \end{psgopartialboard*} & \\
1140 \centering $0.274$ & \centering $0.086$ & \centering $0.083$ & \\
1141 \centering high corner/side opening \tnote{2} & \centering high corner approach & \centering high distant pincer & \\
1143 \hline \multicolumn{4}{|c|}{PCA$_1$ --- Territorial, thick-playing player} \\
1144 \centering \begin{psgopartialboard*}{(3,1)(7,6)}
1145 \stone{white}{d}{4}
1146 \stone[\marktr]{black}{f}{3}
1147 \end{psgopartialboard*} &
1148 \centering \begin{psgopartialboard*}{(3,1)(7,6)}
1149 \stone{white}{c}{6}
1150 \stone{black}{d}{4}
1151 \stone[\marktr]{black}{f}{3}
1152 \end{psgopartialboard*} &
1153 \centering \begin{psgopartialboard*}{(3,1)(7,6)}
1154 \stone{black}{d}{4}
1155 \stone[\marktr]{black}{f}{3}
1156 \end{psgopartialboard*} & \\
1157 \centering $-0.399$ & \centering $-0.399$ & \centering $-0.177$ & \\
1158 \centering low corner approach & \centering low corner reply & \centering low corner enclosure & \\
1160 \hline \multicolumn{4}{|c|}{PCA$_2$ --- Territorial, current player \tnote{3}} \\
1161 \centering \begin{psgopartialboard*}{(3,1)(7,6)}
1162 \stone{white}{c}{6}
1163 \stone{black}{d}{4}
1164 \stone[\marktr]{black}{f}{3}
1165 \end{psgopartialboard*} &
1166 \centering \begin{psgopartialboard*}{(3,1)(8,6)}
1167 \stone{white}{d}{4}
1168 \stone[\marktr]{black}{g}{4}
1169 \end{psgopartialboard*} &
1170 \centering \begin{psgopartialboard*}{(4,1)(9,6)}
1171 \stone{black}{d}{4}
1172 \stone{white}{f}{3}
1173 \stone[\marktr]{black}{h}{3}
1174 \end{psgopartialboard*} & \\
1175 \centering $-0.193$ & \centering $-0.139$ & \centering $-0.135$ & \\
1176 \centering low corner reply \tnote{4} & \centering high distant approach/pincer & \centering near low pincer & \\
1178 \hline
1179 \end{tabular}
1180 \begin{tablenotes}
1181 \item [1] We present the patterns in a simplified compact form;
1182 in reality, they are usually somewhat larger and always circle-shaped
1183 (centered on the triangled move).
1184 We omit only pattern segments that are entirely empty.
1185 \item [2] We give some textual interpretation of the patterns, especially
1186 since some of them may not be obvious unless seen in game context; we choose
1187 the descriptions based on the most frequently observer contexts, but of course
1188 the pattern can be also matched in other positions and situations.
1189 \item [3] In the second PCA dimension, we find no correlated patterns;
1190 only uncorrelated and anti-correlated ones.
1191 \item [4] As the second most significant pattern,
1192 we skip a slide follow-up pattern to this move.
1193 \end{tablenotes}
1194 \end{threeparttable}
1195 \end{table}
1197 \begin{table}[!t]
1198 % increase table row spacing, adjust to taste
1199 \renewcommand{\arraystretch}{1.8}
1200 \begin{threeparttable}
1201 \caption{Characteristic Patterns of PCA$_3$ Dimension \tnote{1}}
1202 \label{fig:style_patterns3}
1203 \centering
1204 % Some packages, such as MDW tools, offer better commands for making tables
1205 % than the plain LaTeX2e tabular which is used here.
1206 \begin{tabular}{|p{2.4cm}p{2.4cm}p{2.4cm}p{0cm}|}
1207 % The virtual last column is here because otherwise we get random syntax errors.
1209 \hline \multicolumn{4}{|c|}{PCA$_3$ --- Old-time player} \\
1210 \centering \begin{psgopartialboard*}{(1,3)(5,7)}
1211 \stone{white}{d}{4}
1212 \stone[\marktr]{black}{c}{6}
1213 \end{psgopartialboard*} &
1214 \centering \begin{psgopartialboard*}{(8,1)(12,5)}
1215 \stone[\marktr]{black}{k}{3}
1216 \end{psgopartialboard*} &
1217 \centering \begin{psgopartialboard*}{(1,1)(5,5)}
1218 \stone[\marktr]{black}{c}{3}
1219 \end{psgopartialboard*} & \\
1220 \centering $0.515$ & \centering $0.264$ & \centering $0.258$ & \\
1221 \centering low corner approach & \centering low side or mokuhazushi opening & \centering san-san opening & \\
1223 \hline \multicolumn{4}{|c|}{PCA$_3$ --- Current player} \\
1224 \centering \begin{psgopartialboard*}{(3,1)(7,5)}
1225 \stone{black}{d}{4}
1226 \stone[\marktr]{black}{f}{3}
1227 \end{psgopartialboard*} &
1228 \centering \begin{psgopartialboard*}{(1,1)(5,5)}
1229 \stone[\marktr]{black}{c}{4}
1230 \end{psgopartialboard*} &
1231 \centering \begin{psgopartialboard*}{(1,2)(5,6)}
1232 \stone{black}{d}{3}
1233 \stone{white}{d}{5}
1234 \stone[\marktr]{black}{c}{5}
1235 \end{psgopartialboard*} & \\
1236 \centering $-0.276$ & \centering $-0.273$ & \centering $-0.116$ & \\
1237 \centering low corner enclosure & \centering 3-4 corner opening \tnote{2} & \centering high approach reply & \\
1239 \hline
1240 \end{tabular}
1241 \begin{tablenotes}
1242 \item [1] We cannot use terms ``classic'' and ''modern'' in case of PCA$_3$
1243 since the current patterns are commonplace in games of past centuries
1244 (not included in our training set) and many would call a lot of the old-time patterns
1245 modern inventions. Perhaps we can infer that the latest 21th-century play trends abandon
1246 many of the 20th-century experiments (lower echelon of our by-year samples)
1247 to return to the more ordinary but effective classic patterns.
1248 \item [2] At this point, we skip two patterns already shown elsewhere:
1249 {\em high side/corner opening} and {\em low corner reply}.
1250 \end{tablenotes}
1251 \end{threeparttable}
1252 \end{table}
1254 It is immediately
1255 obvious both from the measured $r$ and visual observation
1256 that by far the most significant vector corresponds very well
1257 to the territoriality of the players,%
1258 \footnote{Cho Chikun, perhaps the best-known
1259 territorial player, is not well visible in the cluster, but he is
1260 positioned around $-0.8$ on the first dimension.}
1261 confirming the intuitive notion that this aspect of style
1262 is the one easiest to pin-point and also
1263 most obvious in the played shapes and sequences
1264 (that can obviously aim directly at taking secure territory
1265 or building center-oriented framework). Thick (solid) play also plays
1266 a role, but these two style dimensions are already
1267 correlated in the prior data.
1269 The other PCA dimensions are somewhat harder to interpret, but there
1270 certainly is significant influence of the styles on the patterns;
1271 the found correlations are all presented in table \ref{fig:style_r}.
1272 (Larger absolute value means better linear correspondence.)
1274 We also list the characteristic spatial patterns of the PCA dimension
1275 extremes (tables \ref{fig:style_patterns}, \ref{fig:style_patterns3}), determined by their coefficients
1276 in the PCA projection matrix --- however, such naive approach
1277 has limited reliability, better methods will have to be researched.%
1278 \footnote{For example, as one of highly ranked ``Takemiya's'' PCA1 patterns,
1279 3,3 corner opening was generated, completely inappropriately;
1280 it reflects some weak ordering in bottom half of the dimension,
1281 not global ordering within the dimension.}
1282 We do not show the other pattern features since they carry no useful
1283 information in the opening stage.%
1284 \footnote{The board distance feature can be useful in some cases,
1285 but here all the spatial patterns are big enough to reach to the edge
1286 on their own.}
1288 \begin{table}[!t]
1289 % increase table row spacing, adjust to taste
1290 \renewcommand{\arraystretch}{1.4}
1291 \caption{Covariance Measure of Externed-Normalization PCA and~Prior Information}
1292 \label{fig:style_normr}
1293 \centering
1294 % Some packages, such as MDW tools, offer better commands for making tables
1295 % than the plain LaTeX2e tabular which is used here.
1296 \begin{tabular}{|c||r||r||r||r||r|}
1297 \hline
1298 Eigenval. & $\tau$ & $\omega$ & $\alpha$ & $\theta$ & Year \\
1299 \hline
1300 $6.3774289$ & $ \mathbf{0.436}$ & $-0.220$ & $-0.289$ & $ \mathbf{0.404}$ & $\mathbf{-0.576}$ \\
1301 $1.7269775$ & $\mathbf{-0.690}$ & $ 0.340$ & $ 0.315$ & $\mathbf{-0.445}$ & $\mathbf{-0.639}$ \\
1302 $1.1747101$ & $-0.185$ & $ 0.156$ & $ 0.107$ & $-0.315$ & $ 0.320$ \\
1303 $0.8452797$ & $ 0.064$ & $-0.102$ & $-0.189$ & $ 0.032$ & $ 0.182$ \\
1304 $0.8038992$ & $-0.185$ & $ 0.261$ & $ \mathbf{0.620}$ & $ 0.120$ & $ 0.056$ \\
1305 $0.6679533$ & $-0.027$ & $ 0.055$ & $ 0.147$ & $-0.198$ & $ 0.155$ \\
1306 $0.5790000$ & $ 0.079$ & $ \mathbf{0.509}$ & $ 0.167$ & $ 0.294$ & $-0.019$ \\
1307 $0.4971474$ & $ 0.026$ & $-0.119$ & $-0.071$ & $ 0.049$ & $ 0.043$ \\
1308 $0.4938777$ & $-0.061$ & $ 0.061$ & $ 0.104$ & $-0.168$ & $ 0.015$ \\
1309 $0.4888848$ & $ 0.203$ & $-0.283$ & $-0.120$ & $ 0.083$ & $-0.220$ \\
1310 \hline
1311 \end{tabular}
1312 \end{table}
1314 The PCA results presented above do not show much correlation between
1315 the significant PCA dimensions and the $\omega$ and $\alpha$ style dimensions.
1316 However, when we applied the extended vector normalization
1317 (sec. \ref{xnorm}; see table \ref{fig:style_normr}),
1318 some less significant PCA dimensions exhibited clear correlations.%
1319 \footnote{We have found that $c=6$ in the post-processing logistic function
1320 produces the most instructive PCA output on our particular game collection.}
1321 It appears that less-frequent patterns that appear only in the middle-game
1322 phase\footnote{In the middle game, the board is much more filled and thus
1323 particular specific-shape patterns repeat less often.} are defining
1324 for these dimensions, and these are not represented in the pattern vectors
1325 as well as the common opening patterns.
1326 However, we do not use the extended normalization results since
1327 they produced noticeably less accurate classifiers in all dimensions,
1328 including $\omega$ and $\alpha$.
1330 We believe that the next step in interpreting our analytical results
1331 will be more refined prior information input
1332 and precise analysis of the outputs by Go experts.
1334 \begin{figure}[!t]
1335 \centering
1336 \includegraphics[width=3.5in,angle=-90]{sociomap}
1337 \caption{Sociomap visualisation. The spatial positioning of players
1338 is based on the expert knowledge, while the node heights (depicted by
1339 contour lines) represent the pattern vectors.%
1340 %The light lines denote coherence-based hierarchical clusters.
1342 \label{fig:sociomap}
1343 \end{figure}
1345 Fig. \ref{fig:sociomap} shows the Sociomap visualisation
1346 as an alternate view of the player relationships and similarity,
1347 as well as correlation between the expert-given style marks
1348 and the PCA decomposition. The four-dimensional style vectors
1349 are used as input for the Sociomap renderer and determine the
1350 spatial positions of players. The height of a node is then
1351 determined using first two PCA dimensions $R_1,R_2$ and their
1352 eigenvalues $\lambda_1,\lambda_2$ as their linear combination:
1353 $$ h=\lambda_1R_1 + \lambda_2R_2 $$
1355 We can observe that the terrain of the sociomap is reasonably
1356 ``smooth'', again demonstrating some level of connection between
1357 the style vectors and data-mined information. High countour density
1358 indicates some discrepancy; in case of Takemiya Masaki and Yi Ch'ang-ho,
1359 this seems to be merely an issue of scale,
1360 while the Rui Naiwei --- Gu Li cliff suggests a genuine problem;
1361 we cannot say now whether it is because of imprecise prior information
1362 or bad approximation abilities of our model.
1364 \subsection{Style Classification}
1366 %TODO vsude zcheckovat jestli pouzivame stejny cas "we perform, we apply" X "we have performed, ..."
1368 Apart from the PCA-based analysis, we tested the style inference ability
1369 of neural network (sec. \ref{neural-net}), $k$-NN (sec. \ref{knn}) and Bayes (sec. \ref{naive-bayes}) classifers.
1371 \subsubsection{Reference (Training) Data}
1372 As the~reference data, we use expert-based knowledge presented in section \ref{style-vectors}.
1373 For each reference player, that gives $4$-dimensional \emph{style vector} (each component in the
1374 range of $[1,10]$).\footnote{Since the neural network has activation function with range $[-1,1]$, we
1375 have linearly rescaled the \emph{style vectors} from interval $[1,10]$ to $[-1,1]$ before using the training
1376 data. The network's output was afterwards rescaled back to allow for MSE comparison.}
1378 All input (pattern) vectors were preprocessed using PCA, reducing the input dimension from $400$ to $23$.
1379 We measure the performance on the same reference data using $5$-fold cross validation.
1380 To put our measurements in scale, we also include a~random classifier in our results.
1382 \subsubsection{Results}
1383 The results are shown in the table \ref{crossval-cmp}. Second to fifth columns in the table represent
1384 mean square error of the examined styles, $\mathit{Mean}$ is the
1385 mean square error across the styles and finally, the last column $\mathit{Cmp}$
1386 represents $\mathit{Mean}(\mathit{Random classifier}) / \mathit{Mean}(\mathit{X})$ -- comparison of mean square error
1387 of method $\mathit{X}$ with the random classifier. To minimize the
1388 effect of random variables, all numbers were taken as an average of $200$ runs of the cross validation.
1390 Analysis of the performance of $k$-NN classifier for different $k$-values showed that different
1391 $k$-values are suitable to approximate different styles. Combining the $k$-NN classifiers with the
1392 neural network (so that each style is approximated by the method with lowest MSE in that style)
1393 results in \emph{Joint classifier}, which outperforms all other methods. (Table \ref{crossval-cmp})
1394 The \emph{Joint classifier} has outstanding MSE $3.960$, which is equivalent to standard deviation
1395 of $\sigma = 1.99$ per style.
1397 \begin{table}[!t]
1398 \renewcommand{\arraystretch}{1.4}
1399 \begin{threeparttable}
1400 \caption{Comparison of style classifiers}
1401 \label{crossval-cmp}
1402 \begin{tabular}{|c|c|c|c|c|c|c|}
1403 \hline
1404 %Classifier & $\sigma_\tau$ & $\sigma_\omega$ & $\sigma_\alpha$ & $\sigma_\theta$ & Tot $\sigma$ & $\mathit{RndC}$\\ \hline
1405 %Neural network & 0.420 & 0.488 & 0.365 & 0.371 & 0.414 & 1.82 \\
1406 %$k$-NN ($k=4$) & 0.394 & 0.507 & 0.457 & 0.341 & 0.429 & 1.76 \\
1407 %Random classifier & 0.790 & 0.773 & 0.776 & 0.677 & 0.755 & 1.00 \\ \hline
1408 &\multicolumn{5}{|c|}{MSE}& \\ \hline
1409 {Classifier} & $\tau$ & $\omega$ & $\alpha$ & $\theta$ & {\bf Mean} & {\bf Cmp}\\ \hline
1410 Joint classifier\tnote{1} & 4.04 & {\bf 5.25} & {\bf 3.52} & {\bf 3.05} & {\bf 3.960}& 2.97 \\\hline
1411 Neural network & {\bf 4.03} & 6.15 & {\bf 3.58} & 3.79 & 4.388 & 2.68 \\
1412 $k$-NN ($k=2$) & 4.08 & 5.40 & 4.77 & 3.37 & 4.405 & 2.67 \\
1413 $k$-NN ($k=3$) & 4.05 & 5.58 & 5.06 & 3.41 & 4.524 & 2.60 \\
1414 $k$-NN ($k=1$) & 4.52 & {\bf 5.26} & 5.36 & {\bf 3.09} & 4.553 & 2.59 \\
1415 $k$-NN ($k=4$) & 4.10 & 5.88 & 5.16 & 3.60 & 4.684 & 2.51 \\
1416 Naive Bayes & 4.48 & 6.90 & 5.48 & 3.70 & 5.143 & 2.29 \\
1417 Random class. & 12.26 & 12.33 & 12.40 & 10.11 & 11.776 & 1.00 \\\hline
1419 \end{tabular}
1420 \begin{tablenotes}
1421 \item [1] Note that these measurements have a certain variance. The Joint classifier measurements were taken independently and
1422 they can differ from the according methods.
1423 \end{tablenotes}
1424 \end{threeparttable}
1425 \end{table}
1427 % TODO presunout konkretni parametry do Appendixu? (neni jich tolik, mozna ne)
1428 \subsubsection{$k$-NN parameters}
1429 All three variants of $k$-NN classifier ($k=2,3,4$) we have used and compared had the following weight function
1430 \begin{equation}
1431 \mathit{Weight}(\vec x) = 0.8^{10*\mathit{Distance}(\vec x)}
1432 \end{equation}
1433 The parameters were chosen empirically to minimize the MSE.
1435 \subsubsection{Neural network's parameters}
1436 The neural network classifier had $3$-layered architecture (one hidden layer) with following numbers of
1437 neurons:
1438 \vspace{4mm}
1439 \noindent
1440 %\begin{table}
1441 \begin{center}
1442 %\caption{Styles}
1443 \begin{tabular}{|c|c|c|}
1444 \hline
1445 \multicolumn{3}{|c|}{Layer} \\\hline
1446 Input & Hidden & Output \\ \hline
1447 23 & 30 & 4 \\ \hline
1448 \end{tabular}
1449 \end{center}
1450 %\end{table}
1451 \vspace{4mm}
1453 The network was trained until the square error on the training set was smaller than $0.0003$.
1454 Due to a small number of input vectors, this only took $20$ iterations of RPROP learning algorithm on average.
1456 \subsubsection{Naive Bayes parameters}
1458 We have chosen $k = 10/7$ as our discretization parameter;
1459 ideally, we would use $k = 1$ to fully cover the style marks
1460 domain, however our training sample is probably too small for
1461 that.
1463 \section{Proposed Applications}
1465 We believe that our findings might be useful for many applications
1466 in the area of Go support software as well as Go-playing computer engines.
1468 The style analysis can be an excellent teaching aid --- classifying style
1469 dimensions based on player's pattern vector, many study recommendations
1470 can be given, e.g. about the professional games to replay, the goal being
1471 balancing understanding of various styles to achieve well-rounded skill set.
1472 This was also our original aim when starting the research and a user-friendly
1473 tool based on our work is now being created.
1475 We hope that more strong players will look into the style dimensions found
1476 by our statistical analysis --- analysis of most played patterns of prospective
1477 opponents might prepare for the game, but we especially hope that new insights
1478 on strategic purposes of various shapes and general human understanding
1479 of the game might be achieved by investigating the style-specific patterns.
1480 Time by time, new historical game records are still being discovered;
1481 pattern-based classification might help to suggest origin of the games
1482 in Go Archeology.
1484 Classifying playing strength of a pattern vector of a player can be used
1485 e.g. to help determine initial real-world rating of a player before their
1486 first tournament based on games played on the internet; some players especially
1487 in less populated areas could get fairly strong before playing their first
1488 real tournament.
1490 Analysis of pattern vectors extracted from games of Go-playing programs
1491 in light of the shown strength and style distributions might help to
1492 highlight some weaknesses and room for improvements. (However, since
1493 correlation does not imply causation, simply optimizing Go-playing programs
1494 according to these vectors is unlikely to yield good results.)
1495 Another interesting applications in Go-playing programs might be strength
1496 adjustment; the program can classify the player's level based on the pattern
1497 vector from its previous games and auto-adjust its difficulty settings
1498 accordingly to provide more even games for beginners.
1501 % An example of a floating figure using the graphicx package.
1502 % Note that \label must occur AFTER (or within) \caption.
1503 % For figures, \caption should occur after the \includegraphics.
1504 % Note that IEEEtran v1.7 and later has special internal code that
1505 % is designed to preserve the operation of \label within \caption
1506 % even when the captionsoff option is in effect. However, because
1507 % of issues like this, it may be the safest practice to put all your
1508 % \label just after \caption rather than within \caption{}.
1510 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
1511 % option should be used if it is desired that the figures are to be
1512 % displayed while in draft mode.
1514 %\begin{figure}[!t]
1515 %\centering
1516 %\includegraphics[width=2.5in]{myfigure}
1517 % where an .eps filename suffix will be assumed under latex,
1518 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
1519 % via \DeclareGraphicsExtensions.
1520 %\caption{Simulation Results}
1521 %\label{fig_sim}
1522 %\end{figure}
1524 % Note that IEEE typically puts floats only at the top, even when this
1525 % results in a large percentage of a column being occupied by floats.
1528 % An example of a double column floating figure using two subfigures.
1529 % (The subfig.sty package must be loaded for this to work.)
1530 % The subfigure \label commands are set within each subfloat command, the
1531 % \label for the overall figure must come after \caption.
1532 % \hfil must be used as a separator to get equal spacing.
1533 % The subfigure.sty package works much the same way, except \subfigure is
1534 % used instead of \subfloat.
1536 %\begin{figure*}[!t]
1537 %\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
1538 %\label{fig_first_case}}
1539 %\hfil
1540 %\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
1541 %\label{fig_second_case}}}
1542 %\caption{Simulation results}
1543 %\label{fig_sim}
1544 %\end{figure*}
1546 % Note that often IEEE papers with subfigures do not employ subfigure
1547 % captions (using the optional argument to \subfloat), but instead will
1548 % reference/describe all of them (a), (b), etc., within the main caption.
1551 % An example of a floating table. Note that, for IEEE style tables, the
1552 % \caption command should come BEFORE the table. Table text will default to
1553 % \footnotesize as IEEE normally uses this smaller font for tables.
1554 % The \label must come after \caption as always.
1556 %\begin{table}[!t]
1557 %% increase table row spacing, adjust to taste
1558 %\renewcommand{\arraystretch}{1.3}
1559 % if using array.sty, it might be a good idea to tweak the value of
1560 % \extrarowheight as needed to properly center the text within the cells
1561 %\caption{An Example of a Table}
1562 %\label{table_example}
1563 %\centering
1564 %% Some packages, such as MDW tools, offer better commands for making tables
1565 %% than the plain LaTeX2e tabular which is used here.
1566 %\begin{tabular}{|c||c|}
1567 %\hline
1568 %One & Two\\
1569 %\hline
1570 %Three & Four\\
1571 %\hline
1572 %\end{tabular}
1573 %\end{table}
1576 % Note that IEEE does not put floats in the very first column - or typically
1577 % anywhere on the first page for that matter. Also, in-text middle ("here")
1578 % positioning is not used. Most IEEE journals use top floats exclusively.
1579 % Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
1580 % floats. This can be corrected via the \fnbelowfloat command of the
1581 % stfloats package.
1585 \section{Future Research}
1587 Since we are not aware of any previous research on this topic and we
1588 are limited by space and time constraints, plenty of research remains
1589 to be done, in all parts of our analysis --- we have already noted
1590 many in the text above. Most significantly, different methods of generating
1591 and normalizing the $\vec p$ vectors can be explored
1592 and other data mining methods could be investigated.
1593 Better ways of visualising the relationships would be desirable,
1594 together with thorough dissemination of internal structure
1595 of the player pattern vectors space.
1597 It can be argued that many players adjust their style by game conditions
1598 (Go development era, handicap, komi and color, time limits, opponent)
1599 or styles might express differently in various game stages.
1600 More professional players could be consulted on the findings
1601 and for style scales calibration.
1602 Impact of handicap games on by-strength
1603 $\vec p$ distribution should be also investigated.
1605 % TODO: Future research --- Sparse PCA
1607 \section{Conclusion}
1608 We have proposed a way to extract summary pattern information from
1609 game collections and combined this with various data mining methods
1610 to show correspondence of our pattern summaries with various player
1611 meta-information like playing strength, era of play or playing style
1612 as ranked by expert players. We have implemented and measured our
1613 proposals in two case studies: per-rank characteristics of amateur
1614 players and per-player style/era characteristics of well-known
1615 professionals.
1617 While many details remain to be worked out,
1618 we have demonstrated that many significant correlations do exist and
1619 it is practically viable to infer the player meta-information from
1620 extracted pattern summaries. We proposed wide range of applications
1621 for such inference. Finally, we outlined some of the many possible
1622 directions of future work in this newly staked research field
1623 on the boundary of Computer Go, Data Mining and Go Theory.
1626 % if have a single appendix:
1627 %\appendix[Proof of the Zonklar Equations]
1628 % or
1629 %\appendix % for no appendix heading
1630 % do not use \section anymore after \appendix, only \section*
1631 % is possibly needed
1633 % use appendices with more than one appendix
1634 % then use \section to start each appendix
1635 % you must declare a \section before using any
1636 % \subsection or using \label (\appendices by itself
1637 % starts a section numbered zero.)
1641 %\appendices
1642 %\section{Proof of the First Zonklar Equation}
1643 %Appendix one text goes here.
1645 %% you can choose not to have a title for an appendix
1646 %% if you want by leaving the argument blank
1647 %\section{}
1648 %Appendix two text goes here.
1651 % use section* for acknowledgement
1652 \section*{Acknowledgment}
1653 \label{acknowledgement}
1655 Foremostly, we are very grateful for detailed input on specific go styles
1656 by Alexander Dinerstein, Motoki Noguchi and V\'{i}t Brunner.
1657 We appreciate X reviewing our paper, and helpful comments on our general methodology
1658 by John Fairbairn, T. M. Hall, Cyril H\"oschl, Robert Jasiek, Franti\v{s}ek Mr\'{a}z
1659 and several GoDiscussions.com users. \cite{GoDiscThread}
1660 Finally, we would like to thank Radka ``chidori'' Hane\v{c}kov\'{a}
1661 for the original research idea and acknowledge major inspiration
1662 by R\'{e}mi Coulom's paper \cite{PatElo} on the extraction of pattern information.
1665 % Can use something like this to put references on a page
1666 % by themselves when using endfloat and the captionsoff option.
1667 \ifCLASSOPTIONcaptionsoff
1668 \newpage
1673 % trigger a \newpage just before the given reference
1674 % number - used to balance the columns on the last page
1675 % adjust value as needed - may need to be readjusted if
1676 % the document is modified later
1677 %\IEEEtriggeratref{8}
1678 % The "triggered" command can be changed if desired:
1679 %\IEEEtriggercmd{\enlargethispage{-5in}}
1681 % references section
1683 % can use a bibliography generated by BibTeX as a .bbl file
1684 % BibTeX documentation can be easily obtained at:
1685 % http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
1686 % The IEEEtran BibTeX style support page is at:
1687 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1688 \bibliographystyle{IEEEtran}
1689 % argument is your BibTeX string definitions and bibliography database(s)
1690 \bibliography{gostyle}
1692 % <OR> manually copy in the resultant .bbl file
1693 % set second argument of \begin to the number of references
1694 % (used to reserve space for the reference number labels box)
1695 %\begin{thebibliography}{1}
1697 %\bibitem{MasterMCTS}
1699 %\end{thebibliography}
1701 % biography section
1703 % If you have an EPS/PDF photo (graphicx package needed) extra braces are
1704 % needed around the contents of the optional argument to biography to prevent
1705 % the LaTeX parser from getting confused when it sees the complicated
1706 % \includegraphics command within an optional argument. (You could create
1707 % your own custom macro containing the \includegraphics command to make things
1708 % simpler here.)
1709 %\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
1710 % or if you just want to reserve a space for a photo:
1712 %\begin{IEEEbiography}{Petr Baudi\v{s}}
1713 %Biography text here.
1714 %\end{IEEEbiography}
1716 % if you will not have a photo at all:
1717 \begin{IEEEbiographynophoto}{Petr Baudi\v{s}}
1718 Received BSc degree in Informatics at Charles University, Prague in 2009,
1719 currently a graduate student.
1720 Doing research in the fields of Computer Go, Monte Carlo Methods
1721 and Version Control Systems.
1722 Plays Go with the rank of 2-kyu on European tournaments
1723 and 2-dan on the KGS Go Server.
1724 \end{IEEEbiographynophoto}
1726 \begin{IEEEbiographynophoto}{Josef Moud\v{r}\'{i}k}
1727 Received BSc degree in Informatics at Charles University, Prague in 2009,
1728 currently a graduate student.
1729 Doing research in the fields of Neural Networks and Cognitive Sciences.
1730 His Go skills are not worth mentioning.
1731 \end{IEEEbiographynophoto}
1733 % insert where needed to balance the two columns on the last page with
1734 % biographies
1735 %\newpage
1737 %\begin{IEEEbiographynophoto}{Jane Doe}
1738 %Biography text here.
1739 %\end{IEEEbiographynophoto}
1741 % You can push biographies down or up by placing
1742 % a \vfill before or after them. The appropriate
1743 % use of \vfill depends on what kind of text is
1744 % on the last page and whether or not the columns
1745 % are being equalized.
1747 %\vfill
1749 % Can be used to pull up biographies so that the bottom of the last one
1750 % is flush with the other column.
1751 %\enlargethispage{-5in}
1755 % that's all folks
1756 \end{document}