人工智能扫雷项目

Question

我需要实现扫雷求解器。我已经开始实现基于规则的代理程序，实施了某些规则。我有一个启发式函数来选择当前处理的单元格（带有周围单元格信息）的最佳匹配规则。因此，对于每个选择的单元格，它可以决定对8个周围单元格进行打开、标记或什么也不做的操作。我的意思是，目前，代理程序会将一些已揭示的单元格作为输入，并决定如何处理周围的单元格（目前，代理程序不知道如何决定要处理哪个单元格）。

我的问题是，决定要处理哪个单元格应该实现什么算法？

假设，在第一步中，代理程序将揭示一个角落单元格（或根据某些规则揭示其他单元格）。那么之后该怎么办呢？

我知道我需要实现某种搜索，我了解许多搜索算法（BFS、DFS、A-STAR等），这不是问题，但我不明白在这里如何使用这些搜索算法。

我需要按照人工智能原则来实现它：现代方法。

- Nikita

Answer 1

BFS、DFS和A*算法可能不适用于此处。如果你在拥有完整世界知识的情况下尝试规划行动路线，那么这些算法是很好的选择。但是，在扫雷游戏中，你并没有这样的知识。

相反，我建议尝试使用书第三部分中的一些逻辑推理技术，特别是使用SAT或第十章的技巧。这将让你根据事实来得出关于地雷位置的结论，例如：“以下八个方块中的一个是地雷，其中恰好两个方块是地雷。”每一步都这样做将帮助你确定地雷的位置，或者意识到在继续之前必须猜测。

希望这能帮到你！

- templatetypedef

---

我已经在规则中实现了一些技术，我实现了一个名为treatCell(i_CellToTreat)的特定方法，它匹配最佳规则并执行它。我只是不知道如何处理揭示的单元格的顺序，以及选择哪个单元格进行处理，目前它只是遍历所有揭示的单元格并对其进行处理。在小型棋盘上它运行得非常好，但我需要实现一些更好的算法。 - Nikita

Answer 2

我进行了移植（有一点帮助）。这是它工作的链接：http://robertleeplummerjr.github.io/smartSweepers.js/。这是项目：https://github.com/robertleeplummerjr/smartSweepers.js。

玩得开心！

- Robert Plummer

Answer 3

要使用《人工智能：一种现代方法》的原则来实现扫雷求解器，您可以使用搜索算法结合启发式方法来决定下一个要处理的单元格。对于这个问题，一个适合的算法是A*搜索算法。A*是一种最佳优先搜索算法，它同时使用到达节点的成本和到达目标的剩余成本（启发式）来引导搜索。

以下是您可以进行的步骤概述：

状态表示：将扫雷棋盘表示为具有隐藏单元格、已揭示单元格和它们各自的值（相邻地雷数量）的状态。您可以使用二维数组或基于图的表示方法。

启发式函数：开发一个启发式函数，估计扩展特定状态的成本或效用。启发式函数应该引导搜索以揭示或标记最有希望的单元格。

A*搜索：实现A*搜索算法来探索扫雷棋盘的状态空间。在每一步中，A*选择看起来最有希望的单元格，基于已知到达该单元格的成本和从那里到达目标的估计成本（启发式）。

基于规则的代理：将A*搜索与您的基于规则的代理结合起来。当A*搜索选择一个要处理的单元格时，应用您现有的基于规则的代理的规则来决定是否打开周围的单元格、标记它们为地雷或不采取任何行动。

A*搜索将根据当前棋盘状态和估计的潜在结果指导求解器做出智能决策。然后，基于规则的代理将对所选单元格及其周围进行操作，应用预定义的规则来继续探索棋盘。

在开始时，您可以使用简单的启发式函数，例如考虑剩余隐藏单元格的数量或相邻地雷的数量，但您可以随着时间的推移进行实验和改进启发式函数，以提高求解器的性能。

请记住，扫雷是NP完全问题，这意味着高效地找到最优解是具有挑战性的。然而，与基本的随机移动或无信息搜索算法相比，使用适当的启发式函数的A*搜索将显著提高求解器成功的机会。

请记住，您的基于规则的代理还可以利用A*搜索期间收集的信息，以更明智地决定如何处理单元格，例如根据已揭示单元格的模式或检测到的地雷簇调整规则。

- Preeti AI

---

A搜索对于这种类型的问题并不合适。A的思想是通过在计算节点值时包含一个估计的“到目标的成本”启发式来“拉动”探索朝着目标前进。扫雷是一个不完全信息问题，A*无法猜测在探索一个节点后离目标还有多近。 - OLP