完美的Snake AI

Question

在阅读这个问题之前，请注意，我使用术语AI来描述一个没有从错误中学习的算法，只是一个以高效和智能的方式玩游戏的算法。

在不久前看了this视频后，我决定制作自己的蛇AI。你可以找到它的here (它是几个文件，这就是为什么我不在这里包括它们)。这个人工智能远非完美，现在我想知道什么是蛇游戏的完美人工智能算法。与我的版本不同，Snake的原始版本不包含墙，但如果您的AI算法可以处理它，那就更好了。你的算法必须支持多种尺寸的棋盘，并且食物是随机放置的。对于完美的人工智能，我的意思是一个可以收集所有樱桃/食物而不会死亡的人工智能，而不是一个能够存活足够长时间的人工智能。

Answer 1

找到玩任何游戏的完美算法都很难！

考虑游戏Connect 4。1988年，Victor Allis证明了在完美的游戏条件下，白色总是会赢(如果平局没有结果)。His thesis有91页长。

我玩的蛇游戏，包括多条蛇，以及苹果和其他出现时间有限的物品。

多亏了Giovanni Viglietta (2013)，我们知道收藏品和路径只能被一次遍历(你不能在蛇中穿越自己)是NP-hard问题的特征。Viglietta使用他的技术来展示Boulder Dash，Deflektor，Lemmings，Lode Runner，Mindbender，Pac-Man，Pipe，王子of Persia，Puzzle 3，Skweek，Starcraft和Tron都是硬的(在某种意义上)。

我不知道Snake是否属于这一类，但其结构上的相似性(收藏品，暂时的一次性路径)表明它可能属于这一类。如果是这样，那么除了暴力方法之外，没有有效的(在某种意义上)算法来指导蛇的行为，这对于实时游戏来说太慢了。

因此，如果一个完美的算法是可能的，你应该期待这一点的证明是漫长和复杂的。如果你弄清楚了，你应该获得硕士学位，这可能需要大约两年的时间。

如果问题是NP难的，那么你不太可能喜欢完美的算法，你将不得不放弃你的探索，转而支持启发式或近似算法。