蛇游戏人工智能

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*的方法会找到最优解，这是完全不同的问题，您应该寻找最长的闭路径，而不是最短。