1 \documentclass[journal
]{IEEEtran
}
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 ***
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}
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}
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}
42 \usepackage{threeparttable
}
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 ***
62 % http://www.ctan.org/tex-archive/macros/latex/required/tools/
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
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".
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
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:
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}}
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
173 % \let\MYorigsubfloat\subfloat
174 % \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
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 ***
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,
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
}
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.
245 \markboth{Transactions on Computational Intelligence and AI in Games --- DRAFT1p
}%
246 {On Pattern Feature Trends in Large Go Game Corpus --- DRAFT1p
}
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
258 % If you want to put a publisher's ID mark on the page you can do it like
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
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
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.
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
312 % For peer review papers, you can put extra information on the cover
314 % \ifCLASSOPTIONpeerreview
315 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
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
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:
401 \item capture move flag
402 \item atari move flag
403 \item atari escape flag
404 \item contiguity-to-last flag --- whether the move has been played in one of
8 neighbors of the last move
405 \item contiguity-to-second-last flag
406 \item board edge distance --- only up to distance
4
407 \item spatial pattern --- configuration of stones around the played move
410 The spatial patterns are normalized (using a dictionary) to be always
411 black-to-play and maintain translational and rotational symmetry.
412 Configurations of radius between
2 and
9 in the gridcular metric
%
413 \footnote{The
{\em gridcular
} metric
414 $d(x,y) = |
\delta x| + |
\delta y| +
\max(|
\delta x|, |
\delta y|)$ produces
415 a circle-like structure on the Go board square grid.
\cite{SpatPat
} }
418 Pattern vectors representing these features contain information on
419 played shape as well as basic representation of tactical dynamics
420 --- threats to capture stones, replying to last move, or ignoring
421 opponent's move elsewhere to return to an urgent local situation.
422 The shapes most frequently correspond to opening moves
423 (either in empty corners and sides, or as part of
{\em joseki
}
424 --- commonly played sequences) characteristic for a certain
425 strategic aim. In the opening, even a single-line difference
426 in the distance from the border can have dramatic impact on
427 further local and global development.
429 \subsection{Vector Rescaling
}
431 The pattern vector elements can have diverse values since for each object,
432 we consider different number of games (and thus patterns).
433 Therefore, we normalize the values to range $
[-
1,
1]$,
434 the most frequent pattern having the value of $
1$ and the least occuring
436 Thus, we obtain vectors describing relative frequency of played patterns
437 independent on number of gathered patterns.
438 But there are multiple ways to approach the normalization.
442 \includegraphics{patcountdist
}
443 \caption{Log-scaled number of pattern occurences
444 in the GoGoD games examined in sec.
\ref{styleest
}.
}
445 \label{fig:patcountdist
}
448 \subsubsection{Linear Normalization
}
450 One is simply to linearly re-scale the values using:
451 $$y_i =
{x_i - x_
{\rm min
} \over x_
{\rm max
}}$$
452 This is the default approach; we have used data processed by only this
453 computation unless we note otherwise.
454 As shown on fig.
\ref{fig:patcountdist
}, most of the spectrum is covered
455 by the few most-occuring patterns (describing mostly large-diameter
456 shapes from the game opening). This means that most patterns will be
457 always represented by only very small values near the lower bound.
459 \subsubsection{Extended Normalization
}
462 To alleviate this problem, we have also tried to modify the linear
463 normalization by applying two steps ---
{\em pre-processing
}
465 $$x_i' =
\log (x_i +
1)$$
466 and
{\em post-processing
} the re-scaled values by the logistic function:
467 $$y_i' =
{2 \over 1 + e^
{-cy_i
}}-
1$$
468 However, we have found that this method is not universally beneficial.
469 In our styles case study (sec.
\ref{styleest
}), this normalization
470 produced PCA decomposition with significant dimensions corresponding
471 better to some of the prior knowledge and more instructive for manual
472 inspection, but ultimately worsened accuracy of our classifiers;
473 we conjecture from this that the most frequently occuring patterns are
474 also most important for classification of major style aspects.
476 \subsection{Implementation
}
478 We have implemented the data extraction by making use of the pattern
479 features matching implementation
%
480 \footnote{The pattern features matching was developed according
481 to the Elo-rating playing scheme.
\cite{PatElo
}}
482 within the Pachi go-playing program
\cite{Pachi
}.
483 We extract information on players by converting the SGF game
484 records to GTP stream
\cite{GTP
} that feeds Pachi's
{\tt patternscan
}
485 engine, outputting a~single
{\em patternspec
} (string representation
486 of the particular pattern features combination) per move. Of course,
487 only moves played by the appropriate
color in the game are collected.
489 \section{Data Mining
}
492 To assess the properties of gathered pattern vectors
493 and their influence on playing styles,
494 we process the data by several basic data minining techniques.
496 The first two methods
{\em (analytic)
} rely purely on single data set
497 and serve to show internal structure and correlations within the data set.
499 Principal Component Analysis finds orthogonal vector components that
500 have the largest variance.
501 Reversing the process can indicate which patterns correlate with each component.
502 Additionally, PCA can be used as vector preprocessing for methods
503 that are negatively sensitive to pattern vector component correlations.
505 The~second method of Sociomaps
\cite{Sociomaps
} creates spatial
506 representation of the data set elements (e.g. players) based on
507 similarity of their data set features; we can then project other
508 information on the map to illutrate its connection to the data set.
510 Furthermore, we test several
\emph{classification
} methods that assign
511 each pattern vector $
\vec P$ an
\emph{output vector
} $
\vec O$,
512 representing e.g.~information about styles, player's strength or even
513 meta-information like the player's era or a country of origin.
514 Initially, the methods must be calibrated (trained) on some prior knowledge,
515 usually in the form of
\emph{reference pairs
} of pattern vectors
516 and the associated output vectors.
518 Moreover, the reference set can be divided into training and testing pairs
519 and the methods can be compared by the mean square error on testing data set
520 (difference of output vectors approximated by the method and their real desired value).
522 %\footnote{However, note that dicrete characteristics such as country of origin are
523 %not very feasible to use here, since WHAT??? is that even true?? }
525 First, we test the $k$-Nearest Neighbors
\cite{CoverHart1967
} classifier
526 approximates $
\vec O$ by composing the output vectors
527 of $k$ reference pattern vectors closest to $
\vec P$.
529 Another classifier is a~multi-layer feed-forward Artificial Neural Network:
530 the neural network can learn correlations between input and output vectors
531 and generalize the ``knowledge'' to unknown vectors; it can be more flexible
532 in the interpretation of different pattern vector elements and discern more
533 complex relations than the kNN classifier,
534 but may not be as stable and requires larger training sample.
536 Finally, a commonly used classifier in statistical inference is
537 the Naive Bayes classifier; it can infer relative probability of membership
538 in various classes based on previous evidence (training patterns).
\cite{Bayes
}
540 \subsection{Principal Component Analysis
}
542 We use Principal Component Analysis
\emph{PCA
} \cite{Jolliffe1986
}
543 to reduce the dimensions of the pattern vectors while preserving
544 as much information as possible, assuming inter-dependencies between
545 pattern vector dimensions are linear.
547 Briefly, PCA is an eigenvalue decomposition of a~covariance matrix of centered pattern vectors,
548 producing a~linear mapping $o$ from $n$-dimensional vector space
549 to a~reduced $m$-dimensional vector space.
550 The $m$ eigenvectors of the original vectors' covariance matrix
551 with the largest eigenvalues are used as the base of the reduced vector space;
552 the eigenvectors form projection matrix $W$.
554 For each original pattern vector $
\vec p_i$,
555 we obtain its new representation $
\vec r_i$ in the PCA base
556 as shown in the following equation:
558 \vec r_i = W
\cdot \vec p_i
561 The whole process is described in the Algorithm
\ref{alg:pca
}.
564 \caption{PCA -- Principal Component Analysis
}
567 \REQUIRE{$m >
0$, set of players $R$ with pattern vectors $p_r$
}
568 \STATE $
\vec \mu \leftarrow 1/|R|
\cdot \sum_{r
\in R
}{\vec p_r
}$
570 \STATE $
\vec p_r
\leftarrow \vec p_r -
\vec \mu$
572 \FOR{ $(i,j)
\in \
{1,... ,n\
} \times \
{1,... ,n\
}$
}
573 \STATE $
\mathit{Cov
}[i,j
] \leftarrow 1/|R|
\cdot \sum_{r
\in R
}{\vec p_
{ri
} \cdot \vec p_
{rj
}}$
575 \STATE Compute Eigenvalue Decomposition of $
\mathit{Cov
}$ matrix
576 \STATE Get $m$ largest eigenvalues
577 \STATE Most significant eigenvectors ordered by decreasing eigenvalues form the rows of matrix $W$
579 \STATE $
\vec r_r
\leftarrow W
\vec p_r$
585 We want to find correlations between PCA dimensions and
586 some prior knowledge (player rank, style vector).
587 For this purpose, we compute the well-known
588 {\em Pearson product-moment correlation coefficient
} \cite{Pearson
},
589 measuring the strength of the linear dependence
%
590 \footnote{A desirable property of PMCC is that it is invariant to translations and rescaling
592 between the dimensions:
594 $$ r_
{X,Y
} =
{{\rm cov
}(X,Y)
\over \sigma_X \sigma_Y} $$
596 \subsection{Sociomaps
}
598 Sociomaps are a general mechanism for visualising possibly assymetric
599 relationships on a
2D plane such that ordering of the maximum possible
600 object distances in the dataset is preserved in distances on the plane.
602 In our particular case,
%
603 \footnote{A special case of the
{\em Subject-to-Object Relation Mapping (STORM)
} indirect sociomap.
}
604 we will consider a dataset $
\vec S$ of small-dimensional
605 vectors $
\vec s_i$ and determine projection $
\varphi$ of all the $
\vec s_i$
606 to spatial coordinates of an Euclidean plane.
607 The $
\varphi$ projection shall maximize the
{\em three-way ordering
} criterion:
608 ordering of any three members in the dataset and on the plane
609 (by Euclidean metric) must be the same.
611 $$
\min_\varphi \sum_{i
\ne j
\ne k
} \Phi(
\varphi, i, j, k) $$
612 $$
\Phi(
\varphi, i, j, k) =
\begin{cases
}
613 1 &
\delta(s_i,s_j,s_k) =
\delta(
\varphi(i),
\varphi(j),
\varphi(k)) \\
614 0 &
\hbox{otherwise
} \end{cases
} $$
615 $$
\delta(a, b, c) =
\begin{cases
}
618 -
1 & |a-b| < |a-c|
\end{cases
} $$
620 \subsection{k-nearest Neighbors Classifier
}
622 Our goal is to approximate player's output vector $
\vec O$;
623 we know his pattern vector $
\vec P$.
624 We further assume that similarities in players' pattern vectors
625 uniformly correlate with similarities in players' output vectors.
627 We require a set of reference players $R$ with known
\emph{pattern vectors
} $
\vec p_r$
628 and
\emph{output vectors
} $
\vec o_r$.
630 $
\vec O$ is approximated as a~weighted average of
\emph{output vectors
}
631 $
\vec o_i$ of $k$ players with
\emph{pattern vectors
} $
\vec p_i$ closest to $
\vec P$.
632 This is illustrated in the Algorithm
\ref{alg:knn
}.
633 Note that the weight is a function of distance and is not explicitly defined in Algorithm
\ref{alg:knn
}.
634 During our research, exponentially decreasing weight has proven to be sufficient.
637 \caption{k-Nearest Neighbors
}
640 \REQUIRE{pattern vector $
\vec P$, $k >
0$, set of reference players $R$
}
642 \STATE $D
[r
] \leftarrow \mathit{EuclideanDistance
}(
\vec p_r,
\vec P)$
644 \STATE $N
\leftarrow \mathit{SelectSmallest
}(k, R, D)$
645 \STATE $
\vec O
\leftarrow \vec 0$
647 \STATE $
\vec O
\leftarrow \vec O +
\mathit{Weight
}(D
[r
])
\cdot \vec o_r $
652 \subsection{Neural Network Classifier
}
655 Feed-forward neural networks
\cite{ANN
} are known for their ability to generalize
656 and find correlations between input patterns and output classifications.
657 Before use, the network is iteratively trained on the training data
658 until the error on the training set is reasonably small.
660 %Neural network is an adaptive system that must undergo a training
661 %period similarly to the requirement
662 %of reference vectors for the k-Nearest Neighbors algorithm above.
664 \subsubsection{Computation and activation of the NN
}
665 Technically, the neural network is a network of interconnected
666 computational units called neurons.
667 A feedforward neural network has a layered topology;
668 it usually has one
\emph{input layer
}, one
\emph{output layer
}
669 and an arbitrary number of
\emph{hidden layers
} between.
671 Each neuron $i$ is connected to all neurons in the previous layer and each connection has its weight $w_
{ij
}$
673 The computation proceeds in discrete time steps.
674 In the first step, the neurons in the
\emph{input layer
}
675 are
\emph{activated
} according to the
\emph{input vector
}.
676 Then, we iteratively compute output of each neuron in the next layer
677 until the output layer is reached.
678 The activity of output layer is then presented as the result.
680 The activation $y_i$ of neuron $i$ from the layer $I$ is computed as
682 y_i = f
\left(
\sum_{j
\in J
}{w_
{ij
} y_j
}\right)
684 where $J$ is the previous layer, while $y_j$ is the activation for neurons from $J$ layer.
685 Function $f()$ is a~so-called
\emph{activation function
}
686 and its purpose is to bound the outputs of neurons.
687 A typical example of an activation function is the sigmoid function.
%
688 \footnote{A special case of the logistic function, defined by the formula
689 $
\sigma(x)=
\frac{1}{1+e^
{-(rx+k)
}}$; parameters control the growth rate ($r$)
690 and the x-position ($k$).
}
692 \subsubsection{Training
}
693 Training of the feed-forward neural network usually involves some
694 modification of supervised Backpropagation learning algorithm.
695 We use first-order optimization algorithm called RPROP.
\cite{Riedmiller1993
}
697 %Because the \emph{reference set} is usually not very large,
698 %we have devised a simple method for its extension.
699 %This enhancement is based upon adding random linear combinations
700 %of \emph{style and pattern vectors} to the training set.
702 As outlined above, the training set $T$ consists of
703 $(
\vec p_i,
\vec o_i)$ pairs.
704 The training algorithm is shown in Algorithm
\ref{alg:tnn
}.
707 \caption{Training Neural Network
}
710 \REQUIRE{Train set $T$, desired error $e$, max iterations $M$
}
711 \STATE $N
\leftarrow \mathit{RandomlyInitializedNetwork
}()$
712 \STATE $
\mathit{It
} \leftarrow 0$
714 \STATE $
\mathit{It
} \leftarrow \mathit{It
} +
1$
715 \STATE $
\Delta \vec w
\leftarrow \vec 0$
716 \STATE $
\mathit{TotalError
} \leftarrow 0$
717 %\FORALL{$(\overrightarrow{Input}, \overrightarrow{DesiredOutput}) \in T$}
718 %\STATE $\overrightarrow{Output} \leftarrow Result(N, \overrightarrow{Input})$
719 %\STATE $E \leftarrow |\overrightarrow{DesiredOutput} - \overrightarrow{Output}|$
720 \FORALL{$(
\mathit{Input
},
\mathit{DesiredOutput
})
\in T$
}
721 \STATE $
\mathit{Output
} \leftarrow \mathit{Result
}(N,
\mathit{Input
})$
722 \STATE $
\mathit{Error
} \leftarrow |
\mathit{DesiredOutput
} -
\mathit{Output
}|$
723 \STATE $
\Delta \vec w
\leftarrow \Delta \vec w +
\mathit{WeightUpdate
}(N,
\mathit{Error
})$
724 \STATE $
\mathit{TotalError
} \leftarrow \mathit{TotalError
} +
\mathit{Error
}$
726 \STATE $N
\leftarrow \mathit{ModifyWeights
}(N,
\Delta \vec w)$
727 \UNTIL{$
\mathit{TotalError
} < e$ or $
\mathit{It
} > M$
}
731 \subsection{Naive Bayes Classifier
}
733 Naive Bayes Classifier uses existing information to construct
734 probability model of likelihoods of given
{\em feature variables
}
735 based on a discrete-valued
{\em class variable
}.
736 Using the Bayes equation, we can then estimate the probability distribution
737 of class variable for particular values of the feature variables.
739 In order to approximate player's output vector $
\vec O$ based on
740 pattern vector $
\vec P$, we will compute each element of the
741 output vector separately, covering the output domain by several $k$-sized
742 discrete intervals (classes).
744 We will also in fact work on
745 PCA-represented input $
\vec R$ (using the
10 most significant
746 dimensions), since smaller input dimension is more computationally
747 feasible and $
\vec R$ also better fits the pre-requisites of the
748 classifier, the dimensions being more independent and
749 better approximating the normal distribution.
751 When training the classifier for $
\vec O$ element $o_i$
752 of class $c =
\lfloor o_i/k
\rfloor$,
753 we assume the $
\vec R$ elements are normally distributed and
754 feed the classifier information in the form
758 estimating the mean $
\mu_c$ and standard deviation $
\sigma_c$
759 of each $
\vec R$ element for each encountered $c$.
760 Then, we can query the built probability model on
762 $$
\max_c P(c
\mid \vec R) $$
764 obtaining the most probable class $i$ for an arbitrary $
\vec R$.
765 Each probability is obtained using the normal distribution formula:
766 $$ P(c
\mid x) =
{1\over \sqrt{2\pi\sigma_c^
2}}\exp{-(x-
\mu_c)^
2\over2\sigma_c^
2} $$
769 \caption{Training Naive Bayes
}
772 \REQUIRE{Train set $T = (
\mathit{R, c
})$
}
773 \FORALL{$(R, c)
\in T$
}
774 \STATE $
\mathit{RbyC
}_c
\leftarrow \
{\mathit{RbyC
}_c, R\
}$
777 \STATE $
\mu_c \leftarrow {1 \over |
\mathit{RbyC
}_c|
} \sum_{R
\in \mathit{RbyC
}_c
} R$
780 \STATE $
\sigma_c \leftarrow {1 \over |
\mathit{RbyC
}_c|
} \sum_{R
\in \mathit{RbyC
}_c
} R-
\mu_c $
785 \subsection{Implementation
}
787 We have implemented the data mining methods as the
788 ``gostyle'' open-source framework
\cite{GoStyle
},
789 made available under the GNU GPL licence.
791 The majority of our basic processing and the analysis parts
792 are implemented in the Python
\cite{Python25
} programming language.
793 We use several external libraries, most notably the MDP library
\cite{MDP
}.
794 The neural network part of the project is written using the libfann C library
\cite{Nissen2003
}.
796 The sociomap has been visualised using the Team Profile Analyzer
\cite{TPA
}
797 which is part of the Sociomap suite
\cite{SociomapSite
}.
800 \section{Strength Estimator
}
804 \includegraphics[width=
7in
]{strength-pca
}
805 \caption{PCA of by-strength vectors
}
806 \label{fig:strength_pca
}
809 First, we have used our framework to analyse correlations of pattern vectors
810 and playing strength. Like in other competitively played board games, Go players
811 receive real-world
{\em rating number
} based on tournament games,
812 and
{\em rank
} based on their rating.
%
813 \footnote{Elo-type rating system
\cite{GoR
} is usually used,
814 corresponding to even win chances for game of two players with the same rank,
815 and about
2:
3 win chance for stronger in case of one rank difference.
}%
816 \footnote{Professional ranks and dan ranks in some Asia countries may
817 be assigned differently.
}
818 The amateur ranks range from
30-kyu (beginner) to
1-kyu (intermediate)
819 and then follows
1-dan to
7-dan
\footnote{9-dan in some systems.
} (top-level player).
820 Multiple independent real-world ranking scales exist
821 (geographically based), also online servers maintain their own user ranking;
822 the difference between scales can be up to several ranks and the rank
823 distributions also differ.
\cite{RankComparison
}
825 As the source game collection, we use Go Teaching Ladder reviews archive
%
826 \footnote{The reviews contain comments and variations --- we consider only the main
827 variation with the actual played game.
}
828 \cite{GTL
} --- this collection contains
7700 games of players with strength ranging
829 from
30-kyu to
4-dan; we consider only even games with clear rank information,
830 and then randomly separate
770 games as a testing set.
831 Since the rank information is provided by the users and may not be consistent,
832 we are forced to take a simplified look at the ranks,
833 discarding the differences between various systems and thus somewhat
834 increasing error in our model.
\footnote{Since our results seem satisfying,
835 we did not pursue to try another collection;
836 one could e.g. look at game archives of some Go server.
}
838 First, we have created a single pattern vector for each rank, from
30-kyu to
4-dan;
839 we have performed PCA analysis on the pattern vectors, achieving near-perfect
840 rank correspondence in the first PCA dimension
%
841 \footnote{The eigenvalue of the second dimension was four times smaller,
842 with no discernable structure revealed within the lower-order eigenvectors.
}
843 (figure
\ref{fig:strength_pca
}).
845 We measure the accuracy of strength approximation by the first dimension
846 using Pearson's $r$ (see
\ref{pearson
}), yielding quite satisfying value of $r=
0.979$
847 implying extremely strong correlation.
848 Using the eigenvector position directly for classification
849 of players within the test group yields MSE TODO, thus providing
850 reasonably satisfying accuracy by itself.
%
851 \footnote{Extended vector normalization (sec.
\ref{xnorm
})
852 produced noticeably less clear-cut results.
}
854 To further enhance the strength estimator accuracy,
855 we have tried to train a NN classifier on our train set, consisting
856 of one $(
\vec p,
{\rm rank
})$ pair per player --- we use the pattern vector
857 for activation of input neurons and rank number as result of the output
858 neuron. We then proceeded to test the NN on per-player pattern vectors built
859 from the games in the test set, yielding MSE of TODO with TODO games per player
863 \section{Style Estimator
}
866 As a~second case study for our pattern analysis,
867 we investigate pattern vectors $
\vec p$ of various well-known players,
868 their relationships in-between and to prior knowledge
869 in order to explore the correlation of prior knowledge with extracted patterns.
870 We look for relationships between pattern vectors and perceived
871 ``playing style'' and attempt to use our classifiers to transform
872 pattern vector $
\vec p$ to style vector $
\vec s$.
874 The source game collection is GoGoD Winter
2008 \cite{GoGoD
} containing
55000
875 professional games, dating from the early Go history
1500 years ago to the present.
876 We consider only games of a small subset of players (table
\ref{fig:style_marks
});
877 we have chosen them for being well-known within the players community,
878 having large number of played games in our collection and not playing too long
879 ago.
\footnote{Over time, many commonly used sequences get altered, adopted and
880 dismissed; usual playing conditions can also differ significantly.
}
882 \subsection{Expert-based knowledge
}
883 \label{style-vectors
}
884 In order to provide a reference frame for our style analysis,
885 we have gathered some expert-based information about various
886 traditionally perceived style aspects to use as a prior knowledge.
887 This expert-based knowledge allows us to predict styles of unknown players
888 based on the similarity of their pattern vectors,
889 as well as discover correlations between styles and proportions
892 Experts were asked to mark four style aspects of each of the given players
893 on the scale from
1 to
10. The style aspects are defined as shown:
900 \begin{tabular
}{|c|c|c|
}
902 Style &
1 &
10\\
\hline
903 Territoriality $
\tau$ & Moyo & Territory \\
904 Orthodoxity $
\omega$ & Classic & Novel \\
905 Aggressivity $
\alpha$ & Calm & Figting \\
906 Thickness $
\theta$ & Safe & Shinogi \\
\hline
912 We have devised these four style aspects based on our own Go experience
913 and consultations with other experts.
914 The used terminology has quite
915 clear meaning to any experienced Go player and there is not too much
916 room for confusion, except possibly in the case of ``thickness'' ---
917 but the concept is not easy to pin-point succintly and we also did not
918 add extra comments on the style aspects to the questionnaire deliberately
919 to accurately reflect any diversity in understanding of the terms.
921 Averaging this expert based evaluation yields
\emph{reference style vector
}
922 $
\vec s_r$ (of dimension $
4$) for each player $r$
923 from the set of
\emph{reference players
} $R$.
925 Throughout our research, we have experimentally found that playing era
926 is also a major factor differentiating between patterns. Thus, we have
927 further extended the $
\vec s_r$ by median year over all games played
931 % increase table row spacing, adjust to taste
932 \renewcommand{\arraystretch}{1.3}
933 \caption{Covariance Measure of Prior Information Dimensions
}
934 \label{fig:style_marks_r
}
936 % Some packages, such as MDW tools, offer better commands for making tables
937 % than the plain LaTeX2e tabular which is used here.
938 \begin{tabular
}{|r||r||r||r||r||r|
}
940 & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & year \\
942 $
\tau$ &$
1.000$&$-
0.438$&$-
0.581$&$
0.721$&$
0.108$\\
943 $
\omega$& &$
1.000$&$
0.682$&$
0.014$&$-
0.021$\\
944 $
\alpha$& & &$
1.000$&$-
0.081$&$
0.030$\\
945 $
\theta$& &
\multicolumn{1}{c||
}{---
}
946 & &$
1.000$&$-
0.073$\\
947 y. & & & & &$
1.000$\\
952 Three high-level Go players (Alexander Dinerstein
3-pro, Motoki Noguchi
953 7-dan and V\'
{i
}t Brunner
4-dan) have judged style of the reference
955 The complete list of answers is in table
\ref{fig:style_marks
}.
956 Mean standard deviation of the answers is
0.952,
957 making the data reasonably reliable,
958 though much larger sample would of course be more desirable.
959 We have also found significant correlation between the various
960 style aspects, as shown by the Pearson's $r$ values
961 in table
\ref{fig:style_marks_r
}.
964 % increase table row spacing, adjust to taste
965 \renewcommand{\arraystretch}{1.4}
966 \begin{threeparttable
}
967 \caption{Expert-Based Style Aspects of Selected Professionals
\tnote{1} \tnote{2}}
968 \label{fig:style_marks
}
970 % Some packages, such as MDW tools, offer better commands for making tables
971 % than the plain LaTeX2e tabular which is used here.
972 \begin{tabular
}{|c||c||c||c||c|
}
974 {Player
} & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ \\
976 Go Seigen
\tnote{3} & $
6.0 \pm 2.0$ & $
9.0 \pm 1.0$ & $
8.0 \pm 1.0$ & $
5.0 \pm 1.0$ \\
977 Ishida Yoshio
\tnote{4}&$
8.0 \pm 1.4$ & $
5.0 \pm 1.4$ & $
3.3 \pm 1.2$ & $
5.3 \pm 0.5$ \\
978 Miyazawa Goro & $
1.5 \pm 0.5$ & $
10 \pm 0 $ & $
9.5 \pm 0.5$ & $
4.0 \pm 1.0$ \\
979 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$ \\
980 Sakata Eio & $
7.6 \pm 1.7$ & $
4.6 \pm 0.5$ & $
7.3 \pm 0.9$ & $
8.0 \pm 1.6$ \\
981 Fujisawa Hideyuki & $
3.5 \pm 0.5$ & $
9.0 \pm 1.0$ & $
7.0 \pm 0.0$ & $
4.0 \pm 0.0$ \\
982 Otake Hideo & $
4.3 \pm 0.5$ & $
3.0 \pm 0.0$ & $
4.6 \pm 1.2$ & $
3.6 \pm 0.9$ \\
983 Kato Masao & $
2.5 \pm 0.5$ & $
4.5 \pm 1.5$ & $
9.5 \pm 0.5$ & $
4.0 \pm 0.0$ \\
984 Takemiya Masaki
\tnote{4}&$
1.3\pm 0.5$& $
6.3 \pm 2.1$ & $
7.0 \pm 0.8$ & $
1.3 \pm 0.5$ \\
985 Kobayashi Koichi & $
9.0 \pm 1.0$ & $
2.5 \pm 0.5$ & $
2.5 \pm 0.5$ & $
5.5 \pm 0.5$ \\
986 Cho Chikun & $
9.0 \pm 0.8$ & $
7.6 \pm 0.9$ & $
6.6 \pm 1.2$ & $
9.0 \pm 0.8$ \\
987 Ma Xiaochun & $
8.0 \pm 2.2$ & $
6.3 \pm 0.5$ & $
5.6 \pm 1.9$ & $
8.0 \pm 0.8$ \\
988 Yoda Norimoto & $
6.3 \pm 1.7$ & $
4.3 \pm 2.1$ & $
4.3 \pm 2.1$ & $
3.3 \pm 1.2$ \\
989 Luo Xihe & $
7.3 \pm 0.9$ & $
7.3 \pm 2.5$ & $
7.6 \pm 0.9$ & $
6.0 \pm 1.4$ \\
990 O Meien & $
2.6 \pm 1.2$ & $
9.6 \pm 0.5$ & $
8.3 \pm 1.7$ & $
3.6 \pm 1.2$ \\
991 Rui Naiwei & $
4.6 \pm 1.2$ & $
5.6 \pm 0.5$ & $
9.0 \pm 0.8$ & $
3.3 \pm 1.2$ \\
992 Yuki Satoshi & $
3.0 \pm 1.0$ & $
8.5 \pm 0.5$ & $
9.0 \pm 1.0$ & $
4.5 \pm 0.5$ \\
993 Hane Naoki & $
7.5 \pm 0.5$ & $
2.5 \pm 0.5$ & $
4.0 \pm 0.0$ & $
4.5 \pm 1.5$ \\
994 Takao Shinji & $
5.0 \pm 1.0$ & $
3.5 \pm 0.5$ & $
5.5 \pm 1.5$ & $
4.5 \pm 0.5$ \\
995 Yi Se-tol & $
5.3 \pm 0.5$ & $
6.6 \pm 2.5$ & $
9.3 \pm 0.5$ & $
6.6 \pm 1.2$ \\
996 Yamashita Keigo
\tnote{4}&$
2.0\pm 0.0$& $
9.0 \pm 1.0$ & $
9.5 \pm 0.5$ & $
3.0 \pm 1.0$ \\
997 Cho U & $
7.3 \pm 2.4$ & $
6.0 \pm 0.8$ & $
5.3 \pm 1.7$ & $
6.3 \pm 1.7$ \\
998 Gu Li & $
5.6 \pm 0.9$ & $
7.0 \pm 0.8$ & $
9.0 \pm 0.8$ & $
4.0 \pm 0.8$ \\
999 Chen Yaoye & $
6.0 \pm 1.0$ & $
4.0 \pm 1.0$ & $
6.0 \pm 1.0$ & $
5.5 \pm 0.5$ \\
1003 \item [1] Including standard deviation. Only players where we received at least two out of three answers are included.
1004 \item [2] Since the playing era column does not fit into the table, we at least sort the players ascending by their median year.
1005 \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.
1006 \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.
1007 \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.
1009 \end{threeparttable
}
1012 \subsection{Style Components Analysis
}
1016 \includegraphics[width=
3.75in
]{style-pca
}
1017 \caption{PCA of per-player vectors
}
1018 \label{fig:style_pca
}
1021 We have looked at the ten most significant dimensions of the pattern data
1022 yielded by the PCA analysis of the reference player set
%
1023 \footnote{We also tried to observe PCA effect of removing outlying Takemiya
1024 Masaki. That way, the second dimension strongly
1025 correlated to territoriality and third dimension strongly correlacted to era,
1026 however the first dimension remained mysteriously uncorrelated and with no
1027 obvious interpretation.
}
1028 (fig.
\ref{fig:style_pca
} shows the first three).
1029 We have again computed the Pearson's $r$ for all combinations of PCA dimensions
1030 and dimensions of the prior knowledge style vectors to find correlations.
1033 % increase table row spacing, adjust to taste
1034 \renewcommand{\arraystretch}{1.4}
1035 \caption{Covariance Measure of PCA and Prior Information
}
1038 % Some packages, such as MDW tools, offer better commands for making tables
1039 % than the plain LaTeX2e tabular which is used here.
1040 \begin{tabular
}{|c||r||r||r||r||r|
}
1042 Eigenval. & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & Year \\
1044 $
0.4473697$ & $
\mathbf{-
0.530}$ & $
0.323$ & $
0.298$ & $
\mathbf{-
0.554}$ & $
0.090$ \\
1045 $
0.1941057$ & $
\mathbf{-
0.547}$ & $
0.215$ & $
0.249$ & $-
0.293$ & $
\mathbf{-
0.630}$ \\
1046 $
0.0463189$ & $
0.131$ & $-
0.002$ & $-
0.128$ & $
0.242$ & $
\mathbf{-
0.630}$ \\
1047 $
0.0280301$ & $-
0.011$ & $
0.225$ & $
0.186$ & $
0.131$ & $
0.067$ \\
1048 $
0.0243231$ & $-
0.181$ & $
0.174$ & $-
0.032$ & $-
0.216$ & $
0.352$ \\
1049 $
0.0180875$ & $-
0.364$ & $
0.226$ & $
0.339$ & $-
0.136$ & $
0.113$ \\
1050 $
0.0138478$ & $-
0.194$ & $-
0.048$ & $-
0.099$ & $-
0.333$ & $
0.055$ \\
1051 $
0.0110575$ & $-
0.040$ & $-
0.254$ & $-
0.154$ & $-
0.054$ & $-
0.089$ \\
1052 $
0.0093587$ & $-
0.199$ & $-
0.115$ & $
0.358$ & $-
0.234$ & $-
0.028$ \\
1053 $
0.0084930$ & $
0.046$ & $
0.190$ & $
0.305$ & $
0.176$ & $
0.089$ \\
1059 % increase table row spacing, adjust to taste
1060 \renewcommand{\arraystretch}{1.6}
1061 \begin{threeparttable
}
1062 \caption{Characteristic Patterns of PCA$_
{1,
2}$ Dimensions
\tnote{1}}
1063 \label{fig:style_patterns
}
1065 % Some packages, such as MDW tools, offer better commands for making tables
1066 % than the plain LaTeX2e tabular which is used here.
1067 \begin{tabular
}{|p
{2.3cm
}p
{2.4cm
}p
{2.4cm
}p
{0cm
}|
}
1068 % The virtual last column is here because otherwise we get random syntax errors.
1070 \hline \multicolumn{4}{|c|
}{PCA$_1$ --- Moyo-oriented, thin-playing player
} \\
1071 \centering \begin{psgopartialboard*
}{(
8,
1)(
12,
6)
}
1072 \stone[\marktr]{black
}{k
}{4}
1073 \end{psgopartialboard*
} &
1074 \centering \begin{psgopartialboard*
}{(
1,
2)(
5,
6)
}
1076 \stone[\marktr]{black
}{d
}{5}
1077 \end{psgopartialboard*
} &
1078 \centering \begin{psgopartialboard*
}{(
5,
1)(
10,
6)
}
1080 \stone[\marktr]{black
}{j
}{4}
1081 \end{psgopartialboard*
} & \\
1082 \centering $
0.274$ &
\centering $
0.086$ &
\centering $
0.083$ & \\
1083 \centering high corner/side opening
\tnote{2} &
\centering high corner approach &
\centering high distant pincer & \\
1085 \hline \multicolumn{4}{|c|
}{PCA$_1$ --- Territorial, thick-playing player
} \\
1086 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1088 \stone[\marktr]{black
}{f
}{3}
1089 \end{psgopartialboard*
} &
1090 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1093 \stone[\marktr]{black
}{f
}{3}
1094 \end{psgopartialboard*
} &
1095 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1097 \stone[\marktr]{black
}{f
}{3}
1098 \end{psgopartialboard*
} & \\
1099 \centering $-
0.399$ &
\centering $-
0.399$ &
\centering $-
0.177$ & \\
1100 \centering low corner approach &
\centering low corner reply &
\centering low corner enclosure & \\
1102 \hline \multicolumn{4}{|c|
}{PCA$_2$ --- Territorial, current player
\tnote{3}} \\
1103 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1106 \stone[\marktr]{black
}{f
}{3}
1107 \end{psgopartialboard*
} &
1108 \centering \begin{psgopartialboard*
}{(
3,
1)(
8,
6)
}
1110 \stone[\marktr]{black
}{g
}{4}
1111 \end{psgopartialboard*
} &
1112 \centering \begin{psgopartialboard*
}{(
4,
1)(
9,
6)
}
1115 \stone[\marktr]{black
}{h
}{3}
1116 \end{psgopartialboard*
} & \\
1117 \centering $-
0.193$ &
\centering $-
0.139$ &
\centering $-
0.135$ & \\
1118 \centering low corner reply
\tnote{4} &
\centering high distant approach/pincer &
\centering near low pincer & \\
1123 \item [1] We present the patterns in a simplified compact form;
1124 in reality, they are usually somewhat larger and always circle-shaped
1125 (centered on the triangled move).
1126 We omit only pattern segments that are entirely empty.
1127 \item [2] We give some textual interpretation of the patterns, especially
1128 since some of them may not be obvious unless seen in game context; we choose
1129 the descriptions based on the most frequently observer contexts, but of course
1130 the pattern can be also matched in other positions and situations.
1131 \item [3] In the second PCA dimension, we find no correlated patterns;
1132 only uncorrelated and anti-correlated ones.
1133 \item [4] As the second most significant pattern,
1134 we skip a slide follow-up pattern to this move.
1136 \end{threeparttable
}
1140 % increase table row spacing, adjust to taste
1141 \renewcommand{\arraystretch}{1.8}
1142 \begin{threeparttable
}
1143 \caption{Characteristic Patterns of PCA$_3$ Dimension
\tnote{1}}
1144 \label{fig:style_patterns3
}
1146 % Some packages, such as MDW tools, offer better commands for making tables
1147 % than the plain LaTeX2e tabular which is used here.
1148 \begin{tabular
}{|p
{2.4cm
}p
{2.4cm
}p
{2.4cm
}p
{0cm
}|
}
1149 % The virtual last column is here because otherwise we get random syntax errors.
1151 \hline \multicolumn{4}{|c|
}{PCA$_3$ --- Old-time player
} \\
1152 \centering \begin{psgopartialboard*
}{(
1,
3)(
5,
7)
}
1154 \stone[\marktr]{black
}{c
}{6}
1155 \end{psgopartialboard*
} &
1156 \centering \begin{psgopartialboard*
}{(
8,
1)(
12,
5)
}
1157 \stone[\marktr]{black
}{k
}{3}
1158 \end{psgopartialboard*
} &
1159 \centering \begin{psgopartialboard*
}{(
1,
1)(
5,
5)
}
1160 \stone[\marktr]{black
}{c
}{3}
1161 \end{psgopartialboard*
} & \\
1162 \centering $
0.515$ &
\centering $
0.264$ &
\centering $
0.258$ & \\
1163 \centering low corner approach &
\centering low side or mokuhazushi opening &
\centering san-san opening & \\
1165 \hline \multicolumn{4}{|c|
}{PCA$_3$ --- Current player
} \\
1166 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
5)
}
1168 \stone[\marktr]{black
}{f
}{3}
1169 \end{psgopartialboard*
} &
1170 \centering \begin{psgopartialboard*
}{(
1,
1)(
5,
5)
}
1171 \stone[\marktr]{black
}{c
}{4}
1172 \end{psgopartialboard*
} &
1173 \centering \begin{psgopartialboard*
}{(
1,
2)(
5,
6)
}
1176 \stone[\marktr]{black
}{c
}{5}
1177 \end{psgopartialboard*
} & \\
1178 \centering $-
0.276$ &
\centering $-
0.273$ &
\centering $-
0.116$ & \\
1179 \centering low corner enclosure &
\centering 3-
4 corner opening
\tnote{2} &
\centering high approach reply & \\
1184 \item [1] We cannot use terms ``classic'' and ''modern'' in case of PCA$_3$
1185 since the current patterns are commonplace in games of past centuries
1186 (not included in our training set) and many would call a lot of the old-time patterns
1187 modern inventions. Perhaps we can infer that the latest
21th-century play trends abandon
1188 many of the
20th-century experiments (lower echelon of our by-year samples)
1189 to return to the more ordinary but effective classic patterns.
1190 \item [2] At this point, we skip two patterns already shown elsewhere:
1191 {\em high side/corner opening
} and
{\em low corner reply
}.
1193 \end{threeparttable
}
1197 obvious both from the measured $r$ and visual observation
1198 that by far the most significant vector corresponds very well
1199 to the territoriality of the players,
%
1200 \footnote{Cho Chikun, perhaps the best-known
1201 territorial player, is not well visible in the cluster, but he is
1202 positioned around $-
0.8$ on the first dimension.
}
1203 confirming the intuitive notion that this aspect of style
1204 is the one easiest to pin-point and also
1205 most obvious in the played shapes and sequences
1206 (that can obviously aim directly at taking secure territory
1207 or building center-oriented framework). Thick (solid) play also plays
1208 a role, but these two style dimensions are already
1209 correlated in the prior data.
1211 The other PCA dimensions are somewhat harder to interpret, but there
1212 certainly is significant influence of the styles on the patterns;
1213 the found correlations are all presented in table
\ref{fig:style_r
}.
1214 (Larger absolute value means better linear correspondence.)
1216 We also list the characteristic spatial patterns of the PCA dimension
1217 extremes (tables
\ref{fig:style_patterns
},
\ref{fig:style_patterns3
}), determined by their coefficients
1218 in the PCA projection matrix --- however, such naive approach
1219 has limited reliability, better methods will have to be researched.
%
1220 \footnote{For example, as one of highly ranked ``Takemiya's'' PCA1 patterns,
1221 3,
3 corner opening was generated, completely inappropriately;
1222 it reflects some weak ordering in bottom half of the dimension,
1223 not global ordering within the dimension.
}
1224 We do not show the other pattern features since they carry no useful
1225 information in the opening stage.
%
1226 \footnote{The board distance feature can be useful in some cases,
1227 but here all the spatial patterns are big enough to reach to the edge
1231 % increase table row spacing, adjust to taste
1232 \renewcommand{\arraystretch}{1.4}
1233 \caption{Covariance Measure of Externed-Normalization PCA and~Prior Information
}
1234 \label{fig:style_normr
}
1236 % Some packages, such as MDW tools, offer better commands for making tables
1237 % than the plain LaTeX2e tabular which is used here.
1238 \begin{tabular
}{|c||r||r||r||r||r|
}
1240 Eigenval. & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & Year \\
1242 $
6.3774289$ & $
\mathbf{0.436}$ & $-
0.220$ & $-
0.289$ & $
\mathbf{0.404}$ & $
\mathbf{-
0.576}$ \\
1243 $
1.7269775$ & $
\mathbf{-
0.690}$ & $
0.340$ & $
0.315$ & $
\mathbf{-
0.445}$ & $
\mathbf{-
0.639}$ \\
1244 $
1.1747101$ & $-
0.185$ & $
0.156$ & $
0.107$ & $-
0.315$ & $
0.320$ \\
1245 $
0.8452797$ & $
0.064$ & $-
0.102$ & $-
0.189$ & $
0.032$ & $
0.182$ \\
1246 $
0.8038992$ & $-
0.185$ & $
0.261$ & $
\mathbf{0.620}$ & $
0.120$ & $
0.056$ \\
1247 $
0.6679533$ & $-
0.027$ & $
0.055$ & $
0.147$ & $-
0.198$ & $
0.155$ \\
1248 $
0.5790000$ & $
0.079$ & $
\mathbf{0.509}$ & $
0.167$ & $
0.294$ & $-
0.019$ \\
1249 $
0.4971474$ & $
0.026$ & $-
0.119$ & $-
0.071$ & $
0.049$ & $
0.043$ \\
1250 $
0.4938777$ & $-
0.061$ & $
0.061$ & $
0.104$ & $-
0.168$ & $
0.015$ \\
1251 $
0.4888848$ & $
0.203$ & $-
0.283$ & $-
0.120$ & $
0.083$ & $-
0.220$ \\
1256 The PCA results presented above do not show much correlation between
1257 the significant PCA dimensions and the $
\omega$ and $
\alpha$ style dimensions.
1258 However, when we applied the extended vector normalization
1259 (sec.
\ref{xnorm
}; see table
\ref{fig:style_normr
}),
1260 some less significant PCA dimensions exhibited clear correlations.
%
1261 \footnote{We have found that $c=
6$ in the post-processing logistic function
1262 produces the most instructive PCA output on our particular game collection.
}
1263 It appears that less-frequent patterns that appear only in the middle-game
1264 phase
\footnote{In the middle game, the board is much more filled and thus
1265 particular specific-shape patterns repeat less often.
} are defining
1266 for these dimensions, and these are not represented in the pattern vectors
1267 as well as the common opening patterns.
1268 However, we do not use the extended normalization results since
1269 they produced noticeably less accurate classifiers in all dimensions,
1270 including $
\omega$ and $
\alpha$.
1272 We believe that the next step in interpreting our analytical results
1273 will be more refined prior information input
1274 and precise analysis of the outputs by Go experts.
1278 \includegraphics[width=
3.5in,angle=-
90]{sociomap
}
1279 \caption{Sociomap visualisation. The spatial positioning of players
1280 is based on the expert knowledge, while the node heights (depicted by
1281 contour lines) represent the pattern vectors.
%
1282 %The light lines denote coherence-based hierarchical clusters.
1284 \label{fig:sociomap
}
1287 Fig.
\ref{fig:sociomap
} shows the Sociomap visualisation
1288 as an alternate view of the player relationships and similarity,
1289 as well as correlation between the expert-given style marks
1290 and the PCA decomposition. The four-dimensional style vectors
1291 are used as input for the Sociomap renderer and determine the
1292 spatial positions of players. The height of a node is then
1293 determined using first two PCA dimensions $R_1,R_2$ and their
1294 eigenvalues $
\lambda_1,
\lambda_2$ as their linear combination:
1295 $$ h=
\lambda_1R_1 +
\lambda_2R_2 $$
1297 We can observe that the terrain of the sociomap is reasonably
1298 ``smooth'', again demonstrating some level of connection between
1299 the style vectors and data-mined information. High countour density
1300 indicates some discrepancy; in case of Takemiya Masaki and Yi Ch'ang-ho,
1301 this seems to be merely an issue of scale,
1302 while the Rui Naiwei --- Gu Li cliff suggests a genuine problem;
1303 we cannot say now whether it is because of imprecise prior information
1304 or bad approximation abilities of our model.
1306 \subsection{Style Classification
}
1308 %TODO vsude zcheckovat jestli pouzivame stejny cas "we perform, we apply" X "we have performed, ..."
1310 Apart from the PCA-based analysis, we tested the style inference ability
1311 of neural network (sec.
\ref{neural-net
}) and $k$-NN classifiers (sec.
\ref{knn
}).
1313 \subsubsection{Reference (Training) Data
}
1314 As the~reference data, we use expert-based knowledge presented in section
\ref{style-vectors
}.
1315 For each reference player, that gives $
4$-dimensional
\emph{style vector
} (each component in the
1316 range of $
[1,
10]$).
\footnote{Since the neural network has activation function with range $
[-
1,
1]$, we
1317 have linearly rescaled the
\emph{style vectors
} from interval $
[1,
10]$ to $
[-
1,
1]$ before using the training
1318 data. The network's output was afterwards rescaled back to allow for MSE comparison.
}
1320 All input vectors were preprocessed using PCA, reducing the input dimension from $
400$ to $
23$.
1322 \subsubsection{Cross-validation
}
1323 To compare and evaluate both methods, we have performed $
5$-fold cross validation
1324 and compared their performance with a~random classifier.
1325 In the $
5$-fold cross-validation, we randomly divide the training set
1326 (organized by players) into $
5$ distinct parts with comparable
1327 sizes and then iteratively use each part as a~testing set (yielding square error value), while
1328 the rest (remaining $
4$ parts) is taken as a~training set. The square errors across all $
5$ iterations are
1329 averaged, in turn yielding mean square error.
1331 \subsubsection{Results
}
1332 The results are shown in the table
\ref{crossval-cmp
}. Second to fifth columns in the table represent
1333 mean square error of the examined styles, $
\mathit{Mean
}$ is the
1334 mean square error across the styles and finally, the last column $
\mathit{Cmp
}$
1335 represents $
\mathit{Mean
}(
\mathit{Random classifier
}) /
\mathit{Mean
}(
\mathit{X
})$ -- comparison of mean square error
1336 of method $
\mathit{X
}$ with the random classifier. To minimize the
1337 effect of random variables, all numbers were taken as an average of $
200$ runs of the cross validation.
1339 Analysis of the performance of $k$-NN classifier for different $k$-values showed that different
1340 $k$-values are suitable to approximate different styles. Combining the $k$-NN classifiers with the
1341 neural network (so that each style is approximated by the method with lowest MSE in that style)
1342 results in
\emph{Joint classifier
}, which outperforms all other methods. (Table
\ref{crossval-cmp
})
1343 The
\emph{Joint classifier
} has outstanding MSE $
3.979$, which is equivalent to standard deviation
1344 of $
\sigma =
1.99$ per style.
1347 \renewcommand{\arraystretch}{1.4}
1349 \caption{Comparison of style classifiers
}
1350 \label{crossval-cmp
}
1351 \begin{tabular
}{|c|c|c|c|c|c|c|
}
1353 %Classifier & $\sigma_\tau$ & $\sigma_\omega$ & $\sigma_\alpha$ & $\sigma_\theta$ & Tot $\sigma$ & $\mathit{RndC}$\\ \hline
1354 %Neural network & 0.420 & 0.488 & 0.365 & 0.371 & 0.414 & 1.82 \\
1355 %$k$-NN ($k=4$) & 0.394 & 0.507 & 0.457 & 0.341 & 0.429 & 1.76 \\
1356 %Random classifier & 0.790 & 0.773 & 0.776 & 0.677 & 0.755 & 1.00 \\ \hline
1357 &
\multicolumn{5}{|c|
}{MSE
}& \\
\hline
1358 {Classifier
} & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ &
{\bf Mean
} &
{\bf Cmp
}\\
\hline
1359 Joint classifier &
{\bf 4.01} &
{\bf 5.73} &
{\bf 3.37} &
{\bf 2.80} &
{\bf 3.979}&
{\bf 2.96} \\
\hline
1360 Neural network &
4.32 &
6.06 &
{\bf 3.37} &
3.60 &
4.337 &
2.72 \\
1361 $k$-NN ($k=
3$) &
4.20 &
{\bf 5.73} &
4.92 &
2.90 &
4.439 &
2.65 \\
1362 $k$-NN ($k=
2$) &
4.21 &
6.18 &
4.83 &
{\bf 2.80} &
4.503 &
2.62 \\
1363 $k$-NN ($k=
4$) &
{\bf 4.01} &
6.25 &
5.06 &
3.05 &
4.590 &
2.57 \\
1364 Naive Bayes &
4.48 &
6.90 &
5.48 &
3.70 &
5.143 &
2.29 \\
1365 Random class. &
12.26 &
12.33 &
12.40 &
10.11 &
11.776 &
1.00 \\
\hline
1366 %Joint classifier & {\bf 4.008} & {\bf 5.732} & 3.379 & {\bf 2.796} & {\bf 3.979} & {\bf 2.96} \\ \hline
1367 %Neural network & 4.319 & 6.060 & {\bf 3.368} & 3.602 & 4.337 & 2.72 \\
1368 %$k$-NN ($k=3$) & 4.201 & {\bf 5.732} & 4.916 & 2.905 & 4.439 & 2.65 \\
1369 %$k$-NN ($k=2$) & 4.209 & 6.175 & 4.833 & {\bf 2.796} & 4.503 & 2.62 \\
1370 %$k$-NN ($k=4$) & {\bf 4.008} & 6.252 & 5.056 & 3.045 & 4.590 & 2.57 \\
1371 %Random class. & 12.263 & 12.332 & 12.400 & 10.110 & 11.776 & 1.0 \\ \hline
1376 % TODO presunout konkretni parametry do Appendixu? (neni jich tolik, mozna ne)
1377 \subsubsection{$k$-NN parameters
}
1378 All three variants of $k$-NN classifier ($k=
2,
3,
4$) we have used and compared had the following weight function
1380 \mathit{Weight
}(
\vec x) =
0.8^
{10*
\mathit{Distance
}(
\vec x)
}
1382 The parameters were chosen empirically to minimize the MSE.
1384 \subsubsection{Neural network's parameters
}
1385 The neural network classifier had $
3$-layered architecture (one hidden layer) with following numbers of
1392 \begin{tabular
}{|c|c|c|
}
1394 \multicolumn{3}{|c|
}{Layer
} \\
\hline
1395 Input & Hidden & Output \\
\hline
1396 23 &
30 &
4 \\
\hline
1402 The network was trained until the square error on the training set was smaller than $
0.0003$.
1403 Due to a small number of input vectors, this only took $
20$ iterations of RPROP learning algorithm on average.
1405 \subsubsection{Naive Bayes parameters
}
1407 We have chosen $k =
10/
7$ as our discretization parameter;
1408 ideally, we would use $k =
1$ to fully cover the style marks
1409 domain, however our training sample is probably too small for
1412 \section{Proposed Applications
}
1414 We believe that our findings might be useful for many applications
1415 in the area of Go support software as well as Go-playing computer engines.
1417 The style analysis can be an excellent teaching aid --- classifying style
1418 dimensions based on player's pattern vector, many study recommendations
1419 can be given, e.g. about the professional games to replay, the goal being
1420 balancing understanding of various styles to achieve well-rounded skill set.
1421 This was also our original aim when starting the research and a user-friendly
1422 tool based on our work is now being created.
1424 We hope that more strong players will look into the style dimensions found
1425 by our statistical analysis --- analysis of most played patterns of prospective
1426 opponents might prepare for the game, but we especially hope that new insights
1427 on strategic purposes of various shapes and general human understanding
1428 of the game might be achieved by investigating the style-specific patterns.
1429 Time by time, new historical game records are still being discovered;
1430 pattern-based classification might help to suggest origin of the games
1433 Classifying playing strength of a pattern vector of a player can be used
1434 e.g. to help determine initial real-world rating of a player before their
1435 first tournament based on games played on the internet; some players especially
1436 in less populated areas could get fairly strong before playing their first
1439 Analysis of pattern vectors extracted from games of Go-playing programs
1440 in light of the shown strength and style distributions might help to
1441 highlight some weaknesses and room for improvements. (However, since
1442 correlation does not imply causation, simply optimizing Go-playing programs
1443 according to these vectors is unlikely to yield good results.)
1444 Another interesting applications in Go-playing programs might be strength
1445 adjustment; the program can classify the player's level based on the pattern
1446 vector from its previous games and auto-adjust its difficulty settings
1447 accordingly to provide more even games for beginners.
1450 % An example of a floating figure using the graphicx package.
1451 % Note that \label must occur AFTER (or within) \caption.
1452 % For figures, \caption should occur after the \includegraphics.
1453 % Note that IEEEtran v1.7 and later has special internal code that
1454 % is designed to preserve the operation of \label within \caption
1455 % even when the captionsoff option is in effect. However, because
1456 % of issues like this, it may be the safest practice to put all your
1457 % \label just after \caption rather than within \caption{}.
1459 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
1460 % option should be used if it is desired that the figures are to be
1461 % displayed while in draft mode.
1465 %\includegraphics[width=2.5in]{myfigure}
1466 % where an .eps filename suffix will be assumed under latex,
1467 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
1468 % via \DeclareGraphicsExtensions.
1469 %\caption{Simulation Results}
1473 % Note that IEEE typically puts floats only at the top, even when this
1474 % results in a large percentage of a column being occupied by floats.
1477 % An example of a double column floating figure using two subfigures.
1478 % (The subfig.sty package must be loaded for this to work.)
1479 % The subfigure \label commands are set within each subfloat command, the
1480 % \label for the overall figure must come after \caption.
1481 % \hfil must be used as a separator to get equal spacing.
1482 % The subfigure.sty package works much the same way, except \subfigure is
1483 % used instead of \subfloat.
1485 %\begin{figure*}[!t]
1486 %\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
1487 %\label{fig_first_case}}
1489 %\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
1490 %\label{fig_second_case}}}
1491 %\caption{Simulation results}
1495 % Note that often IEEE papers with subfigures do not employ subfigure
1496 % captions (using the optional argument to \subfloat), but instead will
1497 % reference/describe all of them (a), (b), etc., within the main caption.
1500 % An example of a floating table. Note that, for IEEE style tables, the
1501 % \caption command should come BEFORE the table. Table text will default to
1502 % \footnotesize as IEEE normally uses this smaller font for tables.
1503 % The \label must come after \caption as always.
1506 %% increase table row spacing, adjust to taste
1507 %\renewcommand{\arraystretch}{1.3}
1508 % if using array.sty, it might be a good idea to tweak the value of
1509 % \extrarowheight as needed to properly center the text within the cells
1510 %\caption{An Example of a Table}
1511 %\label{table_example}
1513 %% Some packages, such as MDW tools, offer better commands for making tables
1514 %% than the plain LaTeX2e tabular which is used here.
1515 %\begin{tabular}{|c||c|}
1525 % Note that IEEE does not put floats in the very first column - or typically
1526 % anywhere on the first page for that matter. Also, in-text middle ("here")
1527 % positioning is not used. Most IEEE journals use top floats exclusively.
1528 % Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
1529 % floats. This can be corrected via the \fnbelowfloat command of the
1534 \section{Future Research
}
1536 Since we are not aware of any previous research on this topic and we
1537 are limited by space and time constraints, plenty of research remains
1538 to be done, in all parts of our analysis --- we have already noted
1539 many in the text above. Most significantly, different methods of generating
1540 and normalizing the $
\vec p$ vectors can be explored
1541 and other data mining methods could be investigated.
1542 Better ways of visualising the relationships would be desirable,
1543 together with thorough dissemination of internal structure
1544 of the player pattern vectors space.
1546 It can be argued that many players adjust their style by game conditions
1547 (Go development era, handicap, komi and
color, time limits, opponent)
1548 or styles might express differently in various game stages.
1549 More professional players could be consulted on the findings
1550 and for style scales calibration.
1551 Impact of handicap games on by-strength
1552 $
\vec p$ distribution should be also investigated.
1554 % TODO: Future research --- Sparse PCA
1556 \section{Conclusion
}
1557 We have proposed a way to extract summary pattern information from
1558 game collections and combined this with various data mining methods
1559 to show correspondence of our pattern summaries with various player
1560 meta-information like playing strength, era of play or playing style
1561 as ranked by expert players. We have implemented and measured our
1562 proposals in two case studies: per-rank characteristics of amateur
1563 players and per-player style/era characteristics of well-known
1566 While many details remain to be worked out,
1567 we have demonstrated that many significant correlations do exist and
1568 it is practically viable to infer the player meta-information from
1569 extracted pattern summaries. We proposed wide range of applications
1570 for such inference. Finally, we outlined some of the many possible
1571 directions of future work in this newly staked research field
1572 on the boundary of Computer Go, Data Mining and Go Theory.
1575 % if have a single appendix:
1576 %\appendix[Proof of the Zonklar Equations]
1578 %\appendix % for no appendix heading
1579 % do not use \section anymore after \appendix, only \section*
1580 % is possibly needed
1582 % use appendices with more than one appendix
1583 % then use \section to start each appendix
1584 % you must declare a \section before using any
1585 % \subsection or using \label (\appendices by itself
1586 % starts a section numbered zero.)
1591 %\section{Proof of the First Zonklar Equation}
1592 %Appendix one text goes here.
1594 %% you can choose not to have a title for an appendix
1595 %% if you want by leaving the argument blank
1597 %Appendix two text goes here.
1600 % use section* for acknowledgement
1601 \section*
{Acknowledgment
}
1602 \label{acknowledgement
}
1604 Foremostly, we are very grateful for detailed input on specific go styles
1605 by Alexander Dinerstein, Motoki Noguchi and V\'
{i
}t Brunner.
1606 We appreciate X reviewing our paper, and helpful comments on our general methodology
1607 by John Fairbairn, T. M. Hall, Cyril H\"oschl, Robert Jasiek, Franti
\v{s
}ek Mr\'
{a
}z
1608 and several GoDiscussions.com users.
\cite{GoDiscThread
}
1609 Finally, we would like to thank Radka ``chidori'' Hane
\v{c
}kov\'
{a
}
1610 for the original research idea and acknowledge major inspiration
1611 by R\'
{e
}mi Coulom's paper
\cite{PatElo
} on the extraction of pattern information.
1614 % Can use something like this to put references on a page
1615 % by themselves when using endfloat and the captionsoff option.
1616 \ifCLASSOPTIONcaptionsoff
1622 % trigger a \newpage just before the given reference
1623 % number - used to balance the columns on the last page
1624 % adjust value as needed - may need to be readjusted if
1625 % the document is modified later
1626 %\IEEEtriggeratref{8}
1627 % The "triggered" command can be changed if desired:
1628 %\IEEEtriggercmd{\enlargethispage{-5in}}
1630 % references section
1632 % can use a bibliography generated by BibTeX as a .bbl file
1633 % BibTeX documentation can be easily obtained at:
1634 % http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
1635 % The IEEEtran BibTeX style support page is at:
1636 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1637 \bibliographystyle{IEEEtran
}
1638 % argument is your BibTeX string definitions and bibliography database(s)
1639 \bibliography{gostyle
}
1641 % <OR> manually copy in the resultant .bbl file
1642 % set second argument of \begin to the number of references
1643 % (used to reserve space for the reference number labels box)
1644 %\begin{thebibliography}{1}
1646 %\bibitem{MasterMCTS}
1648 %\end{thebibliography}
1652 % If you have an EPS/PDF photo (graphicx package needed) extra braces are
1653 % needed around the contents of the optional argument to biography to prevent
1654 % the LaTeX parser from getting confused when it sees the complicated
1655 % \includegraphics command within an optional argument. (You could create
1656 % your own custom macro containing the \includegraphics command to make things
1658 %\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
1659 % or if you just want to reserve a space for a photo:
1661 %\begin{IEEEbiography}{Petr Baudi\v{s}}
1662 %Biography text here.
1663 %\end{IEEEbiography}
1665 % if you will not have a photo at all:
1666 \begin{IEEEbiographynophoto
}{Petr Baudi
\v{s
}}
1667 Received BSc degree in Informatics at Charles University, Prague in
2009,
1668 currently a graduate student.
1669 Doing research in the fields of Computer Go, Monte Carlo Methods
1670 and Version Control Systems.
1671 Plays Go with the rank of
2-kyu on European tournaments
1672 and
2-dan on the KGS Go Server.
1673 \end{IEEEbiographynophoto
}
1675 \begin{IEEEbiographynophoto
}{Josef Moud
\v{r
}\'
{i
}k
}
1676 Received BSc degree in Informatics at Charles University, Prague in
2009,
1677 currently a graduate student.
1678 Doing research in the fields of Neural Networks and Cognitive Sciences.
1679 His Go skills are not worth mentioning.
1680 \end{IEEEbiographynophoto
}
1682 % insert where needed to balance the two columns on the last page with
1686 %\begin{IEEEbiographynophoto}{Jane Doe}
1687 %Biography text here.
1688 %\end{IEEEbiographynophoto}
1690 % You can push biographies down or up by placing
1691 % a \vfill before or after them. The appropriate
1692 % use of \vfill depends on what kind of text is
1693 % on the last page and whether or not the columns
1694 % are being equalized.
1698 % Can be used to pull up biographies so that the bottom of the last one
1699 % is flush with the other column.
1700 %\enlargethispage{-5in}