java - 适用于Android黑白棋游戏的Minimax/Alpha Beta

Question

我必须为android实现一个reversi游戏。我已经实现了所有的游戏，是功能性的，但问题是我没有一个人工智能。事实上，每移动一步，电脑都会移动到能使他获得最多碎片的位置。
我决定实现和α-β修剪算法。我在网上做了很多关于它的研究，但是我不能得出一个最终的结论怎么做。我试着实现了一些功能，但是没有达到预期的效果。
我的电路板存储在类电路板中（在这个类中，每个播放器占用的部分存储在一个二维int数组中）。我附上了一张小图表（很抱歉它看起来很像）。
图表：https://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit
我需要帮助来找出如何在我的实现中使用minimax算法。
到目前为止，我的理解是，我必须对董事会的价值作出评估。
为了计算董事会的价值，我必须考虑以下因素：
-自由角（我的问题是，我只需要关心自由角，还是我可以在当前的移动？！左右为难）。
-棋盘移动：检查当前移动后可移动的棋子数量。
-板的稳定性…我知道这意味着板上不能翻转的碎片的数量。
-搬家给我提供的数量
我计划实现一个新的类board a i，它将把board对象和dept作为一个参数。
你能告诉我如何实现这个人工智能的逻辑流程吗？
在dept中计算时，我需要一些关于递归的帮助，我不理解它如何计算最佳选择。
谢谢您！

Answer 1

首先，你可以检查this piece of code我多年前写的跳棋a i。有趣的是最后一个函数（alphabeta）。（这是用python编写的，但我认为您可以将其视为伪代码）。
显然我不能教你所有的alpha/beta理论，因为它可能有点棘手，但也许我可以给你一些实用的建议。
评价函数
这是一个好的min/max alpha/beta算法的关键点之一（以及任何其他有信息的搜索算法）。写一个好的启发式函数是人工智能发展的艺术部分。你必须很好地了解这个游戏，与专业的游戏玩家交谈，了解哪些棋盘功能是重要的，回答这个问题：这个位置对玩家X有多好？
您已经指出了一些好的特性，如机动性、稳定性和自由角。但是请注意，求值函数必须是快速的，因为它将被多次调用。
基本的评估函数是

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

其中， f是一个特征得分（例如自由角的数量）， w是一个相应的权重，表示特征f在总分中的重要性。
只有一种方法可以找到权重值：经验和实验。；）
基本算法
现在你可以从算法开始了。第一步是了解游戏树导航。在我的人工智能中，我只是像黑板一样使用主板，人工智能可以尝试移动。
例如，我们从某个配置b1中的board开始。
第一步：获得所有可用的移动。你必须找到所有适用的移动到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()

第三步：停止递归。这三个是非常深，所以你必须把搜索限制到算法。一个简单的方法是在 n级别之后停止迭代。例如，我从b1， max_level=2和 current_level=max_level开始。
例如，从b1（当前电平2）开始，我应用m1移动以获得b11。
例如，从b11（当前级别1）i apple，m2移动以获得b112。
b122是“当前0级”板配置，因此我停止递归。我返回应用于b122的求值函数值，然后返回到级别1。
在代码中：

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

现在。。。标准算法伪代码返回最佳叶值的值。但是我想知道哪一步能让我走到最好的一步！要做到这一点，你必须找到一种方法，将叶值映射到移动。例如，您可以保存移动序列：从b1开始，序列（m1 m2 m3）将值为-1的播放器放入b123板；序列（m1m2 m2）将值为2的播放器放入b122板；依此类推……然后你可以简单地选择移动，把人工智能带到最好的位置。
我希望这能有所帮助。
编辑：关于alpha beta的一些注释。如果没有图形化的例子，alpha-beta算法很难解释。为此，我想链接一个最详细的阿尔法-贝塔修剪解释，我发现： this one。我想我真的不能做得更好。：）
关键是：alpha-beta剪枝增加了节点的min-max两个边界。此界限可用于决定是否应展开子树。
这个界限是：
α：可能解的最大下界。
β：可能解的最小上界。
如果在计算过程中，我们发现一种情况，在这种情况下，我们可以停止对子树的计算。
显然，请检查前一个链接以了解其工作原理。；）