智能五子棋算法的设计实现

《智能五子棋算法的设计实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第21卷第4期系统仿真学报©Vol.21No.42009年2月JournalofSystemSimulationFeb.,2009智能五子棋算法的设计实现王长飞，蔡强，李海生（北京工商大学计算机学院，北京100048）摘要：博弈是人工智能的主要研究领域之一。以五子棋为例，探讨人机博弈中推理技术、搜索方法和决策规划的实现算法。在VisualC++环境下设计了一个基于上述算法的智能的五子棋程序，实现人机博弈。最后探讨了优化五子棋算法的思路，并给出算法实例。相比已有程序，实例在对弈水平和搜索效率方面均有显著的提高。关键词：五子棋；估值；Alpha-Beta搜索；优化

2、中图分类号：TP301.6文献标识码：A文章编号：1004-731X(2009)04-1051-04DesignandImplementationofIntelligentGobangPlaygameWANGChang-fei,CAIQiang,LIHai-sheng(SchoolofComputerScience,BeijingTechnologyandBusinessUniversity,Beijing100048,China)Abstract:Gamblingandchessisoneofmajorresearchareainartificialinte

3、lligence.Basedongobangplaygame,thehuman-computergamereasoning,searchmethodsanddecision-makingplanningalgorithmwerediscussed.Then,anintelligentgobangsystemwasdesignedandrealizedinVisualC++accordingtothementionedalgorithms.Finally,somemeasurestooptimizethegobangalgorithmwereproposedan

4、danapplicationexamplewasgiven.Theapplicationshowsprominentimprovementonboththeplayinglevelandsearchefficiencycomparingtotheexistingprograms.Keywords:gobang;evaluation;alpha-betasearchalgorithm;optimization引言11.1估值函数不同的棋型，其优先级不同。例如，四个棋子连成一人工智能是一门综合性很强的边缘科学，它研究如何使线且还能继续落子的棋型（活四）显然要比只有

5、三个棋子连计算机去做那些过去只能靠人的智力才能做的工作。而博弈成一线（活三或死三）好。要使计算机正确地做出这种判断，是人工智能研究的一个重要分支，它不仅存在于游戏、下棋就要把第一种棋型的估值设高。事实上，对于每一种特定的之中，也存在于政治、经济、军事和生物竞争中。棋型，都需要相应的估值来反映其优劣情况。另外，由于搜五子棋是起源于中国古代的传统黑白棋种之一。现代五索模块频繁地调用估值函数，为了尽可能地加快搜索速度，子棋日文称之为“连珠”，英译为“Renju”，英文称之为估值函数应设计的越仔细越好。“Gobang”或“FIR”（FiveinaRow的缩写），亦有“

6、连五子”、估值时，需要从四个方向上来考虑所下棋子对当前盘面[1]“五子连”、“串珠”、“五目”、“五目碰”等多种称谓。的影响。这四个方向分别是以该棋子为出发点，水平、竖直与其他棋类相比，五子棋每一层搜索节点数量庞大，规和两条为45度角和135度角的线。则简单，估值函数可以做到比较细致。本文以五子棋为例研为方便分析棋盘上的格局，本文中约定以“A”代表黑子，究人机博弈，在传统Alpha-Beta搜索结合估值函数方法的基“B”代表白子，“？”代表棋盘上空位。算法中关于棋子死活础上，提出一系列优化搜索的措施，设计完成一个智能程度的规定如下：一方落子后，它的落子连成的一

7、条线有两条不较高的五子棋系统。损伤的出路，则称该棋型是活的。否则称该棋型是死的。比1传统五子棋算法介绍及初步实现如关于活三的定义：不论对手如何落子，仍然至少有一种方法可以冲四。因此，B?AAA?B中的三个A，不能算是活三；一般地，传统五子棋的算法主要包括：估值函数、搜索B?AAA??B中的三个A，也不是活三，尽管它有可能成为活算法和胜负判断等。四。这样，棋型的估值设计才能比较细致。本文算法对特定棋型的估值如表1所示。收稿日期：2007-08-10修回日期：2008-05-121.2Alpha–Beta搜索基金项目：北京市自然科学基金（4062010）作者简介：

8、王长飞(1985-),男,江西赣州人,