适用于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步:应用移动并开始递归。 假定函数已经返回了三个步骤( M1 , M2 , M3 )。
注:步骤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
。
在代码中:
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两个界限。 这个边界可以用来决定一个子树是否应该被扩展。
这个界限是:
如果在计算过程中发现Beta < Alpha
的情况,我们可以停止对该子树的计算。
显然,检查以前的链接,了解它是如何工作的。 ;)
链接地址: http://www.djcxy.com/p/56305.html