五子棋智能博弈的研究与设计

摘要:机器博弈是人工智能的一个重要研究分支,该文通过设计一个五子棋智能博奕程序,采用传统的博弈树算法,利用剪枝和极大极小树搜索最佳位置,从而实现人机智能博弈。并对现有算法存在的问题进行探究改进,最后给出程序实例,结果表明效果较为理想。

关键词:五子棋;智能;博弈;估值函数

中图分类号:TP18 文献标识码:A文章编号:1009-3044(2010)13-3497-02

Research and Design of Intelligent Gobang Game-playing

XING Sen

(College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, China)

Abstract: Computer game is one of the important branches of Artificial Intelligence, this paper based on the design of a intelligent gobang system, according to the method of the traditional algorithms search-tree, searching the best position by the pruning and the minimax tree, realizing the gaming between human and computer. Then take some measures to solve the problem in the existing algorithm and show the effect by some examples finally.

Key words: gobang; intelligence; game; evaluation function

人工智能是一门综合性的新兴边缘科学,与生物工程、空间技术并列为三大尖端技术,而机器博弈是其一个重要研究分支,很多算法、技术都融合于博弈思想中。在现实中,博弈也是广泛存在于政治、经济、军事、生物进化等领域中。棋类等游戏更是完美体现了博弈的规则和思想,很多算法技术都可以应用在棋类游戏中。[1]五子棋相比其他棋类,如象棋、围棋,其规则极其简单、易学,且具有很强的娱乐性,因此受到人们广泛的喜爱。本文在研究计算机博弈系统的过程中,对五子棋博弈算法进行了一些研究,分析和设计了一个人机对弈的五子棋程序,采用了博弈树的方法,利用剪枝和极大极小树搜索最佳位置,实现人机智能博弈。

1 主要传统算法

1.1 博弈树

传统的算法是采用博弈树法来设计程序。以甲乙两人下棋为例,甲有很多种落子方式,乙也有多种应对走法,如果把所有的走法列出来,自然就构成了一棵树,即为搜索树,也称博弈树。树的根结点为先手的第一步走法,下面的走法构成了树的子结点,直至棋局结束。显然,假如棋盘足够大,子结点数会以几何级数上升,而我们的任务是从这些子结点中寻找一个对己方最有利的结点,从而得到棋局的最佳走法,自然这是一个指数复杂度的过程,费时低效,无法搜索到最终结果(除了棋局结束),通常只能达到一个有限的深度,在有限的范围内来判断走法的好坏,得到一个局部最优解。[2-3]因此,有必要做一些调整改进,以提高算法的效率和质量。

1.2 极大极小算法

极大极小搜索算法就是在博弈树在寻找最优解的一个过程,这主要是一个对各个子结点进行比较取舍的过程,定义一个估值函数F(n)来分别计算各个终结点的分值,通过双方的分值来对棋局形势进行分析判断。还是以甲乙两人下棋为例,甲为max,乙为min。当甲走棋时,自然在博弈树中找最大点的走法,轮到乙时,则寻找最小点的走法,如此反复,这就是一个极大极小搜索过程,以此来寻找对机器的最佳走法。其中估值函数通常是为了评价棋型的状态,根据实现定义的一个棋局估值表,对双方的棋局形态进行计算,根据得到的估值来判断应该采用的走法。棋局估值表是根据当前的棋局形势,定义一个分值来反映其优势程度,来对整个棋局形势进行评价。[3-4]估值表通常如下,还可以根据棋型进行进一步的细分:

表1棋局估值表

一般来说,我们采用的是15×15的棋盘,棋盘的每一条线称为一路,包括行、列和斜线,4个方向,其中行列有30路,两条对角线共有58路,整个棋盘的路数为88路。考虑到五子棋必须要五子相连才可以获胜,这样对于斜线,可以减少8路,即有效的棋盘路数为72路。对于每一路来说,第i路的估分为E(i)=Ec(i)-Ep(i),其中Ec(i)为计算机的i路估分, Ep(i)为玩家的i路估分。棋局整个形势的估值情况通过对各路估分的累加进行判断,即估值函数:

■

1.3 αβ剪枝

αβ剪枝算法简单的来说,就是在搜索过程中减少一定的冗余现象,如已经找到极大值,执行该走法就可以获胜,则无须再往下进行搜索比较,此过程即为剪枝。对于极大的MAX结点,称为α剪枝;反之为β剪枝。具体规则可以简单描述如下:

1) α剪枝:对于极大值层结点的α值如果不小于它的任一祖先极小值层结点的β值,即α(后续层)≥β(祖先层),则可中止该极大值层中这个MAX节点以下的搜索过程,这个MAX节点最终的倒推值就确定为这个α值。

2) β剪枝:对于极小值结点层的β值如果不大于它任一祖先极大值层结点的α值,即α(祖先层)≥β(后续层),则可中止对该极小值层中这个MIN节点以下结点的搜索,这个MIN节点最终的倒推值就确定为这个β值。[2]

αβ剪枝可以进一步进行改进,在走棋过程中,在中心先下的一方往往有一定的优势,双方的搏斗纠缠都是在争夺最佳位置,可以考虑从中心往外螺旋进行扩展搜索;另外由于防守的需要,落子的位置通常也是在彼此下子的附近,因此可以优先考虑在这些位置进行搜索,也就是对落子位置进行排序预先搜索,更进一步的缩减冗余现象,进而提高搜索效率和行棋质量。[5]

2 改进传统算法

传统算法最大的一个缺点还是在于它的指数复杂度问题,虽然通过剪枝、优化搜索位置等方法减少了冗余,提高了一定的搜索效率,但都无法解决搜索深度增加带来的呈几何级数增加的巨大计算量问题。[4]在进一步的实验中发现,搜索超过7层以后,程序响应速度明显变慢,到9层会出现1-2s的间隔期。因此,通过研究五子棋的规律和特点,结合实际经验,可以对程序作一些预定的调整措施,从而提高算法的执行效率和对弈能力。

2.1 缩减搜索范围

对于15x15的棋盘,每一种走法都有上百种可能,如果对每种走法都进行计算估值,则无疑大大增加了计算量,降低了算法的效率和质量。根据规则和实际经验,我们知道只要考虑以棋子为中心的邻近区域皆可,比如不大于4的距离通常为该子的有效范围,同理我们还可以在对方的落子范围进行判断估值。这样可以缩减搜索范围,同时提高算法的效率和走法的实用性。

2.2 置换表搜索

前面我们讨论了利用αβ剪枝来处理冗余结点,对于已经搜索过的结点,我们可以通过设置一张Hash表记录该结点,这样在后续的搜索过程中,可以对这些点的记录进行查询如先前有过记录则直接调用,免于重新搜索,从而避免出现重复操作,加快搜索速度。该方法通常称为置换表(Transposition Table)。

2.3 建立棋谱库

该方法广泛应用在象棋程序设计中,五子棋远比象棋简单,该方法也更为有效实用。通过在数据库中存储一些开局“定式”手法和经典棋局,开局阶段,程序使用开局库,一旦发现相同棋局,则直接调用该走法,无须再次搜索,同时建立数据库来存储失败案例不断进行调整对策。该方法可以极大的提高程序的智能化,只是增加了额外的系统开销。另外对于棋谱的匹配和存储也是关键问题。蒋加伏等人提出的利用Apriori算法提取方法,较为有效实用。[4]

2.4 合理设置搜索深度

理论上来说,为了寻找最优解,最好是对完整博弈树进行完全搜索,但实际中是不可行的,无论是从时间上还是从系统资源上。在后面实际程序设计中,最大使用了9层搜索策略,默认为5层,当然也可以根据不同机器配置加以调整,以达到最大效率。

3 实例分析

在WindowsXP操作系统下,利用上述算法思想,采用C#编程实现一个实现人机对战的五子棋程序。通过实验分析比较,程序的智能化和质量效果较为理想。当计算机执黑时,基本上每次都能获胜,且步骤、时间较短;当玩家执黑先行,计算机获胜比率也较高,具有很好的智能性。右图1,图2是棋局实例。

4 结束语

本文介绍了一个智能五子棋的主要算法思想和实现技术,利用剪枝和极大极小树搜索博弈树,作出了一些改进措施,寻求最佳下棋位置,从而提高了智能博弈的质量。进行优化以后,五子棋程序的智能水平和搜索效率有了明显的提升。本文所讨论的算法思想和设计过程也为其他棋类游戏(如象棋和围棋等)提供了一定的参考价值。此外,五子棋的国际规则较为复杂,加入了禁手判负、三手交换等规则限制黑手先行优势,可以在进一步的工作中考虑实现。

参考文献:

[1] 蔡自兴.人工智能及其应用[M].北京:清华大学出版社,1999:2-12.

[2] 朱全民,陈松乔.五子棋算法的研究与思考[J].计算技术与自动化,2006(02):75-78.

[3] 董红安,蒋秀英.智能五子棋博弈程序的核心算法[J].枣庄学院学报,2005(2):61-65.

[4] 蒋加伏,陈蔼祥,唐贤英.基于知识推理的博弈树搜索算法[J].计算机工程与应用,2004(1):74-76.

[5] 张海峰,白振兴,张登福.五子棋中的博弈智能设计[J].现代电子技术,2004,27(7): 25-27.