第23卷第2期广东教育学院学报2003年5月VoI．23NO．2JournalofGuangdongEducationInstituteMay2003五子棋中的博弈问题曾小宁(广东教育学院数学系，广东广州510310)摘要：人机对战五子棋程序设计，分为知识库设计和博弈树搜索两个方面．其中五子棋博弈树搜索包括产生子结点顺序与访问结点的具体操作．通过a—B剪枝求解产生子结点顺序问题．访问结点的具体操作即是五子棋的静态估值函数求值．系统中博弈问题用产生式系统描述．关键词：产生式系统；博弈树；静态估值函数；极大极小搜索；旷剪枝中图分类号：TP311；TP18文献标识码：A文章编号：1007-8754(2003)02一o096—051五子棋及博弈问题博弈问题一向被认为是一种具有智能行为的游戏，因而很早就受到人工智能界的重视．对于单人游戏可用一般的搜索算法，这里我们讨论的是双人博弈问题．这种问题有以下几个特点：(1)二人零和，(2)非偶然性，(3)全信息．所谓“二人零和”即竞争双方利益完全对立，分别用估值函数e。(，z)，e(，z)衡量状态，z对双方的利益程度，有e。(，z)+e(，z)一0．为描述博弈问题，可引入产生式系统把博弈问题转化为计算机可识别的对象．产生式系统是由三个基本要素组成的：一个综合数据库(GlobalDatabase)，一组产生式规则(Setofrules)和一个控制系统(ControlSystem)．以五子棋问题为例，综合数据库可用15×15的2维数组表示棋盘内各点状态(空、白子、黑子)；规则集合由具体下棋规则决定，对于五子棋可分为禁手和无禁手两类，以下为一规则：if棋盘(，．f)处为空then令(，j；)处为白子，诸如此类规则还有很多．对于搜索策略，它是此问题的关键．策略的好坏直接影响五子棋算法的效率、智能的高低．VictorAllis的论文“Searchingforsolutioningamesandartificialintelligence”中提到了五子棋的解法，他的结论是五子棋(五子棋有不同的规则，VictorAllis解决的是非职业比赛规则的五子棋，没有复杂的开局规则)执黑必胜，不过作者在文中提到，还没有程序能够执黑击败人类棋手．他在论文中提到最强的五子棋程序是vertex，作者是Shaposhnikov，使用了旷搜索，深度16-ply，14种最可能的走法．2博弈搜索树中极大极小搜索及a—搜索在大多数博弈问题中，要想把该问题完整的解图画出并根据对对手可能走的所有走步的预测来使计算机在对弈中不管对手走出哪种走步都获胜是不可能实现的．按照VictorAllis的分析，五子棋的复杂程度如下：博弈树复杂度为10知，状态空间复杂度为10。．因此即使使用了强有力的启发式搜索技术，也不可能使分支数目减到很少．故这种完全取胜策略必须丢弃，而把目标定为如何寻找一步相对的好棋．这种情况下搜索深度可根据实际情况进行调整，从局部搜索树中选取一步最好的走步．等对方走步后再寻找下一步好棋．可通过极大极小搜索方法来达到这种搜索策略．2．1极大极小搜索我们考虑两个玩家对弈，分别为MAX和MIN．MAX先走，之后两人交替走步直到游戏结束．游戏用产生式系统描述．由于不可能对完整解图进行搜索，我们定义一个静态估计函数收稿日期：2003—02—25作者简介：曾小宁(1975一)。男。江西临川人。广东教育学院数学系助教．第2期曾小宁：五子棋中的博弈问题97厂，以便对游戏状态的当前势态进行估值．一般规定有利于MAX的状态取厂(s)>O，有利于MIN的状态取，(s)<O．用一字棋为例给出极大极小搜索的5个步骤．(1)生成整个博弈树，即扩展树的每个节点．(2)用静态估值函数，对每个叶节点进行估值，得出每个终节点的评价值．(3)用终节点的估值来得到其搜索树上一层节点的估值．如图1所示A1走步的MIN结点选择走步，应选A15，由A15走步得到的估值是A1走步中最小的，同样A2、A3的MIN也选择最小值走步．(4)重复(3)过程在MAX层取其分支的最大值，MIN层取其分支的最小值，一直回溯到根结点．(5)最终，根结点选择分支值最大的走步走，如图1中，A3走步为根的最佳走步．这就是极大极小搜索过程(M1N1MAXdecision)．MAX6-5"15-S-O6-5"15-5-04．孓一15-6=15-5-05-6—16．6I_04-6；．25．4—1图1一字棋的一阶搜索树，深度为3，其中估计函数f的值为棋盘上剩余格全用MAX填满所成的三子一线的个数m减去棋盘上剩余格全用MIN填满所成的三子一线的个数n，即，(s)