前面几期, 我们基本把界面操作给搞定了,甚至基本的行棋规则判断也有了。接下来,我们考虑一下怎样教会JS下象棋的问题。坦白说,我也没写过象棋的对弈AI,只是几年前写过五子棋的而已。不过,我们还是一起尝试一下吧,我相信会成功的。

对弈算法对与陌生人来说或许很神奇,但对于“懂行”的人来说,只有两档子事儿:路径搜索与局势评估(当然,如果你是研究神经网络或其它高级飞机的,请忽视本文吧)。

对弈AI的最终目的,就是找到通向胜利之路。每步着法是一个路径分枝,双方轮流行棋,则在这个路径树中,每条路径上的主动权都是交替着的。胜负的判断比较容易,但对于一般的应用程序来说,由于这个路径树过于庞大,我们不可能将之穷举。那么在看不到输赢的情况下,要怎么判断哪条路更光明呢?这就需要一个评估算法,对当前形势进行量化的评价。有了这个评价,搜索路径时就可以对不完全的路径进行对比,选择最好的结果。

仅仅限制路径搜索的广度和深度,有事候仍然并不理想。爆炸式的路径增涨带来的计算量真的不容忽视。有一个经典的搜索算法对对弈树的搜索进行了有效的优化,那就是Alpha-Beta搜索。

Alpha代表己方最优结果,Beta代表对方最优结果,也即己方最差结果。前面提到下棋的特点,就是主动权轮流变换。己方主动时,当然想选择对自己最有利的局势。但眼下最有利的,不一定真正有利,因为下一步对手将在己方先择的路径基础上,选择一个对己方来说最糟糕的路径。这样,实际上我们要做的事情就成了选择一条“最坏”情况“最好”的分枝。

这和切水果的故事很像。别误会,不是说那个触摸屏游戏。两兄弟要吃一个水果,妈妈该设计一个怎样的规则来保证公平性呢?这个聪明的妈妈提出了一个很简单的规则:老大来切,老二来挑。因为主动权的交替,老大不可能切得一大一小妄想自己可以得到大的那块。

当然这个故事只有两步,下棋则更复杂,很难直观的判断哪条路径更好,因为主动权的不断交替,什么都不好说。我们假设越往后局势越明朗,并预设最大搜索深度,以叶子节点的评估分数为参考。这些概念有点绕,不过如果顺着一种思路展开,或者有个直观的动画展示,还是不难理解的。

Alpha-Beta搜索算法只能用递归来实现。我们知道只有到达预设的最大深度时,或者中途分出胜负时(可以理解为到达叶子结点时)才有评分,有了评分才有Alpha-Beta。那么不妨从下往上看(递归和奇妙的数学归纳法是一回事),对每个叶子节点,Alpha,Beta分别代表了递归进行到当前节点时,已经发现的最好、最坏情况。关键的东西出现了:如果我们发现当前分枝比已经发现的最坏情况(代表了在其它分枝中已经发现的可以保底的路径)还要差,那这个分枝还要么?显然不要了,咔嚓,剪枝事件发生了?

等等,都已经到达叶子节点了,还能剪什么分枝啊?确实,没得剪了。不过别急,数学归纳法告诉我们,当我们回到上一层、上上一层时,都可以运用同样的逻辑。上层节点会从下层节点获取Alpha,Beta值,只是因为换了玩家,这两个值也要交换一下(己方有利,敌方就弊,反之亦然)。如果这时发现比已有最差情况(Beta)更差的,并且还有尚未搜索的子分枝,那是否可以咔嚓了呢?绝对可以!这正是Alpha-Beta搜索的意义所在,它可以通过剪枝提高搜索效率。

当然,如果碰到比已发现的更好的情况,就更新Alpha,返回上一层后它将变成对手的Beta值。如果你想了解更多关于Alpha-Beta搜索的资料,可以谷歌一下,资料很多,甚至有图有真象,比如亲爱的wikipedia:

http://en.wikipedia.org/wiki/Alpha-beta_pruning

Alpha-Beta搜索算法适用于绝大多数棋类AI,但评估算法就没有通用的了(似乎是废话)。除了胜出时得最高分,败阵时得最低分外,其它形势如何打分呢?就象棋来说,可以统计一下双方现存实力(带权重的棋子得分之和),再参考一下棋子的状态(比如有没有人掩护,有没有被敌人瞄上)。不过,写到此,我还没有直正开始动工做这个AI,所以评估算法还只是初步设想,有待实践。

敬请期待下期的AI实践!

本文作者:admin 转载请注明来自:携程设计委员会