Re: [computer-go] Cellular automata

["chrilly" <chrilly@xxxxxxxx>]

Waldviertel-Hochland, 22.07.2004

>Has anyone tried cellular automata as an approach to Go?
I made a proposal to a FPGA-Board company for a FPGA-based Go programm. The
basic architecture of this programm was a Cellular Automata. The CA fits
very well to the FPGA.
But before the project was decided, I got a very good offer for going on
with my FPGA-based chess project Hydra. The proposal is therefor so far only
a paper-design.

The problem I see is that in some degenerate cases it takes N steps/Cycles
to compute e.g. with the CA approach the liberties of a string. (N is the
number of points on the board). Maybe it is necessary to introduce a
hierarchy similar to the communication-network in parallel machines. This
makes things more complicated and blows up the logic.
But maybe this worst-case-behaviour is no problem at all, because the
mean-time behaviour is much better. There are - especially in a search -
very few long chain-snakes (Do not know it, one has to test this
assumption).

I have run some simulations computing an CA-based influence map. The results
were very promising. But I do not think that CAs are appropriate for a
software implementation.
It is much too slow. But in Hardware one can use the full implicit
parallelism of CAs.
I assume that an FPGA-based design could run with almost. 100MHz. Processing
1 node/position should take in the mean 20 cycles. This would give 5 Million
positions/Sec.

It was not my intention to use an automatic learning approach. It is the
programmer who learns to apply/improve the  CA rules.

Best Regards
Chrilly Donninger



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