《五子棋算法研究》由会员分享，可在线阅读，更多相关《五子棋算法研究（11页珍藏版）》请在金锄头文库上搜索。
1、1五子棋算法研究信息与计算科学 2003 级 蔡 杰指导教师 汪 建 副教授摘要：摘要：人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一，他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。关键词：关键词：五子棋，人工智能，搜索Gobang algorithm to researchCAI Jie Information and Computational Science, Grade 2003 Directed by WANG Jian (Associate Professo
2、r)Abstract: Artificial intelligence is a newly-developed and highly comprehensive frontier science of rapid development. Gambling and chess is one of the major artificial intelligence research areas. It involves reasoning，decisionmaking and planning. These techniques are applied to the gobang. An in
3、telligent gobang system is designed and realized in the game between human and computer.Keywords: Gobang, Artificial intelligence, Search1 绪论绪论在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算2机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近 50 年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农(
4、1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从 1980 开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了 1997 年，IBM超级电脑 Deeper Blue 击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。1.1 电脑五子棋简介电脑五子棋简介五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠” ，英译为“Ren-ju”，英文称之为“Gobang”或“FIR”(Five in a Row 的缩写)，亦有“连五子” 、“五子连” 、 “串珠” 、 “五目” 、 “五目碰” 、 “五格”等
5、多种称谓。五子棋不仅能增强思维能力，提高智力，而且变化多端，非常富有趣味性 5 和消遣性，因此为人民群众所喜闻乐见。本文在研究博弈机器人系统过程中，对五子棋博弈算法进行了一些有效的研究，设计和实现一个人机对弈的五子棋程序。五子棋属于黑白棋的一种，它的博弈树复杂度为 10，状态空间复杂度为 10。因此盘面预测的计算量是非常大的，比如对于五子棋70105的中盘走法中，如果要预测四步的局面数的话可以达到一百万。1.2 设计思路总介绍设计思路总介绍本文是对五子棋算法的设计原理和实现方法进行探讨和研究，主要包括数据结构、搜索算法和优劣评价函数组成，主要的特点包括快速的数据结构设计实现、以及高效率的搜索算
6、法和尽可能的模拟人类的智能。1.3 本文架构本文架构第一章将会阐述计算机博弈发展以及对电脑五子棋的介绍、电脑五子棋的状态空间复杂度以及文章架构。第二章首先描述了电脑象棋表示的一些基本数据结构。第三章将重点讲述博弈树的搜索方法，包括博弈树构建、各算法介绍、以及五子棋规则的实现，最后对整体搜索框架进行总结。最后，第四章是全文的总结及展望。2 数据结构数据结构2.1 棋局的表示棋局的表示我们知道五子棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方出现三三（包括“四、三、三”） 、四四（包括“四、四、三”） ，而黑方只能以四三取胜，如3果黑方走出禁手则是输；五连与禁手同时形成，先五为胜，
7、等等的规矩。但是电脑毕竟不是人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明白的评判标准。首先介绍一个五子棋中的常用术语：阳线：棋盘上可见的横纵直线。阴线：棋盘上无实线连接的隐形斜线。活 3：由于一方走一着在无子交叉点上形成一个“活三”的局面，也就是在放一子就可行成 4 连了。活 4：在棋盘某一条阳线或阴线上有同色 4 子不间隔地紧紧相连，且在此 4 子两端延长线上各有一个无子的交叉点与此 4 子紧密相连。冲四：除“活四“外的，再下一着棋便可形成五连，并且存在五连的可能性的局面。由于篇幅有限不能将所有的规则讲完，只是提出了对讲算法有用的几点加以叙述。如何让电脑知道该落子在哪一点
8、呢，在这方面。电脑要做得和人一样，判断棋盘上每一点的重要度。比如冲四比冲强，冲三比造二强，遇到四三如果是对方的，堵死，如果是自己的，优先落子。遇到双三，如果是黑棋，黑方输，如果是白棋，优先等级仅次于四三。我们看到电脑在运算的时候，同种棋型在敌我双方的优先等级并不相同，由于禁手的缘故黑棋和白棋的处理也不相同。同样是四三，如果是玩家的，则电脑不会冲自己的，而是先堵玩家的。禁手的处理比较复杂，我们稍候讨论。下面，我列出基本的棋型优先顺序：造一个二 ) return ;)return ;)MIN 结点的 剪枝函数：int Min (point p, , )在 p 处下黑子；if(已到达搜索的最后一层)
9、 return Evalue();for(int i= 0；i 15；i+ + )for(int j=0；j 15；j+ +)point pt=(i,j)；=min(, Max (pt, , )if(=) return ;)returnp ;)如果 Max(point p,)函数，则返回对 Max 结点最有利的走步的局势静态估值函数值。反之 Min (point p, , )函数，则返回对 Min 结点最有利的局势静态估值函数值。两种互为递归调用，可以动态改变搜索深度。3.3 优化估值函数优化估值函数通过以上的研究可以看出，在博弈的程序中电脑的行为都是以估值函数为依据的，所以说估值函数在很大的
10、程度上是决定了电脑的棋力高低。我们可以采用遗传算法来改进静态估值。遗传算法的估计值在很大的程度上也依赖于实施者的经验。但是可以利用一些高水平名局棋谱或同其他博弈程序对弈，看使用某一组参数时取胜的机率有多大来进行较验。经过几次的试验一般就可以得到较好的静态估值。9传统的算法一般只能维护一组较好的参数。遗传算法同传统的算法相比可以同时维护几组较好的参数，通过向其中添加一组新参数，通常是将几组老参数中选出的值组合在一起做一点变化。然后同几组老的参数比较孰优孰劣，将最差的一组从中去除。这里面较重要的操作是交叉和变异操作。交叉通过随机交换父代个体的信息来继承已有参数中的优良内容；变异通过随机改变个体中的
11、基因而增加种群的多样性，避免优化的因局部震荡而失败。遗传算法的优点：(1)由于搜索算法是从问题的解开始的，而不是一组参数。所以被局部震荡干扰导致求最优解失败的可能性大大减小。(2)此算法能将搜索重点集中于性能高的部分，能较快地求出最佳的参数。遗传算法的优化估值参数的过程：首先是随机产生几组参数作为初始种群；接着对种群的参数进行收敛判断，收敛则输出优化结果并且评估过程结束，否则就执行复制操作产生一组新参数；然后取 0、1 之间的随机数，让随机数和交叉概率进行比较；若大于则执行交叉操作改变新参数，若小于就不用执行这一步；接着取 0、1 之间的随机数，随机数和变异概率进行比较，若大于就执行变异操作改
12、变新参数，小于就不执行这一步；接着是把较差的一组参数从种群中去除；接着跳回第二步判断是否已经收敛，如此循环就能将搜索重点集中于性能高的部分，能较快地求出最佳的参数。画图2 表示如下：10随机产生几组参数作为初始种群对种群的参数进行是否收敛判断Y输出优化结果 N执行复制操作产生一组新参数取 0、1 之间的随机数，让随机数和交叉概率进行比 较执行交叉操作改变新参数取 0、1 之间的随机数，随机数和变异概率进行比较执行变异操作改变新参数把较差 的一组 从种群 中去掉图 4：遗传算法评估过程 图 3.4 禁手特征计算禁手特征计算五子棋中还有项规则就是是禁手的判断，在上边已经给出了 3 颗棋子的时候的分
13、值为1000。如果是双三则需要乘以 2，即 2000。电脑在分值表中将会判断双三点比一个三的点更为重要。这在电脑进行全局判断的时候也是正确的，可是如果电脑执黑子，这一点是不能落子的，否则将导致失败。但是电脑不能真的会自己去判断，只有认为的给他一个判断的标准，处理的方法是：在累加分值的时候增加一个判断语句，如果正好形成双三，那么这一点不加入分值表同时判断此点落棋将判为负，其他禁手按同样的方法处理。4 结论及展望未来结论及展望未来.1 总结总结本文介绍了应用人工智能设计五子棋的总体方法。用极大极小值的过程以及启发式搜索的方法，采用静态估值函数对各节点的代价进行估计，应用遗传算法对估计的值进行了优化
14、，克服了人为主观因素的片面性。对博弈的研究具有一定的借鉴意义。在实际五子棋系统的设计中。应用本方法只向前搜索了三步，就可以取得很好的效果。也可以增加搜索的深度来提高系统的判断能力，但是是以牺牲电脑的运算速度为前提的，毕竟加深搜索的话就需要更大的运算量。此外，也可以通过增加机器学习，比如电脑对棋局进行记忆，在对手落子之前对棋局和之前记忆的棋局进行比较，先判断出更优的走法，就11可以进一步提高系统的智能。4.2 未来展望未来展望随着 Intel HP(超线程技术)的实现和将来多处理器 PC 机的普及对于数据计算量大的人机对弈问题必然要求应用并行的思想去处理。超快搜索速度和必要的复盘“反思”必然带给
15、下棋电脑更多智慧。参考文献：参考文献：1蔡自兴人工智能及其应用M北京：清华大学出版社，19992阎平凡人工神经网络与模拟进化计算M北京：清华大学出版社，20023王小春游戏编程(人机博弈)M重庆：重庆大学出版社，20024Nils J Nilsson，郑扣根，庄越挺译Artificial Intelligence A New SynthesisM北京：机械工业出版社，20005陈尔绍传感器实用装置制作集锦M北京：人民邮电出版社，19996邓天炎，李爱华，尹正主编离散数学教程M徐州：中国矿业大学出版社，20027潘金贵，顾铁成，曾俭等编译现代计算机常用数据结构和算法M南京：南京大学出版社，199
16、48王小平遗传算法理论应用与软件实现M西安：西安交通大学出版社，19989王永庆人工智能原理与方法M西安：西安交通大学出版社，199810 林尧瑞，马少平人工智能导论M北京：清华出版社，198911 田盛丰，黄厚宽人工智能与知识工程M北京：中国铁道出版社，199912 陆汝钤人工智能M北京：科学出版社，199513 王镌博弈树搜索的算法改进J福建电脑2004，(2)14 蒋加伏，陈蔼样，唐贤英基于知识推理的博弈树搜索算法J计算机工程与应用，2004，(1)15 Nilsson NJ人工智能M北京：机械工业出版社，2000致谢致谢本论文是在汪建老师的悉心指导下完成的，在论文写作过程中王老师深切关注，在我题目选择上和文章写作上都得到了汪建老师的悉心指导和帮助，在此
