algorithm - 在游戏 “circle the cat” 中捕捉猫的好算法是什么？

Question

我做了基于广度优先搜索的 cat 算法 - BFS(因为我在这里的另一个主题中读到了它)。但是现在我想知道是否有一个好的策略来捕获猫。

对于那些不知道的人，游戏是这样的:
Game Circle the Cat

Answer 1

不错的游戏。今天之前我没见过它。我玩了一段时间，如果我要编写它，我会尝试记录我的算法......免责声明:这些只是我的想法，当我离开我的电脑时，没有数学证明它有效或诸如此类。

我想首先为每个正方形赋值(我知道它们不是正方形，我使用“正方形”来表示棋盘中的每个位置)。这些值将有助于表明哪个可能是猫的最佳选择。对于以下每个步骤，忽略已填充的方 block 。

首先，为每个方格分配一个 DistanceToWin 值，以显示到棋盘边缘的距离，如下所示...

1. 为棋盘边缘旁边的每个方格指定 DistanceToWin 值 1。
2. 与 1 相邻的每个方 block 的值为 2；在 2 旁边得到 3；等等。继续下去，直到没有设置新的值。请注意，有些方 block 可能没有设置值:这些方 block 没有通往边缘的路线，因此如果猫在这些方 block 之一上，它就会被困住，迟早你会赢。

现在我们需要指示每个方 block 的HowManyRoutes 是可能的，如下所示...(这可以在分配DistanceToWin)

1. DistanceToWin=1 的每个方 block 的 HowManyRoutes 值为 2。(我的想法是，这表示无法阻止逃生:再走一步，并且你不能在一个回合中阻塞两条路线。)
2. 具有DistanceToWin 值的每个其他正方形都将HowManyRoutes 设置为具有较小DistanceToWin< 的邻居的HowManyRoutes 之和/em> 值(value)。

猫的最佳选择方格是与猫方格相邻的方格，该方格的 HowManyRoutes 除以 DistanceToWin(我将其称为 < em>得分)。如果 Score>= 2，则猫可以/应该逃脱。每次填充一个方 block 时，这些值都需要在整个棋盘上重新计算，除非您想计算出哪些方 block 受到影响。

捕捉猫的算法似乎分为 3 类:

1. 猫被包围了(DistanceToWin 没有为猫的方格设置)，只需要最后被困即可。
2. 猫的最佳逃生路线需要在此移动中被阻挡(猫的邻居的最佳分数 = 1，并且该路线上任何下一步的最差分数是 >1)
3. 这只猫有很多逃生路线，您需要限制它的选择。

对于类别 1，我建议填充猫旁边的任何方 block 。

第2类，填充需要填充的方 block 。

第 3 类:填写一个正方形，使整个棋盘的总分数减少最多。