代码之家 › 专栏 › 技术社区 › Aidos

在尽可能少的“参数”中表示双精度的二维映射

neat game-ai neural-network artificial-intelligence

3

Aidos · 技术社区 · 16 年前

我正在使用一种叫做 NEAT .我正试图训练一个可以在二维(x&y坐标)空间中移动的网络,该空间给定了存储在有效二维数组中的各种值。

我可以看到使用神经网络的两种策略:

对于网格中的每个“细胞”,提供来自不同启发式的分数作为神经元的输入,并创建一个实际上是非常复杂的“评分”系统的神经网络。将非播放角色(npc)移动到得分最高的位置。
为每个Heuristic度量创建一个压缩值(以某种方式压缩到尽可能少的位),并为每个度量提供一个输入神经元。

我对选项2很感兴趣,因为它提供了所需的最少的计算量(游戏的运行时间很长),但是我对我可以使用什么方法来创建二维Heuristic值的“小表示”版本感到困惑。我知道有一些技术,比如傅立叶变换,但是我不知道这些是否适合我的问题。基本上,我正在寻找一种将50x50双精度数组转换为一个或两个双精度值的方法。这两个双值可以有损压缩,我不需要能够得到原始值,我只需要一个合理的机制将输入数据更改为一个小的内存占用。

这两种可能性的另一种选择是根据与npc的距离对“区域”进行某种编码(因此,您可以得到“近”单元格的实际值,以及“远”单元格的近似值)。我不知道该如何将其连接起来,但它至少消除了在游戏的每一轮中评估每个单元的需要(考虑到我每轮大约1秒查看500万个回合,我能想到的任何简化都将大有帮助)。

如果这没什么意义的话,我很抱歉,这是一个困扰了我一段时间的难题,我想不出一个简单的方法来描述它。

谢谢你,

艾丹

编辑以添加(并更改标题):

多亏了克里斯,我们改进了我要找的东西。我要寻找的是一种方法,以尽可能少的参数来近似一条线(我可以将二维地图转换为一条线)。我以前用过三次样条插值,但是我需要一个更有效的数据集,它在0.0和1.0之间变化很大。我正在寻找的是地图的“散列图”。

我知道有一些技术,如三次样条曲线,我可以从中找出一些“关键点”,这些值是我所寻找的一个合理的类比。我需要一种方法来获取2500个值,并提出这些值的一个小的表示,我可以用于神经网络。我认为神经网络可以被训练来推断这些表示的真正意义,或者至少确定表示和现实世界之间的某种相关性,因此它不一定是可逆函数,但我认为许多单向函数(如MD5、SHA)实际上也不会非常有帮助…

2 回复 | 直到 15 年前

1

2

Chris Upchurch 16 年前

基本上,任何图形压缩算法都会满足您的需要。它们经过了大量优化,可以将二维数字阵列压缩到尽可能小的占地面积中。

编辑添加:

另一个需要考虑的问题是,由于您希望使用压缩来减少处理时间,因此获得真正高的压缩比通常需要更多的计算来压缩和解压缩数组。你可能会遇到这样的情况:比起运行神经网络,你花费更多的时间压缩和解压缩数组。

再次编辑以添加:

根据你的评论,听起来你可能想要的是 space-filling curve . 使用曲线将50x50*数组转换为1x2500行,然后得出一个公式,该公式近似于数组中每个单元格所需的值。

*数组必须是50x50吗?如果空间填充曲线是一个尺寸稍有不同的正方形,那么用它填充可能会容易得多。例如,希尔伯特曲线适用于二次幂的维度。

2

1

rlbond 16 年前

有一件事你可以尝试的是采取你的1d线的快速傅立叶变换,然后删除稍后(高频)的条款。例如,在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的八度音阶,甚至excel,然后玩类似的游戏,找到最适合你的结果。