Re: About brute force and knowledge...

[Henrik Rydberg <rydberg@xxxxxxxxxxxxxx>]

A agree with Antii's statement that perfect play probably is
inconcievable even to the best human players. As he points out,
it does rise some hope, too; Just as humans, a good program
should learn to avoid really complex situations, which should
be a quite substantial part of the state-space.

At this point, it would be interesting to make some kind of estimate
of how large that part really is. To answer that question, we first need
a measure of complexity. That measure should be related to Lyuapunov
coefficients in some way, i.e., they should measure how chaotic the
time-evolution of a certain board position is. A simple measure would be
something related to what Bernd Brugmann did in -93, where he used a 
Monte Carlo algorithm to statistically find good moves to play. In his
algorithm, he simply started from the given position, and played random
sequences of moves until the bitter end, according to some simple
criteria.
Then, by counting the stones at the end, he updated the sequence of
moves
played, and by simulated annealing tried to find the best first move.
Now, in such a setup there are much more information available; one
could
for instance measure the *variance* in results emerging from a certain
position. For instance, if after playing lots of different sequences
from
a position one finds a large spread in outcome, it would be a hint that
it
might be hard to find the perfect sequence from that position, hence a
large
complexity. 

The relation of this measure to the Luapunov coefficients requires a
clarification on what state-space we are talking about. Assume that we 
know the sequence of truly perfect play from a certain position, and
know
the outcome of that sequence. A handful of moves might be sufficient.
Also
assume that we can evaluate the new board position exactly. Now assume
we
make a small change to the initial position, for instance by placing the
last stone at some other point. Again assuming perfect play, we might
now
after a couple of moves end up in a completely different position, and
in a
completely different evaluation. The magnitude of the change in those
two
entities, summed over all possible adjustments to the initial position,
would be the Luyapunov coefficients of the position, and the rate of
change
of the evaluation function, correspondingly. Summing over all initial
positions would be the Luyapunov coefficients of the game of Go itself.
A comparison to Chess, for instance would be quite interesting in this
respect. Antii's argument and my own actually indicate, in my opinion,
that Go is *played* less chaoticly than Chess, although the game it self
might not need to be.

Henrik

-- 
Henrik Rydberg (http://fy.chalmers.se/~rydberg),
Department of Applied Physics, Chalmers University of Technology.