Re: [computer-go] Cellular-Automata

["chrilly" <chrilly@xxxxxxxx>]

>
>I might as well throw my two cents in.  It seems like CA, by it's nature,
is
>going to have a hard time with non-local concepts.  How would a CA-based
>engine (I assume it is really just a CA-based evaluation, correct me if I'm
>wrong) take non-local features into account?
>
As already stated by Don Dailey, the info is propagated. E.g. for the
liberties of a string, each stone propagates its own liberty to the
neighbour. And after at least N steps (N= lenght of string) all stones know
the liberty of the string. N steps is  the worst case, usually it is much
faster. The only tricky part is how to avoid double-counting common
liberties.

This progation mechanism works quite well for influence. The influence is
propagated like a wave. The morphing-algorithms can be easily formulated as
a CA. The number of iterations/steps defines how far-reaching the influence
of each stone is.
One can also detect quite reasonable links. The link-distance is the minimum
number of iterations/steps it takes to propagate the "wave" from one group
to the next.

One interesting point is how opponent and own stones influence the
wave-propagation. In the simplest case they are transparent. But a more
realistic model is that opponent stones absorb at least parts of the wave.
Another parameter is, if one considers only waves along the shortest
distance between two points or if later arriving waves are also counted.
Another parameter is the decay-factor of the wave...  Another parameter is
isotropism. E.g. if a wave goes first up, but then to the left/right, is
this the same, as the waves goes one point further up. This question is
important for classifying links. Another point is how to treat the border.
Are all cells equal or have cells near the border another behaviour? Or is
the border itself an own cell-type which sends its waves too?
The number of possibile rules is practically infinite.

For concepts like eyes I think finding good concepts is more difficult. But
there are local measures like e.g. the Euler-Number, which approximate the
concept of eyes reasonable.

In my FPGA-based paper design I wanted to trade some evaluation accuracy for
search speed. The concept of an eye is only approximate, but the fast search
shall find out, if it is really an eye which can live. This delegation of
tasks from the evaluation to the search is quite common in chess. I think it
works to a certain extend also in Go (but not as good as in chess).
Note1: My plan was (and is) to build a massive parallel Go-Programm (at
least 32- maybe even 256-processors). Each processor shall process 5
MPos/sec. The high branching factor of Go is good news for the
parallel-algorithm. There should be a better speedup than in chess. With
this speed a search starts to be interesting.
Note2: I have currently a 16-processor machine available. A 32-processor
machine is under construction, a 256-processor machine is planned. "Only"
the FPGA-Go-programm is missing. The current sponsor is only interested in
chess, but not in Go. He did not even know the game.

Best Regards
Chrilly Donninger


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/