Android Reversi游戏的Minimax/Alpha测试版

Question

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

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

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

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

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

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

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

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

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

非常感谢。

Answer 1

首先，您可以检查这段代码，以获取我多年前编写的跳棋AI。有趣的部分是最后一个函数（alphabeta）。（它是用python编写的，但我认为您可以将其视为伪代码）。

显然，我不能教你所有的α/β理论，因为它可能有点棘手，但也许我可以给你一些实用的提示。

评估功能

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

您已经指出了一些良好的特性，如灵活性、稳定性和自由转角。但是请注意，求值函数必须快速，因为它将被多次调用。

一个基本的评估函数是

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

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

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

基本算法

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

例如，我们从特定配置B1中的电路板开始。

步骤1：获得所有可用的移动。对于给定的玩家，你必须找到所有适用于B1的移动。在我的代码中，这是由self完成的。板所有移动（玩家）。它返回一个移动列表。

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

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

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

In代码：

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。

1. 例如，从B1（current\u level 2）我应用M1移动以获得B11

In代码：

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修剪解释之一：这一个。我想我真的没有比这更好的了。：）

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

该界限为：

• Alpha：可能解的最大下界
• Beta：可能解的最小上界

如果在计算过程中，我们发现

显然，请查看前面的链接以了解其工作原理。）