蛇游戏人工智能

Question

我正在为iOS开发一个贪吃蛇游戏：https://github.com/ScottBouloutian/Snake

我的目标是让AI以最佳方式完成蛇的游戏（让蛇填满棋盘）。

我正在使用IDA*找到一条从蛇当前位置到食物的路径。这是有效的。然而，该算法没有考虑到它将来可能需要获得更多食物的事实。因此，有时它倾向于把自己框起来。

也就是说，蛇在任何给定时间的目标都是找到食物，而它的目标应该是填满棋盘（一路上找到食物）。

如何添加或修改此方法以使AI赢得贪吃蛇游戏？我应该使用更好的方法吗？我只是想出一些想法。谢谢！

Answer 1

如果一个电路板是一个静态矩形（不是圆环形，所以不跨越边界），那么唯一的最佳策略是找到一组最长的闭合电路板路径，这样电路板中的每个点都至少位于一条路径中。

如果一个板是空的（没有障碍物），那么表单中存在一条“终极”路径

 16|.1|.6|.7
 15|.2|.5|.8
 14|.3|.4|.9
 13|12|11|10

它穿过所有的瓷砖，遵循这种模式的蛇最终会吃掉所有的食物，并填满整个木板

如果有一些障碍，那么这样的路径不一定存在，那么当食物出现在当前路径的不可到达点时，你应该找到这样的最长路径的集合，并在它们之间切换。

例如

#######
#.....#
#.#.#.#
#.....#
#######

在这里，您必须考虑两条路径，一条最长的，绕过整个棋盘，但缺少中心点，以及一条穿过它的小循环。只要食物没有出现在中心，就应该使用外环。希望，如果你填满所有剩余的方块时食物出现在中心——你会“赢”。如果它更早出现在那里 - 你必须吃掉它（切换到另一个循环）并根据你当前的长度 - 你会回到最好的循环，或者撞到你的尾巴并“输”。在每种情况下，您的分数都将是在这个食物位置上取得的最佳成绩。

非基于A*的方法会找到最优，这是完全不同的问题，你应该寻找最长的封闭路径，而不是最短的。