象棋软件之引擎核心搜索和剪接算法|精品文章

过去去过

级别: 宣传大使

发帖: 172

金币: 335

威望: 2

贡献值: 140

乐币: 51

主题: 65

只看楼主更多操作楼主发表于: 2012-08-26

— 本帖被棋中论坛从棋软知道移动到本区(2012-08-26) —

计算机引擎棋步搜索，是“引擎”的核心，它驱动着整个引擎程序，是人工智能博弈在实践中的典型应用。但就中国象棋博弈树的搜索而言，博弈节点相当庞大（它会成指数增长），因而搜索（限定层数以内的）整棵树是一件相当费时的工作——其时间复杂度为O(bⁿ)。其中b是分枝因子，即针对各种局面的合法着法的数目的平均值，n是搜索的深度。中国象棋在中盘时平均着法数目大约是40种左右，那么搜索4层需要检查250万条路线，搜索5层需要检查1亿条路线，搜索6层需要检查40亿条路线……我们以现在比较典型的16核机，超频3.5G，按照中局搜索速度20M/秒个节点，同时不经“裁剪”采取蛮力搜索（穷尽）的方式。搜索7层以上所需的时间，是你难以想象的。具体每层所需搜索的节点数和所需时间见下表：

如果按照每一步平均有40种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，则要考虑 40⁹⁰=1.5× 10¹⁴⁴ 种局面。这一天文数字要比地球上的原子数目还要多，即使用世界上最快的计算机进行计算，直到地球毁灭也无法算出第一步的着法。由于完整的博弈树过于庞大，蛮力搜索所能达到的层数十分有限，在象棋博弈中几乎没有实用价值。若想在指定时间内将搜索深度加以提高，一方面需要改进硬件与优化程序代码，提高单位时间内搜索的节点数；另一方面就需要像人类棋手一样有选择性地进行搜索，即对博弈树进行必要的裁剪-------搜索裁剪算法。

搜索算法对于整个下棋引擎来说都是至关重要的。搜索算法的好坏直接影响着程序执行的效率，它影响着计算机的下棋水平。因为计算机必须在有限的时间内完成思考，搜索速度快意味着在相同的时间内程序可以“看”得更远，“想”的更多。下面用传统的Alpha-Beta搜索算法为例讲讲“裁剪”的实现。在中国象棋里，双方棋手获得相同的棋盘信息。他们轮流走棋，目的就是将死对方，或者避免被将死。由此，我们可以用一棵“博弈树”（一棵n叉树）来表示下棋的过程——树中每一个结点代表棋盘上的一个局面，对每一个局面根据不同的走法又产生不同的局面，如此不断直到再无可选择的走法，即到棋局结束。幸运的是，搜索算法使得我们能在不影响搜索精度的前提下大幅减少工作量。因为，如果考虑到下棋是一个你来我往的交替进行并且相互“较劲”的过程。由于每一方都会尽可能将局面导向对自己有利而对对方不利的方向，那么某些局面由于能够产生出很糟糕的局面因而根本没有再继续考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时，你应当立刻停止对其剩余子结点的分析——不要对它再抱任何幻想了，如果你选择了它，那么你必将得到那个很糟糕的局面，甚至可能更糟……这样一来便可以在很大程度上减少搜索的工作量，提高搜索效率，这称为“搜索树的裁剪”。下面用图来进一步说明“搜索树的裁剪”。为了简便起见，我将博弈树进行了简化——每个结点只有三个分支，实际情况中，刚才讲过在中盘应有大约40个分支。我们假定棋盘上的局面发展到了结点A（见下图），现在轮到你走棋了，你是“最大的一方”——即你希望棋局的分值尽可能的高。让我们试着搜索两层来看一看“树的裁剪”对提高搜索效率的帮助。

图中口表示该结点要取子结点中的最大值； O表示该结点要取子结点中的最小值首先，我们考察结点A的子结点B。结点B所属的这一层是轮到你的对手——“最小者”来走棋了，他的目的是使得棋局的分值尽可能的小。依次考察结点B的各个子结点，查看它们的分值（因为我们事先约定好了搜索两层，现在已达到搜索深度的要求了，所以就停下来调用局面评估函数来给它打分）。结点Ｂ的第一个子结点（从左到右算起）返回5，第二个子结点返回了8，第三个子结点返回了4。由于结点Ｂ这层是你的对手来做选择，我们假设他一定会做出明智的选择（你不能寄希望于你的对手会走出一步“昏招”），那么他会选择返回值为4的那个结点。4最终也就成了从结点B传递回的值，即倘若你（现在位于结点A）选择了产生结点B的走法，使得局面发展到了结点B。那么下一步，你的对手的选择就会使得棋局发展成为分值为4的那个结点所表示的局面。我们再来分析结点A的第二个子结点C，结点C与结点B同属一层，它依然是轮到你的对手作选择。依次查看结点C的各个子结点的分值，其第一个子结点返回了6、第二个子结点返回了2、……好了，该是“裁剪”登场的时候了。你已经不必再继续考察结点C的剩余子结点了，因为结点C已经够糟糕的了，不管结点C的剩余子结点有怎样的分值，它最多只能传回2（有可能其剩余子结点中还有分值更小的结点，因而结点C还有可能传回更小的值）。而与前面已经分析过的结点B所传回4相比较，作为“最大一方”的你显然更不愿意看到2的局面。所以，你当然不会选择相应的着法使得局面发展成为结点C。因为那样的话，下一步你的对手就会带给你一个分值不高于2的局面。同理，我们再来分析结点A的第三个子结点D，结点D与结点B、C同属一层，它依然是轮到你的对手作选择。依次查看结点D的各个子结点的分值，其第一个子结点返回了3……不管结点D的剩余子结点有怎样的分值，它最多只能传回3（有可能其剩余子结点中还有分值更小的结点，因而结点D还有可能传回更小的值）。而与前面已经分析过的结点A所传回4相比较，作为“最大一方”的你显然也不愿意看到3的局面，所以D分支“裁剪”掉。由此，我们就在不影响搜索质量的前提下避免了搜索“无价值的”结点C和D的剩余子结点的大量工作，从而节省了宝贵时间，为在同样机器配置下搜索更多的层数提供了可能。有了好的搜索算法，才是“引擎“在有限时间内找到”正着“。提高了搜索的效率，才使”引擎“的应用有了实际价值。希望各位从中认识到“裁剪”的必要性。 by 天剑出击 2012-8-23
[ 此帖被天剑出击在2012-08-24 16:08重新编辑 ]

本帖最近评分记录：共 5 条评分金币 +14

隐藏

评分

关键词: 引擎搜索剪接算法


	http://www.qqzze.com 访问内容超出本站范围，不能确定是否安全


	关闭选中1篇评分全选

帖子

象棋软件之引擎核心搜索和剪接算法

相关话题