适用于Android Reversi游戏的Minimax / Alpha Beta

我必须为Android实施Reversi游戏。 我设法实现了所有的游戏,都是功能性的,但问题是我没有AI。 事实上,每一次移动计算机移动的位置,达到他的最高件数。

我决定实施alpha-beta修剪算法。 我在互联网上做了大量的研究,但我无法得出最终结论如何去做。 我试图实现一些功能,但我无法达到预期的行为。

我的棋盘存储在班级板(在这个班级内,每个玩家占用的棋子存储在一个二维int数组中)。 我附上了一个小图(对于它的样子,很抱歉)。

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

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

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

为了计算董事会的价值,我必须考虑以下因素: - 免费的角落(我的问题是我只需要关注自由角落,或者我可以在当前的行动中采取的角度?!困境) 。 - 棋盘的移动性:检查当前移动后可移动棋子的数量。 电路板的稳定性...我知道这意味着不能在电路板上翻转的部分数量。 - 移动将为我提供的件数

我计划实施一个新的课程委员会AI,该委员会将以我的理事会对象和部门的观点为理由。

你能告诉我一个合理的思路如何实现这个AI吗? 在计算部门时,我需要关于递归的一些帮助,我不明白它是如何计算最佳选择的。

谢谢!


首先,您可以检查这段代码,以查看几年前我写过的跳棋AI。 有趣的部分是最后一个函数( alphabeta )。 (这是在Python中,但我认为你可以看看像伪代码)。

显然,我不能教你所有的alpha / beta理论,因为它可能有点棘手,但也许我可以给你一些实用的技巧。

评估函数

这是一个良好的最小/最大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步:应用移动并开始递归。 假定函数已经返回了三个步骤( M1M2M3 )。

  • 采取第一步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=2current_level=max_level

  • 从B1(current_level 2)我申请,例如,M1移动来获得B11。
  • 从B11(current_level 1)我苹果,例如M2移动来获得B112。
  • 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修剪解释之一: 这一个 。 我想我不能做得比这更好。 :)

    关键是:Alpha-beta修剪增加了MIN-MAX两个界限。 这个边界可以用来决定一个子树是否应该被扩展。

    这个界限是:

  • Alpha:可能解决方案的最大下限。
  • Beta:可能解决方案的最小上限。
  • 如果在计算过程中发现Beta < Alpha的情况,我们可以停止对该子树的计算。

    显然,检查以前的链接,了解它是如何工作的。 ;)

    链接地址: http://www.djcxy.com/p/56305.html

    上一篇: Minimax / Alpha Beta for Android Reversi Game

    下一篇: beta pruning for Minimax