3

我必须为 Android 实现一个黑白棋游戏。我已经设法实现了所有游戏，功能齐全，但问题是我没有人工智能。事实上，每走一步，计算机都会移动到使他获得最多棋子的位置。

我决定实现和 alpha-beta 修剪算法。我在互联网上做了很多关于它的研究，但我无法得出最终结论如何去做。我尝试实现一些功能，但无法实现所需的行为。

我的棋盘存储在 Board 类中（在这个类中，每个玩家占用的棋子存储在一个二维 int 数组中）。我附上了一张小图（对它的外观感到抱歉）。

图表：https ://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

我需要帮助来弄清楚如何在我的实现中使用 minimax 算法。

到目前为止，我所理解的是，我必须对董事会的价值进行评估。

为了计算棋盘的价值，我必须考虑以下因素： - 自由角（我的问题是我必须只关心自由角，或者我现在可以采取的那个？！这里的困境） . - 棋盘移动性：检查当前移动后可移动的棋子数。-棋盘的稳定性……我知道这意味着棋盘上不能翻转的棋子数量。- 移动将提供给我的件数

我计划实现一个新的 Class BoardAI，它将我的 Board 对象和部门作为参数。

你能告诉我我应该如何实现这个人工智能的逻辑思路吗？在进行深度计算时，我需要一些有关递归的帮助，但我不明白它是如何计算最佳选择的。

谢谢！

4

1 回答 1

5

首先，您可以检查我多年前编写的跳棋 AI 的这段代码。有趣的部分是最后一个函数 ( alphabeta)。（它在 python 中，但我认为你可以像伪代码一样看待它）。

显然我不能教你所有的阿尔法/贝塔理论，因为它可能有点棘手，但也许我可以给你一些实用的技巧。

评价功能

这是良好的最小/最大 alpha/beta 算法（以及任何其他知情搜索算法）的关键点之一。编写一个好的启发式函数是 AI 开发的艺术部分。您必须非常了解游戏，与专家级玩家交谈以了解哪些棋盘特征对回答以下问题很重要：玩家 X 这个位置有多好？

您已经指出了一些不错的功能，例如机动性、稳定性和自由角。但是请注意，评估函数必须快速，因为它会被调用很多次。

一个基本的评价函数是

H = f1 * w1 + f2 * w2 + ... + fn * wn

其中f是一个特征分数（例如自由角的数量），w是一个相应的权重，表示特征 f 在总分中的重要性。

只有一种方法可以找到权重值：经验和实验。;)

基本算法

现在您可以从算法开始。第一步是了解游戏树导航。在我的 AI 中，我只是将主板用作黑板，AI 可以在其中尝试移动。

例如，我们从某个配置B1中的板开始。

第 1 步：获取所有可用的招式。您必须为给定玩家找到所有适用于 B1 的移动。在我的代码中，这是由self.board.all_move(player). 它返回一个移动列表。

第 2 步：应用移动并开始递归。假设函数返回了三个动作（M1、M2、M3）。

  1. 采取第一步 M1 并应用它以获得新的板配置 B11。
  2. 在新配置上递归应用算法（找到 B11 中适用的所有移动，应用它们，递归结果，......）
  3. 撤消移动以恢复 B1 配置。
  4. 采取下一步行动 M2 并应用它以获得新的板配置 B12。
  5. 等等。

注意：步骤 3 只能在所有移动都可逆的情况下完成。否则，您必须找到另一种解决方案，例如为每个动作分配一个新棋盘。

在代码中：

for mov in moves :
    self.board.apply_action(mov)
    v = max(v, self.alphabeta(alpha, beta, level - 1, self._switch_player(player), weights))
    self.board.undo_last()

第三步：停止递归。这三个非常深，因此您必须对算法进行搜索限制。n一个简单的方法是在关卡之后停止迭代。例如，我从B1和.max_level=2current_level=max_level

  1. 例如，我从 B1 (current_level 2) 应用 M1 移动以获得 B11。
  2. 从 B11 (current_level 1) I apple，例如，M2 移动获得 B112。
  3. B122 是“current_level 0”板配置，所以我停止递归。我返回应用于 B122 的评估函数值，然后返回到级别 1。

在代码中：

if level == 0 :
    value = self.board.board_score(weights)
    return value

现在...标准算法伪代码返回最佳叶子值的值。但是我想知道哪个动作能把我带到最好的叶子！为此，您必须找到一种将叶值映射到移动的方法。例如，您可以保存移动序列：从 B1 开始，序列 (M1 M2 M3) 将玩家带入棋盘 B123，值为 -1；序列（M1 M2 M2）将玩家带入棋盘 B122，值为 2；等等...然后您可以简单地选择将 AI 带到最佳位置的动作。

我希望这会有所帮助。

编辑：关于alpha-beta 的一些注释。没有图形示例很难解释 Alpha-Beta 算法。出于这个原因，我想链接我发现的最详细的 alpha-beta 修剪解释之一：this one。我想我真的不能做得比这更好。:)

关键点是：Alpha-beta 剪枝为节点添加了 MIN-MAX 两个边界。此边界可用于决定是否应扩展子树。

这个界限是：

  • Alpha：可能解决方案的最大下限。
  • Beta：可能解决方案的最小上限。

如果在计算过程中，我们发现Beta < Alpha可以停止对该子树的计算。

显然检查上一个链接以了解它是如何工作的。;)

于 2013-01-17T11:18:18.123 回答