五子棋中的博弈智能设计.pdf

五子棋中的模拟人工智能设计蒋甜 曹涛三峡大学计算机与信息学院 20081121班摘要: 博弈是人工智能的主要研究领域之一, 他涉及人工智能中的推理技术搜索方法和决策规划本文将这些技术用于五子棋中, 设计了一个智能五子棋系统, 实现人和计算机进行博弈关键字：博弈 ; 五子棋; 人工智能 ; 遗传算法引言随着近几十年来人工智能的飞速发展，越来越多的具有智能的机器进入了人类的生活， 人工智能的重要性如今显而易见人工智能属于计算机科学的领域，它以计算机技术为基础，近几十年来，它的理论和技术已经日益成熟， 应用领域也正在不断扩大， 显示出强大的生命力广义上来讲，博弈是指在一定的环境条件和一定的规则约束下，依靠自己所能够掌握的信息， 从各自选择的行为或是策略进行选择并加以实施，并从各自取得相应结果或收益的过程而在本文狭义的讲，博弈论主要是研究棋手们落子中理性化、逻辑化的部分， 进而找出攻守最合理的棋子位置 换言之，博弈就是研究个体如何在错综复杂的相互影响中得出最合理的策略，从而找出最佳的解决方法 人工智能中大多以下棋为例研究博弈规律, 在此, 以五子棋为入口进行研究, 设计了一个模拟人工智能的五子棋系统, 共同探讨博弈中人工智能的设计方法。

1、人机博弈的要点人机对弈的程序 , 至少应具备以下5 个部分 : (1) 某种在机器中表示棋局的方法, 能够让程序知道博弈的状态2) 产生合法走法的规则 , 以使博弈公正地进行 , 并可判断人类对手是否乱走3) 从所有合法的走法中选择最佳的走法技术4) 一种评估局面优劣的方法, 用以同上面的技术配合做出智能的选择5) 一个用户界面 , 有了他 , 这个程序才能用2、五子棋的下棋规则(1) 棋盘采用像围棋盘一样的15 路或 19 路线的棋盘 , 在此采用 15 路的棋盘2) 下法两人分别执黑白两色棋子 轮流在棋盘上选择一个无子的交叉点落子 , 无子的交叉点又被称为空点3) 输赢判断黑、白双方有一方的五个棋子在横、竖或斜方向上连接成一线即为该方赢3、算法设计3.1权值图 3-1 假如某棋局如图 3-1 所示，黑子为计算机所有的对于计算机来说，若要进攻可选择（ 4,5 ）,(7,5),(9,5)这些位置，当然其中 (7,5) 肯定是最佳的，我们可以用权值的大小来区分它们在进攻中的重要性，位置（4,5 ）进攻权值可设为2500、位置（7,5 ）进攻权值可设为4000,、位置（ 9,5 ）可设为2500。

若要防守，位置（ 7,2 ）肯定是最佳的，因此我们可以将 (5,2) 、 (7,2) 、 (9,2) 的防守权值分别设为2500、 4000、2500，来区分每个位置在防守中的重要性对棋盘上的每个位置赋权值, 权值越大表示此位置越重要每个位置都有两个权值（ maxa 、maxd ） ，maxa表示进攻的权值， maxd表示防守的权值 计算机每次下棋之前都要对整个棋盘进行扫描，分别计算出各个空位置（没有棋子的位置）的maxa 、maxd ，并分别将它们存储起来计算机再根据各个位置的maxa 、maxd来决定要下的位置3.2 权值估算权值的大小是根据下五子棋的经验来估算的，权值的大小设置得越恰当程序的智能就越高每个位置的maxa和 maxd都是用同一个函数来计算的权值的计算方法： 每个位置的权值等于其各个方向权值累加之和而各个方向上的权值的计算按以下方法进行例如在某个方向上：（@ 表示计算机的棋子后面说成黑子，#表示对手棋子以后说成白子或棋盘边界， 0 表示空位置 , ）@ @ @ # @ 0 @ 0 @ 0 1 2 3 4 5 6 7 8 9 10 位置 6 处进攻的权值可以这样来计算，假设位置5 处已经下了一颗黑子，那么位置3~7 为@@@0@这种组合，这种组合对应的权值为2500。

（之所以选择5~9 这种组合而不选择2~6、6~10，是因为 5~9中所包含的黑子数最多并且不能包含白子）位置 6 处防守权值可以用类似的方法求得，我们只需将位置6 处的黑子改为白子， 找连续 5 个位置包含白子最多的那种组合（这五个位置中不允许出现黑子， 如果找不到这样连续的五个位置，则将其权值设置为 0） ，根据此组合找到对应的权值在系统中使用的主要估值规则如下（给出连续 7个位置组合， 位置1, 、 7分别为首和尾） : a) 当这七个位置的形式为 0？？？？？ 0或#0？？？？ 0或0？？？？ 0#时（下面只写出中间五个连续位置的组合） @000@ 权值=5；@00@0或0@00@ 权值=25； @0@00或0@0@0或00@0@ 权值=65； @@000或0@@00或00@@0或000@@ 权值=70； @0@0@ 权值=90； @@00@ 权值=90； @@0@0 权值=550； @@@00 权值=650； @@0@@ 权值=2400； @0@@@或@@@0@ 权值=2500； @@@@0或0@@@@ 进攻权值 =5100，防守权值 =4000 （注意此处的 进攻与防守权值是不同的） b) #@ ？？？？ 0或0？？？？ @# 或#？？？？ #类型时 当其中有 4个黑子时权值=2250； 当其中黑字数少于 4颗时权值=0； c) ？@@@@@？类型（即连续有五颗子在同一直线上） 权值=50000； 注：以上的权值都是经验值 通过下面这个例子我们来看一下权值的具体求法：图3-2 我们要求（ 6，6）处进攻权值 maxa 和防守权值 maxd ，具体的求法： 1) maxa ：先在（ 6,6）处放上一颗黑子，再由各个方向上黑子的 组合情况来确定权值 竖直方向 maxa1=0；（（1,0 ），（ 0,1））方向上 maxa2=0； 水平方向上由(5,6),(6,6),(7,6),(8,6),(9,6)五个 位置组成 0@@0@@0类型， 其对应的权值 maxa3=2400；((0,0)，(1,1))方向上由 (3,3),(4,4),(5,5),(6,6),(7,7)五个位置组成 000@@@0类型 其对应的权值为 maxa4=650；maxa=maxa1+ maxa2+ maxa3+ maxa4=3050; 2) maxd ：先在（ 6,6）处置一白子，再由各个方向上白子的组合 情况来确定权值 竖直方向上 (4,6),(5,6),(6,6),(7,6,),(8,6)五个位 置组成 #@@@0@0类型maxd1=2250; （（1,0），（0,1 ））方向上 maxd2=0； 水平方向 maxd3=0；((0,0)，(1,1))方向上 maxd4=0 ； maxd=maxd1+maxd2+maxd3+mxad4=2250; 3.3 策略抉择计算机将棋子下在某个位置，可以用于进攻、可以用于防守、也可以既进攻又防守。

在决策中我们采用的是遗传算法，先分别找出 maxa较大的一些位置和maxd较大的位置，并对这些位置运用同样的策略算法进行第一次预测，经过第一步预测淘汰一些位置，再对保留下来的位置运用同样的策略算法进行第二步预测，进过第二步预测再淘汰一些位置，再对保留下来的位置运用同样的策略算法进行第三步预测,,预测的程度越深，则选择的位置将越恰当决策算法：其中 Maxa 、Maxd分别表示棋盘上所有空位置maxa 、maxd的最大值, 当 Maxa ≥50000 时直接选择 maxa最大的那个位置，进攻当 2800≤Maxa ＜50000且 Maxd550和 maxd>550的位置进行预测，第一步预测后保留部分进攻权值较大和防守权值较大的位置，类似的进行第二步， 第三步预测 并根据最终 maxa和 maxd的值来确定是选择进攻还是防守 下棋子时的目的就是让棋盘上所有位置的 maxa最大值 Maxa变得更大或 maxd最大值 Maxd变得更小，或 Maxa变大同时 Maxd变小下棋的原则就是让Maxa变得更大， Maxd变得更小以图 3-2 的棋局为例进行说明策略算法的具体实现过程图 3-2 黑子为计算机，白子为对手程序先对整个棋盘空位置进行扫描并计算出各个位置的maxa和 maxd ，通过搜索找到 maxa与 maxd的最大值，图 3-2 中Maxa=3050 、Maxd=2250满足“2800≤Maxa ＜50000且 Maxd<50000 ”这种条件，因此不必进行预测直接选择Maxa对应的位置（ 6,6）。

五子棋最终的实现：4、结语本文介绍了模拟人工智能博弈设计五子棋, 用设定权值的方法, 采用权值计算函数对各节点的权值大小进行计算通过对各种情况的分析优化权值的大小， 进而达到更高的人工智能， 同时运用遗传算法进一步提高人工智能 当然模拟人工智能的方法还有很多，比如说建立树搜索模型等等， 此外, 也可以通过增加机器学习, 对棋局进行记忆、总结学习 , 就可以进一步提高系统的智能参考文献 [ 1 ] 蔡自兴 1 人工智能及其应用 [M ] 1 北京: 清华大学 出版社 , 19991 [ 2 ] 王永庆 1 人工智能原理与方法 [M ] 1 西安: 西安 交通大学出版社 , 20001 。