algorithm - 基于AI招式的提示功能

Question

我正在制作一款类似于 Greedy Spiders 的游戏.简而言之，这是一款回合制游戏，其中有一只或多只蜘蛛试图靠近苍蝇吃掉它们。用户的任务是通过从网上切下一小部分以释放苍蝇或诱捕蜘蛛来防止这种情况发生。有一个提示功能，显示如何完成关卡并释放苍蝇或用最少的切割(移动)捕获蜘蛛。

我正在使用 A* 算法寻找到其中一只苍蝇的最短路径。该算法仍然不是很智能，因为它只找到最短路径并且没有考虑用户的切割。

我想知道的是如何实现提示功能。我现在想的是使用博弈树并评估每个结果并选择最佳结果，但我不确定这是否是最佳方法。

对于实现这样的功能，您有什么建议？

附言。我不是要复制应用程序。我想通过自己的努力做一些类似的事情，这样我就可以更好地解决问题。我想要一个想法，而不是一个解决方案...

Answer 1

这是我的猜测。

1. 在每一轮中，对所有蜘蛛使用 A*，为所有蜘蛛找到到最近苍蝇的最短路径。以某种方式将所有边缘存储在某种有序数据结构中，用于每个蜘蛛的每个最短路径。如果蜘蛛有几条共享最短路径长度的可用路径，请存储所有这些路径。例如如果一只蜘蛛有 3 条路径可供 3 只不同的苍蝇使用，并且所有这些路径的长度均为 2，则存储所有这些路径。

2. 按路径长度“排序”步骤 1 中找到的路径。找到其中最短的(长度最小的那些)。我们称这些为最短的最短路径。

3. 在所有这些最短的最短路径中，尝试找到所有路径中最常见(频率最高)的边。告诉玩家切割该特定边缘(如果存在)。如果不存在这样的“公共(public)”边，请告诉玩家在最短路径之一上切断最后一个边，因为这将提供一次释放一只或多只苍蝇的最大机会。

我没有确凿的证据证明这有效。作为玩家，这似乎是最佳选择。

在多个最短路径之间找到“公共(public)边”的想法浮现在脑海中，作为一种在一个回合中完成多个重要目标的方法，例如一次阻挡多个蜘蛛(或一次阻挡单个蜘蛛的多条路径)。可能有更高级的算法来做这件事。否则，如果不存在“公共(public)边缘”(即所有边缘的频率 == 1)，则最佳策略似乎是慢慢地切掉处于最紧迫危险中的苍蝇周围的边缘。