人工智能五子棋论文
本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。以下是小编整理分享的关于人工智能五子棋论文的相关文章，欢迎阅读!
人工智能五子棋论文篇一
智能五子棋博弈算法研究
摘要：人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一，他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。
关键词：五子棋 人工智能 搜索
人工智能是一门综合性很强的边缘科学，它研究如何使计算机去做那些过去只能靠人的智力才能做的工作。而博弈是人工智能研究的一个重要分支，它不仅存在于游戏、下棋之中，也存在于政治、经济、军事和生物竞争中。
五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Ren-ju”，英文称之为“Gobang”或“FIR”(Five in a Row的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。与其他棋类相比，五子棋每一层搜索节点数量庞大，因此盘面预测的计算量是非常大的，比如对于五子棋的中盘走法中，如果要预测四步的局面数的话可以达到一百万。
本文是对五子棋算法的设计原理和实现方法进行探讨和研究，主要包括数据结构、搜索算法和优劣评价函数组成，主要的特点包括快速的数据结构设计实现、以及高效率的搜索算法和尽可能的模拟人类的智能。
1、棋局的数据结构表示
我们知道五子棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方出现三三(包括“四、三、三”)、四四(包括“四、四、三”)，而黑方只能以四三取胜，如果黑方走出禁手则是输;五连与禁手同时形成，先五为胜，等等的规矩。但是电脑毕竟不是人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明白的评判标准。
下面，我列出基本的棋型优先顺序：
造一个二<……<造四个二<冲三<……<冲两个二和一个三<冲双三<冲四<冲四三。
之所以这么设置是由于五子棋的下法所致，只要构成5颗一线就赢了，所以说一条线上构成的越多那么就有优势，当然就是棋数越多，分越多。
那么为了让电脑明确的知道是不是应该落子，就给它一个标准：分值。用程序语言表示：
enum Value {FAILED=-99999，SKIP=20，LENG=10，TWO =100，THREE =1000， IF0UR =10000，FOUR =50000，SF0UR=70000，WIN=100000};
如果某一点导致失败，则分值为FAILED，由于它足够小，所以无论任何棋型与它的组合都小于0，SKIP之所以给它20分，是为了避免电脑出现无棋可下的情况，LENG是有可能发生长连的点，这有可能导致禁手，TWO、THREE、FOUR、WIN 观名知意，TFOUR 和SFOUR分别是弱四和强四。强四的点比普通的冲四重要的多，比如一个活四，意味着即将判出胜负。弱四是为了提供更大的灵活。也许有某种冲四并不一定比冲三重要，我在这里并没有使用，以后可以扩充。
2、五子棋算法介绍及初步实现
2.1 五子棋博弈树中的极大极小搜索和α-β剪枝
为了使谈论更有条理性[5]，将博弈的双方分别命名为MAX和MIN。而搜索的任务是为MAX找最佳的移动。假设MAX先移动(此时暂时不考虑五子棋的禁手等规则)，然后2个博弈者轮流移动。因此，深度为偶数的节点，对应于MAX下一步移动的位置，称为MAX节点;深度为奇数的节点对应于MIN下一步移动的位置，称为MIN节点(博弈树的顶节点深度为0)。k层包括深度为2k和2k+1的节点。通常用层数表示博弈树的搜索深度。他可以表示出向前预测的MAX和MIN交替运动的回合数。
用整个棋盘估值的函数h(n)为静态估值函数。设想当前棋局S为轮到计算机方下棋(用方框表示)，任选一空点作为计算机方的下棋位置(可有若干种选择)，接着考虑在此情况下游戏者一方下棋的棋局(用圆圈表示);从某一个圆圈棋局出发，任选一空点作为游戏者一方的落子处(又有若干种选择)。再次形成计算机方下棋的方框棋局;依此类推，这样可形成一棵以S为根结点的博弈树，该树以圆圈棋局为第2层子结点，以方框棋局为第3层子结点等等。如果继续向前搜索，可形成多层子结点，现在以向前搜索3层子结点为例来说明极大极小值的过程。对第3层子结点的某一棋局n，求出其估计值h(n)，假设有一博弈树已形成，如图1所示[2]，h(n)的值由各结点旁的数值给出。
根据极小极大化分析法，先计算第3层子结点h(n)值，然后第2层子结点的估计值取他的各后继子结点的极小值，根结点的估计值取他的各子结点的极大值。这个取得最大估计值的子结点即为从S出发的计算机方的最佳落子方案。棋盘上某一行、某一列或某一对角线为一路，这里使用的棋盘为19行19列，因此，行和列方向上共有19+19=38路;从左下到右上方向的对角线有37路，同样，从左上到右下方向的对角线也有37路。但对于五子棋来说必须在一条直线上有连续五个棋子才能赢。因此，在对角线上就可以减少8路。所以，整个棋盘路的总数为：38+(37-8)+(37-8)=96路。对某一棋局n[14-15]，第i路得分：
h(i)=h(i)t-hm(i)[1]。
我们不用把每个节点都搜索一遍也可获得和极大极小搜索同样结果的走步，不搜索分支节点而舍弃该分支的过程叫剪枝。常用的剪枝方法是α-β剪枝算法。
在极大极小搜索的过程中，存在着一定程度的数据冗余。如下图2所示左半部的一棵极大极小树的片断，节点下面为该节点的值，设A 为极大值节点，节点B的值为18，节点D 的值为16，由此可以判断节点C的值将小于等于16(取极小值);而节点A的值为节点Max(B，C)，是18，也就是说不再需要估节点C的其他子节点如E、F的值就可以得出父节点A 的值了。这样将节点D 的后继兄弟节点减去称为Alpha剪枝(α剪枝)。如图2：
同样道理在图3右半部一棵极大极小树的片段中，设A为极小值节点，节点B的估值为8，节点D的估值为l8，由此可以判断节点C的值将大于等于18(取极大值);而节点A 的值为Min(B，c)，是8。也就是说不再需要求节点C的其他子节点如E、F值就可以得出父节点A 的值了。这样将节点D的后继兄弟节点剪去称为Beta剪枝(β剪枝)。如图3： 将Alpha剪枝和Beta剪枝加入极大极小搜索，就得到α-β搜索算法。
现在假设五子棋问题深度为3的搜索树给出α-β剪枝算法，用类C语言对其进行描述：
设电脑为Max，人为Min，初始时α为-∞，β为+∞;函数Evalue( )返回对当前局面的估值
在p处下黑子;
if(已到达搜索的最后一层) return Evalue( );
如果Max(point p，α，β)函数，则返回对Max结点最有利的走步的局势静态估值函数值。反之Min (point p， α， β)函数，则返回对Min结点最有利的局势静态估值函数值。两种互为递归调用，可以动态改变搜索深度。
2.2 优化估值函数
通过以上的研究可以看出，在博弈的程序中电脑的行为都是以估值函数为依据的，所以说估值函数在很大的程度上是决定了电脑的棋力高低。我们可以采用遗传算法来改进静态估值。
遗传算法的优点：
(1)由于搜索算法是从问题的解开始的，而不是一组参数。所以被局部震荡干扰导致求最优解失败的可能性大大减小。
(2)此算法能将搜索重点集中于性能高的部分，能较快地求出最佳的参数。
遗传算法的优化估值参数的过程：首先是①随机产生几组参数作为初始种群;接着②对种群的参数进行收敛判断，收敛则③输出优化结果并且评估过程结束，否则就④执行复制操作产生一组新参数;然后⑤取0、1之间的随机数，让随机数和交叉概率进行比较;若大于⑥则执行交叉操作改变新参数，若小于就不用执行这一步;⑦接着取0、1之间的随机数，随机数和变异概率进行比较，若⑧大于就执行变异操作改变新参数，小于就不执行这一步;接着是⑨把较差的一组参数从种群中去除;接着跳回第二步判断是否已经收敛，如此循环就能将搜索重点集中于性能高的部分，能较快地求出最佳的参数。画图4表示如下：
2.3 禁手特征计算
五子棋中还有项规则就是是禁手的判断，在上边已经给出了3颗棋子的时候的分值为1000。如果是双三则需要乘以2，即2000。电脑在分值表中将会判断双三点比一个三的点更为重要。这在电脑进行全局判断的时候也是正确的，可是如果电脑执黑子，这一点是不能落子的，否则将导致失败。但是电脑不能真的会自己去判断，只有认为的给他一个判断的标准，处理的方法是：在累加分值的时候增加一个判断语句，如果正好形成双三，那么这一点不加入分值表同时判断此点落棋将判为负，其他禁手按同样的方法处理。
3、结论及展望未来
3.1总结
本文介绍了应用人工智能设计五子棋的总体方法。用极大极小值的过程以及启发式搜索的方法，采用静态估值函数对各节点的代价进行估计，应用遗传算法对估计的值进行了优化，克服了人为主观因素的片面性。对博弈的研究具有一定的借鉴意义。在实际五子棋系统的设计中。应用本方法只向前搜索了三步，就可以取得很好的效果。也可以增加搜索的深度来提高系统的判断能力，但是是以牺牲电脑的运算速度为前提的，毕竟加深搜索的话就需要更大的运算量。此外，也可以通过增加机器学习，比如电脑对棋局进行记忆，在对手落子之前对棋局和之前记忆的棋局进行比较，先判断出更优的走法，就可以进一步提高系统的智能。
3.2 未来展望
随着Intel HP(超线程技术)的实现和将来多处理器PC机的普及.对于数据计算量大的人机对弈问题必然要求应用并行的思想去处理。超快搜索速度和必要的复盘“反思”必然带给下棋电脑更多智慧。
参考文献：
[1]蔡自兴.人工智能及其应用[M].北京：清华大学出版社，1999
[2]阎平凡.人工神经网络与模拟进化计算[M].北京：清华大学出版社，2002
[3]王小春.游戏编程(人机博弈)[M].重庆：重庆大学出版社，2002
[4]Nils J Nilsson，郑扣根，庄越挺译.Artificial Intelligence A New Synthesis[M].北京：机械工业出版社，2000
[5]陈尔绍.传感器实用装置制作集锦[M].北京：人民邮电出版社，1999
[6]邓天炎，李爱华，尹正主编.离散数学教程[M].徐州：中国矿业大学出版社，2002
[7]潘金贵，顾铁成，曾俭等编译.现代计算机常用数据结构和算法[M].南京：南京大学出版社，1994
[8]王小平.遗传算法-理论应用与软件实现[M].西安：西安交通大学出版社，1998
[9]王永庆.人工智能原理与方法[M].西安：西安交通大学出版社，1998
[10]林尧瑞，马少平.人工智能导论[M].北京：清华出版社，1989
[11]田盛丰，黄厚宽.人工智能与知识工程[M].北京：中国铁道出版社，1999
[12]陆汝钤.人工智能[M].北京：科学出版社，1995
[13]王镌.博弈树搜索的算法改进[J].福建电脑.2004，(2)
[14]蒋加伏，陈蔼样，唐贤英.基于知识推理的博弈树搜索算法[J].计算机工程与应用，2004，(1)
[15]Nilsson NJ.人工智能[M].北京：机械工业出版社，2000