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
}
51 %\newcommand{\rv}[1]{\ul{#1}}
53 \newcommand{\rv}[1]{#1}
57 %\newcommand{\rvv}[1]{\ul{#1}}
59 \newcommand{\rvv}[1]{#1}
63 \newcommand{\rvvv}[1]{\ul{#1}}
65 %\newcommand{\rvvv}[1]{#1}
67 \usepackage{algorithm
}
68 \usepackage{algorithmic
}
69 %\usepackage{algpseudocode}
70 % WICKED: nefunguje ani jedno???
71 % algorithmic.sty can be obtained at:
72 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
73 % There is also a support site at:
74 % http://algorithms.berlios.de/index.html
75 % Also of interest may be the (relatively newer and more customizable)
76 % algorithmicx.sty package by Szasz Janos:
77 % http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/
79 % *** ALIGNMENT PACKAGES ***
82 % http://www.ctan.org/tex-archive/macros/latex/required/tools/
87 % http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/
90 % IEEEtran contains the IEEEeqnarray family of commands that can be used to
91 % generate multiline equations as well as matrices, tables, etc., of high
94 %\usepackage{eqparbox}
95 % Also of notable interest is Scott Pakin's eqparbox package for creating
96 % (automatically sized) equal width boxes - aka "natural width parboxes".
98 % http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/
102 % *** SUBFIGURE PACKAGES ***
103 %\usepackage[tight,footnotesize]{subfigure}
104 % subfigure.sty was written by Steven Douglas Cochran. This package makes it
105 % easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
106 % work, it is a good idea to load it with the tight package option to reduce
107 % the amount of white space around the subfigures. subfigure.sty is already
108 % installed on most LaTeX systems. The latest version and documentation can
110 % http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
111 % subfigure.sty has been superceeded by subfig.sty.
115 %\usepackage[caption=false]{caption}
116 %\usepackage[font=footnotesize]{subfig}
117 % subfig.sty, also written by Steven Douglas Cochran, is the modern
118 % replacement for subfigure.sty. However, subfig.sty requires and
119 % automatically loads Axel Sommerfeldt's caption.sty which will override
120 % IEEEtran.cls handling of captions and this will result in nonIEEE style
121 % figure/table captions. To prevent this problem, be sure and preload
122 % caption.sty with its "caption=false" package option. This is will preserve
123 % IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
124 % (recommended due to many improvements over 1.2) of subfig.sty supports
125 % the caption=false option directly:
126 %\usepackage[caption=false,font=footnotesize]{subfig}
128 % The latest version and documentation can be obtained at:
129 % http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
130 % The latest version and documentation of caption.sty can be obtained at:
131 % http://www.ctan.org/tex-archive/macros/latex/contrib/caption/
135 % *** FLOAT PACKAGES ***
137 %\usepackage{fixltx2e}
138 % fixltx2e, the successor to the earlier fix2col.sty, was written by
139 % Frank Mittelbach and David Carlisle. This package corrects a few problems
140 % in the LaTeX2e kernel, the most notable of which is that in current
141 % LaTeX2e releases, the ordering of single and double column floats is not
142 % guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
143 % single column figure to be placed prior to an earlier double column
144 % figure. The latest version and documentation can be found at:
145 % http://www.ctan.org/tex-archive/macros/latex/base/
149 %\usepackage{stfloats}
150 % stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
151 % the ability to do double column floats at the bottom of the page as well
152 % as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
153 % LaTeX2e). It also provides a command:
155 % to enable the placement of footnotes below bottom floats (the standard
156 % LaTeX2e kernel puts them above bottom floats). This is an invasive package
157 % which rewrites many portions of the LaTeX2e float routines. It may not work
158 % with other packages that modify the LaTeX2e float routines. The latest
159 % version and documentation can be obtained at:
160 % http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
161 % Documentation is contained in the stfloats.sty comments as well as in the
162 % presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
163 % does not allow \baselineskip to stretch. Authors submitting work to the
164 % IEEE should note that IEEE rarely uses double column equations and
165 % that authors should try to avoid such use. Do not be tempted to use the
166 % cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
167 % not format its papers in such ways.
170 %\ifCLASSOPTIONcaptionsoff
171 % \usepackage[nomarkers]{endfloat}
172 % \let\MYoriglatexcaption\caption
173 % \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
175 % endfloat.sty was written by James Darrell McCauley and Jeff Goldberg.
176 % This package may be useful when used in conjunction with IEEEtran.cls'
177 % captionsoff option. Some IEEE journals/societies require that submissions
178 % have lists of figures/tables at the end of the paper and that
179 % figures/tables without any captions are placed on a page by themselves at
180 % the end of the document. If needed, the draftcls IEEEtran class option or
181 % \CLASSINPUTbaselinestretch interface can be used to increase the line
182 % spacing as well. Be sure and use the nomarkers option of endfloat to
183 % prevent endfloat from "marking" where the figures would have been placed
184 % in the text. The two hack lines of code above are a slight modification of
185 % that suggested by in the endfloat docs (section 8.3.1) to ensure that
186 % the full captions always appear in the list of figures/tables - even if
187 % the user used the short optional argument of \caption[]{}.
188 % IEEE papers do not typically make use of \caption[]'s optional argument,
189 % so this should not be an issue. A similar trick can be used to disable
190 % captions of packages such as subfig.sty that lack options to turn off
193 % \let\MYorigsubfloat\subfloat
194 % \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
196 % \let\MYorigsubfigure\subfigure
197 % \renewcommand{\subfigure}[2][\relax]{\MYorigsubfigure[]{#2}}
198 % However, the above trick will not work if both optional arguments of
199 % the \subfloat/subfig command are used. Furthermore, there needs to be a
200 % description of each subfigure *somewhere* and endfloat does not add
201 % subfigure captions to its list of figures. Thus, the best approach is to
202 % avoid the use of subfigure captions (many IEEE journals avoid them anyway)
203 % and instead reference/explain all the subfigures within the main caption.
204 % The latest version of endfloat.sty and its documentation can obtained at:
205 % http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
207 % The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
208 % later in the document, say, to conditionally put the References on a
209 % page by themselves.
211 % *** PDF, URL AND HYPERLINK PACKAGES ***
214 % url.sty was written by Donald Arseneau. It provides better support for
215 % handling and breaking URLs. url.sty is already installed on most LaTeX
216 % systems. The latest version can be obtained at:
217 % http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
218 % Read the url.sty source comments for usage information. Basically,
222 % *** Do not adjust lengths that control margins, column widths, etc. ***
223 % *** Do not use packages that alter fonts (such as pslatex). ***
224 % There should be no need to do such things with IEEEtran.cls V1.6 and later.
225 % (Unless specifically asked to do so by the journal or conference you plan
226 % to submit to, of course. )
228 % correct bad hyphenation here
229 \hyphenation{op-tical net-works semi-conduc-tor know-ledge
}
235 % can use linebreaks \\ within to get better formatting as desired
236 \title{On Move Pattern Trends\
\in \rvv{a
} Large Go Games Corpus
}
238 % use \thanks{} to gain access to the first footnote area
239 % a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
240 % was not built to handle multiple paragraphs
241 \author{Petr~Baudi
\v{s
},~Josef~Moud
\v{r
}\'
{i
}k
% <-this % stops a space
242 \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
243 \thanks{J. Moud
\v{r
}\'
{i
}k is student at the Faculty of Math and Physics, Charles University, Prague, CZ.
}}
245 % note the % following the last \IEEEmembership and also \thanks -
246 % these prevent an unwanted space from occurring between the last author name
247 % and the end of the author line. i.e., if you had this:
249 % \author{....lastname \thanks{...} \thanks{...} }
250 % ^------------^------------^----Do not want these spaces!
252 % a space would be appended to the last name and could cause every name on that
253 % line to be shifted left slightly. This is one of those "LaTeX things". For
254 % instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
255 % "AB" then you have to do: "\textbf{A}\textbf{B}"
256 % \thanks is no different in this regard, so shield the last } of each \thanks
257 % that ends a line with a % and do not let a space in before the next \thanks.
258 % Spaces after \IEEEmembership other than the last one are OK (and needed) as
259 % you are supposed to have spaces between the names. For what it is worth,
260 % this is a minor point as most people would not even notice if the said evil
261 % space somehow managed to creep in.
265 \markboth{Transactions on Computational Intelligence and AI in Games --- REV. SUBMISSIONp
}%
266 {On Move Pattern Trends in Large Go Games Corpus --- REV. SUBMISSIONp
}
267 % The only time the second header will appear is for the odd numbered pages
268 % after the title page when using the twoside option.
270 % *** Note that you probably will NOT want to include the author's ***
271 % *** name in the headers of peer review papers. ***
272 % You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
278 % If you want to put a publisher's ID mark on the page you can do it like
280 %\IEEEpubid{0000--0000/00\$00.00~\copyright~2007 IEEE}
281 % Remember, if you use this you must call \IEEEpubidadjcol in the second
282 % column for its text to clear the IEEEpubid mark.
286 % use for special paper notices
287 %\IEEEspecialpapernotice{(Invited Paper)}
292 % make the title area
299 We process a~large corpus of game records of the board game of Go and propose
300 a~way of extracting summary information on played moves. We then apply several
301 basic data-mining methods on the summary information to identify the most
302 differentiating features within the summary information, and discuss their
303 correspondence with traditional Go knowledge. We show statistically significant
304 mappings of the features to player attributes such as playing strength or
305 informally perceived ``playing style'' (e.g. territoriality or aggressivity),
306 describe accurate classifiers for these attributes, and propose applications
307 including seeding real-work ranks of internet players, aiding in Go study and
308 tuning of Go-playing programs, or contribution to Go-theoretical discussion on
309 the scope of ``playing style''.
312 % IEEEtran.cls defaults to using nonbold math in the Abstract.
313 % This preserves the distinction between vectors and scalars. However,
314 % if the journal you are submitting to favors bold math in the abstract,
315 % then you can use LaTeX's standard command \boldmath at the very start
316 % of the abstract to achieve this. Many IEEE journals frown on math
317 % in the abstract anyway.
319 % Note that keywords are not normally used for peerreview papers.
321 Board games, Evaluation, Function approximation, Go, Machine learning, Neural networks, User modelling
329 % For peer review papers, you can put extra information on the cover
331 % \ifCLASSOPTIONpeerreview
332 % \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
335 % For peerreview papers, this IEEEtran command inserts a page break and
336 % creates the second title. It will be ignored for other modes.
337 \IEEEpeerreviewmaketitle
340 This work has been submitted to the IEEE for possible publication. Copyright
341 may be transferred without notice, after which this version may no longer be
345 \section{Introduction
}
346 % The very first letter is a 2 line initial drop letter followed
347 % by the rest of the first word in caps.
349 % form to use if the first word consists of a single letter:
350 % \IEEEPARstart{A}{demo} file is ....
352 % form to use if you need the single drop letter followed by
353 % normal text (unknown if ever used by IEEE):
354 % \IEEEPARstart{A}{}demo file is ....
356 % Some journals put the first two words in caps:
357 % \IEEEPARstart{T}{his demo} file is ....
359 % Here we have the typical use of a "T" for an initial drop letter
360 % and "HIS" in caps to complete the first word.
361 \IEEEPARstart{T
}{he
} field of Computer Go usually focuses on the problem
362 of creating a~program to play the game, finding the best move from a~given
363 board position
\cite{GellySilver2008
}.
364 We will make use of one method developed in the course
365 of such research and apply it to the analysis of existing game records
366 with the aim of helping humans to play and understand the game better
369 Go is a~two-player full-information board game played
370 on a~square grid (usually $
19\times19$ lines) with black and white
371 stones; the goal of the game is to surround the most territory and
372 capture enemy stones. We assume basic familiarity with the game.
374 Many Go players are eager to play using computers (usually over
375 the internet) and review games played by others on computers as well.
376 This means that large amounts of game records are collected and digitally
377 stored, enabling easy processing of such collections. However, so far
378 only little has been done with the available data. We are aware
379 only of uses for simple win/loss statistics
\cite{KGSAnalytics
} \cite{ProGoR
}
380 and ``next move'' statistics on a~specific position
\cite{Kombilo
} \cite{MoyoGo
}.
382 \rvvv{Additionally
},
\rvv{a simple machine learning technique based on GNU Go's
}\cite{GnuGo
}\rvv{
383 move evaluation feature has recently been presented in
}\cite{CompAwar
}\rvv{. The authors used decision trees
384 to predict whether a given user belongs into one of three classes based on his strength
385 (causal, intermediate or advanced player). This method is however limited by the
386 blackbox-use of GNU Go engine, making it unsuitable for more detailed analysis of the moves.
}
388 We present a~more in-depth approach --- from all played moves, we devise
389 a~compact evaluation of each player. We then explore correlations between
390 evaluations of various players in the light of externally given information.
391 This way, we can discover similarity between move characteristics of
392 players with the same playing strength, or discuss the meaning of the
393 ``playing style'' concept on the assumption that similar playing styles
394 should yield similar move characteristics.
396 \rv{We show that a~sample of player's games can be used to quite reliably estimate player's strength,
397 game style, or even a time when he/she was active. Apart from these practical results,
398 the research may prove to be useful for Go theoretists by investigating the principles behind
399 the classical ``style'' classification.
}
401 % XXX \rv{ \ref{bla} } is not working
403 \rv{We shall first present details of the extraction and summarization of
404 information from the game corpus (section~
}\ref{pattern-vectors
}\rv{).
405 Afterwards, we will explain the statistical methods applied (section~
}\ref{data-mining
}\rv{),
406 and then describe our findings on particular game collections,
407 regarding the analysis of either strength (section~
}\ref{strength-analysis
}\rv{)
408 or playing styles (section~
}\ref{style-analysis
}\rv{).
409 Finally, we will explore possible interpretations and few applications
410 of our research (section~
}\ref{proposed-apps-and-discussion
}\rv{)
411 and point out some possible future research directions (section~
}\ref{future-research
}\rv{).
}
414 \section{Data Extraction
}
415 \label{pattern-vectors
}
417 As the input of our analysis, we use large collections of game records
418 \rvv{in SGF format
} \cite{SGF
}
419 \rv{grouped by the primary object of analysis
420 (player name when analyzing style of a particular player,
421 player rank when looking at the effect of rank on data, etc.).
}
422 We process the games, generating a description for each
423 played move -- a
{\em pattern
}, being a combination of several
424 {\em pattern features
} described below.
426 We
\rv{compute the occurence counts of all encountered patterns,
427 eventually
} composing $n$-dimensional
{\em pattern vector
}
428 $
\vec p$ of counts of the $n$
\rvv{(we use $n =
500$)
} globally most frequent patterns
429 (the mapping from patterns to vector elements is common for
430 \rv{all generated vectors
}).
431 We can then process and compare just the pattern vectors.
433 \subsection{Pattern Features
}
434 When deciding how to compose the patterns we use to describe moves,
435 we need to consider a specificity tradeoff --- overly general descriptions carry too few
436 information to discern various player attributes; too specific descriptions
437 gather too few specimen over the games sample and the vector differences are
438 not statistically significant.
440 We have chosen an intuitive and simple approach inspired by pattern features
441 used when computing Elo ratings for candidate patterns in Computer Go play
442 \cite{PatElo
}. Each pattern is a~combination of several
{\em pattern features
}
443 (name--value pairs) matched at the position of the played move.
444 We use these features:
447 \item capture move flag
\rvvv{,
}
448 \item atari move flag
\rvvv{,
}
449 \item atari escape flag
\rvvv{,
}
450 \item contiguity-to-last flag
%
451 \footnote{We do not consider contiguity features in some cases when we are working
452 on small game samples and need to reduce pattern diversity.
}
453 --- whether the move has been played in one of
8 neighbors of the last move
\rvvv{,
}
454 \item contiguity-to-second-last flag
\rvvv{,
}
455 \item board edge distance --- only up to distance
4\rvvv{,
}
456 \item and spatial pattern --- configuration of stones around the played move.
459 The spatial patterns are normalized (using a dictionary) to be always
460 black-to-play and maintain translational and rotational symmetry.
461 Configurations of radius between
2 and
9 in the gridcular metric
%
462 \footnote{The
{\em gridcular
} metric
463 $d(x,y) = |
\delta x| + |
\delta y| +
\max(|
\delta x|, |
\delta y|)$ produces
464 a circle-like structure on the Go board square grid
\cite{SpatPat
}.
}
467 Pattern vectors representing these features contain information on
468 played shape as well as a basic representation of tactical dynamics
469 --- threats to capture stones, replying to last move, or ignoring
470 opponent's move elsewhere to return to an urgent local situation.
471 The shapes
\rv{often
} correspond to opening moves
472 (either in empty corners and sides, or as part of
{\em joseki
}
473 --- commonly played sequences) characteristic for a certain
474 strategic aim. In the opening, even a single-line difference
475 in the distance from the border can have dramatic impact on
476 further local and global development.
478 \subsection{Vector Rescaling
}
480 The pattern vector elements can have diverse values since for each object,
481 we consider a different number of games (and thus patterns).
482 Therefore, we normalize the values to range $
[-
1,
1]$,
483 the most frequent pattern having the value of $
1$ and the least occuring
485 Thus, we obtain vectors describing relative frequency of played patterns
486 independent on number of gathered patterns.
487 But there are multiple ways to approach the normalization.
491 \includegraphics{patcountdist
}
492 \caption{Log-scaled number of pattern occurences
493 in the GoGoD games examined in sec.
\ref{style-analysis
}.
}
494 \label{fig:patcountdist
}
497 \subsubsection{Linear Normalization
}
499 \rvv{An intuitive solution is to
} linearly re-scale the values using:
500 $$y_i =
{x_i - x_
{\rm min
} \over x_
{\rm max
}}$$
501 This is the default approach; we have used data processed by only this
502 computation unless we note otherwise.
503 As shown on fig.
\ref{fig:patcountdist
}, most of the spectrum is covered
504 by the few most-occuring patterns (describing mostly large-diameter
505 shapes from the game opening). This means that most patterns will be
506 always represented by only very small values near the lower bound.
508 \subsubsection{Extended Normalization
}
511 To alleviate this problem, we have also tried to modify the linear
512 normalization by applying two steps ---
{\em pre-processing
}
514 $$x_i' =
\log (x_i +
1)$$
515 and
{\em post-processing
} the re-scaled values by the logistic function:
516 $$y_i' =
{2 \over 1 + e^
{-cy_i
}}-
1$$
517 However, we have found that this method is not universally beneficial.
518 In our styles case study (sec.
\ref{style-analysis
}), this normalization
519 produced PCA decomposition with significant dimensions corresponding
520 better to some of the prior knowledge and more instructive for manual
521 inspection, but ultimately worsened accuracy of our classifiers.
522 \rvvv{From this we conjecture
} that the most frequently occuring patterns are
523 also most important for classification of major style aspects.
525 \subsection{Implementation
}
527 We have implemented the data extraction by making use of the pattern
528 features matching implementation
529 within the Pachi Go-playing program
\cite{Pachi
},
\rvv{which works according to
530 the Elo-rating pattern selection scheme
} \cite{PatElo
}.
531 We extract information on players by converting the SGF game
532 records to GTP stream
\cite{GTP
} that feeds Pachi's
{\tt patternscan
}
533 engine,
\rv{producing
} a~single
{\em patternspec
} (string representation
534 of the particular pattern features combination) per move. Of course,
535 only moves played by the appropriate
\rv{player
} are collected.
537 \section{Data Mining
}
540 To assess the properties of gathered pattern vectors
541 and their influence on playing styles,
542 we analyze the data using several basic data minining techniques.
543 The first two methods
{\em (analytic)
} rely purely on single data set
544 and serve to show internal structure and correlations within the data set.
546 \rvvv{\emph{ Principal Component Analysis
}} \rvv{\emph{(PCA)
}} \cite{Jolliffe1986
}
547 finds orthogonal vector components that
\rv{represent
} the largest variance
548 \rv{of values within the dataset.
549 That is, PCA will produce vectors representing
550 the overall variability within the dataset --- the first vector representing
551 the ``primary axis'' of the dataset, the next vectors representing the less
552 significant axes; each vector has an associated number that
553 determines its impact on the overall dataset variance: $
1.0$ would mean
554 that all points within the dataset lie on this vector, value close to zero
555 would mean that removing this dimension would have little effect on the
556 overall shape of the dataset.
}
558 \rvv{Reversing the process of the PCA by backprojecting the orthogonal vector components into the
559 original pattern space can indicate which patterns correlate with each component.
}
560 Additionally, PCA can be used as vector preprocessing for methods
561 that are negatively sensitive to pattern vector component correlations.
563 \rv{On the other hand,
} Sociomaps
\cite{Sociomaps
} \cite{TeamProf
} \cite{SociomapsPersonal
} produce
564 spatial representation of the data set elements (e.g. players) based on
565 similarity of their data set features
\rvvv{. Projecting some other
566 information on this map helps illustrate connections within the data set.
}
568 % Pryc v ramci snizeni poctu footnotu
569 %\footnote{\rv{We also attempted to visualise the player relationships
570 %using Kohonen maps, but that did not produce very useful results.}}
572 Furthermore, we test several
\emph{classification
} methods that assign
573 an
\emph{output vector
} $
\vec O$
\rv{to
} each pattern vector $
\vec P$,
574 \rv{the output vector representing the information we want to infer
575 from the game sample
} --- e.g.~
\rv{assessment of
} the playing style,
576 player's strength or even meta-information like the player's era
577 or the country of origin.
578 Initially, the methods must be calibrated (trained) on some prior knowledge,
579 usually in the form of
\emph{reference pairs
} of pattern vectors
580 and the associated output vectors.
581 The reference set is divided into training and testing pairs
582 and the methods can be compared by the mean square error (MSE) on testing data set
583 (difference of output vectors approximated by the method and their real desired value).
585 %\footnote{However, note that dicrete characteristics such as country of origin are
586 %not very feasible to use here, since WHAT??? is that even true?? }
588 The most trivial method is approximation by the PCA representation
589 matrix, provided that the PCA dimensions have some already well-defined
590 \rv{interpretation
}\rvvv{. This
} can be true for single-dimensional information like
591 the playing strength.
592 Aside of that, we test the $k$-Nearest Neighbors (
\emph{$k$-NN
}) classifier
\cite{CoverHart1967
}
593 that approximates $
\vec O$ by composing the output vectors
594 of $k$ reference pattern vectors closest to $
\vec P$.
596 Another classifier is a~multi-layer feed-forward Artificial Neural Network
\rv{(see e.g.
}\cite{Haykin1994
}\rv{)
}.
597 The neural network can learn correlations between input and output vectors
598 and generalize the ``knowledge'' to unknown vectors
\rvvv{. The neural network
} can be more flexible
599 in the interpretation of different pattern vector elements and discern more
600 complex relations than the $k$-NN classifier,
601 but may not be as stable and expects larger training sample.
603 Finally, a commonly used classifier in statistical inference is
604 the Naive Bayes Classifier
\cite{Bayes
}\rvvv{. It
} can infer relative probability of membership
605 in various classes based on previous evidence (training patterns).
607 \subsection{Statistical Methods
}
608 We use couple of general statistical analysis
\rv{methods
} together
609 with the particular techniques.
611 To find correlations within or between extracted data and
612 some prior knowledge (player rank, style vector), we compute the well-known
613 {\em Pearson product-moment correlation coefficient (PMCC)
} \cite{Pearson
},
614 measuring the strength of the linear dependence
%
615 \footnote{A desirable property of PMCC is that it is invariant to translations and rescaling
617 between any two dimensions:
619 $$ r_
{X,Y
} =
{{\rm cov
}(X,Y)
\over \sigma_X \sigma_Y} $$
621 To compare classifier performance on the reference data, we employ
622 {\em $k$-fold cross validation
}:
623 we randomly divide the training set
624 into $k$ distinct segments of similar sizes and then iteratively
625 use each part as a~testing set as the other $k-
1$ parts are used as a~training set.
626 We then average results over all iterations.
628 \subsection{Principal Component Analysis
}
630 We use Principal Component Analysis
631 to reduce the dimensions of the pattern vectors while preserving
632 as much information as possible, assuming inter-dependencies between
633 pattern vector dimensions are linear.
634 \rv{Technically
}, PCA is an eigenvalue decomposition of a~covariance matrix of centered pattern vectors,
635 producing a~linear mapping $o$ from $n$-dimensional vector space
636 to a~reduced $m$-dimensional vector space.
637 The $m$ eigenvectors of the original vectors' covariance matrix
638 with the largest eigenvalues are used as the base of the reduced vector space;
639 the eigenvectors form projection matrix $W$.
641 For each original pattern vector $
\vec p_i$,
642 we obtain its new representation $
\vec r_i$ in the PCA base
643 as shown in the following equation:
645 \vec r_i = W
\cdot \vec p_i
648 The whole process is described in the Algorithm
\ref{alg:pca
}.
651 \caption{PCA -- Principal Component Analysis
}
654 \REQUIRE{$m >
0$, set of players $R$ with pattern vectors $p_r$
}
655 \STATE $
\vec \mu \leftarrow 1/|R|
\cdot \sum_{r
\in R
}{\vec p_r
}$
657 \STATE $
\vec p_r
\leftarrow \vec p_r -
\vec \mu$
659 \FOR{ $(i,j)
\in \
{1,... ,n\
} \times \
{1,... ,n\
}$
}
660 \STATE $
\mathit{Cov
}[i,j
] \leftarrow 1/|R|
\cdot \sum_{r
\in R
}{\vec p_
{ri
} \cdot \vec p_
{rj
}}$
662 \STATE Compute Eigenvalue Decomposition of $
\mathit{Cov
}$ matrix
663 \STATE Get $m$ largest eigenvalues
664 \STATE Most significant eigenvectors ordered by decreasing eigenvalues form the rows of matrix $W$
666 \STATE $
\vec r_r
\leftarrow W
\vec p_r$
671 \subsection{Sociomaps
}
673 Sociomaps are a general mechanism for
\rv{visualizing
}
674 relationships on a
2D plane such that
\rv{given
} ordering of the
675 \rv{player
} distances in the dataset is preserved in distances on the plane.
676 In our particular case,
677 %\footnote{A special case of the {\em Subject-to-Object Relation Mapping (STORM)} indirect sociomap.}
678 we will consider a dataset $
\vec S$ of small-dimensional
679 vectors $
\vec s_i$. First, we estimate the
{\em significance
}
680 of difference
{\rv of
} each two subjects.
681 Then, we determine projection $
\varphi$ of all the $
\vec s_i$
682 to spatial coordinates of an Euclidean plane, such that it reflects
683 the estimated difference significances.
685 % TODO: Clarify, clean up references
687 To quantify the differences between the subjects (
{\em team profiling
})
688 into an $A$ matrix, for each two subjects $i, j$ we compute the scalar distance
%
689 \footnote{We use the
{\em Manhattan
} metric $d(x,y) =
\sum_i |x_i - y_i|$.
}
690 of $s_i, s_j$ and then estimate the $A_
{ij
}$ probability of at least such distance
691 occuring in uniformly-distributed input (the higher the probability, the more
692 significant and therefore important to preserve the difference is).
694 To visualize the quantified differences, we need to find
695 the $
\varphi$ projection such that it maximizes a
{\em three-way ordering
} criterion:
696 ordering of any three members within $A$ and on the plane
697 (by Euclidean metric) must be the same.
699 $$
\max_\varphi \sum_{i
\ne j
\ne k
} \Phi(
\varphi, i, j, k) $$
700 $$
\Phi(
\varphi, i, j, k) =
\begin{cases
}
701 1 &
\delta(
1,A_
{ij
},A_
{ik
}) =
\delta(
\varphi(i),
\varphi(j),
\varphi(k)) \\
702 0 &
\hbox{otherwise
} \end{cases
} $$
703 $$
\delta(a, b, c) =
\begin{cases
}
706 -
1 & |a-b| < |a-c|
\end{cases
} $$
708 The $
\varphi$ projection is then determined by randomly initializing
709 the position of each subject and then employing gradient descent methods.
711 \subsection{k-Nearest Neighbors Classifier
}
713 Our goal is to approximate
\rvv{the
} player's output vector $
\vec O$,
714 knowing their pattern vector $
\vec P$.
715 We further assume that similarities in players' pattern vectors
716 uniformly correlate with similarities in players' output vectors.
718 We require a set of reference players $R$ with known
\emph{pattern vectors
} $
\vec p_r$
719 and
\emph{output vectors
} $
\vec o_r$.
720 $
\vec O$ is approximated as weighted average of
\emph{output vectors
}
721 $
\vec o_i$ of $k$ players with
\emph{pattern vectors
} $
\vec p_i$ closest to $
\vec P$.
722 This is illustrated in the Algorithm
\ref{alg:knn
}.
723 Note that the weight is a function of distance and is not explicitly defined in Algorithm
\ref{alg:knn
}.
724 During our research, exponentially decreasing weight has proven to be sufficient
\rvvv{,
725 as detailed in each of the case studies.
}
728 \caption{k-Nearest Neighbors
}
731 \REQUIRE{pattern vector $
\vec P$, $k >
0$, set of reference players $R$
}
733 \STATE $D
[r
] \leftarrow \mathit{EuclideanDistance
}(
\vec p_r,
\vec P)$
735 \STATE $N
\leftarrow \mathit{SelectSmallest
}(k, R, D)$
736 \STATE $
\vec O
\leftarrow \vec 0$
738 \STATE $
\vec O
\leftarrow \vec O +
\mathit{Weight
}(D
[r
])
\cdot \vec o_r $
743 \subsection{Neural Network Classifier
}
746 Feed-forward neural networks are known for their ability to generalize
747 and find correlations between input patterns and output classifications.
748 Before use, the network is iteratively trained on the training data
749 until the error on the training set is reasonably small.
751 %Neural network is an adaptive system that must undergo a training
752 %period similarly to the requirement
753 %of reference vectors for the k-Nearest Neighbors algorithm above.
755 \subsubsection{Computation and activation of the NN
}
756 Technically, the neural network is a network of interconnected
757 computational units called neurons.
758 A feed-forward neural network has a layered topology
\rvvv{. It
}
759 usually has one
\emph{input layer
}, one
\emph{output layer
}
760 and an arbitrary number of
\emph{hidden layers
} between.
761 Each neuron $i$ gets input from all neurons in the previous layer,
762 each connection having specific weight $w_
{ij
}$.
764 The computation proceeds in discrete time steps.
765 In the first step, the neurons in the
\emph{input layer
}
766 are
\emph{activated
} according to the
\emph{input vector
}.
767 Then, we iteratively compute output of each neuron in the next layer
768 until the output layer is reached.
769 The activity of output layer is then presented as the result.
771 The activation $y_i$ of neuron $i$ from the layer $I$ is computed as
773 y_i = f
\left(
\sum_{j
\in J
}{w_
{ij
} y_j
}\right)
775 where $J$ is the previous layer, while $y_j$ is the activation for neurons from $J$ layer.
776 Function $f()$ is a~so-called
\emph{activation function
}
777 and its purpose is to bound the outputs of neurons.
778 A typical example of an activation function is the sigmoid function.
%
779 \footnote{A special case of the logistic function $
\sigma(x)=(
1+e^
{-(rx+k)
})^
{-
1}$.
780 Parameters control the growth rate $r$ and the x-position $k$.
}
782 \subsubsection{Training
}
783 Training of the feed-forward neural network usually involves some
784 modification of supervised Backpropagation learning algorithm.
785 We use first-order optimization algorithm called RPROP
\cite{Riedmiller1993
}.
787 %Because the \emph{reference set} is usually not very large,
788 %we have devised a simple method for its extension.
789 %This enhancement is based upon adding random linear combinations
790 %of \emph{style and pattern vectors} to the training set.
792 As outlined above, the training set $T$ consists of
793 $(
\vec p_i,
\vec o_i)$ pairs.
794 The training algorithm is shown in Algorithm
\ref{alg:tnn
}.
797 \caption{Training Neural Network
}
800 \REQUIRE{Train set $T$, desired error $e$, max iterations $M$
}
801 \STATE $N
\leftarrow \mathit{RandomlyInitializedNetwork
}()$
802 \STATE $
\mathit{It
} \leftarrow 0$
804 \STATE $
\mathit{It
} \leftarrow \mathit{It
} +
1$
805 \STATE $
\Delta \vec w
\leftarrow \vec 0$
806 \STATE $
\mathit{TotalError
} \leftarrow 0$
807 %\FORALL{$(\overrightarrow{Input}, \overrightarrow{DesiredOutput}) \in T$}
808 %\STATE $\overrightarrow{Output} \leftarrow Result(N, \overrightarrow{Input})$
809 %\STATE $E \leftarrow |\overrightarrow{DesiredOutput} - \overrightarrow{Output}|$
810 \FORALL{$(
\mathit{Input
},
\mathit{DesiredOutput
})
\in T$
}
811 \STATE $
\mathit{Output
} \leftarrow \mathit{Result
}(N,
\mathit{Input
})$
812 \STATE $
\mathit{Error
} \leftarrow |
\mathit{DesiredOutput
} -
\mathit{Output
}|$
813 \STATE $
\Delta \vec w
\leftarrow \Delta \vec w +
\mathit{WeightUpdate
}(N,
\mathit{Error
})$
814 \STATE $
\mathit{TotalError
} \leftarrow \mathit{TotalError
} +
\mathit{Error
}$
816 \STATE $N
\leftarrow \mathit{ModifyWeights
}(N,
\Delta \vec w)$
817 \UNTIL{$
\mathit{TotalError
} < e$ or $
\mathit{It
} > M$
}
821 \subsection{Naive Bayes Classifier
}
824 The Naive Bayes Classifier uses existing information to construct
825 probability model of likelihoods of given
{\em feature variables
}
826 based on a discrete-valued
{\em class variable
}.
827 Using the Bayes equation, we can then estimate the probability distribution
828 of class variable for particular values of the feature variables.
830 In order to approximate the player's output vector $
\vec O$ based on
831 pattern vector $
\vec P$, we will compute each element of the
832 output vector separately, covering the output domain by several $k$-sized
833 discrete intervals (classes).
834 \rv{In fact, we use the PCA-represented input $
\vec R$ (using the
10 most significant
835 dimensions), since it better fits the pre-requisites of the
836 Bayes classifier -- values in each dimension are more independent and
837 they approximate the normal distribution better. Additionally, small input dimensions
838 are computationaly feasible.
}
840 When training the classifier for $
\vec O$ element $o_i$
841 of class $c =
\lfloor o_i/k
\rfloor$,
842 we assume the $
\vec R$ elements are normally distributed and
843 feed the classifier information in the form
845 estimating the mean $
\mu_c$ and standard deviation $
\sigma_c$
846 of each $
\vec R$ element for each encountered $c$
847 (see algorithm
\ref{alg:tnb
}).
848 Then, we can query the built probability model on
849 $$
\max_c P(c
\mid \vec R) $$
850 obtaining the most probable class $i$ for an arbitrary $
\vec R$
851 Each probability is obtained using the normal distribution formula:
852 $$ P(c
\mid x) =
{1\over \sqrt{2\pi\sigma_c^
2}}\exp{-(x-
\mu_c)^
2\over2\sigma_c^
2} $$
855 \caption{Training Naive Bayes
}
858 \REQUIRE{Training set $T = (
\mathit{R, c
})$
}
859 \FORALL{$(R, c)
\in T$
}
860 \STATE $
\mathit{RbyC
}_c
\leftarrow \mathit{RbyC
}_c
\cup \
{R\
}$
863 \STATE $
\mu_c \leftarrow {1 \over |
\mathit{RbyC
}_c|
} \sum_{R
\in \mathit{RbyC
}_c
} R$
866 \STATE $
\sigma_c \leftarrow {1 \over |
\mathit{RbyC
}_c|
} \sum_{R
\in \mathit{RbyC
}_c
} R-
\mu_c $
871 \subsection{Implementation
}
873 We have implemented the data mining methods as the
874 ``gostyle'' open-source framework
\cite{GoStyle
},
875 made available under the GNU GPL licence.
876 The majority of our basic processing and
\rv{analysis
877 is
} implemented in the Python
\cite{Python25
} programming language.
879 We use several external libraries, most notably the MDP library
\cite{MDP
} \rv{for the PCA analysis
}.
880 The neural network
\rv{component
} is written using the libfann C library
\cite{Nissen2003
}.
881 The Naive Bayes Classifier
\rv{is built around
} the
{\tt AI::NaiveBayes1
} Perl module
\cite{NaiveBayes1
}.
882 The sociomap has been visualised using the Team Profile Analyzer
\cite{TPA
}
883 which is a part of the Sociomap suite
\cite{SociomapSite
}.
886 \section{Strength Analysis
}
887 \label{strength-analysis
}
891 \includegraphics[width=
7in
]{strength-pca
}
892 \caption{PCA of by-strength vectors
}
893 \label{fig:strength_pca
}
896 First, we have used our framework to analyse correlations of pattern vectors
897 and playing strength. Like in other competitively played board games, Go players
898 receive real-world
{\em rating number
} based on tournament games,
899 and
{\em rank
} based on their rating.
900 %\footnote{Elo-type rating system \cite{GoR} is usually used,
901 %corresponding to even win chances for game of two players with the same rank,
902 %and about 2:3 win chance for the stronger in case of one rank difference.}
903 %\footnote{Professional ranks and dan ranks in some Asia countries may be assigned differently.}
904 The amateur ranks range from
30-kyu (beginner) to
1-kyu (intermediate)
905 and then follows
1-dan to
9-dan
906 %\footnote{7-dan in some systems.}
909 There are multiple independent real-world ranking scales
910 (geographically based),
\rv{while
} online servers
\rv{also
} maintain their own user rank
\rv{list
}\rvvv{.
911 The
} difference between scales can be up to several ranks and the rank
912 distributions also differ
\cite{RankComparison
}.
914 \subsection{Data source
}
915 As the source game collection, we use
\rvv{the
} Go Teaching Ladder reviews archive
916 %\footnote{The reviews contain comments and variations --- we consider only the main variation with the actual played game.}
917 \cite{GTL
}. This collection contains
7700 games of players with strength ranging
918 from
30-kyu to
4-dan; we consider only even games with clear rank information.
920 Since the rank information is provided by the users and may not be consistent,
921 we are forced to take a simplified look at the ranks,
922 discarding the differences between various systems and thus somewhat
923 increasing error in our model.
\footnote{Since our results seem satisfying,
924 we did not pursue to try another collection;
925 one could e.g. look at game archives of some Go server to work within
926 single more-or-less consistent rank model.
}
927 We represent the rank in our dataset
\rv{as an integer in the range
} $
[-
3,
30]$ with positive
928 numbers representing the kyu ranks and numbers smaller than
1 representing the dan
929 ranks:
4-dan maps to $-
3$,
1-dan to $
0$, etc.
931 \subsection{Strength PCA analysis
}
932 First, we have created a single pattern vector for each rank between
30-kyu to
4-dan;
933 we have performed PCA analysis on the pattern vectors, achieving near-perfect
934 rank correspondence in the first PCA dimension
%
935 \footnote{The eigenvalue of the second dimension was four times smaller,
936 with no discernable structure revealed within the lower-order eigenvectors.
}
937 (figure
\ref{fig:strength_pca
}).
938 We measure the accuracy of the strength approximation by the first PCA dimension
939 using Pearson's $r$ (see
\ref{pearson
}), yielding very satisfying value of $r=
0.979$
940 implying extremely strong correlation.
%
941 %\footnote{Extended vector normalization (sec. \ref{xnorm}) produced noticeably less clear-cut results.}
943 \rv{This reflects the trivial fact that the most important ``defining characteristic''
944 of a set of players grouped by strength is indeed their strength and confirms
945 that our methodics is correct.
946 At the same time, this result suggests that it is possible to accurately estimate
947 player's strength
\rvvv{just
} from a sample of his games,
948 as we confirm below.
}
949 %\footnote{The point is of course that the pattern analysis can be done even if we do not know the opponent's strength, or even the game result.}
951 \rv{When investigating a player's $
\vec p$, the PCA decomposition could be also
952 useful for study suggestions --- a program could examine the pattern gradient at the
953 player's position on the PCA dimensions and suggest patterns to avoid and patterns
954 to play more often. Of course, such an advice alone is certainly not enough and it
955 must be used only as a basis of a more thorough analysis of reasons behind the fact
956 that the player plays other patterns than they ``should''.
}
958 \subsection{Strength Classification
}
959 \label{strength-class
}
961 \rv{In line with results of the PCA analysis, we have tested the strength approximation ability
962 of $k$-NN (sec.
} \ref{knn
}\rv{), neural network (sec.
}\ref{neural-net
}\rv{),
963 and a simple PCA-based classifier (sec.
}\ref{PCA
}\rv{).
}
965 \subsubsection{Reference (Training) Data
}
966 \rv{We have trained the tested classifiers using one pattern vector per rank
967 (aggregate over all games played by some player declaring the given rank),
968 then performing PCA analysis to reduce the dimension of pattern vectors.
}
969 We have explored the influence of different game sample sizes (
\rv{$G$
})
970 on the classification accuracy to
\rv{determine the
} practicality and scaling
971 abilities of the classifiers.
972 In order to reduce the diversity of patterns (negatively impacting accuracy
973 on small samples), we do not consider the contiguity pattern features.
975 The classifiers were compared by running a many-fold validation by repeatedly and
976 exhaustively taking disjunct
\rv{$G$
}--game samples of the same rank from the collection
977 and measuring the standard error of the classifier.
978 Arbitrary game numbers were approximated by pattern file sizes,
979 iteratively selecting all games of randomly selected player
980 of the required strength.
982 %We have randomly separated $10\%$ of the game database as a testing set,
983 %Using the most %of players within the test group yields MSE TODO, thus providing
984 %reasonably satisfying accuracy by itself.
986 %Using the Naive Bayes classifier yields MSE TODO.
988 \subsubsection{Results
}
989 \rv{The results are shown in the table~
}\ref{table-str-class
}\rv{.
990 The $G$ column describes the number of games in each sample,
991 $
\mathit{MSE
}$ column shows measured mean square error and $
\sigma$ is the empirical standard deviation.
993 compared (column $
\mathit{Cmp
}$) to the random classifier by the quotient of their~$
\sigma$.
}
995 \rv{From the table, it should be obvious that the $k$-NN is obtaining good
996 accuracy even on as few as
9 games as a sample
\rvv{, where the classifier performs within a standard deviation of $
4.6$kyu.
}
997 For a large number of training vectors -- albeit not very accurate due to small
998 sample sizes -- the neural network classifier performs very similarly.
999 For samples of
2 games, the neural network is even slightly better on average.
1000 However, due to the decreasing number of training vectors with increasing game sample sizes,
1001 the neural network gets unusable for large sample sizes.
1002 The table therefore only shows the neural network results for samples of
17 games and smaller.
}
1003 \rv{PCA-based classifier (the most significant PCA eigenvector position is simply directly taken as a~rank) and
1004 a random classifier are listed mainly for the sake of comparison, because they do not perform
1008 % increase table row spacing, adjust to taste
1009 \renewcommand{\arraystretch}{1.3}
1010 \caption{Strength Classifier Performance
}
1011 \label{table-str-class
}
1013 \begin{tabular
}{|c|c||c|c||c|
}
1015 Method &
\rv{$G$
} & MSE & $
\sigma$ & Cmp \\
\hline
1016 $k$-NN&$
85$ & $
5.514$ & $
2.348$ & $
6.150$ \\
1017 &$
43$ & $
8.449$ & $
2.907$ & $
4.968$ \\
1018 &$
17$ & $
10.096$& $
3.177$ & $
4.545$ \\
1019 &$
9$ & $
21.343$& $
4.620$ & $
3.126$ \\
1020 &$
2$ & $
52.212$& $
7.226$ & $
1.998$ \\
\hline
1022 \rv{Neural Network
} & $
17$ & $
110.633$ & $
10.518$ & $
1.373$ \\
1023 &$
9$ & $
44.512$ & $
6.672$ & $
2.164$ \\
1024 &$
2$ & $
43.682$ & $
6.609$ & $
2.185$ \\
\hline
1025 %&$1$ & $58.051$ & $7.619$ & $1.895$ \\ \hline
1027 PCA & $
85$ & $
24.070$ & $
4.906$ & $
2.944$ \\
1028 &$
43$ & $
31.324$ & $
5.597$ & $
2.580$ \\
1029 &$
17$ & $
50.390$ & $
7.099$ & $
2.034$ \\
1030 &$
9$ & $
72.528$ & $
8.516$ & $
1.696$ \\
1031 &$
2$ & $
128.660$& $
11.343$ & $
1.273$ \\
\hline
1033 Rnd & N/A & $
208.549$ & $
14.441$ & $
1.000$ \\
\hline
1037 \subsubsection{$k$-NN parameters
}
1038 \rv{Using the $
4$-Nearest Neighbors classifier with the weight function
}
1040 \mathit{Weight
}(
\vec x) =
0.9^
{M*
\mathit{Distance
}(
\vec x)
}
1042 (parameter $M$ ranging from $
30$ to $
6$).
1044 \subsubsection{Neural network's parameters
}
1045 \rv{The neural network classifier had three-layered architecture (one hidden layer)
1046 comprising of these numbers of neurons:
}
1052 \begin{tabular
}{|c|c|c|
}
1054 \multicolumn{3}{|c|
}{Layer
} \\
\hline
1055 Input & Hidden & Output \\
\hline
1056 119 &
35 &
1 \\
\hline
1062 \rv{The network was trained until the square error on the training set was smaller than $
0.0005$.
1063 Due to the small number of input vectors,
1064 this only took about $
20$ iterations of RPROP learning algorithm on average.
}
1067 %#Finally, we used $8$-fold cross validation on one-file-per-rank data,
1068 %yielding a MSE $0.085$ which is equivalent to standard deviation of $15\%$.
1070 \section{Style Analysis
}
1071 \label{style-analysis
}
1073 As a~second case study for our pattern analysis,
1074 we investigate pattern vectors $
\vec p$ of various well-known players,
1075 their relationships in-between and to prior knowledge
1076 in order to explore the correlation of prior knowledge with extracted patterns.
1077 We look for relationships between pattern vectors and perceived
1078 ``playing style'' and attempt to use our classifiers to transform
1079 the pattern vector $
\vec p$ to a style vector $
\vec s$.
1081 \subsection{Data sources
}
1082 \subsubsection{Game database
}
1083 The source game collection is GoGoD Winter
2008 \cite{GoGoD
} containing
55000
1084 professional games, dating from the early Go history
1500 years ago to the present.
1085 We consider only games of a small subset of players (table
\ref{fig:style_marks
})
\rvvv{. These players
1086 were chosen
} for being well-known within the players community,
1087 having large number of played games in our collection and not playing too long
1089 %\footnote{Over time, many commonly used sequences get altered, adopted and
1090 %dismissed\rvvv{. Usual} playing conditions can also differ significantly.}
1092 \subsubsection{Expert-based knowledge
}
1093 \label{style-vectors
}
1094 In order to provide a reference frame for our style analysis,
1095 we have gathered some information from game experts about various
1096 traditionally perceived style aspects to use as a prior knowledge.
1097 This expert-based knowledge allows us to predict styles of unknown players
1098 based on the similarity of their pattern vectors,
1099 as well as discover correlations between styles and
\rv{particular
}
1102 Experts were asked to mark four style aspects of each of the given players
1103 on the scale from
1 to
10. The style aspects are defined as shown:
1110 \begin{tabular
}{|c|c|c|
}
1112 Style &
1 &
10\\
\hline
1113 Territoriality $
\tau$ & Moyo & Territory \\
1114 Orthodoxity $
\omega$ & Classic & Novel \\
1115 Aggressivity $
\alpha$ & Calm & Fighting \\
1116 Thickness $
\theta$ & Safe & Shinogi \\
\hline
1122 We have devised these four style aspects based on our own Go experience
1123 and consultations with other experts.
1124 The used terminology has quite
1125 clear meaning to any experienced Go player and there is not too much
1126 room for confusion, except possibly in the case of ``thickness'' ---
1127 but the concept is not easy to pin-point succintly and we also did not
1128 add extra comments on the style aspects to the questionnaire deliberately
1129 to accurately reflect any diversity in understanding of the terms.
1130 Averaging this expert based evaluation yields
\emph{reference style vector
}
1131 $
\vec s_r$ (of dimension $
4$) for each player $r$
1132 from the set of
\emph{reference players
} $R$.
1134 Throughout our research, we have experimentally found that playing era
1135 is also a major factor differentiating between patterns. Thus, we have
1136 further extended the $
\vec s_r$ by median year over all games played
1140 % increase table row spacing, adjust to taste
1141 \renewcommand{\arraystretch}{1.3}
1142 \caption{Covariance Measure of Prior Information Dimensions
}
1143 \label{fig:style_marks_r
}
1145 % Some packages, such as MDW tools, offer better commands for making tables
1146 % than the plain LaTeX2e tabular which is used here.
1147 \begin{tabular
}{|r||r||r||r||r||r|
}
1149 & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & year \\
1151 $
\tau$ &$
1.000$&$
\mathbf{-
0.438}$&$
\mathbf{-
0.581}$&$
\mathbf{ 0.721}$&$
0.108$\\
1152 $
\omega$& &$
1.000$&$
\mathbf{ 0.682}$&$
0.014$&$-
0.021$\\
1153 $
\alpha$& & &$
1.000$&$-
0.081$&$
0.030$\\
1154 $
\theta$& &
\multicolumn{1}{c||
}{---
}
1155 & &$
1.000$&$-
0.073$\\
1156 y. & & & & &$
1.000$\\
1161 Three high-level Go players (Alexander Dinerstein
3-pro, Motoki Noguchi
1162 7-dan and V\'
{i
}t Brunner
4-dan) have judged the style of the reference
1164 The complete list of answers is in table
\ref{fig:style_marks
}.
1165 Standard error of the answers is
0.952, making the data reasonably reliable,
1166 though much larger sample would of course be more desirable
1167 (but beyond our means to collect).
1168 We have also found a~significant correlation between the various
1169 style aspects, as shown by the Pearson's $r$ values
1170 in table
\ref{fig:style_marks_r
}.
1172 \rv{We have made few manual adjustments in the dataset, disregarding some
1173 players or portions of their games. This was done to achieve better
1174 consistency of the games (e.g. considering only games of roughly the
1175 same age) and to consider only sets of games that can be reasonably
1176 rated as a whole by human experts (who can give a clear feedback in this
1177 effect). This filtering methodology can be easily reproduced
1178 and such arbitrary decisions are neccessary only
1179 for processing the training dataset, not for using it (either for exloration
1180 or classification).
}
1183 % increase table row spacing, adjust to taste
1184 \renewcommand{\arraystretch}{1.4}
1185 \begin{threeparttable
}
1186 \caption{Expert-Based Style Aspects of Selected Professionals
\tnote{1} \tnote{2}}
1187 \label{fig:style_marks
}
1189 % Some packages, such as MDW tools, offer better commands for making tables
1190 % than the plain LaTeX2e tabular which is used here.
1191 \begin{tabular
}{|c||c||c||c||c|
}
1193 {Player
} & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ \\
1195 Go Seigen
\tnote{3} & $
6.0 \pm 2.0$ & $
9.0 \pm 1.0$ & $
8.0 \pm 1.0$ & $
5.0 \pm 1.0$ \\
1196 Ishida Yoshio
\tnote{4}&$
8.0 \pm 1.4$ & $
5.0 \pm 1.4$ & $
3.3 \pm 1.2$ & $
5.3 \pm 0.5$ \\
1197 Miyazawa Goro & $
1.5 \pm 0.5$ & $
10 \pm 0 $ & $
9.5 \pm 0.5$ & $
4.0 \pm 1.0$ \\
1198 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$ \\
1199 Sakata Eio & $
7.6 \pm 1.7$ & $
4.6 \pm 0.5$ & $
7.3 \pm 0.9$ & $
8.0 \pm 1.6$ \\
1200 Fujisawa Hideyuki & $
3.5 \pm 0.5$ & $
9.0 \pm 1.0$ & $
7.0 \pm 0.0$ & $
4.0 \pm 0.0$ \\
1201 Otake Hideo & $
4.3 \pm 0.5$ & $
3.0 \pm 0.0$ & $
4.6 \pm 1.2$ & $
3.6 \pm 0.9$ \\
1202 Kato Masao & $
2.5 \pm 0.5$ & $
4.5 \pm 1.5$ & $
9.5 \pm 0.5$ & $
4.0 \pm 0.0$ \\
1203 Takemiya Masaki
\tnote{4}&$
1.3\pm 0.5$& $
6.3 \pm 2.1$ & $
7.0 \pm 0.8$ & $
1.3 \pm 0.5$ \\
1204 Kobayashi Koichi & $
9.0 \pm 1.0$ & $
2.5 \pm 0.5$ & $
2.5 \pm 0.5$ & $
5.5 \pm 0.5$ \\
1205 Cho Chikun & $
9.0 \pm 0.8$ & $
7.6 \pm 0.9$ & $
6.6 \pm 1.2$ & $
9.0 \pm 0.8$ \\
1206 Ma Xiaochun & $
8.0 \pm 2.2$ & $
6.3 \pm 0.5$ & $
5.6 \pm 1.9$ & $
8.0 \pm 0.8$ \\
1207 Yoda Norimoto & $
6.3 \pm 1.7$ & $
4.3 \pm 2.1$ & $
4.3 \pm 2.1$ & $
3.3 \pm 1.2$ \\
1208 Luo Xihe & $
7.3 \pm 0.9$ & $
7.3 \pm 2.5$ & $
7.6 \pm 0.9$ & $
6.0 \pm 1.4$ \\
1209 O Meien & $
2.6 \pm 1.2$ & $
9.6 \pm 0.5$ & $
8.3 \pm 1.7$ & $
3.6 \pm 1.2$ \\
1210 Rui Naiwei & $
4.6 \pm 1.2$ & $
5.6 \pm 0.5$ & $
9.0 \pm 0.8$ & $
3.3 \pm 1.2$ \\
1211 Yuki Satoshi & $
3.0 \pm 1.0$ & $
8.5 \pm 0.5$ & $
9.0 \pm 1.0$ & $
4.5 \pm 0.5$ \\
1212 Hane Naoki & $
7.5 \pm 0.5$ & $
2.5 \pm 0.5$ & $
4.0 \pm 0.0$ & $
4.5 \pm 1.5$ \\
1213 Takao Shinji & $
5.0 \pm 1.0$ & $
3.5 \pm 0.5$ & $
5.5 \pm 1.5$ & $
4.5 \pm 0.5$ \\
1214 Yi Se-tol & $
5.3 \pm 0.5$ & $
6.6 \pm 2.5$ & $
9.3 \pm 0.5$ & $
6.6 \pm 1.2$ \\
1215 Yamashita Keigo
\tnote{4}&$
2.0\pm 0.0$& $
9.0 \pm 1.0$ & $
9.5 \pm 0.5$ & $
3.0 \pm 1.0$ \\
1216 Cho U & $
7.3 \pm 2.4$ & $
6.0 \pm 0.8$ & $
5.3 \pm 1.7$ & $
6.3 \pm 1.7$ \\
1217 Gu Li & $
5.6 \pm 0.9$ & $
7.0 \pm 0.8$ & $
9.0 \pm 0.8$ & $
4.0 \pm 0.8$ \\
1218 Chen Yaoye & $
6.0 \pm 1.0$ & $
4.0 \pm 1.0$ & $
6.0 \pm 1.0$ & $
5.5 \pm 0.5$ \\
1222 \item [1] Including standard deviation. Only players where we received at least two out of three answers are included.
1223 \item [2] Since the playing era column does not fit into the table, we at least sort the players ascending by their median year.
1224 \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.
1225 \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.
1226 \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.
1228 \end{threeparttable
}
1231 \subsection{Style PCA analysis
}
1235 \includegraphics[width=
3in
]{style-pca
}
1236 \caption{Columns with the most significant PCA dimensions of the dataset.
}
1237 \label{fig:style_pca
}
1240 We have looked at the ten most significant dimensions of the pattern data
1241 yielded by the PCA analysis of the reference player set
1243 %We also tried to observe PCA effect of removing outlying Takemiya
1244 %Masaki. That way, the second dimension strongly
1245 %correlated to territoriality and third dimension strongly correlacted to era,
1246 %however the first dimension remained mysteriously uncorrelated and with no
1247 %obvious interpretation.}
1248 (fig.
\ref{fig:style_pca
} shows the first three).
1249 We have again computed the Pearson's $r$ for all combinations of PCA dimensions
1250 and dimensions of the prior knowledge style vectors to find correlations.
1253 % increase table row spacing, adjust to taste
1254 \renewcommand{\arraystretch}{1.4}
1255 \caption{Covariance Measure of PCA and Prior Information
}
1258 % Some packages, such as MDW tools, offer better commands for making tables
1259 % than the plain LaTeX2e tabular which is used here.
1260 \begin{tabular
}{|c||r||r||r||r||r|
}
1262 Eigenval. & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & Year \\
1264 $
0.447$ & $
\mathbf{-
0.530}$ & $
0.323$ & $
0.298$ & $
\mathbf{-
0.554}$ & $
0.090$ \\
1265 $
0.194$ & $
\mathbf{-
0.547}$ & $
0.215$ & $
0.249$ & $-
0.293$ & $
\mathbf{-
0.630}$ \\
1266 $
0.046$ & $
0.131$ & $-
0.002$ & $-
0.128$ & $
0.242$ & $
\mathbf{-
0.630}$ \\
1267 $
0.028$ & $-
0.011$ & $
0.225$ & $
0.186$ & $
0.131$ & $
0.067$ \\
1268 $
0.024$ & $-
0.181$ & $
0.174$ & $-
0.032$ & $-
0.216$ & $
0.352$ \\
1269 %$0.018$ & $-0.364$ & $ 0.226$ & $ 0.339$ & $-0.136$ & $ 0.113$ \\
1270 %$0.014$ & $-0.194$ & $-0.048$ & $-0.099$ & $-0.333$ & $ 0.055$ \\
1271 %$0.0110575$ & $-0.040$ & $-0.254$ & $-0.154$ & $-0.054$ & $-0.089$ \\
1272 %$0.0093587$ & $-0.199$ & $-0.115$ & $ 0.358$ & $-0.234$ & $-0.028$ \\
1273 %$0.0084930$ & $ 0.046$ & $ 0.190$ & $ 0.305$ & $ 0.176$ & $ 0.089$ \\
1275 %$0.4473697$ & $\mathbf{-0.530}$ & $ 0.323$ & $ 0.298$ & $\mathbf{-0.554}$ & $ 0.090$ \\
1276 %$0.1941057$ & $\mathbf{-0.547}$ & $ 0.215$ & $ 0.249$ & $-0.293$ & $\mathbf{-0.630}$ \\
1277 %$0.0463189$ & $ 0.131$ & $-0.002$ & $-0.128$ & $ 0.242$ & $\mathbf{-0.630}$ \\
1278 %$0.0280301$ & $-0.011$ & $ 0.225$ & $ 0.186$ & $ 0.131$ & $ 0.067$ \\
1279 %$0.0243231$ & $-0.181$ & $ 0.174$ & $-0.032$ & $-0.216$ & $ 0.352$ \\
1280 %$0.0180875$ & $-0.364$ & $ 0.226$ & $ 0.339$ & $-0.136$ & $ 0.113$ \\
1281 %$0.0138478$ & $-0.194$ & $-0.048$ & $-0.099$ & $-0.333$ & $ 0.055$ \\
1282 %$0.0110575$ & $-0.040$ & $-0.254$ & $-0.154$ & $-0.054$ & $-0.089$ \\
1283 %$0.0093587$ & $-0.199$ & $-0.115$ & $ 0.358$ & $-0.234$ & $-0.028$ \\
1284 %$0.0084930$ & $ 0.046$ & $ 0.190$ & $ 0.305$ & $ 0.176$ & $ 0.089$ \\
1290 % increase table row spacing, adjust to taste
1291 \renewcommand{\arraystretch}{1.6}
1292 \begin{threeparttable
}
1293 \caption{Characteristic Patterns of PCA$_
{1,
2}$ Dimensions
\tnote{1}}
1294 \label{fig:style_patterns
}
1296 % Some packages, such as MDW tools, offer better commands for making tables
1297 % than the plain LaTeX2e tabular which is used here.
1298 \begin{tabular
}{|p
{2.3cm
}p
{2.4cm
}p
{2.4cm
}p
{0cm
}|
}
1299 % The virtual last column is here because otherwise we get random syntax errors.
1301 \hline \multicolumn{4}{|c|
}{PCA$_1$ --- Moyo-oriented, thin-playing player
} \\
1302 \centering \begin{psgopartialboard*
}{(
8,
1)(
12,
6)
}
1303 \stone[\marktr]{black
}{k
}{4}
1304 \end{psgopartialboard*
} &
1305 \centering \begin{psgopartialboard*
}{(
1,
2)(
5,
6)
}
1307 \stone[\marktr]{black
}{d
}{5}
1308 \end{psgopartialboard*
} &
1309 \centering \begin{psgopartialboard*
}{(
5,
1)(
10,
6)
}
1311 \stone[\marktr]{black
}{j
}{4}
1312 \end{psgopartialboard*
} & \\
1313 \centering $
0.274$ &
\centering $
0.086$ &
\centering $
0.083$ & \\
1314 \centering high corner/side opening
\tnote{2} &
\centering high corner approach &
\centering high distant pincer & \\
1316 \hline \multicolumn{4}{|c|
}{PCA$_1$ --- Territorial, thick-playing player
} \\
1317 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1319 \stone[\marktr]{black
}{f
}{3}
1320 \end{psgopartialboard*
} &
1321 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1324 \stone[\marktr]{black
}{f
}{3}
1325 \end{psgopartialboard*
} &
1326 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1328 \stone[\marktr]{black
}{f
}{3}
1329 \end{psgopartialboard*
} & \\
1330 \centering $-
0.399$ &
\centering $-
0.399$ &
\centering $-
0.177$ & \\
1331 \centering low corner approach &
\centering low corner reply &
\centering low corner enclosure & \\
1333 \hline \multicolumn{4}{|c|
}{PCA$_2$ --- Territorial, current player
\tnote{3}} \\
1334 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
6)
}
1337 \stone[\marktr]{black
}{f
}{3}
1338 \end{psgopartialboard*
} &
1339 \centering \begin{psgopartialboard*
}{(
3,
1)(
8,
6)
}
1341 \stone[\marktr]{black
}{g
}{4}
1342 \end{psgopartialboard*
} &
1343 \centering \begin{psgopartialboard*
}{(
4,
1)(
9,
6)
}
1346 \stone[\marktr]{black
}{h
}{3}
1347 \end{psgopartialboard*
} & \\
1348 \centering $-
0.193$ &
\centering $-
0.139$ &
\centering $-
0.135$ & \\
1349 \centering low corner reply
\tnote{4} &
\centering high distant approach/pincer &
\centering near low pincer & \\
1354 \item [1] We present the patterns in a simplified compact form;
1355 in reality, they are usually somewhat larger and always circle-shaped
1356 (centered on the triangled move).
1357 We omit only pattern segments that are entirely empty.
1358 \item [2] We give some textual interpretation of the patterns, especially
1359 since some of them may not be obvious unless seen in game context; we choose
1360 the descriptions based on the most frequently observer contexts, but of course
1361 the pattern can be also matched in other positions and situations.
1362 \item [3] In the second PCA dimension, we find no correlated patterns;
1363 only uncorrelated and anti-correlated ones.
1364 \item [4] As the second most significant pattern,
1365 we skip a slide follow-up pattern to this move.
1367 \end{threeparttable
}
1371 % increase table row spacing, adjust to taste
1372 \renewcommand{\arraystretch}{1.8}
1373 \begin{threeparttable
}
1374 \caption{Characteristic Patterns of PCA$_3$ Dimension
\tnote{1}}
1375 \label{fig:style_patterns3
}
1377 % Some packages, such as MDW tools, offer better commands for making tables
1378 % than the plain LaTeX2e tabular which is used here.
1379 \begin{tabular
}{|p
{2.4cm
}p
{2.4cm
}p
{2.4cm
}p
{0cm
}|
}
1380 % The virtual last column is here because otherwise we get random syntax errors.
1382 \hline \multicolumn{4}{|c|
}{PCA$_3$ --- Old-time player
} \\
1383 \centering \begin{psgopartialboard*
}{(
1,
3)(
5,
7)
}
1385 \stone[\marktr]{black
}{c
}{6}
1386 \end{psgopartialboard*
} &
1387 \centering \begin{psgopartialboard*
}{(
8,
1)(
12,
5)
}
1388 \stone[\marktr]{black
}{k
}{3}
1389 \end{psgopartialboard*
} &
1390 \centering \begin{psgopartialboard*
}{(
1,
1)(
5,
5)
}
1391 \stone[\marktr]{black
}{c
}{3}
1392 \end{psgopartialboard*
} & \\
1393 \centering $
0.515$ &
\centering $
0.264$ &
\centering $
0.258$ & \\
1394 \centering low corner approach &
\centering low side or mokuhazushi opening &
\centering san-san opening & \\
1396 \hline \multicolumn{4}{|c|
}{PCA$_3$ --- Current player
} \\
1397 \centering \begin{psgopartialboard*
}{(
3,
1)(
7,
5)
}
1399 \stone[\marktr]{black
}{f
}{3}
1400 \end{psgopartialboard*
} &
1401 \centering \begin{psgopartialboard*
}{(
1,
1)(
5,
5)
}
1402 \stone[\marktr]{black
}{c
}{4}
1403 \end{psgopartialboard*
} &
1404 \centering \begin{psgopartialboard*
}{(
1,
2)(
5,
6)
}
1407 \stone[\marktr]{black
}{c
}{5}
1408 \end{psgopartialboard*
} & \\
1409 \centering $-
0.276$ &
\centering $-
0.273$ &
\centering $-
0.116$ & \\
1410 \centering low corner enclosure &
\centering 3-
4 corner opening
\tnote{2} &
\centering high approach reply & \\
1415 \item [1] We cannot use terms ``classic'' and ''modern'' in case of PCA$_3$
1416 since the current patterns are commonplace in games of past centuries
1417 (not included in our training set) and many would call a lot of the old-time patterns
1418 modern inventions. Perhaps we can infer that the latest
21th-century play trends abandon
1419 many of the
20th-century experiments (lower echelon of our by-year samples)
1420 to return to the more ordinary but effective classic patterns.
1421 \item [2] At this point, we skip two patterns already shown elsewhere:
1422 {\em high side/corner opening
} and
{\em low corner reply
}.
1424 \end{threeparttable
}
1428 obvious both from the measured $r$ and visual observation
1429 that by far the most significant vector corresponds very well
1430 to the territoriality of the players,
1431 confirming the intuitive notion that this aspect of style
1432 is the one easiest to pin-point and also
1433 most obvious in the played shapes and sequences
1434 (that can obviously aim directly at taking secure territory
1435 or building center-oriented framework). Thick (solid) play also plays
1436 a role, but these two style dimensions are already
1437 correlated in the prior data.
1439 The other PCA dimensions are somewhat harder to interpret, but there
1440 certainly is significant influence of the styles on the patterns;
1441 the correlations are all presented in table
\ref{fig:style_r
}.
1442 (Larger absolute value means better linear correspondence.)
1444 We also list the characteristic spatial patterns of the PCA dimension
1445 extremes (tables
\ref{fig:style_patterns
},
\ref{fig:style_patterns3
}), determined by their coefficients
1446 in the PCA projection matrix --- however, such naive approach
1447 has limited reliability, better methods will have to be researched.
%
1448 \footnote{For example, as one of highly ranked ``Takemiya's'' PCA1 patterns,
1449 3,
3 corner opening was generated, completely inappropriately;
1450 it reflects some weak ordering in bottom half of the dimension,
1451 not global ordering within the dimension.
}
1452 We do not show the other pattern features since they carry no useful
1453 information in the opening stage.
1454 %\footnote{The board distance feature can be useful in some cases, but here all the spatial patterns are wide enough to reach to the edge on their own.}
1456 % increase table row spacing, adjust to taste
1457 \renewcommand{\arraystretch}{1.4}
1458 \caption{Covariance Measure of Externed-Normalization PCA and~Prior Information
}
1459 \label{fig:style_normr
}
1461 % Some packages, such as MDW tools, offer better commands for making tables
1462 % than the plain LaTeX2e tabular which is used here.
1463 \begin{tabular
}{|c||r||r||r||r||r|
}
1465 Eigenval. & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ & Year \\
1467 $
6.377$ & $
\mathbf{0.436}$ & $-
0.220$ & $-
0.289$ & $
\mathbf{0.404}$ & $
\mathbf{-
0.576}$ \\
1468 $
1.727$ & $
\mathbf{-
0.690}$ & $
0.340$ & $
0.315$ & $
\mathbf{-
0.445}$ & $
\mathbf{-
0.639}$ \\
1469 $
1.175$ & $-
0.185$ & $
0.156$ & $
0.107$ & $-
0.315$ & $
0.320$ \\
1470 $
0.845$ & $
0.064$ & $-
0.102$ & $-
0.189$ & $
0.032$ & $
0.182$ \\
1471 $
0.804$ & $-
0.185$ & $
0.261$ & $
\mathbf{0.620}$ & $
0.120$ & $
0.056$ \\
1472 $
0.668$ & $-
0.027$ & $
0.055$ & $
0.147$ & $-
0.198$ & $
0.155$ \\
1473 $
0.579$ & $
0.079$ & $
\mathbf{0.509}$ & $
0.167$ & $
0.294$ & $-
0.019$ \\
1474 %$0.4971474$ & $ 0.026$ & $-0.119$ & $-0.071$ & $ 0.049$ & $ 0.043$ \\
1475 %$0.4938777$ & $-0.061$ & $ 0.061$ & $ 0.104$ & $-0.168$ & $ 0.015$ \\
1476 %$0.4888848$ & $ 0.203$ & $-0.283$ & $-0.120$ & $ 0.083$ & $-0.220$ \\
1478 %$6.3774289$ & $ \mathbf{0.436}$ & $-0.220$ & $-0.289$ & $ \mathbf{0.404}$ & $\mathbf{-0.576}$ \\
1479 %$1.7269775$ & $\mathbf{-0.690}$ & $ 0.340$ & $ 0.315$ & $\mathbf{-0.445}$ & $\mathbf{-0.639}$ \\
1480 %$1.1747101$ & $-0.185$ & $ 0.156$ & $ 0.107$ & $-0.315$ & $ 0.320$ \\
1481 %$0.8452797$ & $ 0.064$ & $-0.102$ & $-0.189$ & $ 0.032$ & $ 0.182$ \\
1482 %$0.8038992$ & $-0.185$ & $ 0.261$ & $ \mathbf{0.620}$ & $ 0.120$ & $ 0.056$ \\
1483 %$0.6679533$ & $-0.027$ & $ 0.055$ & $ 0.147$ & $-0.198$ & $ 0.155$ \\
1484 %$0.5790000$ & $ 0.079$ & $ \mathbf{0.509}$ & $ 0.167$ & $ 0.294$ & $-0.019$ \\
1485 %$0.4971474$ & $ 0.026$ & $-0.119$ & $-0.071$ & $ 0.049$ & $ 0.043$ \\
1486 %$0.4938777$ & $-0.061$ & $ 0.061$ & $ 0.104$ & $-0.168$ & $ 0.015$ \\
1487 %$0.4888848$ & $ 0.203$ & $-0.283$ & $-0.120$ & $ 0.083$ & $-0.220$ \\
1492 The PCA results presented above do not show much correlation between
1493 the significant PCA dimensions and the $
\omega$ and $
\alpha$ style dimensions.
1494 However, when we applied the extended vector normalization
1495 (sec.
\ref{xnorm
}; see table
\ref{fig:style_normr
}),
1496 some less significant PCA dimensions exhibited clear correlations.
%
1497 \footnote{We have found that $c=
6$ in the post-processing logistic function
1498 produces the most instructive PCA output on our particular game collection.
}
1499 While we do not use the extended normalization results elsewhere since
1500 they produced noticeably less accurate classifiers in all dimensions
1501 (including $
\omega$ and $
\alpha$), it is instructive to look at the PCA dimensions.
1503 \rv{In contrast with the emphasis of opening patterns in the $
\tau$ and $
\theta$
1504 dimensions, the most contributing patterns of the $
\omega$ and $
\alpha$
1505 dimensions are the middle-game patterns that occur less frequently and require
1506 the extended normalization not to be over-shadowed by the opening patterns.
}%
1507 \footnote{In the middle game,
\rv{basic areas of influence have been staked
1508 out and invasions and group attacks are being played out
}.
1509 Notably, the board is much more filled
\rv{than in the opening
} and thus
1510 particular specific-shape patterns repeat less often.
}
1511 E.g. the most characteristic patterns
1512 on the aggressiveness dimension represent moves that make life with small,
1513 unstable groups (connecting kosumi on second line or mouth-shape eyespace
1514 move), while the novel-ranked players seem to like the (in)famous tsuke-nobi
1516 \footnote{\rv{Tsuke-nobi is a well-known joseki popular among beginners,
1517 but professionals usually play it only in special contexts.
}}
1518 \rv{This may either mean that novel players like to play the joseki more,
1519 or (more likely, in our opinion) that novel players are more likely to
1520 get into unorthodox situation that require resorting to the tsuke-nobi
1522 We believe that the next step in interpreting our analytical results
1523 will be more refined prior information input
1524 and precise analysis of the outputs by Go experts.
1528 \includegraphics[width=
3.5in,angle=-
90]{sociomap
}
1529 \caption{Sociomap visualisation. The spatial positioning of players
1530 is based on the expert knowledge, while the node heights (depicted by
1531 contour lines) represent the pattern vectors.
%
1532 %The light lines denote coherence-based hierarchical clusters.
1534 \label{fig:sociomap
}
1537 Fig.
\ref{fig:sociomap
} shows the Sociomap visualisation
1538 as an alternate view of the player relationships and similarity,
1539 as well as correlation between the expert-given style marks
1540 and the PCA decomposition. The four-dimensional style vectors
1541 are used as input for the Sociomap renderer and determine the
1542 spatial positions of players. The height of a node is then
1543 determined using first two PCA dimensions $R_1,R_2$ and their
1544 eigenvalues $
\lambda_1,
\lambda_2$ as their linear combination:
1545 $$ h=
\lambda_1R_1 +
\lambda_2R_2 $$
1547 We can observe that the terrain of the sociomap is reasonably
1548 ``smooth'', again demonstrating some level of connection between
1549 the style vectors and data-mined information. High countour density
1550 indicates some discrepancy; in case of Takemiya Masaki and Yi Ch'ang-ho,
1551 this seems to be merely an issue of scale,
1552 while the Rui Naiwei --- Gu Li cliff suggests a genuine problem;
1553 we cannot say now whether it is because of imprecise prior information
1554 or lacking approximation abilities of our model.
1556 \subsection{Style Classification
}
1559 %TODO vsude zcheckovat jestli pouzivame stejny cas "we perform, we apply" X "we have performed, ..."
1561 Similarly to the the Strength classification (section
\ref{strength-class
}), we have tested the style inference ability
1562 of $k$-NN (sec.
\ref{knn
}), neural network (sec.
\ref{neural-net
}), and Bayes (sec.
\ref{naive-bayes
}) classifers.
1564 \subsubsection{Reference (Training) Data
}
1565 As the~reference data, we use expert-based knowledge presented in section
\ref{style-vectors
}.
1566 For each reference player, that gives $
4$-dimensional
\emph{style vector
} (each component in the
1567 range of $
[1,
10]$).
\footnote{Since the neural network has activation function with range $
[-
1,
1]$, we
1568 have linearly rescaled the
\emph{style vectors
} from interval $
[1,
10]$ to $
[-
1,
1]$ before using the training
1569 data. The network's output was afterwards rescaled back to allow for MSE comparison.
}
1571 All input (pattern) vectors were preprocessed using PCA, reducing the input dimension from $
400$ to $
23$.
1572 We measure the performance on the same reference data using $
5$-fold cross validation.
1573 To put our measurements in scale, we also include a~random classifier in our results.
1575 \subsubsection{Results
}
1576 The results are shown in the table
\ref{crossval-cmp
}. Second to fifth columns in the table represent
1577 mean square error (MSE) of the examined styles, $
\mathit{Mean
}$ is the
1578 mean square error across the styles and finally, the last column $
\mathit{Cmp
}$
1579 represents $
\mathit{Mean
}(
\mathit{Random classifier
}) /
\mathit{Mean
}(
\mathit{X
})$ -- comparison of mean square error
1580 of each method with the random classifier. To minimize the
1581 effect of random variables, all numbers were taken as an average of $
200$ runs of the cross validation.
1583 Analysis of the performance of $k$-NN classifier for different $k$-values has shown that different
1584 $k$-values are suitable to approximate different styles. Combining the $k$-NN classifiers with the
1585 neural network (so that each style is approximated by the method with lowest MSE in that style)
1586 results in
\emph{Joint classifier
}, which outperforms all other methods.
1587 The
\emph{Joint classifier
} has outstanding MSE $
3.960$, which is equivalent to standard error
1588 of $
\sigma =
1.99$ per style.
%
1589 \footnote{We should note that the pattern vector for each tested player
1590 was generated over at least few tens of games.
}
1593 \renewcommand{\arraystretch}{1.4}
1594 \begin{threeparttable
}
1595 \caption{Comparison of style classifiers
}
1596 \label{crossval-cmp
}
1597 \begin{tabular
}{|c|c|c|c|c|c|c|
}
1599 %Classifier & $\sigma_\tau$ & $\sigma_\omega$ & $\sigma_\alpha$ & $\sigma_\theta$ & Tot $\sigma$ & $\mathit{RndC}$\\ \hline
1600 %Neural network & 0.420 & 0.488 & 0.365 & 0.371 & 0.414 & 1.82 \\
1601 %$k$-NN ($k=4$) & 0.394 & 0.507 & 0.457 & 0.341 & 0.429 & 1.76 \\
1602 %Random classifier & 0.790 & 0.773 & 0.776 & 0.677 & 0.755 & 1.00 \\ \hline
1603 &
\multicolumn{5}{|c|
}{MSE
}& \\
\hline
1604 {Classifier
} & $
\tau$ & $
\omega$ & $
\alpha$ & $
\theta$ &
{\bf Mean
} &
{\bf Cmp
}\\
\hline
1605 Joint classifier
\tnote{1} &
4.04 &
{\bf 5.25} &
{\bf 3.52} &
{\bf 3.05} &
{\bf 3.960}&
2.97 \\
\hline
1606 Neural network &
{\bf 4.03} &
6.15 &
{\bf 3.58} &
3.79 &
4.388 &
2.68 \\
1607 $k$-NN ($k=
2$) &
4.08 &
5.40 &
4.77 &
3.37 &
4.405 &
2.67 \\
1608 $k$-NN ($k=
3$) &
4.05 &
5.58 &
5.06 &
3.41 &
4.524 &
2.60 \\
1609 $k$-NN ($k=
1$) &
4.52 &
{\bf 5.26} &
5.36 &
{\bf 3.09} &
4.553 &
2.59 \\
1610 $k$-NN ($k=
4$) &
4.10 &
5.88 &
5.16 &
3.60 &
4.684 &
2.51 \\
1611 Naive Bayes &
4.48 &
6.90 &
5.48 &
3.70 &
5.143 &
2.29 \\
1612 Random class. &
12.26 &
12.33 &
12.40 &
10.11 &
11.776 &
1.00 \\
\hline
1616 \item [1] Note that these measurements have a certain variance.
1617 Since the Joint classifier performance was measured from scratch,
1618 the precise values may not match appropriate cells of the used methods.
1620 \end{threeparttable
}
1623 % TODO presunout konkretni parametry do Appendixu? (neni jich tolik, mozna ne)
1624 \subsubsection{$k$-NN parameters
}
1625 All three variants of $k$-NN classifier ($k=
2,
3,
4$) had the weight function
1627 \mathit{Weight
}(
\vec x) =
0.8^
{10*
\mathit{Distance
}(
\vec x)
}
1629 The parameters were chosen empirically to minimize the MSE.
1631 \subsubsection{Neural network's parameters
}
1632 The neural network classifier had three-layered architecture (one hidden layer)
1633 comprising of these numbers of neurons:
1639 \begin{tabular
}{|c|c|c|
}
1641 \multicolumn{3}{|c|
}{Layer
} \\
\hline
1642 Input & Hidden & Output \\
\hline
1643 23 &
30 &
4 \\
\hline
1649 The network was trained until the square error on the training set was smaller than $
0.0003$.
1650 Due to a small number of input vectors, this only took $
20$ iterations of RPROP learning algorithm on average.
1652 \subsubsection{Naive Bayes parameters
}
1654 We have chosen $k =
10/
7$ as our discretization parameter;
1655 ideally, we would use $k =
1$ to fully cover the style marks
1656 domain, however our training sample
\rv{turns out to be
} too small for
1659 \section{Proposed Applications
}
1660 %\section{Proposed Applications and Discussion}
1661 \label{proposed-apps-and-discussion
}
1663 %\rv{TODO Discussion}
1665 We believe that our findings might be useful for many applications
1666 in the area of Go support software as well as Go-playing computer engines.
1667 \rv{However, our foremost aim is to use the style analysis as an excellent
1668 teaching aid
} --- classifying style
1669 dimensions based on player's pattern vector, many study recommendations
1670 can be given, e.g. about the professional games to replay, the goal being
1671 balancing understanding of various styles to achieve well-rounded skill set.
%
1672 \footnote{\rv{The strength analysis could be also used in a similar fashion,
1673 but the lesson learned cannot simply be ``play pattern $X$ more often'';
1674 instead, the insight lays in the underlying reason of disproportionate
1675 frequency of some patterns.
}}
1676 \rv{A user-friendly tool based on our work is currently in development.
}
1678 \rv{Another promising application we envision is helping to
}
1679 determine the initial real-world rating of a player before their
1680 first tournament based on a sample of their games played on the internet;
1681 some players especially in less populated areas could get fairly strong
1682 before playing in their first real tournament.
1683 \rv{Similarly, a computer Go program can quickly
} classify the level of its
1684 \rv{human opponent
} based on the pattern vector from
\rv{their previous games
}
1685 and auto-adjust its difficulty settings accordingly
1686 to provide more even games for beginners.
1687 \rvvv{This can also be achieved using
} win-loss statistics,
1688 but pattern vector analysis
\rv{should
} converge faster
\rv{initially,
1689 providing a much better user experience
}.
1691 We hope that more strong players will look into the style dimensions found
1692 by our statistical analysis --- analysis of most played patterns of prospective
1693 opponents might prepare for
\rv{a tournament
} game, but we especially hope that new insights
1694 on strategic purposes of various shapes and general human understanding
1695 of the game might be
\rv{improved
} by investigating the style-specific patterns.
1697 \rv{Of course, it is challenging to predict all possible uses of our work by others.
1698 Some less obvious applications might include
}
1699 analysis of pattern vectors extracted from games of Go-playing programs:
1700 the strength and style
\rv{classification
} might help to highlight some weaknesses
1701 and room for improvements.
%
1702 \footnote{Of course, correlation does not imply causation
\rv{and we certainly do not
1703 suggest simply optimizing Go-playing programs according to these vectors.
1704 However, they could hint on general shortcomings of the playing engines if the
1705 actual cause of e.g. surprisingly low strength prediction is investigated.
}}
1706 Also, new historical game records are still
\rv{occassionally
} being discovered;
1707 pattern-based classification might help to suggest
\rv{or verify
} origin of the games
1711 % An example of a floating figure using the graphicx package.
1712 % Note that \label must occur AFTER (or within) \caption.
1713 % For figures, \caption should occur after the \includegraphics.
1714 % Note that IEEEtran v1.7 and later has special internal code that
1715 % is designed to preserve the operation of \label within \caption
1716 % even when the captionsoff option is in effect. However, because
1717 % of issues like this, it may be the safest practice to put all your
1718 % \label just after \caption rather than within \caption{}.
1720 % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
1721 % option should be used if it is desired that the figures are to be
1722 % displayed while in draft mode.
1726 %\includegraphics[width=2.5in]{myfigure}
1727 % where an .eps filename suffix will be assumed under latex,
1728 % and a .pdf suffix will be assumed for pdflatex; or what has been declared
1729 % via \DeclareGraphicsExtensions.
1730 %\caption{Simulation Results}
1734 % Note that IEEE typically puts floats only at the top, even when this
1735 % results in a large percentage of a column being occupied by floats.
1738 % An example of a double column floating figure using two subfigures.
1739 % (The subfig.sty package must be loaded for this to work.)
1740 % The subfigure \label commands are set within each subfloat command, the
1741 % \label for the overall figure must come after \caption.
1742 % \hfil must be used as a separator to get equal spacing.
1743 % The subfigure.sty package works much the same way, except \subfigure is
1744 % used instead of \subfloat.
1746 %\begin{figure*}[!t]
1747 %\centerline{\subfloat[Case I]\includegraphics[width=2.5in]{subfigcase1}%
1748 %\label{fig_first_case}}
1750 %\subfloat[Case II]{\includegraphics[width=2.5in]{subfigcase2}%
1751 %\label{fig_second_case}}}
1752 %\caption{Simulation results}
1756 % Note that often IEEE papers with subfigures do not employ subfigure
1757 % captions (using the optional argument to \subfloat), but instead will
1758 % reference/describe all of them (a), (b), etc., within the main caption.
1761 % An example of a floating table. Note that, for IEEE style tables, the
1762 % \caption command should come BEFORE the table. Table text will default to
1763 % \footnotesize as IEEE normally uses this smaller font for tables.
1764 % The \label must come after \caption as always.
1767 %% increase table row spacing, adjust to taste
1768 %\renewcommand{\arraystretch}{1.3}
1769 % if using array.sty, it might be a good idea to tweak the value of
1770 % \extrarowheight as needed to properly center the text within the cells
1771 %\caption{An Example of a Table}
1772 %\label{table_example}
1774 %% Some packages, such as MDW tools, offer better commands for making tables
1775 %% than the plain LaTeX2e tabular which is used here.
1776 %\begin{tabular}{|c||c|}
1786 % Note that IEEE does not put floats in the very first column - or typically
1787 % anywhere on the first page for that matter. Also, in-text middle ("here")
1788 % positioning is not used. Most IEEE journals use top floats exclusively.
1789 % Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
1790 % floats. This can be corrected via the \fnbelowfloat command of the
1795 \section{Future Research
}
1796 \label{future-research
}
1798 Since we are not aware of any previous research on this topic and we
1799 are limited by space and time constraints, plenty of research remains
1800 to be done in all parts of our analysis --- we have already noted
1801 many in the text above. Most significantly, different methods of generating
1802 and normalizing the $
\vec p$ vectors can be explored
1803 and other data mining methods could be investigated.
1804 Better ways of visualising the relationships would be desirable,
1805 together with thorough expert dissemination of internal structure
1806 of the player pattern vectors space:
1807 more professional players should be consulted on the findings
1808 and for style scales calibration.
1810 It can be argued that many players adjust their style by game conditions
1811 (Go development era, handicap, komi and
color, time limits, opponent)
1812 or that styles might express differently in various game stages
\rvvv{.
1813 These
} factors should be explored by building pattern vectors more
1814 carefully than by simply considering all moves in all games of a player.
1815 Impact of handicap and uneven games on by-strength
1816 $
\vec p$ distribution should be also investigated.
1818 % TODO: Future research --- Sparse PCA
1820 \section{Conclusion
}
1821 We have proposed a way to extract summary pattern information from
1822 game collections and combined this with various data mining methods
1823 to show correspondence of our pattern summaries with various player
1824 meta-information
\rvvv{such as
} playing strength, era of play or playing style,
1825 as ranked by expert players. We have implemented and measured our
1826 proposals in two case studies: per-rank characteristics of amateur
1827 players and per-player style/era characteristics of well-known
1830 While many details remain to be worked out,
1831 we have demonstrated that many significant correlations
\rv{doubtlessly
}
1833 it is practically viable to infer the player meta-information from
1834 extracted pattern summaries
\rv{and we have proposed applications
}
1835 for such inference. Finally, we outlined some of the many possible
1836 directions of future work in this newly staked research field
1837 on the boundary of Computer Go, Data Mining and Go Theory.
1840 % if have a single appendix:
1841 %\appendix[Proof of the Zonklar Equations]
1843 %\appendix % for no appendix heading
1844 % do not use \section anymore after \appendix, only \section*
1845 % is possibly needed
1847 % use appendices with more than one appendix
1848 % then use \section to start each appendix
1849 % you must declare a \section before using any
1850 % \subsection or using \label (\appendices by itself
1851 % starts a section numbered zero.)
1856 %\section{Proof of the First Zonklar Equation}
1857 %Appendix one text goes here.
1859 %% you can choose not to have a title for an appendix
1860 %% if you want by leaving the argument blank
1862 %Appendix two text goes here.
1865 % use section* for acknowledgement
1866 \section*
{Acknowledgment
}
1867 \label{acknowledgement
}
1869 Foremostly, we are very grateful for detailed input on specific Go styles
1870 by Alexander Dinerstein, Motoki Noguchi and V\'
{i
}t Brunner.
1871 We appreciate helpful comments on our general methodology
1872 by John Fairbairn, T. M. Hall, Cyril H\"oschl, Robert Jasiek, Franti
\v{s
}ek Mr\'
{a
}z
1873 and several GoDiscussions.com users
\cite{GoDiscThread
}.
1874 Finally, we would like to thank Radka ``chidori'' Hane
\v{c
}kov\'
{a
}
1875 for the original research idea and acknowledge major inspiration
1876 by R\'
{e
}mi Coulom's paper
\cite{PatElo
} on the extraction of pattern information.
1879 % Can use something like this to put references on a page
1880 % by themselves when using endfloat and the captionsoff option.
1881 \ifCLASSOPTIONcaptionsoff
1887 % trigger a \newpage just before the given reference
1888 % number - used to balance the columns on the last page
1889 % adjust value as needed - may need to be readjusted if
1890 % the document is modified later
1891 %\IEEEtriggeratref{8}
1892 % The "triggered" command can be changed if desired:
1893 %\IEEEtriggercmd{\enlargethispage{-5in}}
1895 % references section
1897 % can use a bibliography generated by BibTeX as a .bbl file
1898 % BibTeX documentation can be easily obtained at:
1899 % http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
1900 % The IEEEtran BibTeX style support page is at:
1901 % http://www.michaelshell.org/tex/ieeetran/bibtex/
1902 \bibliographystyle{IEEEtran
}
1903 % argument is your BibTeX string definitions and bibliography database(s)
1904 \bibliography{gostyle
}
1906 % <OR> manually copy in the resultant .bbl file
1907 % set second argument of \begin to the number of references
1908 % (used to reserve space for the reference number labels box)
1909 %\begin{thebibliography}{1}
1911 %\bibitem{MasterMCTS}
1913 %\end{thebibliography}
1917 % If you have an EPS/PDF photo (graphicx package needed) extra braces are
1918 % needed around the contents of the optional argument to biography to prevent
1919 % the LaTeX parser from getting confused when it sees the complicated
1920 % \includegraphics command within an optional argument. (You could create
1921 % your own custom macro containing the \includegraphics command to make things
1923 %\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
1924 % or if you just want to reserve a space for a photo:
1926 %\begin{IEEEbiography}{Petr Baudi\v{s}}
1927 %Biography text here.
1928 %\end{IEEEbiography}
1930 % if you will not have a photo at all:
1931 \begin{IEEEbiographynophoto
}{Petr Baudi
\v{s
}}
1932 Received the M.Sc. degree in Theoretical Computer Science at Charles University, Prague in
2012.
1933 \rvvv{He is doing
} research in the fields of Computer Go, Monte Carlo Methods and Version Control Systems.
1934 \rvvv{He plays
} Go with the rank of
2-kyu on European tournaments and
2-dan on the KGS Go Server.
1935 \end{IEEEbiographynophoto
}
1937 \begin{IEEEbiographynophoto
}{Josef Moud
\v{r
}\'
{i
}k
}
1938 Received the B.Sc. degree in Informatics at Charles University, Prague in
2009, and is currently a graduate student.
1939 \rvvv{He is doing
} research in the fields of Neural Networks and Cognitive Sciences. His Go skills are not worth mentioning.
1940 \end{IEEEbiographynophoto
}
1942 % insert where needed to balance the two columns on the last page with
1946 %\begin{IEEEbiographynophoto}{Jane Doe}
1947 %Biography text here.
1948 %\end{IEEEbiographynophoto}
1950 % You can push biographies down or up by placing
1951 % a \vfill before or after them. The appropriate
1952 % use of \vfill depends on what kind of text is
1953 % on the last page and whether or not the columns
1954 % are being equalized.
1958 % Can be used to pull up biographies so that the bottom of the last one
1959 % is flush with the other column.
1960 %\enlargethispage{-5in}