博弈树启发式搜索的α-β剪枝技术研究

５４

２００８，４４（１６）

Ｃｏｍｐｕｗｒ

Ｅｎ百ｎｅｅｎｎｇ

ａｎｄ

Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用

博弈树启发式搜索的倥书剪枝技术研究

张聪品，刘春红，徐久成

ＺＨＡＮＧ

Ｃｏｎｇ－ｐｉｎ，ＬＩＵ

Ｃｈｕｎ—ｈｏｎｇ，ＸＵＪｉｕ—ｃｈｅｎｇ

河南师范大学计算机与信息技术学院智能信息处理实验室，河南新乡４５３００７

ＫｅｙＬａｂｏｒａｔｏｒｙｆｏｒＩｎｔｅｌｌｉｇｅｎｔＩｎｆｏｒｍａｔｉｏｎＰｒｏｃｅｓｓｉｎｇ，ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒａｎｄ

ＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，Ｈｅｎａｎ

Ｎｏｒｍａｌ

Ｕｎｉｖｅｒｓｉｔｙ，

Ｘｉｎｘｉａｎｇ，Ｈｅｎａｎ４５３００７，Ｃｈｉｎａ

ＺＨＡＮＧＣｏｎｇ－ｐｉｎ。ＬＩＵＣｈｕｎ－ｈｏｎｇ。ＸＵＪｉｕ－ｃｈｅｎｇ．Ｒｅｓｅａｒｃｈ

ｏｎ

ａｌｐｈａ—ｂｅｔａｐｒｕｎｉｎｇｏｆ

ｈｅｕｒｉｓｔｉｃｓｅａｒｃｈｉｎ

ｇａｍｅ—ｐｌａｙｉｎｇ

ｔｒｅｅ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄ

Ａｐｐｌｉｃａｔｉｏｎｓ．２００８．４４（１６）：５４－５５．

Ａｂｓｔｒａｃｔ：Ｔｈｅｇａｍｅｐｌａｙｉｎｇ

ｉｓ

ａｎ

ｉｍｐｏｒｔａｎｔｄｏｍａｉｎｏｆｈｅｕｒｉｓｔｉｃ

ｓｅａｒｃｈ，ａｎｄ

ｉｔｓｐｒｏｃｅｄｕｒｅ

ｉｓ

ｒｅｐｒｅｓｅｎｔｅｄ

ｂｙ

ａ

ｓｐｅｃｉａｌａｎｄ／ｏｒ

ｔｒｅｅ．Ａｌｐｈａ－ｂｅｔａｐｒｕｎｉｎｇｉｓａｌｗａｙｓｕｓｅｄ

ｆｏｒｐｒｏｂｌｅｍ

ｓｏｌｖｉｎｇ

ｂｙ

ｓｅａｒｃｈｉｎｇｔｈｅ

ｇａｍｅ—ｐｌａｙｉｎｇ－ｔｒｅｅ．Ｉｎ

ｔｈｉｓ

ｐａｐｅｒ，ｔｈｅｐｌａｎ

ｗｈｉｃｈｃｈｉｌｄ

ｎｏｄｅｓ

ａｒｅ

ｉｎｓｅｒｔｅｄ

ｉｎｔｏ

ｇａｍｅ－ｐｌａｙｉｎｇ－ｔｒｅｅ

ｆｒｏｍｌａｒｇｅ

ｖａｌｕｅｏｆ

ｅｓｔｉｍａｔｉｏｎｆｕｎｃｔｉｏｎ

ｔｏ

ｓｍａｌｌ

ｏｎｅ

ｗｈｅｎ

ｔｈｅｎｏｄｅ

ｏｆ

ｎｏ

ｒｅｃｅｉｖｉｎｇｆｉｘｅｄｐｌｙｄｅｐｔｈｉｓｅｘｐａｎｄｅｄ

ｉｓ

ｐｒｏｐｏｓｅｄ

ｂａｓｅｄ

ｏｎ

ａｌｐｈａ—ｂｅｔａｐｒｕｎｉｎｇ．Ｉｔｉｍｐｒｏｖｅｓ

ｔｈｅｅｆｆｅｃｔｏｆ

ｓｅａｒｃｈ．

Ｋｅｙｗｏｒｄｓ：

ｇａｍｅｐｌａｙｉｎｇ；ｈｅｕｒｉｓｔｉｃｓｅａｒｃｈ；ａｌｐｈａ－ｂｅｔａｐｒｕｎｉｎｇ

摘要：博弈是启发式搜索的一个重要应用领域，博弈的过程可以用一棵博彝搜索树表示，通过对博弈树进行搜索求取问题的解，搜索策略常采用吐］８剪枝技术。在深入研究ｎ１８剪枝技术的基础上，提出在扩展未达到规定深度节点时，对扩展出的子节点按照

估价函数大小顺序插入到搜索树中，从而在ａ书剪枝过程中剪掉更多的分枝，提高搜索效率。

关键淘：博弈；启发式搜索；ａ－／３剪枝ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２—８３３１．２００８．１６．０１６

文章编号：１００２—８３３１（２００８）１６—００５４—０２

文献标识码：Ａ

中图分类号：１Ｐ１８

１引言

掌握在曰的手里，任何一个方案部有可能被日选中，Ａ必须防博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争止那种对自己最为不利的情况的发生。

等，是启发式搜索的一个重要应用领域，最简单的一种博弈是

（３）整个博弈过程始终站在某一方的立场上，所有能使自双人完备信息博奕。双人完备信息博奕Ｉｔ指两位选手对垒，轮流

己一方获胜的终局都是本原问题，相应的节点是可解节点；所走步，每一方不仅知道对方已经走过的棋步，而且还能估计出有使对方获胜的终局都是不可解节点。

对方未来的走步，对弈的结果是一方赢，另一方输，或者双方和求解Ｉ＇口Ｊ题时一般采用搜索博弈树的方法，利用完整的博弈局。本文利用双人完备信息博弈作为研究对象，为复杂的博弈树进行分析是不现实的，可行的办法是只生成一定深度的博弈问题提供参考基础。

树，找出当前最好的行动方案，在此之后，再在已经选定的分枝双人完备信息博弈过程可以使用一棵特殊的“与或树”表上扩展一定深度，再选择最好的行动方案，如此进行下去，直到示，这种与／或树被称为博弈树，通过搜索博弈树实现问题求分出胜负或者和局。每次生成博弈树的深度，当然是越大越好，解。博弈树有下面一些特点：

但由于受计算机内存空Ｉ＇日Ｊ的限制，博弈树的深度根据实际情况（１）博弈的初始状态是初始节点。

而定，但每次扩展节点时必须至少扩展一层或节点一层与节点。

（２）博弈树中的“或”节点和“与”节点是逐层交替出现的。博弈树的搜索包括盲目搜索和启发式搜索，盲目搜索效率

自己一方扩展的节点之间是或的关系，对方扩展的节点之间是太低，解决实际问题时一般不予考虑。常用的启发式搜索有极“与”的关系。双方轮流扩展节点。

大极小搜索法和ａ－－＃剪枝技术。极大极小搜索过程将搜索树假设博奕的一方为Ａ，另一方为Ｂ。博弃过程的每一步，供的产生和位置评估完全分开，只有生成规定深度的博弈搜索树月和Ｂ选择的行动方案都可能有多种。从Ａ方的观点看，可供后，才利用估价函数对位置进行评估，算法的效率比较低。如果自己选择的那些行动方案之间是“或”的关系，原因是主动权掌在生成博弈搜索树的过程中就对位置评估（到达了规定的深

握在自己手里，选择哪个方案完全是由自己决定的；而对那些度，但博弈搜索树还没有完全生成），从而剪去一些没用的分

可供曰选择的行动方案之间则是“与”的关系，原因是主动权

枝，提高算法效率，这种技术称为ａ－－＃剪枝过程，它的搜索效率

基金项日：河南省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆ

Ｈｅｎｎａ

Ｐｒｏｖｉｎｅｅ

ｏｆ

ＣｈｉｎａｕｎｄｅｒＧｒａｎｔ

Ｎｏ．０５１１０１２５００）；河南省高校新世纪优秀人

才支持计ＪｅｌＪ（ｔｈｅ

Ｎｅｗ

ＣｅｎｔｕｒｙＥｘｃｅｌｌｅｎｔＴａｌｅｎｔＦｏｕｎｄａｔｉｏｎｏｆＨｅｎａｎＰｒｏｖｉｎｃｅｏｆ

Ｃｈｉｎａ）。

作者简介：张聪品（１９６８一），女，副教授，主要研究方向：人工智能理论、编译技术；刘春红（１９６９一），女，讲师，主要研究方向：计算机网络；徐久成

（１９６３一），教授，主要研究方向：人工智能理论。

收稿口期：２００７—１２—１２

修回日期：２００８—０３—２４

张聪品，刘春红，徐久成：博弈树启发式搜索的ｄ］８剪枝技术研究２００８，４４（１６）

５５

比极大极小搜索法Ｉｚ有了很大提高。为了进一步提高博弈树的

搜索效率，本文在研究ａ］８剪枝过程的基础上，提出了一种改进的方案。

度，则按照ａ－ｉ３剪枝技术进行搜索。

（２）在搜索过程中，把本次搜索出的最佳格局存储在一个表中。这样。在以 …… 此处隐藏：7301字，全部文档内容请下载后查看。喜欢就下载吧 ……