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

Question

我必须为Android实施一个Reversi游戏.我已经设法实现了所有游戏,功能齐全,但问题是我没有AI.实际上,在每次移动时,计算机都会移动到能够获得最多件数的位置.

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

我的电路板存储在类Board中(在这个类中,每个播放器占用的部分存储在一个二维int数组中).我附上了一张小图(抱歉看起来很像).

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

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

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

为了计算董事会的价值,我必须考虑以下因素: - 免费角落(我的问题是我必须只关注自由角落,或者我现在可以采取的角落？!这里的困境) . - 董事会的动力:检查当前移动后可移动的件数. - 板的稳定性......我知道这意味着无法在板上翻转的件数. - 此举将为我提供的件数

我计划实现一个新的类BoardAI,它将把我的Board对象和部门作为参数.

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

谢谢!

Answer 1

首先,您可以查看我在几年前写过的棋子AI的这段代码.有趣的部分是最后一个函数(alphabeta).(它在python中,但我认为你可以像伪代码那样看待它).

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

评估功能

这是良好的最小/最大alpha/beta算法(以及任何其他知情搜索算法)的关键点之一.写一个好的启发函数是AI开发中的艺术部分.你必须要熟悉游戏,与专业游戏玩家交谈,了解哪些棋盘功能对于回答这个问题很重要:玩家X的这个位置有多好？

你已经指出了一些很好的功能,如移动性,稳定性和自由角落.但请注意,评估函数必须快速,因为它会被调用很多次.

基本的评估功能是

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

其中f是特征分数(例如自由角的数量),并且w是相应的权重,表示特征f在总分中的重要程度.

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

基本算法

现在您可以从算法开始.第一步是了解游戏树导航.在我的人工智能中,我刚刚使用了主板,就像黑板一样人工智能可以尝试移动.

例如,我们从某个配置B1中的 board开始.

第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()

第3步:停止递归.这三个非常深,因此您必须对算法设置搜索限制.一种简单的方法是在n级别之后停止迭代.例如,我从B1开始,max_level=2然后current_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修剪解释:这一个.我想我不能做得更好.:)

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

这个界限是:

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

如果在计算过程中我们发现了Beta < Alpha可以停止对该子树进行计算的情况.

显然,请查看上一个链接以了解其工作原理.;)