\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file


% macros

\input prepictex
\input pictex
\input postpictex
\input makros


% sizes

%\setlength{\textwidth}{16cm}            
%\setlength{\textheight}{23cm}
%\setlength{\topmargin}{-1.05cm}
%\setlength{\oddsidemargin}{-0.04cm}     % = distance - 2.54cm
%\setlength{\evensidemargin}{-0.04cm}



% misc.

\renewcommand{\bottomfraction}{1}	
\renewcommand{\topfraction}{1}		

\def\CW{{\cal W}}
\def\CD{{\cal D}}
\def\CL{{\cal L}}
\def\bx{\mbox{\boldmath$x$}}

\def\d{d\kern -0.32em\raise 0.63ex \hbox{-}\kern-0.051ex \hbox{}}
\def\D{D\kern -0.7em \raise 0.26ex \hbox{-}\kern 0.829ex \hbox{}}
\def\c{\'c}

\def\Durdanovic{\D ur\d ano\-vi\c}

% xfig-Quatsch

\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup



\begin{document}

\input titleabs
\vspace{-0.15cm}
\input intro
\input combi
\input examples
\input comp
\input discuss
\input ref

\end{document}
\font\thinlinefont=cmr5
\mbox{\beginpicture
\setcoordinatesystem units < 1.000cm, 1.000cm>
\unitlength= 1.000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig CIRCULAR ARC object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\circulararc 73.740 degrees from  5.683 13.049 center at  7.112 14.954
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  1.429:0.476  360 degrees 
	from  8.541 15.272 center at  7.112 15.272
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from  5.683 15.272 to  5.683 13.049
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from  8.541 15.272 to  8.541 13.049
%
% Fig CIRCULAR ARC object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\circulararc 73.740 degrees from 14.573 13.081 center at 16.002 14.986
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  1.429:0.476  360 degrees 
	from 17.431 15.304 center at 16.002 15.304
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 14.573 15.304 to 14.573 13.081
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 17.431 15.304 to 17.431 13.081
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  0.159:0.159  360 degrees 
	from 10.922 14.796 center at 10.763 14.796
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 11.398 15.431
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 10.763 12.891
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 10.763 14.161
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  0.159:0.159  360 degrees 
	from 10.922 13.526 center at 10.763 13.526
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  0.159:0.159  360 degrees 
	from 12.478 14.796 center at 12.319 14.796
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  0.159:0.159  360 degrees 
	from 12.002 13.526 center at 11.843 13.526
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\ellipticalarc axes ratio  0.159:0.159  360 degrees 
	from 12.954 13.526 center at 12.795 13.526
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 11.843 14.161
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 12.795 14.161
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 12.319 12.891
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\put{\makebox(0,0)[l]{\circle*{ 0.318}}} at 13.271 12.891
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 11.398 15.399 10.890 14.922 /
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 10.763 14.637 to 10.763 14.319
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 10.763 14.161 to 10.763 13.684
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 10.763 13.367 to 10.763 13.049
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 11.398 15.399 12.192 14.859 /
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from  8.858 14.002 to  9.811 14.002
%
% arrow head
%
\plot  9.557 13.938  9.811 14.002  9.557 14.065 /
%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 13.303 14.002 to 14.256 14.002
%
% arrow head
%
\plot 14.002 13.938 14.256 14.002 14.002 14.065 /
%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 12.224 14.669 11.843 14.161 /
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 12.414 14.669 12.795 14.161 /
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 11.843 14.129 to 11.843 13.684
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\putrule from 12.795 14.161 to 12.795 13.684
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 12.700 13.399 12.351 12.922 /
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\plot 12.890 13.399 13.271 12.859 /
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 10.128 12.732
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KV$} [lB] at 10.128 13.367
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KV$} [lB] at 10.128 14.637
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 10.763 15.272
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 10.128 14.002
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KV$} [lB] at 11.176 14.002
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 11.176 13.367
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{rm}Database consisting } [lB] at  5.524 11.843
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{rm}About 2.5 Million} [lB] at 14.478 11.843
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{rm}classified positions} [lB] at 14.446 11.176
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{rm}of ca.~60,000 games} [lB] at  5.556 11.208
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 11.684 14.637
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KG$} [lB] at 12.636 12.732
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KU$} [lB] at 11.748 12.732
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KU$} [lB] at 12.224 13.367
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{rm}$\KU$} [lB] at 12.224 14.002
%
% Fig TEXT object
%
\put{\SetFigFont{11}{13.2}{rm}Game tree} [lB] at 10.922 11.525
\linethickness=0pt
\putrectangle corners at  5.524 15.780 and 17.431 11.176
\endpicture}
\section{Statistical Feature Combination}

The formal basis of statistical feature combination for position evaluation 
can be stated as follows:
%
%
\begin{itemize}
\item
$\Omega$ is the set of positions to evaluate.
%
%
\item $Y:\Omega \rightarrow \{\CL,\CW\}$ classifies positions
as a loss or win for the player to move,\\
assuming optimal play by both sides.
%
Draws can be handled in the manner\\outlined in Section 4.
%
%
\item $X_1,\ldots,X_n : \Omega \rightarrow \Reell$ are the features.
%
%
\item
The evaluation of a position $\omega \in \Omega$ with $\bx =
(X_1,\ldots,X_n)(\omega)$ is the con-\\
ditional winning probability
%
$$ V(\omega) = P(Y = \CW \mid (X_1,\ldots,X_n) = \bx) =: P(\CW \mid
\bx).$$
%
%
\item There are $N$ classified example positions 
$\omega_1,\ldots,\omega_N \in \Omega$ available with\\
$\bx_i = (X_1,\ldots,X_n)(\omega_i)$ and $y_i = Y(\omega_i)$.
\end{itemize}

\def\bbeta{\mbox{\boldmath$\beta$}}
\def\bmu{\mbox{\boldmath$\mu$}}
\def\bSigma{\mbox{\boldmath$\Sigma$}}
\def\bDelta{\mbox{\boldmath$\Delta$}}
\def\bpi{\mbox{\boldmath$\pi$}}
\def\bq{\mbox{\boldmath$q$}}
\def\bx{\mbox{\boldmath$x$}}
\def\by{\mbox{\boldmath$y$}}
\def\bz{\mbox{\boldmath$z$}}
\def\bX{\mbox{\boldmath$X$}}
\def\bH{\mbox{\boldmath$H$}}
%
\def\ds{\displaystyle}


\no
In the following subsections models which express $P(\CW \mid \bx)$ as
a function of linear or quadratic feature combinations are briefly
introduced in a way that is sufficient for practical purposes.
%
Good introductions and further theoretical details are given for
instance by Duda \& Hart (1973), Hand (1981), Agresti (1990), and
McCullagh \& Nelder (1989).
%
Both Fisher's classical method and logistic regression are used here
to model $P(\CW \mid \bx)$ for the first time; the quadratic
discriminant function has been used by Lee \& Mahajan (1988), however,
without considering Fisher's discriminant first.
%


\input discrim
\input logit
\section{Parameter Estimation and Playing Strength Comparison}

\no
Although only about 5\% of the example positions were labelled as
drawn, it was decided to use them for parameter estimation since these
positions give exact information about feature balancing.
%
A natural way to handle drawn positions within the statistical
evaluation framework considered here is to define the winning
probability to be $1/2$ in this case.
%
For this extension the logistic regression parameters can easily
determined by setting $y_i = n_i/2$ in case of a draw.
%
Alternatively, doubling won or lost positions and incorporating drawn
positions once as won and once as lost leads to the same estimate
because both log likelihood functions are equal up to a constant
factor.
%
The latter technique was used for fitting the other models.
 
Previous experiments showed that the parameters depend on the game
phase, for which disc count is an adequate measure in Othello.
%
So the example positions were grouped according to the number of discs
on the board, and adjacent groups were used for parameter estimation
in order to smooth the data and to ensure almost equal numbers of won
and lost positions.

The success of the Othello program {\sf BILL} described by Lee \&
Mahajan (1990) shows that in Othello table--based features can be
quite effective.
%
For instance, the important edge structure can be quickly evaluated by
adding four pre--computed edge evaluations which are stored in a
table.
%
All 13 features used by {\sf LOGISTELLO} are table--based. They fall
into two groups: in the first group pattern instances including the
horizontal, vertical, and most diagonal lines of the board are
evaluated while in the second group two mobility measures are
computed.$^5$


After parameter estimation for the three described models, tournaments
between the players {\sf QUAD} (which uses the quadratic discriminant
function for normally distributed 
%
%
\def\zw{\hspace{-0.3cm}$-$&\hspace{-0.3cm}}%
%
\begin{table}[h]%
\begin{center}%
%\vspace{-0.6cm}
\small
\begin{tabular}{ccccccc}
\multicolumn{3}{c}{Pairing} & Time per game & Result          & Winning\\
 & &                        & (Minutes) & (Win$-$Draw$-$Loss) & Percentage\\[0.1cm]
\hline\\[-0.1cm]
{\sf LOG}    &\zw {\sf QUAD}   & $30-30$  & $116-15-69$   &   61.8\% \\
{\sf FISHER} &\zw {\sf QUAD}   & $30-30$  & $112-15-73$   &   59.8\% \\
{\sf LOG}    &\zw {\sf FISHER} & $30-30$  & $\,~93-35-72$ &   55.3\% \\[0.2cm]

{\sf LOG}    &\zw {\sf FISHER} & $30-36$  & $\,~86-24-90$ &   49.0\% \\[0.2cm]

{\sf LOG}    &\zw {\sf QUAD}   & $30-38$  & $\,~93-33-74$ &   54.8\% \\
{\sf FISHER} &\zw {\sf QUAD}   & $30-38$  & $\,~84-30-86$ &   49.5\% \\[0.2cm]

{\sf LOG}    &\zw {\sf QUAD}   & $30-45$  & $\,~88-26-86$ &   50.5\% \\
\end{tabular}%
\end{center}
\vspace{-0.4cm}
\caption[tabres1]{Tournament results}%
\vspace{-0.4cm}
\label{tabres1}%
\end{table}
%
features), {\sf FISHER}, and {\sf LOG} were played in order to
determine the best tournament player.
%
Starting with 100 nearly even opening positions with 14 discs
(i.e.~before move 11) from {\sf LOGISTELLO}'s opening book, each game
and its return game with colours reversed was played.%
%
\footnote{%
{\sf LOG}'s 11--ply evaluation of these positions lies in the range
$[-0.4,+0.4]$ which corresponds to winning probabilities in the range
$[0.4,0.6]$.
%
Only nearly even starting positions should be used to compare programs
of similar playing strength since in clear positions the colour
determines the winner and the winning percentage would be 50\% even if
one player is stronger.
% 
Of the 100 starting positions only six always led to game pairs with a
balanced score.}%
%
%
\,\,In the opening and midgame phase all program versions performed their
usual iterative deepening NegaScout searches (Reinefeld, 1983) with a
selective corner quiescence search extension.
%
Endgame positions with about 22 empty squares were solved by
win--draw--loss searches.
%
There was no pattern learning during the tournaments, and the facility
to think on opponent's time was turned off in order to speed up the
tournaments which were run in parallel on seven SUN SPARC--10
workstations.


Applying a conservative statistical test$^5$ it can be seen that all
results listed in Table~\ref{tabres1} stating a winning percentage
greater than 59\% are statistically significant at the 5\% level.
%
The first two results show a clear advantage for the li\-near combinations 
under normal tournament conditions (30 minutes per player per game). 
%
Furthermore, since {\sf LOG} outperforms {\sf FISHER} the features
would not seem to be even approximately normally distributed.
%
Here lies the advantage of logistic regression:
%
even very discrete features like castling status in
chess or parity in Othello can be used.


Further tournaments were played with more time for the weaker players 
{\sf FISHER} and {\sf QUAD} in order to determine the time factors which 
lead to an equal playing strength.
%
As shown in Table~\ref{tabres1} {\sf FISHER} reaches {\sf LOG}'s strength
if it is given about 20\% more time, and {\sf QUAD} needs about 50\% more 
time to compete with {\sf LOG}.
%
With {\sf LOGISTELLO}'s optimized implementation, the search speed when using
the quadratic combination is still about 20\% slower than that with the linear
combination.
%
Thus, giving {\sf QUAD} 25\% more time $(1/(1-0.2)=1.25)$ balances the total
number of nodes searched during a game.
%
But even with this timing, {\sf LOG} is stronger than {\sf QUAD}, 
and {\sf FISHER} can still compete with it.
%
All in all, the quadratic combination is not only slower than the linear 
combination, but it also has no better discrimination properties.
%
Indeed, a look at the estimated covariance matrices of each class revealed 
that they are almost equal, and therefore a better evaluation quality than
that of Fisher's linear discriminant could not be expected.
\subsection{Discriminant Functions for Normally Distributed Features}

\no
Bayes' rule gives
%
%
%
\vspace{-0.2cm}
\begin{eqnarray*}
P(\CW \mid \bx) 
& = & { 
     {p(\bx \mid \CW) P(\CW) } 
       \over
     {p(\bx)}
   }
~ = ~ { 
     {p(\bx \mid \CW) P(\CW) } 
       \over
     {p(\bx \mid \CW) P(\CW) } + {p(\bx \mid \CL) P(\CL) }
   }\\[0.2cm]
& = &
     \left( 1 + {{ p(\bx \mid \CL) P(\CL)} \over { p(\bx \mid \CW) P(\CW)}} \right)^{-1},
\end{eqnarray*}
%
%
%
\no
where $p(\bx \mid C)$ is the features' conditional density function and $P(C)$ is
the a priori probability of class $C \in \{ \CL, \CW \}$.
%
In the case that the a priori probablities are equal, and the features 
are multivariate normally distributed within each class, i.e.\
%
%
%
$$
  p(\bx \mid C) = (2\pi)^{-n/2} |\bSigma_C|^{-1/2} 
         \exp\!\Big\{\!-\!{\textstyle{1 \over 2}} (\bx - \bmu_C) \bSigma_C^{-1} (\bx - \bmu_C)' \Big\}
$$
%
%
%
with mean vector $\bmu_C$ and covariance matrix $\bSigma_C$ for 
$C \in \{ \CW, \CL \}$, it follows
%
%
$$ P(\CW \mid \bx) = { 1 \over { 1+ \exp(- f(\bx))}},$$
%
%
%
where $f$ is the following quadratic discriminant function:
%
%
%
\begin{eqnarray*}
f(\bx) & = &
%     -{\textstyle{ 1 \over 2}} \Big\{
%        (\bx - \bmu_\CW) \bSigma_\CW^{-1} (\bx - \bmu_\CW)' -
%        (\bx - \bmu_\CL) \bSigma_\CL^{-1} (\bx - \bmu_\CL)' +\\
%       &   &
%         ~~~~~\log |\bSigma_\CW| -
%         \log |\bSigma_\CL|
%     \Big\}\\
%       & = &
     -\Big\{
	{\textstyle{ 1 \over 2}} 
        \bx \Big(\bSigma_\CW^{-1} - \bSigma_\CL^{-1} \Big) \bx'+
	\Big(\bmu_\CL \bSigma_\CL^{-1}  - \bmu_\CW \bSigma_\CW^{-1}\Big) \bx'+\\
       &   &
    ~~~~~{\textstyle{ 1 \over 2}} \Big(\bmu_\CW \bSigma_\CW^{-1} \bmu_\CW' -
	 \bmu_\CL \bSigma_\CL^{-1} \bmu_\CL' + 
	 \log |\bSigma_\CW| - \log |\bSigma_\CL| \Big)
     \Big\}.
\label{eqnQUAD}
\end{eqnarray*}

\no
If the covariance matrices are equal $(=\!\!\Sigma)$, the expression can be
simplified to a linear function:
%
%
%
\begin{eqnarray*}
\label{eqnFISHER}
%
f(\bx) & = &
  (\bmu_\CW - \bmu_\CL) \bSigma^{-1} \{ \bx - (\bmu_\CL + \bmu_\CW)/2 \}'.
%
\end{eqnarray*}
%
%
%
%  diskrim 
%
\begin{figure}[t]
%
\begin{center}%
\def\MinAnz@{-6}
\def\MaxAnz@{6}
\def\MinAnzS@{-6}
\def\MaxAnzS@{6}
\def\SkipAnz@{4}
\def\SkipAnzD2@{2}
%
\def\MinPar@{0}
\def\MaxPar@{1}
\def\SkipPar@{0.5}
\def\SkipParD2@{8}
%
%
%
\parbox{10cm}{%
%
\newbox{\boxv}
\newbox{\boxg}
%
\savebox{\boxv}{\tiny $\CL$}
\savebox{\boxg}{\tiny $\CW$}
%
\beginpicture
\setcoordinatesystem units <0.58cm,3cm>
%
\setplotarea x from \MinAnzS@ to \MaxAnzS@, y from \MinPar@ to \MaxPar@ 
\axis bottom label {\small $x$}
 ticks withvalues $\mu_{\usebox{\boxv}}$ $\mu_{\usebox{\boxg}}$ / from -1 to 1 by 2 /
\axis left %label {$p(x | C)$}
 ticks numbered from \MinPar@ to \MaxPar@ by \SkipPar@ /
%
\setsolid
\setquadratic
%
%\beginpicture
%\setcoordinatesystem units <0.58cm,3cm>
%
%\setplotarea x from \MinAnzS@ to \MaxAnzS@, y from \MinPar@ to \MaxPar@ 
%\axis bottom label {\small$x$}
% ticks withvalues $\mu_\CL$ $\mu_\CW$ / from -1 to 1 by 2 /
%\axis left %label {\small$P(\CW\mid x)$}
% ticks numbered from \MinPar@ to \MaxPar@ by \SkipPar@ 
%/
%
%
\plot -6 0
    -5.5 0
      -5 0.002
    -4.5 0.004
      -4 0.008
      -3 0.054
      -2 0.243 
      -1 0.4
       0 0.243
       1 0.054
       2 0.008
     2.5 0.004
       3 0.002 
     3.5 0 
       4 0
       5 0
       6 0 /
%
\plot -6 0
      -5 0
      -4 0
    -3.5 0
      -3 0.002
    -2.5 0.004
      -2 0.008
      -1 0.054
       0 0.243 
       1 0.4
       2 0.243
       3 0.054
       4 0.008
     4.5 0.004
       5 0.002
     5.5 0
       6 0 /
%
%
\plot -6 0.005  -5 0.01  -4 0.02 -3 0.05  -2 0.12  -1 0.27  
       0 0.5  
       1 0.73  2 0.88  3 0.95  4 0.98  5 0.99  6 .995 /
%
%
%
\endpicture%
}\end{center}
\vspace{-0.5cm}
\caption[abb_pxdis]{Conditional densities and winning probability~~~}
\label{abb_pxdis}
%
%
\end{figure}
%
%
%
$\!$Interestingly, this function is also a solution to the problem of
finding a li\-near transformation which maximizes the ratio of the
squared sample mean distance to the sum of the within--class sample
variances after transformation.
%
Therefore, it has good separator properties even if the features are
not normally distributed.
%
This is called Fisher's linear discriminant.
%
Figure~\ref{abb_pxdis} illustrates the relation between the
conditional densities and the winning probability.

The maximum likelihood (ML) parameter estimates are
%
%
\begin{eqnarray*}
 \hat{\bmu}_C     & = & { 1 \over {|I_C|}} 
	\sum_{i \in I_C} \bx_i\\
 \hat{\bSigma}_C  & = & { 1 \over {|I_C|}} 
	\sum_{i \in I_C} (\bx_i-\hat{\bmu}_C)' (\bx_i-\hat{\bmu}_C)\\
\end{eqnarray*}

\vspace{-0.2cm}

\no
with $I_C = \{ i \mid y_i = C\}$. If the covariance matrices are equal, 
%
%
%
$$
 \hat{\bSigma}    =  { 1 \over {|I_\CW|+|I_\CL|}} 
	\sum_{C \in \{\CL,\CW\}}
	  \sum_{i \in I_C} (\bx_i-\hat{\bmu}_C)' (\bx_i-\hat{\bmu}_C).
$$
%


\vspace{-0.2cm}

\section{Discussion}

In this paper three statistical approaches for modelling evaluation
functions with a game--phase--independent meaning have been presented
and compared empirically using a world--class Othello program.
%
Quadratic feature combinations do not necessarily lead to stronger
programs than linear combinations since the evaluation speed can drop
significantly.
%
Of course, this effect depends on the number of features used and
their evaluation speed:
%
if only a few features are used or if it takes a long time to evaluate
them, then the playing strength differences cannot be explained by
different speeds because in this case the evaluation times are almost
equal.
%
In any case, before using quadratic combinations the covariance
matrices should be compared; if they are (almost) equal, the quadratic
terms can be omitted and Fisher's linear discriminant can be used.
%
Therefore, the motivations of Lee \& Mahajan (1988) need refinement,
since an existing feature correlation does not necessarily justify the
use of nonlinear combinations.
%
Generally, possibly more accurate nonlinear feature combinations (such as
ANNs) should be compared to simpler but faster approaches {\em in
practice}, since their use does not always guarantee a greater playing
strength.

Besides linear regression and discriminant analysis, logistic
regression has proven to be a suitable tool for the construction of
evaluation functions with a global interpretation.
%
The drawback, that for parameter estimation a system of nonlinear
equations has to be solved, is more than compensated for by the higher
quality of the evaluation function in comparison to the other
approaches, since in this application the parameters have to be
determined only once.
%
The current tournament version of {\sf LOGISTELLO} uses feature
weights estimated by means of logistic regression and profits from the
comparability of evaluations from different game phases which is
ensured by the use of value adaptation.
%
As a result it is possible to perform selective searches in which
values from different game phases are compared; moreover, values from
the opening can be compared even with late midgame values in order to
find promising move alternatives in the program's opening book (Buro
1994,1995).
%
In this sense, value comparability is a cornerstone of {\sf
LOGISTELLO}'s strength.
	
\vspace{-0.3cm}

\acks{

\vspace{-0.7cm}

\no
I wish to thank my wife Karen for competently answering many of my
statistical questions.
%
I also thank my colleague Igor \Durdanovic\ for many fruitful
discussions which have led to considerable improvements of our Othello
programs.
%
Furthermore, I am grateful to Colin Springer, Richard E.~Korf, and the
anonymous referees for their useful suggestions on earlier versions of
this paper, which helped improve both the presentation and the
contents.}

\section{Generation and Classification of Example Positions}

\no
Value adaptation requires labelled example positions.
%
Here, some problems arise.
%
First of all, for most nontrivial games only endgame positions can be
classified correctly as won, drawn, or lost; for opening and midgame
positions optimal play is out of reach due to the lack of game knowledge
and time constraints.
%
Furthermore, the example positions should contain significant feature variance
since otherwise no discrimination is possible.
%
Hence, it is problematic to use only high level games --- which might be the
first idea --- since good players and programs know the relevant features 
and try to maximize them during a game.
%
Therefore, these features tend to be constant most of the time
and statistical methods would assign only small weights to them.
%
As a final difficulty, estimating parameters accurately for different game
phases requires many positions.


A pragmatic ``solution'' to these problems is indicated in 
Figure~\ref{fig_class}:
%
over a period of two years, about 60,000 Othello games%
%
\footnote{The game file can be obtained via anonymous ftp.\\
(\verb+ftp.uni-paderborn.de/unix/othello/misc/database.zip+)}
%
were played by early versions of {\sf LOGISTELLO} and Igor
\Durdanovic's program {\sf REV}.\footnote{A brief description of both
programs is given in the help pages of the Internet Othello Server.\\
(\verb+telnet faust.uni-paderborn.de 5000+)}
%
Feature variance was ensured by examining all openings of length seven
which led mostly to unbalanced starting positions.
%
Since early program versions were used which had only 5--10 minutes
thinking time, the games, though well played most of the time, are not
error free.
%
In some cases even big mistakes occurred in which, for example, one
side fell into a corner losing trap\footnote{In its implications this
can be compared with losing material for nothing in chess.} caused by
a lack of look--ahead.
%
But without these errors, no reasonable weight estimation of principal
features (such as corner possession in Othello) is possible as
explained above.
%
Following Lee \& Mahajan (1988), all positions were then classified by
the final game results.
%
This approach is problematic 
%
%
%
\begin{figure}[h]
\def\KG{\CW}
\def\KV{\CL}
\def\KU{\CD}
\vspace{-0.2cm}
\begin{center}
\input class.pictex
\end{center}
\vspace{-10pt}
\caption[fig_class]{The classification process~~~}
\label{fig_class}
%
%
\end{figure}
%
because the classification reliability decreases
>from the endgame to the opening phase due to player mistakes.
%
To reduce this effect, early outcome searches were performed for solving
Othello positions 20 moves before game end.
%
%
Furthermore, from time to time the game database was searched for
``obvious'' errors using new program versions and longer searches to
correct these games.
%
Since in this process many lines of play were repeated, the
misclassification rate was further reduced by propagating the game
results from the leaves to the root of the game--tree, which had been
built from all games according to the NegaMax principle.
%
In this way the classification of a position depends on that of {\em all} 
examined successors and is therefore more reliable.


The proposed classification method is relatively fast and allows us to label 
many positions in a reasonable time 
(on average about 42 new positions in 10--20 minutes). 
%
In addition to ensuring an accurate parameter estimation even for
different game phases (which is indicated by small parameter
confidence intervals), this method enabled us to develop new pattern
features for Othello based on estimating the winning probability
conditioned upon occurrence of sub--configurations, like edge or
diagonal instances, of the board.%
%
\footnote{Details are given by Buro (1994). The postscript file of
this thesis can be obtained via anonymous ftp.}
%
% LaTeX-File (4.95)
%
%  Michael Buro:
%  
%      Statistical Feature Combination for the
%           Evaluation of Game Positions
%
%
%  Article submitted to JAIR (4/95)
%


% LaTeX definitions
%
\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file


% macros

\input prepictex
\input pictex
\input postpictex
\input makros


% sizes

%\setlength{\textwidth}{16cm}            
%\setlength{\textheight}{23cm}
%\setlength{\topmargin}{-1.05cm}
%\setlength{\oddsidemargin}{-0.04cm}     % = distance - 2.54cm
%\setlength{\evensidemargin}{-0.04cm}



% misc.

\renewcommand{\bottomfraction}{1}	
\renewcommand{\topfraction}{1}		

\def\CW{{\cal W}}
\def\CD{{\cal D}}
\def\CL{{\cal L}}
\def\bx{\mbox{\boldmath$x$}}

\def\d{d\kern -0.32em\raise 0.63ex \hbox{-}\kern-0.051ex \hbox{}}
\def\D{D\kern -0.7em \raise 0.26ex \hbox{-}\kern 0.829ex \hbox{}}
\def\c{\'c}

\def\Durdanovic{\D ur\d ano\-vi\c}

% xfig-Quatsch

\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup



\begin{document}

\input titleabs
\vspace{-0.15cm}
\input intro
\input combi
\input examples
\input comp
\input discuss
\input ref

\end{document}
\section{Introduction}

Programs playing games like chess, draughts, or Othello use evaluation
functions to estimate the players' winning chances in positions at the
leaves of game--trees.
%
These values are propagated to the root according to the NegaMax
principle in order to choose a move in the root position which leads
to the highest score.
%
Normally, evaluation functions combine features that measure
properties of the position correlated with the winning chance, such as
material in chess or mobility in Othello.
%
Most popular are quickly computable linear feature combinations.
%
In the early days of game programming, the feature weights were chosen
intuitively and improved in a manual hill--climbing process until
the programmer's patience gave out.
%
This technique is laborious.
%
Samuel (1959,1967) was the first to describe a method for automatic
improvement of evaluation function parameters.
%
Since then many approaches have been investigated.
%
Two main strategies can be distinguished:
%
%
\begin{description}
\item[Move adaptation:]
Evaluation function parameters are tuned to maximize the frequency
with which searches yield moves that occur in the lists of moves
belonging to training positions.
%
The idea is to get the program to mimic experts' moves.

\item[Value adaptation:]
Given a set of labelled example positions, parameters are determined
such that the evaluation function fits a specific model.
%
For instance, evaluation functions can be constructed in this way to
predict the final game result.
%
\end{description}
%
\no
In move adaptation, proposed for instance by Marsland
(1985), v.d.~Meulen (1989), and Mysliwietz (1994), a linear feature
combination has two degrees of freedom: it can be multiplied by a
positive constant and any constant can be added to it without changing
the move decision.
%
If the evaluation function depends on the game phase, and positions
>from different phases are compared (for example within the framework
of selective extensions or opening book play), these constants must be
chosen suitably.
%
Because evaluation functions optimized by move adaptation for the
moment have no global interpretation, a solution of this problem is
not obvious.
%
Schaeffer et~al.~(1992) presented an {\em ad hoc} and game--specific approach.


In this respect, value adaptation is more promising.
%
Here, evaluations from different phases are comparable if the example
position labels have a phase--independent meaning.
%
Mitchell (1984) labelled Othello positions occurring in a game with
the final game result in the form of the disc differential and tried to
approximate these values using a linear combination of features.
%
Since a regression was used to determine the weights, it was also
possible to investigate the features' statistical relevance.
%
Another statistical approach for value adaptation was used by Lee \&
Mahajan (1988):
%
example positions were classified as a win or loss for the side to
move and --- assuming the features to be multivariate normal --- a
quadratic discriminant function was used to predict the winning
probability.
%
This technique ensures the desired comparability and applies also to
games without win degrees, i.e.~that only know wins, draws, and losses.

Besides these classical approaches which heavily rely on given 
feature sets, in recent years artificial neural networks (ANNs)
have been trained for evaluating game positions.
%
For instance, Moriarty \& Miikkulainen~(1993) used genetic algorithms
to evolve both the topology and weights of ANNs in order to learn
Othello concepts by means of tournaments against fixed programs.
%
After discovering the concept of mobility, their best 1--ply
ANN--player was able to win 70\% of the games against a 3--ply
brute--force program that used an evaluation function without mobility
features.
%
The most important contribution in this field is by Tesauro
(1992,1994,1995).
%
Using temporal difference learning (Sutton, 1988) for updating the
weights, his ANNs learned to evaluate backgammon positions at master
level by means of self--play.
%
Tesauro conjectured the stochastic nature of backgammon to be
responsible for the success of this approach.
%
Though several researchers obtained encouraging preliminary results
applying Tesauro's learning procedure to deterministic games, this
work has not yet led to strong tournament programs for tactical games
such as Awari, draughts, Othello, or chess, that allow deep searches
and for which powerful and quickly computable evaluation functions are
known.
%
It might be that due to tactics for these games more knowledgeable but
slower evaluation functions are not necessarily more accurate than
relatively simple and faster evaluation functions in conjunction with
deeper searches.


In what follows, three well--known statistical models --- namely the
quadratic discrimination function for normally distributed features,
Fisher's linear discriminant, and logistic regression --- are
described for the evaluation of game positions in the context of value
adaptation.
%
Thereafter, it is shown how example positions for parameter estimation
were generated.
%
Finally, the playing strengths of three versions of a world--class
Othello program\footnote{Since its appearance in October 1993 it 
won twelve of the 14 international tournaments it played.} --- {\sf
LOGISTELLO} --- equipped with the resulting evaluation functions are
compared in order to deter\-mine the strongest tournament player.
%
It turns out that quadratic feature combinations do not necessarily
lead to stronger programs than linear combinations, and that logistic
regression gives the best results in this application.
\subsection{Logistic Regression}

In logistic regression the conditional winning probability 
$P(\CW \mid \bx)$ depends on a linear combination of the $x_i$.
%
Here, $X_1 \equiv 1$ is assumed in order to be able to model
constant offsets.
%
The simple approach $P(\CW \mid \bx) = \bx \bbeta$ using a parameter column
vector $\bbeta$ is unusable because $\bx \bbeta \in [0,\!1]$ cannot be 
guaranteed generally.
%
This requirement can be fulfilled by means of a link--function
$g: (0,\!1)\rightarrow \Reell$  according to $g(P(\CW \mid \bx)) = \bx \bbeta$. 
%
Figure~\ref{abb_px} shows a typical nonlinear relation 
between the winning probability and one feature.
%
%  logit 
%
\begin{figure}[b]
%
\begin{center}%
\def\MinAnz@{-6}
\def\MaxAnz@{6}
\def\MinAnzS@{-6}
\def\MaxAnzS@{6}
\def\SkipAnz@{4}
\def\SkipAnzD2@{2}
%
\def\MinPar@{0}
\def\MaxPar@{1}
\def\SkipPar@{0.5}
\def\SkipParD2@{8}
%
%
%
\parbox{10cm}{%
\beginpicture
\setcoordinatesystem units <0.58cm,3cm>
%
\setplotarea x from \MinAnzS@ to \MaxAnzS@, y from \MinPar@ to \MaxPar@ 
\axis bottom label {\small$x$} /
\axis left label {\small$P(\CW\mid x)$}
 ticks numbered from \MinPar@ to \MaxPar@ by \SkipPar@ 
/
%
\setsolid
\setquadratic
%
\plot -6 0.005  -5 0.01  -4 0.02 -3 0.05  -2 0.12  -1 0.27  
       0 0.5  
       1 0.73  2 0.88  3 0.95  4 0.98  5 0.99  6 .995 /
%
\endpicture%
}\end{center}
\vspace{-0.5cm}
\caption[abb_px]{Typical shape of the winning probability~~~}
\label{abb_px}
\end{figure}
%
%
Since the probability is usually a monotone increasing function of the
features, $g$ should satisfy $\lim_{x \rightarrow 0+} g(x) = -\infty$ and
$\lim_{x \rightarrow 1-} g(x) = +\infty$.
%
The link--function $g(t) = \mbox{logit}(t) := \log(t/(1-t))$ has these
properties.
%
Using $g=\mbox{logit}$, since $g^{-1}(x) = \{1 + \exp(-x)\}^{-1}$, it
follows that
%
$$ P(\CW \mid \bx) = { 1 \over { 1+\exp(- \bx\bbeta)}}. 
$$ 
%
\no
Hence, the winning probability has the same shape as for discriminant 
analysis.
%
But logistic regression does not require the features to be multivariate 
normal; even the use of very discrete features is possible.

Again the parameter vector $\bbeta$ can be estimated using the
ML approach.
%
Unfortunately, in this case it is necessary to solve a system of nonlinear 
equations.
%
In what follows, a known solving approach will be briefly described
(cf.~Agresti, 1990; McCullagh \& Nelder, 1989).

In order to ensure convergence of the iterative algorithm given below, it is
necessary to slightly generalize our model:
%
>from now on $y_i$ is the observed value of random variable
$Y_i = \sum_{j=1}^{n_i} Y_{i,j}$, where the $Y_{i,j}:\Omega\rightarrow\{0,1\}$ have 
mean $\pi_i = \{1+\exp(- \bx_i \bbeta)\}^{-1}$ and are stochastically independent.
%
This definition includes the old model ($n_i=1$ and $y_i\in\{0,1\}$).
%
The likelihood function $L(\bbeta)$, which is a probability density,
measures how likely it is to see the realization $\by$ of the stochastically 
independent random variables $Y_i$, if $\bbeta$ is the true parameter vector.
%
In order to maximize $L$, it suffices to consider $\log(L)$:
%
%
\begin{eqnarray*}
\log(L(\bbeta)) & = &
   \log\!\Big(
      \displaystyle\prod_{i=1}^{N} 
         \pi_i^{y_i} (1-\pi_i) ^{n_i-y_i} 
   \Big) 
~~=~~\sum_{i=1}^{N} y_i \log\pi_i + (n_i-y_i) \log(1-\pi_i)\\
%
%
% & = & \sum_{i=1}^{N} y_i \log\!\Big({\pi_i \over {1-\pi_i}}\Big) + \log(1-\pi_i)\\
%
%
 & = & \sum_{j=1}^{n} \Big(\sum_{i=1}^{N} y_i x_{ij} \Big) \beta_j -
       \sum_{i=1}^{N} n_i \log\!\Big[1+\exp\!\Big(\sum_{j=1}^{n}  x_{ij} \beta_j\Big)\Big].
\end{eqnarray*}


\no
This function is twice differentiable, is strictly concave up to rare
border cases, and has a unique maximum location if $0 < y_i < n_i$ for
all $i$ (cf.~Wedderburn, 1976) that can be iteratively found using the
Newton--Raphson method as follows:
%
$$ \hat{\bbeta}^{(t+1)} = 
    (\bX'\! \bDelta^{\!(t)} \bX)^{\!-1} \bX'\! \bDelta^{\!(t)} \,\bz^{(t)}
$$
%
\no
with
%
\begin{eqnarray*}
%
\bullet & & \mbox{the $(N \times n)$--matrix $\bX$ built from the $\bx_i$,}\\[0.4cm]  
%
\bullet & & \bDelta^{\!(t)} = \mbox{\bf diag}\big[n_i \hat{\pi}^{(t)}_i(1-\hat{\pi}^{(t)}_i)\big],~~
%
\hat{\pi}^{(t)}_i = 
\Big\{1+\exp\!\Big(-\ds\sum_{j=1}^{n}  x_{ij} \hat\beta_j^{(t)} \Big)\Big\}^{-1},~\mbox{and}\\
%
%
\bullet & &
  z^{(t)}_i = \log\!\Big({\hat{\pi}^{(t)}_i \over {1-\hat{\pi}^{(t)}_i}}\Big) + 
          { {y_i - n_i \hat{\pi}^{(t)}_i} \over {n_i \hat{\pi}^{(t)}_i (1-\hat{\pi}^{(t)}_i)} }.
%
%
\end{eqnarray*}



\no
Starting with $\hat{\pi}^{(0)}_i = (y_i + 1/2) / (n_i + 1)$, the ML estimate 
$\hat{\bbeta}$ may usually be computed with high accuracy within a few 
steps since the method is quadratically convergent and relatively robust
with respect to the choice of the starting vector.
%
Unfortunately, if there is an $i$ with $y_i = 0$ or $y_i = n_i$ the 
estimates might not converge.
%
But our original model can be approximated,
for instance, by setting $n_i = 100$ and $y_i = 1$ or $99$, depending
on whether the position in question is lost or won.
%
%This technique also reveals a natural way to incorporate drawn positions for
%parameter estimation by simply defining $y_i = 50$ for these examples.
%\vspace{-0.3cm}

\begin{thebibliography}{}
%
%
%
\def\bibit#1#2#3{%
\item #1.
\newblock #2.
\newblock {\em #3.}
\vspace{-0.05cm}
}

\bibit{Agresti, A.~(1990)}
{Categorical Data Analysis}
{Wiley}

\bibit{Buro, M.~(1994)}
{Techniken f\"ur die Bewertung von Spielsituationen anhand von Beispielen}
{Ph.D.~thesis, University of Paderborn, Germany}\\
\verb+(ftp.uni-paderborn.de/unix/othello/ps-files/mics_dis.ps.gz)+

\def\c#1{\setbox0=\hbox{#1}\ifdim\ht0=1ex \accent'30 #1%
\else{\ooalign{\hidewidth\char'30\hidewidth\crcr\unhbox0}}\fi}

\bibit{Buro, M.~(1995)}
{L'apprentissage des ouvertures chez Logistello}
{Magazine de la F\'ed\'eration Fran{\c c}aise d'Othello FFORUM 37, 18--20}

\bibit{Duda, R., Hart, P.~(1973)}
{Pattern Classification and Scene Analysis}
{Wiley}

\bibit{Hand, D.J.~(1981)}
{Discrimination and Classification}
{Wiley}

\bibit{Lee, K.F., Mahajan, S.\ (1988)}
{A Pattern Classification Approach to Evaluation Function Learning}
{Artificial Intelligence 36, 1--25} 

\bibit{Lee, K.F., Mahajan, S.\ (1990)}
{The Development of a World Class Othello Program}
{Artificial Intelligence 43, 21--36} 

\bibit{Marsland, T.A.~(1985)}
{Evaluation Function Factors}
{ICCA Journal 8(2)}

\bibit{McCullagh, P., Nelder, J.A.~(1989)}
{Generalized Linear Models}
{Chapman \& Hall}

\bibit{van den Meulen, M.~(1989)}
{Weight Assesment in Evaluation Functions}
{In: D.F.~Beal (Editor), Advances in Computer Chess 5, Elsevier Science
Publishers}

\bibit{Mitchell, D.H.~(1984)}
{Using Features to Evaluate Positions in Experts' and Novices' Othello Games} {Master Thesis, Northwestern University, Evanston Illinois U.S.A} 

\bibit{Moriarty, D., Miikkulainen, R.~(1993)}
{Evolving Complex Othello Strategies Using Marker--Based Genetic
Encoding of Neural Networks}
{Tech.~rep.~AI93--206, Department of Computer Sciences, University of
Texas at Austin}

\bibit{Mysliwietz, P.~(1994)}
{Konstruktion und Optimierung von Bewertungsfunktionen beim Schach}
{Ph.D.~thesis, University of Paderborn, Germany}

\bibit{Reinefeld, A.~(1983)}
{An Improvement of the Scout Tree Search Algorithm}
{ICCA Journal 6(4), 4--14}

\bibit{Samuel, A.L.~(1959)}
{Some Studies in Machine Learning Using the \mbox{Game} of Checkers}
{IBM Journal of Research and Development 3, 210--229}

\bibit{Samuel, A.L.~(1967)}
{Some Studies in Machine Learning Using the \mbox{Game} of Checkers II}
{IBM Journal of Research and Development 11, 601--617}

\bibit{Schaeffer, J., Culberson, J., Treloar, N., Knight, B., Lu, P., Szafron, D.~(1992)}
{A World Championship Caliber Checkers Program} 
{Artificial Intelligence 53, 273--289}

\bibit{Sutton, R.S.~(1988)}
{Learning to Predict by the Methods of Temporal Differences}
{Machine Learning 3, 9--44}

\bibit{Tesauro, G.~(1992)}
{Practical Issues in Temporal Difference Learning}
{Machine Learning 8, 257--277}

\bibit{Tesauro, G.~(1994)}
{TD--Gammon, A Self--Teaching Backgammon Program, Achieves
Master--Level Play}
{Neural Computation 6, 215--219}

\bibit{Tesauro, G.~(1995)}
{Temporal Difference Learning and TD--Gammon}
{Communications of the ACM 38(3), 58--68}

\bibit{Wedderburn, R.W.M.~(1976)}
{On the Existence and Uniqueness of Maximum Likelihood Estimates for Certain
Generalized Linear Models}
{Biometrika 63, 27--32}

\end{thebibliography}\jairheading{3}{1995}{373-382}{7/95}{12/95}
\ShortHeadings{Statistical Feature Combination}
{Buro}
\firstpageno{373}


\title{Statistical Feature Combination for the\\Evaluation of Game Positions\vspace{-0.15cm}}

\author{%
\name Michael Buro 
\email mic@research.nj.nec.com\\
\addr NEC Research Institute\\ 
4 Independence Way\\
Princeton NJ 08540 U.S.A.}


\maketitle

\vspace{-0.5cm}

\begin{abstract} 
%
\no
This article describes an application of three well--known statistical 
methods in the field of game--tree search:
%
\mbox{using} a large number of classified Othello positions, feature
weights for evaluation functions with a game--phase--independent
meaning are estimated by means of logistic regression, Fisher's linear
discriminant, and the quadratic discriminant function for normally
distributed features.
%
Thereafter, the playing strengths are compared by means of tournaments
between the resulting versions of a world--class Othello program.
%
In this application, logistic regression --- which is used here for
the first time in the context of game playing --- leads to better results
than the other approaches.
%
\end{abstract} 




