graph - AI Snake BFS 问题

Question

我正在努力解决蛇拳本身的问题。我相信如果我使用广度优先搜索（BFS）进行移动，它可以大大降低被装箱的风险。我的问题是我应该寻找多少可能的空白空间（连接）以确保这一举动不会导致自己拳击。

Answer 1

您必须查看的距离以查看您是否被装箱始终取决于蛇的大小/位置。100%确定的唯一方法是提前搜索所有动作，并避免导致蛇被装箱的动作。也就是说，深度优先搜索可能比广度优先搜索更好，因为它可以快速找到死胡同（如果存在）。然后避免这些动作。在您的第二个示例中，深度优先会很快发现“向上”移动是一条死胡同。

Answer 2

我认为搜索游戏树所需的移动深度与蛇环绕自身时可以包含的正方形区域有关。例如，一条长度为 12 的蛇：

----
|00|
|00|
91--

如果蛇向上（向北），它仍然可以生存，但前提是它向东移动。如果它再次向北移动，它就会死去。

一条蛇可以包含的最大面积是：(length/4 - 1)^2。当这是小数时，您可能想要四舍五入。