> --- In abalone_prog@yahoogroups.com, "Colin Springer" <colin@m...>
> wrote:
> I don't get the initial premise of your argument . "for 1D it is
> easy to update the mass center (agreed), and also the compactness"
> incrementally.

A friend of mine asked the same question. I wrote a few LaTeX lines to
explain the method. I hope they are more clear.



\section{Math}

Let $I$ denote all possible locations. Let $B \subset I$ denote the
locations occupied by friendly pieces. Define $x(i)$ as the x-coordinate
of location $i$. The number of friendly pieces on the board is defined
$n = |B|$.

\subsection{Initial}

Center of mass $c$ and Manhattan distance $m$ is computed.
$$
c = \sum_{i \in B} { x(i) \over n }
$$

$$
m(c) = \sum_{i \in B} | x(i) - c |
$$

Note that $m(c)$ is expressed as a function of $c$. It is desireable to
be able to have a different target point than the center of mass. Werner
found that the average of the black center of mass, the white center
of mass,
and the center of the board worked better. When the computer was
winning, it could gradually decrease the influcence from the center of
the board.

\subsection{Incremental}

The ideas behind incremental computation is:

\begin{itemize}

\item Center of mass is easy to compute incrementally.

\item If $c$ is any variable, the Manhanntan distance $m(c)$ is a
piecewise
linear function, whith breaks every time $c$ corresponds to a location
where
pieces are situated. This will always be integer locations.

\item $m(c)$ can be expressed as $m(\floor{ c }) + \delta m(c)$ where
$\delta m(c)$ is easy to compute incrementally.

\end{itemize}


If moving a piece from $f$ to $t$ the new values $c_2, m_2$ can be
computed from the old $c_1, m_1$.

It is straight forward to compute the new center of mass $c_2$:

$$
c_2 = c_1 + { x(t) - x(f) \over n }
$$

To compute the Manhattan distance, we use the helper variables $s$ and
$w$. The Manhattan distance for point $\floor{c}$ is denoted $s$ and the
slope of $m(c)$ is denoted $w$. Both variables are static most of the
time.

$$
h(x) = | \{ i \in B | x(i) = x \} |
$$
$$
s = m(\floor{c})
\qquad
w = \sum_{x \leq \floor{c} } h(x)
- \sum_{x > \floor{c} } h(x)
$$
$$
m(c) = s + w ( c - \floor{c} )
$$

If $\floor{c_1} \neq \floor{c_2}$ then we must update $s$ and $w$ before
computing $m(c)$. Note that $s_2$ is dependent on $w_2$ if $c_2 <
\floor{c_1}$.

$$
\begin{array}{lll}
s_2 = s_1 + w_1
& w_2 = w_1 - 2 h(\floor{c_1})
& \textrm{if } \floor{c_2} = \floor{c_1} + 1 \\
s_2 = s_1 - w_2
& w_2 = w_1 + 2 h(\floor{c_1})
& \textrm{if } \floor{c_2} = \floor{c_1} - 1 \\
\end{array}
$$