Re: [computer-go] Designing faster, better influence functions

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Erik wrote:
> Well, the point is that convolutions in the spatial domain are 
> multiplications in the Fourier domain.

Ok, that's where we differ. I don't consider an influence function
which allows influence to flow through other (living) stones to be
interesting, but as usual it depends on what you want to do with the
influence.

> Multiplications are of course faster. The question is how much time
> extra the FFT /IFFT transforms take.

To begin with multiplication doesn't correspond to convolution in the
discrete case but to circular convolution, so it's absolutely
necessary to pad the board, possibly with reflected stones. The amount
of padding needed depends on type of padding and the size of the
convolution kernel. Second FFT can only be done on sizes which are
composite numbers, the smaller the prime factors the better. Although
there are other choices the power of 2 algorithms are best known so
let's assume that we pad to 32x32. Conventional wisdom says that 2D
FFT has complexity O(N^2*log(N)), but that is not exact enough for our
purposes. I don't have a good reference at hand but pulling from
memory (so this might be wrong) I think at the very least you need
2*N^2*log(N) complex floating point multiplications, which in this
case would amount to 10240. Double this number (FFT + IFFT) and
multiply by 4 to get real multiplications and we have 81920
multiplications. Splitting this by 19x19 leaves us with 227
multiplications per vertex, which should be big enough for almost any
kernel.

Now there may be some optimizations I have missed (e.g. that the
original data is real) and I could be off by some factor in my
recollection. Also hardware optimized implementations may be available
which could completely change the numbers. On the other hand if you
are using convolution to compute influence it would almost certainly
suffice with a Cartesian separable kernel, which means that even for a
very big kernel 30-40 coefficients are enough.

> I'm pretty sure others have already tested this, so I was hoping
> somebody would remember the timing details.

Maybe somebody has, but I wouldn't count on it. Some hard numbers
would be interesting of course.

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