安卓翻转棋游戏的极小化极大/Alpha Beta算法

Question

安卓翻转棋游戏的极小化极大/Alpha Beta算法

javaandroidartificial-intelligenceminimaxalpha-beta-pruning

3

我需要在Android上实现一个黑白棋游戏。我已经实现了所有的游戏功能，但问题是我没有AI。事实上，每次电脑移动都是在能够获得最多棋子的位置上移动。

我决定实现一个Alpha-Beta剪枝算法。我在网上做了很多研究，但我无法得出最终结论如何做到这一点。我尝试实现了一些函数，但不能达到期望的行为。

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

图表：https://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit 我需要帮助来弄清楚如何在我的实现中使用Minimax算法。

到目前为止，我所理解的是，我必须制作一个关于棋盘价值的评估函数。

为了计算棋盘的价值，我必须考虑以下元素： -自由角（我的问题是我只需要关注自由角，还是我可以在当前移动中获取的自由角？！这里有一个两难的问题）。 -棋盘的可行性：检查在当前移动后将可用于移动的棋子数量。 -棋盘的稳定性...我知道这意味着无法翻转的棋子数。 -移动将为我提供的棋子数量

我计划实现一个新的BoardAI类，它将以我的Board对象和深度作为参数。

你能告诉我如何实现这个AI的逻辑思路吗？我需要一些关于递归计算深度的帮助，我不理解它是如何计算最佳选择的。

谢谢！

- Cristian Holdunu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Davide Aversa · Accepted Answer

首先，您可以查看我多年前编写的这段代码，用于对抗AI。有趣的部分是最后一个函数 (alphabeta)。（虽然它是用Python编写的，但我认为您可以将其视为伪代码）。

显然，我不能教您所有关于alpha/beta理论的内容，因为它可能有点棘手，但也许我可以给您一些实用的提示。

评估函数

这是好的min/max 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）。

取第一个移动M1并将其应用于获得新的板配置B11。
在新配置上递归地应用算法（查找B11中适用的所有移动，应用它们，递归结果，...）
撤消移动以恢复B1配置。
取下一个移动M2并将其应用于获得新的板配置B12。
等等。

注意：仅当所有移动都可逆时才能执行步骤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()

步骤 3：停止递归。这棵树非常深，因此您必须对算法设置搜索限制。一种简单的方法是在 n 级后停止迭代。例如，从B1 开始，max_level = 2，current_level = max_level。

从B1（当前级别为 2）开始，我应用例如 M1 移动以获得 B11。
从B11（当前级别为 1）开始，我应用例如 M2 移动以获得 B112。
B122 是“当前级别为 0”的板配置，因此我停止递归。我返回应用于 B122 的评估函数值，并回到第 1 级。

代码示例：

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

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

我希望这可以有所帮助。

编辑：关于alpha-beta的一些注释。很难在没有图形示例的情况下解释Alpha-Beta算法。出于这个原因，我想链接我曾经发现过的最详细的alpha-beta剪枝解释之一：此链接。我认为我无法比那更好。 :)

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

这些边界是：

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

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

显然，请查看上面的链接以了解其工作原理。 :)