最短路径的AI算法可能解

Question

我需要启发式扫雷游戏的建议。如果发现有10个字段没有我的字段，我很好奇如何估计下一个要打开的字段？我在考虑在每个有编号的领域周围寻找地雷的可能性，并在计算结束时选择一个可能性最小的领域，但我不认为它会给我带来好的结果，因为我需要打开已经安全的领域，我需要的是打开一个领域，这将打开最大的区域在板上。我想读一些好的想法，但不要作弊的算法。

Answer 1

您可以尝试使用蒙特卡洛模拟进行A*搜索。也就是说，定义要打开的每种类型的单元格的成本/奖励(每种类型的操作)。

假设您可以执行K个不同的操作(a_1、a_2、a_3...)在当前时间步。

1. 为每个动作(打开单元格X)，并使用游戏模型来模拟接下来会发生什么。存储动作序列的奖励，并将奖励累加到原始动作。您可以将概率权重添加到活动和结果中，以使估计更准确。
2. 采用每个活动和活动序列的模拟奖励的平均值。在深度D处进行M次模拟(其中M和D只是预定义的值，以确保算法不会花费太长时间)之后，从(a_1，a_2，a_3...)中选择一个操作最高的模拟奖励。修剪是必要的，以使此方法有效(即，不将时间浪费在经过几个步骤模拟后肯定不会带来高回报的操作上)