Representing a 2D map of doubles in as few "parameters" as possible.

Question

Hi Guys,

I am working on a turn-based-game AI using a neural-network technique known as NEAT. I am attempting to train a network that can move around a two dimensional (X&Y coords) space given a variety of values that are stored in what is effectively a two dimensional array.

I can see two strategies for using the neural network:

1. For each "cell" in the grid, provide the scores from the different heuristics as inputs to neurons and create a NN that is effectively a very complicated "scoring" system. Move the Non Playing Character (NPC) to the location with the highest score.

2. Create a compressed value for each heiuristic measure (somehow compressed into as few bits as possible) and provide an input neuron for each of these measures.

I am quite interested in option two because it presents the least amount of calculations required (the runtime of the game is quite long), however I am confused as to what approach I could use to create the "small representation" version of the two-dimensional heiuristic values. I know there are techniques such as Fourier Transformations out there, however I don't know if these will suit my problem. Basically I am looking for a way to convert a 50x50 array of doubles into one or maybe two double values. These two double values can be lossy-compressed, I don't need to be able to get the original values back, I just need a reasonable mechanism for changing the input data into a small footprint.

An alternative to these two possibilities is to somehow encode a "region" based on some distance from the NPC (so you get the actual values for a "close" cell, and an approximation for a "far" cell). I don't know exactly how I would wire this up, but it at least gets rid of the need to evaluate every cell every turn of the game (given I am looking at about 5 million rounds at approximately 1 second per round, any simplification I can come up with would greatly help).

I apologise if this isn't making much sense, it is quite a difficult problem that has stumped me for a while, and I can't think of an easy way to describe it.

Thankyou,

Aidan

EDITED TO ADD (and change title):

Thanks to Chris we've refined what I am looking for. What I am looking for is a way to approximate a line (I can convert the 2D map into a line) in as few parameters as possible. I have used cubic splines for interpolation before, however I need something a lot more feasable for a data-set that varies between 0.0 and 1.0 quite aggressively. What I am realling looking for I suppose is a "hash" of the map.

I know there are techniques such as cubic splines that I can work out some "key-points" from, and these values are a reasonable analogy for what I am looking for. I need a way to take the 2500 values and come up with a small representation of these values that I can use for the neural network. I think the NN can be trained to infer the true meaning of these representations, or at least to determine some correlation between the representation and the real world, so it doesn't necessarily need to be a reversible function, but I don't think many one way functions (such as MD5's, SHA's) are actually going to be very helpful either...

Answer 1

Basically, any graphics compression algorithm is going to do what you want. They're heavily optimized for compressing 2D arrays of numbers into the smallest possible footprint.

Edited to add:

The other thing to consider, since you're looking to use compression to reduce processing time, is that getting really high compression ratios generally involves more calculation to compress and decompress the array. You may reach a point where you're spending more time compressing and decompressing the array than running the neural network.

Edited again to add:

Based on your comments, it sounds like what you may want is a space-filling curve. Use the curve to turn your 50x50* array into a 1x2500 line and then come up with a formula that approximates the values you want for each cell of the array.

*Does the array have to be 50x50? It may be much easier to fill with a space filling curve if it's a square of slightly different dimensions. The Hilbert curve works nicely for dimensions that are powers of two, for instance.

Answer 2

One thing you can try is taking the FFT of your 1D line and then removing later (high-frequency) terms. For example, in MATLAB I did the following:

x = [1:1000];
y = rand(1,1000);
f = fft(y, 250); % truncate to 250 terms
plot(x,y, x,abs(ifft(f), 1000));

What tended to happen was that the peaks of the iFFT of f were very close to peaks of y. They weren't necessarily the highest points of y, but they were peaks. For instance, this run, there were peaks at x=424, 475, and 725 in the inverted FFT of f, and there were also peaks in y at x=423, 475, and 726. However, y's global max was at x=503, which was a peak in ifft(f), but not a very high one.

However, this only really cuts your data usage in half, because I converted 1000 doubles into 250 complex values. A further increase can be obtained by only using the real part of the FFT:

x = [1:1000];
y = rand(1,1000);
f = real(fft(y, 250)); % only uses 1/4 the space now
plot(x,y, x,abs(ifft(f, 1000)));

This still yielded pretty good results, with each major peak of ifft(f) corresponding to a peak in y that was only at most a distance of 2 away most of the time, and you use 1/4 the space of storing the double directly.

However, this still doesn't get you the results of "one or two double values". You are now packing 2500 doubles into 625. You can experiment by cutting more terms, but you will have to test more values "up close" by cutting more terms. Maybe you can keep the first 10% of terms, and find the maximum, and then look within a distance of 3 or 4; this would reduce your 2500 doubles to a "mere" 250. Only testing will find out what works best for your application.

If you're really desperate, you can go as low as the lowest 1% frequencies, and search 5 or 6 in either direction for the true peak. But this still leaves you with 25 doubles.

I don't think there's any way to convert 2500 doubles into only 1 or 2, and have it reversible into anything meaningful. Take a look at information theory texts to see why. I suggest you get MATLAB, GNU Octave, or even Excel, and play around with something like this and find what results are best for you.