用尽可能少的“参数”代表双打的2D地图

Question

我正在使用称为NEAT的神经网络技术开展基于回合的游戏AI。我试图训练一个网络，该网络可以在二维（X & Y coords）空间中移动，并给出存储在实际上是二维数组中的各种值。

我可以看到两个策略使用神经网络：

1. 对于网格中的每个“单元”，提供了从不同的启发式的得分作为输入神经元，并创建一个NN，有效地一个是非常复杂的“评分”系统。将非演奏角色（NPC）移动到得分最高的位置。

2. 为每个启发式度量创建一个压缩值（以某种方式压缩成尽可能少的位），并为这些度量提供一个输入神经元。

我在方案二颇感兴趣，因为它提出了计算所需的最低量（游戏是相当长的运行时间），但我很困惑，我会用什么方式来打造“小表示“版本的二维启发式值。我知道那里有傅立叶变换等技术，但我不知道这些技术是否适合我的问题。基本上我正在寻找一种方法来将50x50的双打数组转换为一个或两个双精度值。这两个double值可以进行有损压缩，我不需要能够获取原始值，我只需要一个合理的机制将输入数据更改为小型足迹。

这两种可能性的替代方法是以某种方式编码一个基于距离NPC一定距离的“区域”（因此您可以获得“关闭”单元的实际值，以及“远”单元的近似值）。我不确切知道如何连接它，但它至少摆脱了在游戏的每一轮都要评估每个单元格的需要（因为我在每轮大约1秒钟内查看大约500万轮，任何简化我可以拿出很大的帮助）。

我很抱歉，如果这没有多大意义，这是一个相当困难的问题，一直困扰着我，我想不出一个简单的方式来描述它。

三江源，

艾丹

编辑补充（并更改标题）：

感谢Chris我们已经精制我所期待的。我正在寻找的是一种用尽可能少的参数近似直线（我可以将二维地图转换为一条直线）的方法。我之前使用三次样条插值进行插值，但是我需要一些更有用的数据集，这些数据集在0.0到1.0之间变化很大。我正在寻找的东西我想是地图的“哈希”。

我知道有一些技术，如三次样条，我可以从中找出一些“关键点”，这些值是我寻找的合理比喻。我需要一种方法来取得2500个值，并拿出这些值的一个小表示，我可以用于神经网络。我认为神经网络可以被训练来推断这些表征的真正含义，或者至少可以确定表示与现实世界之间的某种相关性，所以它不一定需要是可逆函数，但我不认为许多单向函数（如MD5，SHA's）实际上也会非常有用......

Answer 1

基本上，任何图形压缩算法都会做你想做的。它们经过大量优化，可以将2D数组压缩成尽可能小的占位面积。

编辑补充：

其他的事情要考虑，因为你正在寻找使用压缩以减少处理时间，是变得非常高的压缩比通常涉及到更多的计算，压缩和解压缩阵列。与运行神经网络相比，您可能会花费更多时间来压缩和解压缩阵列。

再次编辑补充：

根据您的意见，这听起来像你可能想要的是一个space-filling curve。使用曲线将50x50 *阵列转换为1x2500行，然后提出一个公式，该公式近似于阵列中每个单元所需的值。

*数组是否必须是50x50？如果空间填充曲线的尺寸略有不同，则填充空间填充曲线可能会更容易。例如，希尔伯特曲线很好地适用于两个幂的维度。

Answer 2

你可以尝试的一件事就是对你的一维线进行FFT处理，然后再去掉（高频）项。例如，在MATLAB我做了以下内容：

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

什么往往发生的是，f的IFFT的峰非常接近Y的峰值。它们不一定是y的最高点，但它们是峰值。例如，这次运行中，在f的反向FFT中x = 424,475和725有峰值，在x = 423,475和726处也有y的峰值。然而，y的全局最大值是x = 503，这是ifft（f）的峰值，但不是很高。

但是，这只能将您的数据使用量减半，因为我将1000个双打转换为250个复杂值。进一步增加可以通过只使用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))); 

这仍然取得了不错的成果，与IFFT的每个主要峰（F）对应于为y的峰值也仅仅是在最大部分时间距离为2，而你使用直接存储双倍空间的1/4。

但是，这仍然没有得到“一个或两个双重值”的结果。现在你正在把2500个双打打包成625个。你可以通过削减更多的条款来进行试验，但是你必须通过削减更多的条款来“更近距离”测试更多的价值。也许你可以保持前10％的条件，并找到最大值，然后在3或4的距离内查看;这会将你的2500个双打减少到“仅仅”250个。只有测试才能找出最适合你的应用的东西。

如果你真的真的绝望，你可以低至最低1％的频率，并搜索5或6在任一方向的真正的高峰。但是这仍然让你有25个双打。

我不认为有任何方法可以将2500双打转换为1或2，并且可以将其翻转为任何有意义的东西。看看信息理论文本，看看为什么。 我建议你得到MATLAB，GNU Octave，甚至是Excel，并且玩弄这样的东西，找出最适合你的结果。