Re: [computer-go] Cellular automata

[Peter Drake <drake@xxxxxxxxxx>]

On Thursday, July 22, 2004, at 12:23  PM, Don Dailey wrote:

> >    Has anyone tried cellular automata as an approach to Go?
> >
> >   Peter Drake
> >   Assistant Professor of Computer Science
> >   Lewis & Clark College
> >   http://www.lclark.edu/~drake/
> I  can't believe  you asked  that question!   I am  in the  process of
> experimenting with something like this.
>
> The idea  is to  have a  limited number of  possible states  that each
> point can have.   The states of course are  determined by the previous
> generations neighboring points.
We thought each point should have a state vector, rather than a single 
number.  This way, a point can keep track of its liveliness, its number 
of liberties, the size of its blocks, whether it matches some 
particular pattern, and so on.  The CA update rule could then take this 
information into account.

If the vector elements are numbers, it might be possible for the CA 
propagation to pass around automatically-generated "tags" to 
distinguish one group (or eye, or whatever) from another.

The previous post mentioned the apparent lack of global understanding 
on behalf of a CA player.  Perhaps some sort of hierarchical structure 
might be in order, where groups or regions of the board have state 
vectors of their own?

To speed up computation, only the cells in the same neighborhood of 
changed cells need by updated on each CA step.  A good rule might, 
hypothetically, not propagate across unconditionally live groups, thus 
reducing the need to update regions of the board that don't change.  
It's not clear how to integrate this with the hierarchical structure 
mentioned above.

> The interesting part is that the rules to  generate a new state will be
> determined using some kind of learning algorithm such as PBIL or GA's.
We were thinking of using Koza's Genetic Programming approach to 
generate the rules.

> The rules to generate a new state might also change from generation to
> generation.  That might add  some flexibility that might not otherwise
> be possible.
>
> Of course I'm probably barking up  the wrong tree, but it's fun to try
> this stuff  anyway.  I'll give you a  report when I'm done  if you are
> interested.
Yes, by all means!

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/

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