|
|
摘要: 人工智能(Artificial Intelligence) 是计算机科学、控制论、信息论、神经生物学、心理学、语言学等多种学科互相渗透而发展起来的一门综合性学科; 是研究解释和模拟人类智能、智能行为及其规律的一门综合性的边缘学科。 博弈是人工智能的重要研究领域。现以五子棋为例, 提出了用遗传算法与改进的搜索树算法相结合的方法设计智能五子棋系统, 实现人机博弈。关键词: 五子棋 人工智能 博弈 算法 0 前言 五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋也称为“ 串珠”“、五子连”“、五目”“、五目碰”“、五格”等。五子棋有“ 短、平、快”的现代游戏特征[1], 简单易学而富有趣味, 不仅能增强思维能力, 提高智力, 而且有助于修身养性。然而五子棋变化多端, 包含深奥的哲理和弈战技巧, 尤其是随着国际职业联珠运动的发展和竞赛规则的逐步完善, 弈棋技法和战术有了很大的发展, 因此不再是简单的游戏。人工智能(Artificial Intelligence) 是“研究如何在计算机上实现人类智能”的新兴学科,自1956 年问世以来,已经取得了许多引人瞩目的成就,逐渐形成了诸如专家系统、机器学习、模式识别等多个领域。 1 五子棋特点及规则 五子棋简单易学流行性广, 一般不需要经过长时间专门训练就可自如行棋,因此极受大家的喜欢。五子棋规则为:(1 )棋盘:采用像围棋盘一样的15 路或19 路线的棋盘,本文讨论的是15 路的棋盘;(2 )下法:两人分别执黑白两色棋子,轮流在棋盘上选择一个无子的交叉点落子,无子的交叉点又被称为空点或合法点;(3 )输赢判断:黑、白双方有一方的五个棋子在横、竖或斜方向上连接成一线即为该方赢。2 人机博弈的要点 人机博弈的程序至少需要以下几个部分:(1 )棋局的状态能够在机器中表示出来, 并能让程序知道当时的博弈状态;(2 )合法的走法规则如何在机器中实现, 以便不让机器随便乱走而有失公平;(3 )如何让机器从所有的合法走法中选择最佳的走法;(4 )一种判断博弈状态优劣的方法, 并能让机器能够做出智能的选择;(5 )一个显示博弈状态的界面, 有了这样的界面程序才能用的起来而有意义。故我们对棋局状态显示进行如下设计: 把15×15 的棋盘中每一个节点标号, 并将编号用数组jiedian_dizhi[ ]的下标表示, 即若是第8 行第9 列的节点, 则jiedian_dizhi[ ]的下标为8×15+9=129。若某节点上有棋子, 则用1 表示, 反之用0 表示。并将值存放于jiedian_dizhi[ ]中。棋盘上的黑子用1表示, 白子用2表示, 无子用0表示, 则对每一个当前的棋局状态都可以用长为225 的字符串表示。例如棋局状态为0012010210⋯⋯, 则表示第一行的第三个节点上有黑子, 第四个节点上有白子,jiedian_dizhi[3]=1,jiedian_dizhi[4]=1,下一步就不能在这两个节点下子, 当前状态下第一行的第三节点和第四节点为非法走法。3 实现人机博弈的算法设计3.1 博弈树法 解决博弈问题的传统算法是搜索树法, 也叫博弈树法。以甲乙两人对弈五子棋为例。假定现在该甲走棋, 且甲有若干种走法, 而对甲的任一走法, 乙也可以有与之对应的不同的多种走法, 然后又轮到甲走棋, 而对乙的走法甲又有若干种方法应对⋯⋯, 如此反复。显然, 若从当前棋局状态(根节点)出发,找出所有可能的乙的走法(子节点), 再从每个子节点出发找出甲对应于每个乙的走法的所有应对(子子节点)⋯⋯,直到终局。由此构成了一棵树。
用字符串来表示每个棋局状态, 他们分别为⋯00000000⋯, ⋯00001000⋯, ⋯00010000⋯, ⋯00021000⋯,⋯00001200⋯, ⋯00012000⋯, ⋯00010⋯0200⋯, ⋯000210⋯0100⋯ , ⋯00021100⋯ , ⋯0100⋯00210⋯ , ⋯0010⋯00210⋯。 这是一个典型的指数复杂度问题,其计算量之大是目前所有的计算机都无法承受的, 因此,用搜索树法来解决人机博弈时,通常只能搜索到一个非常有限的深度,并根据此有限深度的形势来判断每种走法的优劣。为了提高搜索的效率,人们对搜索树法提出了各种改进方案。3.2 极小极大法(MinMa x 算法) 极小极大算法[4]是考虑双方对弈若干步之后, 从可能的走法中选一步相对好的来走。若最大(MAX)节点为己方下的棋,此时选择估值最大的点走。最小(MIN)节点为对方下的棋, 此时选择估值最小的点行走。因此MIN 节点的父节点(MAX 节点)所赋的倒推值等于端节点估值中的最大值。另一方面, MAX 节点的父节点(MIN 节点)所赋的倒推值等于端节点估值中的最小值。这样一级一级地计算倒推值, 直至起始节点的后继节点也被赋以倒推值为止, 即从下往上逐层交替使用极小极大的选值方法。部分算法描述如下:if (jiedian_dizhi=0), then chessboard= style;if (style=1), then t=Minmax (deepness- 1), 且value=max{value,t};else t= Minmax(deepness- 1), 且value=min{value,t}; 为了描述棋局状态的优劣, 要确定一个估值函数f。而博弈问题不同于一般的数值计算。它追求的目标不仅要是对己方最有利的方案, 而且要尽量选择对对方有利的方案。即不能简单地以输赢为目的, 而是要以对弈的质量为目标。所以我们设计这样的估值函数。找出字符串中的1 或2 所在的位置Wi, 并通过计算Wi / 15 来判断棋盘上落子情况, 并据此定义每一条直线上的估值函数[5]f( i) =hc( i) + hm( i) 。具体定义方法如下: 若棋型为(“1) +++*++”, 则hc( i) = 30, (“2) ++**++”, 则hc( i) = 100,(“3) +***++”, 则hc( i) = 300, (“4) +****+”, 则hc( i) =1000,(“5) *****”, 则hc( i) = 10000, (“6) #****++”, 则hc( i)= 300,同理定义hm( i) 。其中“, +”代表空点“, *”代表棋子“, #”代表对方棋子, hc( i) 表示一方的评价函数, hm( i) 表示另一方的评价函数。这样便可知道f=!f( i) 来判断棋局状态的优劣了。显然, 当搜索深度增加时, 搜索节点快速大幅增加, 时间和内存空间消耗太大, 且利用先前信息的效率较低。于是人们在极小极大的基础上提出了α—β 剪枝技术。3.3 αβ 算法 αβ 算法是指, 当甲向下搜索节点时发现走第一个子节点就可以赢了, 则剩下的节点就不需要再搜索, 甲的值就是第一个子节点的值。即可以将甲的其余后继节点抛弃, 此过程称为剪枝。如果甲所在的层是MAX 节点的层, 则称此剪枝为α剪枝, 否则成为β 剪枝。如图2 所示, 若节点A 在极大层, 而节点B 的值为15, 节点D 的值为10, 则节点C 的值必10, 而A的值取15, 即C 及其后继节点就可以剪去。此过程为α 剪枝。若节点A 在极小层, 而节点B 的值为15, 节点D 的值为20, 则节点C 的值必20, 而A 的值取15, 即C 及其后继节点就可以剪去。此过程为β 剪枝。在程序实现过程中, 被剪枝的节点在jiedian_dizhi[ ]中被赋值为1。与极小极大算法相比, αβ 剪枝需要遍历的节点远远减少, 它能在较短的时间内找到最佳的走法节点。αβ 算法的部分算法为:if (jiedian_dizhi=0), then chessboard= style, t=AlphaB(deepness- 1, Alp, Bet);if (style=1), then t=max{Alp,t}且if (Alp>Bel), 进行α 剪枝;else t=min{Bel,t}且if (Alp>Bel), 进行β 剪枝;3.4 修正α—β 剪枝法 虽然αβ 算法的搜索速度大有提高, 但搜索效率还是不太理想, 不利于实现真正的人机对弈。分析αβ 算法的实现过程, 发现在一次搜索过程中被修剪的枝数取决于早期的αβ值与最终的倒推值之间的近似程度, 且剪枝数越多, 搜索速度越快。因此在程序实现时对棋子的位置进行排序[4]。如在棋盘中心下了棋子的一方获胜的机率就大, 在中心周围下子的机率就次之。再者, 考虑到实际应用。在下棋过程中双方一般都是尽量在棋盘中心位置附近下子, 且双方下子的位置一般都在对方棋子的附近某个地方, 因此不必要让计算机每次都从整个棋盘开始搜索, 从而减少搜索范围提高搜索效率。3.5 遗传算法 以上各种算法都是从博弈树开始的, 并在此基础上提出了各种改进方案, 提高了搜索的效率, 但这些方法都无法从根本上解决搜索树的指数复杂度问题。当搜索深度不断加深时, 对计算机的智能水平要求就增加, 而上述各种方法却是反应速度越来越慢。所以我们考虑用遗传算法来改变这种瓶颈状态。遗传算法是一种非数值并行随机优化算法, 是基于生物学适者生存理论的进化算法, 非常适用于可行解优化问题的求解。遗传算法的基本思想是:对问题的可行解进行二进制编码从而得到一个串,随机选择若干可行解,组成原始种群。设计适应度函数,并计算种群中每个个体的适应度函数值,再根据适应度函数值的大小确定种群中每个个体的遗传概率,让适应性强的个体获得较多的遗传机会来生成子代。重复上述过程,最终得到问题的满意解。3.5.1 初始化种群的选择 从αβ 算法得到的结果中随机选取m 个编号排列作为父代初始种群, 并分别计算他们的适应度函数值, 并对其按适应度函数值由大到小排序。3.5.2 遗传操作 (1 )交叉: 对博弈串进行交叉操作时必须保证可下子的地方只能下一个棋子, 故要及时更新jiedian_dizhi[ ]。且在具体的实现过程中采用多点顺序交叉的方法进行, 并结合修正α—β 剪枝法优先选取中心位置及对方棋子附近的点作为交叉点。 (2 )变异: 从博弈串中以较大的概率随机选取中心位置及对方棋子附近的若干对点进行交换。 (3 )保优: 在父代种群中保留最好的一个作为子代种群中的一个。3.5.3 停止条件 重复上述的遗传操作, 直至所得到的最优解的适应度函数值达到了期望值或达到了最大遗传代数。3.5.4 部分算法描述for i=1,2,⋯,nCrossover (group[n]); New_jdwz (p, q, k);Changeover (group[n]); New_jdwz (p, q, k);group[n]= group[n+1];4 例证实验 因为我们设计程序时没有考虑具体的界面输出, 所以在例证时是通过及时输入转化后的数据进行的, 而博弈的结果也是通过数据再次转化得到的。通过分析转化后的结果可以看到博弈的质量基本上能够达到实用的要求。5 结束语 将遗传算法结合现有的改进博弈树法进行运算, 能够在较短时间内找到下子的最佳位置, 从而提高了对弈的质量。用这种方法求解时需要准备大量的数据, 相对来说也抑制了博弈程序的快速运算, 且在适应度函数的选择上也有需要改进的地方。参考文献[1] 吕健希.关于五子棋对弈程序的讨论[J].中文信息,2003.22(7):66- 68.[2] 严小卫,莫建文.智能五子棋的设计与实现[J].广西师范大学学报(自然科学版),1999.17(4):11- 14.[3] 董红安, 蒋秀英.智能五子棋博弈程序的核心算法[J].枣庄学院学报,2005.22(2):61- 65.[4] 瞿锡泉, 白振兴,包建平.棋类博弈算法的改进[J].现代电子技术,2005.35(1):96- 99.[5] 白振兴, 张海峰,张登福.棋类博弈算法的改进[J].现代电子技术,2004.27(7):25- 27.
|
|
发表于 2008-1-8 12:14:28
/4 
