阅读 563

如何写一个象棋 AI (一)

本文代码:github.com/ParadeTo/ch…

Demo 地址:www.paradeto.com/vue-chinese…

我们都知道,把大象关进冰箱需要三步。同理,写一个象棋 AI 程序也只需要三步:

  1. 遍历出所有可能的走法
  2. 选择出最好的走法

第三步其实只是凑数而已,可以去掉,这样写一个 AI 程序就更简单了,只需要两步。

其中,第一步对于稍微有点象棋和编程知识的人来说并不是很难,除了马和炮的走法需要写一些额外的规则来判断以外,其他的棋子都比较类似,这一部分不在本文的讨论范围之内。

第二步才是本文需要讨论的重点,首先我们要解决的第一个问题是,给定一个棋局,如何判断该棋局的好坏呢?

局势评估

关于象棋局势的评估已有不少学者做过研究,有静态单子型、未来局势型、象棋知识型、局面附加信息等。本文采取的是静态单子型。

所谓静态单子型评估,是指对棋盘上的每一个棋子考虑其种类和位置,依种类的重要性与位置的优劣决定它的评估值,然后将棋盘上所有己方棋子的评估值直接累加得到己方战力值,将对手所有棋子的评估值累加得到对手战力值,已方战力值减去对手战力值得到最终的局势评估值。

最大最小值算法

有了局势评估方法后,每次遍历出所有的可能走法,然后从中选取局势分数最高的走法就是一个最简单的象棋 AI 了。不过这个 AI 会有点蠢,有点短视。想想小时候跟院子里的老大爷下棋时是怎么被玩弄的吧,老大爷总是故意让一个车给你吃,而正当你开心得忘乎所以的时候,一声 “将军” 瞬间让你跌回了深渊,死棋,游戏结束。每当这个时候,心中总会暗忖,这个老头子可真阴险。后来才知道,对付这种阴险的战术需要我们下棋时能抵抗住诱惑,看得更加长远一些,不能只顾当前这一步,要考虑到后面两步、三步……的情况。

既然这样,那程序实现起来也简单,无非就是递归的遍历几层,达到叶子节点后计算当前局势得分,然后选择分数最高的不就可以了。就像下图这样:

我先遍历出所有可能的走法(图中黑色方块),然后基于该层的走法继续遍历(图中最后一排的白色方块),计算局势分数,选择最高分数的走法,即选择左边黑色方块的走法。但是,你忘记了一点,你走完后,接下来是轮到你对手走了,你如果想得到 100 的分数,就需要你的对手配合你选择分数 100 的走法。很明显你的对手不会那么傻,此时,只要他跟你一样聪明,他应该会选择走分数为 1 的那一步。而如果你选择右边黑色方块的走法,你的对手会选择分数为 33 的走法,你反而会得到一个高一点的分数。

让我们用一个别的例子再来模拟一下上面的情景,以便更好的理解。假设你朋友给你两个袋子,第一个袋子里面装了一颗螺丝和一台 Mac Pro,第二个袋子里面装了一台小米9和一台华为p30。然后跟你说,选择一个袋子,然后我从里面拿一个礼物送给你。你会怎么选?你肯定选第二个袋子是吧。当然,这里重要的一点是你的朋友智商一定要正常,如果是个傻子的话,保不准你选了第一个袋子,他会送台 Mac 给你。

人可以做出这样的决策这很正常,但是如何教会计算机也这样思考呢?这就需要用到最大最小值算法了。最大最小算法把搜索树分成最大值层和最小值层,AI 处于最大值层,对手处于最小值层,最大值层总是从下一层选取最大的值作为结果,最小值层总是从下一层选择最小值作为结果。如下图所示:

思路清楚了,代码实现起来就很简单了,以下是来自 wiki 的一段伪代码:

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value
复制代码

总结

本文阐述了实现一个象棋 AI 的基本步骤,引出了最大最小值算法并通过例子加以分析。不过该算法比较耗时,假设每次遍历平均产生 30 种走法,则深度为 5 的 AI 的一共需要进行 24300000 次的局势分数计算。事实上该算法通过一定的规则可以进行优化,这个就留在下一篇文中再进行论述吧。

参考

  1. 中国象棋计算机博弈局面评估技术研究
  2. Minimax
  3. IntelligentChineseChessSystem
  4. gobang
关注下面的标签,发现更多相似文章
评论