毕业设计（论文）-基于C语言的五子棋辅助软件的设计与实现.doc

广东工业大学广东工业大学 本科毕业设计（论文） 基于基于 c c 语言的五子棋辅助软件的设计与实现语言的五子棋辅助软件的设计与实现 系系 部部 专专 业业 年年 级级 班级名称班级名称 学学 号号 学生姓名学生姓名 指导教师指导教师 2012 年年 5 月月 2 摘要摘要 1 随着近代电子计算机技术的突飞猛进，带动了各个产业各个部门的飞速改革， 人们的生活乃至世界观都被深深地影响着。而五子棋这一古老而传统的休闲对弈游 戏，在各种计算机辅助软件的帮助下， 发展、修正、建立起的连珠五子棋理论，超 过了过去一百多年全世界连珠五子棋开局理论总和的数百甚至上千倍之多。不同 类型的软件往往适用于不同方面的工作， 本软件适用于对时间限制比较严格的网 络棋赛的参考型辅助软件，局部分析能力具有优势。因为着重于内部算法的优化， 所以内部结构比较复杂，可移植性 稍有不足。使得本软件具有比赛辅助软件的棋力 的核心算法在于 vcf 遍历算法和对深度遍历算法的优化，例如权值的优化，以及 剪枝的优化算法，大大减少了时间的消耗，最大可能性的得到最优解。本次研发 使用 visual c+ 6.0 以及 c 语言进行开发与测试。 关键词：关键词：连珠， c 语言，算法分析，人工智能 2 abstractabstract with the rapid development of modern computer technology，various industrial is changing and peoples lives are profoundly affected. the renju which is a kind of ancient and traditional casual games development, amendment, and establish a pente renju theory with the help of a variety of computer-aided software. the modern theory is thousands of times more than in the past. different types of software often apply to different aspects of the work. this software applies to the reference to the time limit more stringent network chess game supporting software. this software focus on the optimization of the internal algorithm and has local analysis capability advantages. but portability is slightly insufficient. vcf traversal algorithm and the optimization of the depth of the traversal algorithm can make the software thinking depth of the supporting software. it greatly reducing the time consumption and maximum likelihood to obtain the optimal solution. using visual c + + 6.0 and the c programming language to develop and test. keywords：renju ，c programming language，algorithm analysis，artificial intelligence 目目 录录 1 绪论 1 1.1 五子棋背景简介.1 1.1.1 传统五子棋.1 1.1.2 连珠五子棋.1 1.2 连珠五子棋规则简介.1 1.3 c 语言简介 .2 2 系统分析.4 2.1 市场分析.4 2.1.1 五子棋辅助软件简介 .4 2.1.2 五子棋辅助软件的优劣势 .4 2.1.3 市场需求 .4 2.2 目的分析.5 2.3 总架构.5 2.3.1 总体功能结构 .5 2.3.2 总体流程 .6 2.4 功能架构.7 3 基础算法分析与实现 .10 3.1 棋盘 .10 3.1.1 位棋盘 10 3.1.2 权值棋盘 10 3.1.3 四色棋盘 11 3.2 棋谱12 3.3 胜负判定 .13 3.4 图层深度 .14 4 ai 运算算法分析与实现.16 4.1 四色棋盘算法16 4.2 权值棋盘算法17 4.3 a-b 剪枝 19 4.4 vcf 22 4.5 综合算法23 5 系统测试 .28 5.1 测试环境28 5.2 测试过程及结果28 结论 .31 参考文献 .33 致谢 .34 1 1 1 绪论绪论 1.1 五子棋背景简介五子棋背景简介 1.1.1 传统五子棋 五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白 棋种之一。发展于日本，流行于欧美。容易上手，老少皆宜，而且趣味横生，引人 入胜；不仅能增强思维能力，提高 智力，而且富含 哲理，有助于修身养性。 传统五子棋的 棋具与围棋相同， 棋子分为黑白两色，棋盘为 1515，棋子放 置于棋盘线交叉点上。两人对局，各执一色，轮流下一子，先将横、竖或斜线的 5 个或 5 个以上同色棋子连成不间断的一排者为胜。 1.1.2 连珠五子棋 据史料文献记载， 中国古代的五子棋先由中国传到 高丽（朝鲜） ，然后于公元 1688 年至 1704 年日本的元禄时代再从高丽传到日本，最 初在皇宫和贵族大家庭 中流行，到元禄末期，开始在民间盛行。 1899 年，对传统五子棋进行规则改良后， 经过公开征名， “联珠”这一名称才被正式确定下来。取意于 汉书律历志上中 “日月如合璧，五星如联珠 ”一句。现写做 “连珠”。 几乎是随着“连珠”名字的正式确立，各种越来越规范的五子棋规则发展起来， 其中包括了最为大众接受的禁手规则，以及进阶的 “三手可换” 、 “五手两打”专 用比赛规则，为了追求游戏本身的公平性，还有很多不同的规则被制定出来，五子 棋已经不再是大众所熟知的那个轻松简单的娱乐游戏，而逐渐演变为严谨而不失娱 乐的专业棋赛。 1.2 连珠五子棋规则简介连珠五子棋规则简介 在此主要介绍 “禁手”的规则，本次设计并未考虑职业比赛中必然出现的 “三手可换” 、 “五手两打”规则，因为职业比赛绝大多数是不能使用辅助软件的， 所以辅助软件只是为了理论研究以及提高个人棋艺的辅助工具。 2 禁手的规定： （1）黑棋禁手判负、白棋无禁手。黑棋禁手有 “三、三”、 “四、四”和“长连”， 包括“四、三、三 ”和“四、四、三 ”，即黑棋只能以 “四、三”取胜； 例举如下图所示： 图 1.1“三、三”禁手举例 图 1.1 中浅红色为三、三禁手点 图 1.2“四、四”禁手举例 图 1.2 中浅红色为四、四禁手点 图 1.3“长连”禁手举例 图 1.3 中浅红色为长连禁手点 （2）五连与禁手同时形成，判胜； （3）黑方禁手形成时，白方应立即指出。若白方未发现或发现后不立即指出， 反而继续落子，则禁手失效，不再判黑方负。 1.3 c 语言简介语言简介 c 语言是一种计算机程序设计语言 。它既具有 高级语言的特点，又具有 汇编 语言的特点。它由美国贝尔研究所的 d.m.ritchie 于 1972 年推出。1978 后，c 语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写 系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。 3 它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类 科研都需要用到 c 语言，适于编写系统软件，三维，二维图形和动画。具体应用比 如单片机以及 嵌入式系统开发 。 之所以选择 c 语言作为程序的开发语言，正是由于c 语言的高效性，这对于 加快程序的运行速度有着很大的帮助。之所以没用使用更加有利于运行速度的汇编 语言，主要考虑的还是一般非计算机专业人员很难从汇编的返回值中得到满意的答 案。所以最终剧中选择了最实用的 c 语言作为开发语言。 4 2 2 系统分析系统分析 2.1 市场分析市场分析 2.1.1 五子棋辅助软件简介 五子棋辅助软件的迅速发展 ，对连珠五子棋开局理论的研究起到了前所未有的 巨大推进作用，并成为网络连珠五子棋对弈中最 必要的工具之一。在各种辅助软 件的帮助下， 发展、修正、建立起的连珠五子棋开局理论，超过了过去一百多年全 世界连珠五子棋开局理论总和的数百甚至上千倍之多；目前高水平的网络五子棋对 弈、比赛，参赛选手绝大多选用 多个辅助软件互相作用，共同协作 。 2.1.2 五子棋辅助软件的优劣势 劣势：各种职业性大赛都是禁止使用任何辅助工具参加比赛的，这也在维持比 赛的趣味性的同时保障了比赛的公正性。有人说经常使用辅助软件会因为过于依赖 计算机的计算而忽略了 自身对局势的思考，因此 越来越对自己的判断失去信心， 进而有碍于个人棋力的增长 。所以，所有面对面比赛是不能使用软件来代替思考， 过多依赖软件确实会影响到个人的棋力。 优势：但是要知道，目前已经公开的 “花月” 、 “普月”开局必胜局的最精简 棋谱有接近 1 万张，即使是一个人花费了一生的精力也不可能完成制作出1 万张 无重复的必胜法棋谱，但是在当今计算机技术的发展之下，计算机的强大计算能力， 加之不断优化计算机的算法，越来越多的必胜局开局已经被完全正式确定。如今有 也有许多的网络棋赛，在比赛规则上就已经默认了使用辅助软件的有效性，而且作 为理论研究，辅助软件占据着非常重要的地位。 2.1.3 市场需求 一个专业的网络棋手，往往熟悉多个辅助软件并同时使用，这是由于不同的软 件有不同的优缺点，各个软件在时间以及深度的取舍不一样，有长考型、速度型、 棋谱记录型、局势分析型、局部计算型等等。而作为时间资源紧缺的比赛，那么速 5 度型的软件更加优越于细致全面的研究分析型软件，在研究分析棋谱的时候则是完 全相反的情况了。所以，市场的需求是无穷无尽的，不同的场合、不同的人群需要 不同类型的软件用于满足自身需求。 2.2 目的分析目的分析 结合市场分析的诸多要素，本软件的目标集中于耗时与深度的平衡，取舍于两 个极端，达到高效、有用的目的。为此，使用了多个分析算法为基础算法，根据不 同的情况，合理选择并收集其中的一个或者多个的计算结果，综合处理其信息，得 出一个新的、总的、最终的 ai 演算答案。 在基础算法中，对计算时间这一条件影响最大的莫过于“搜索的层数 ” ，类似 于我们在预测未来几步棋的发展趋势，总所周知，一个棋手看得比对手更远，自然 跟容易赢得比赛。同理作用于计算机，可是 即使计算机的存储器已经扩大到了足 够的大小，但是运算器的运算效率才是时间消耗的最大问题，假设在15*15 的棋 盘上已经存在 k 个棋子，要无差别的推算出 n 步之后棋盘上所有可能出现的情况， 那么就需要重复运算 (15*15-k)!/( 15*15-k-n)!，时间复杂度 t(n)=o(nn)，可见 随着 n 的增大，运算量足以变得大得惊人。于是，如何在基础算法上优化搜索范围， 尽可能降低搜索层次的同时保障运算结果的可靠性，是一个很难也是很核心的问题。 2.3 总架构总架构 2.3.1 总体功能结构 主要功能模块包括： （1） 输入：输入落子信息以及输入控制信息。 （2） 换子：玩家与 ai 互换棋子，在软件实现中表现为玩家放弃落子转而让 ai 代替玩家落子，但同时也完成了黑白棋子的互换。 （3） 查询：查询当前棋子的颜色，以及查询棋谱。 （4） 悔棋：删除上一步棋子，然后轮到玩家落子。 （5） ai 运算：ai 计算出最优落子点落子。 6 如图 2.1 所示： 落 子 信 息 控 制 信 息 输 入 换 子 查 询 悔 棋 胜 负 判 定 主 控 制 循 环 ai 运 算 盘 面 分 析 连珠五子棋辅助软件 图 2.1 总体功能结构图 2.3.2 总体流程 主要流程模块如下： （1）初始化 （2）主控制循环 （3）盘面分析计算 （4）胜负判定 如图 2.2 所示： 7 玩家落子电脑落子 胜负未定 某方获胜 初始化 外部输入落子 开始 主控制循 环模块 盘面分析计算 计算结果落子 胜负判定 结束 图 2.2 总流程图 2.4 功能架构功能架构 （1）初始化：首先，建立 位棋盘 byteboard256、对战双方的 权值棋盘 computer15154,player15154、四色棋盘 color1515 ，并将它们清零以 备使用。如图 2.3 所示： 初始化 byteboard 模块初始化 computer,player 模块初始化 color 模块初始化 图 2.3 初始化功能模块 （2）主循环控制模块： 8 输入，输入落子信息、输入主控信息 交换，棋子互换 查询，查询当前棋子颜色、查询棋谱 悔棋，退回上一步 退出，退出程序 实现流程如图所示 2.4 所示： y y n n n y 输入 输入是否为 3 输入是否为 4 输入是否为 5 查询 悔棋 退出 提示界面 输入是否为 2 交换 y n 结束 开始 图 2.4 主控制循环 流程图 ps:主控模块，默认为落子输入，格式为： x 空格 x，x 代表落子坐标。 （3）盘面分析： ai 计算运算生效。如图 2.5 所示： 9 四色优化算法 权值计算算法 vcf 遍历算法 - 剪枝 剪 时间度判断 深度搜索 运算结果 图 2.5 ai 运算功能结构图 具体在第 4 章实现。 （4）胜负判定 流程如图 2.6 所示： n n n 白方落子 黑棋判定禁手 结束 开始 黑方落子 白棋判定 n4 黑棋判定 n=5 黑方胜 白方胜 y y y 图 2.6 胜负判定流程图 10 3 3 基础算法分析与实现基础算法分析与实现 3.1 棋盘棋盘 3.1.1 位棋盘 目前国际五子棋通用棋盘为 15*15，所以可以使用 1 个字节的空间 存储一颗 棋子的位置 以节省空间、提高运算效率。 1byte=8bit，因此可以利用 1byte 表示 棋盘上的棋子位置，低 4 位为行值，高 4 位为列值，即棋盘上的任意一点都可以 用 1byte 唯一表示 如天元（7,7）的位置为 0111，0111（6，9）=0110，1001 第 16 行和第 16 列没有用，因此整个棋盘为 type byteboard256的数组。使用棋子位置的字节码 可以直接作为索引，如 byteboard01110111就是天元的棋子 。具体使用在第 4 章基础算法中会详细解释。 结构体如下： struct byteboard ; for(n=1; n=256;n+) bit byteboard=0; . ; 3.1.2 权值棋盘 以数组的形式 建立两张棋盘，通常一张为电脑 ai，一张为玩家，分别为 computer15154,player15154。其中第一第二维度，是棋盘的 2 个维度， 第三维是棋盘上某一个空白点的价值，也就是这指代着一点临近的横竖撇捺四部分。 最终的数值就是横竖撇捺 4 部分上的权值总和。其权值的计算在第4 章基础算法 11 中会详细解释。 结构体如下： void creatbin1(bintree *t,list pro,list mid) list midr,q; char ch; if(pro-next=null | mid-next=null) *t=null; else *t=(bintree)malloc(sizeof(binnode); (*t)-lchild=null; (*t)-rchild=null; ch=pro-next-ch; pro-next=pro-next-next; (*t)-data=ch; for(midr=mid-next,q=mid;midr-ch!=ch;q=midr,midr=midr-next); q-next=null; creatbin1( creatbin1( return; 3.1.3 四色棋盘 以数组建立 color1515。先行落子的黑棋为黑色，用 color1515=1 表示； 后手落子的白子为白色，用 color1515=2 表示；可对本方带来效益或者给对方 带来负效益的落子点为绿色，用 color1515=3 表示；完全不需要纳入搜索考量 的无效落子点为灰色，用 color1515=0 表示。具体计算棋盘所属颜色在第4 章 基础算法中会详细解释。 架构如下所示： void creatbin2(bintree *t,list pro,list mid) list midr,q; char ch; 12 if(pro-next=null | mid-next=null) *t=null; else *t=(bintree)malloc(sizeof(binnode); (*t)-lchild=null; (*t)-rchild=null; ch=pro-next-ch; pro-next=pro-next-next; (*t)-data=ch; for(midr=mid-next,q=mid;midr-ch!=ch;q=midr,midr=midr-next); q-next=null; creatbin2( creatbin2( return; 3.2 棋谱棋谱 为了尽可能缩减占用空间，采用位棋盘记录棋谱 。 遵循黑子先行规则，则可以省略对黑白子的标记，只要知道是偶数还是奇数次 落子即可判断黑白色。 单张棋谱使用单链表存储结构 。 void dgtree(bintree *t) char ch; ch=getchar(); getchar(); if(ch=#) *t=null; else (*t)=(bintree)malloc(sizeof(binnode); (*t)-data=ch; 13 dgtree( dgtree( void creatbin3(bintree *t,list pro,list mid) list midr,q; char ch; if(pro-next=null | mid-next=null) *t=null; else *t=(bintree)malloc(sizeof(binnode); (*t)-lchild=null; (*t)-rchild=null; ch=pro-next-ch; pro-next=pro-next-next; (*t)-data=ch; for(midr=mid-next,q=mid;midr-ch!=ch;q=midr,midr=midr-next); q-next=null; creatbin1( creatbin1( return; 3.3 胜负判定胜负判定 在图层算法中已经包含了对胜负的计算，但是考虑到在玩家落子之后，需要 在 ai 计算棋型之前有一次胜负判断 。 白棋判定： 轮到白方行棋，判断横竖撇捺任意方向书否具有不间断连接白子，并且棋子数 4， “是”则白子胜， “否”则轮到黑方行棋。如图所示： 黑子判定： (1)轮到黑方行棋，判断横竖撇捺任意方向 黑方落子是否 具有不间断连接黑子， 并且棋子数 n=5， “是”则黑方胜， “否”则继续判断。 (2)判断黑方是否形成禁手，“是”则白方胜， “否”则轮到白方落子。 具体实现如下所示： 14 void isalpha(void) inta33= 25, 2, 166667, 33, 25, 2, 5,1,2,x3,y3,b3=9,8,8,l33,u33,f1=0,f2=0; int i,j,k; for(i=0;i=0;i-) for(j=i+1;jsqrt(b) c=a-b; else continue; for(j=2;jsqrt(c) printf(“%d=%d+%d“,a,b,c); 4.2 权值棋盘算法权值棋盘算法 本程序核心模块之一！其具体实现方法如下： 计算“活三”、 “冲四”， “禁手”点 权值计算基于四色算法之上，四色算法中已经得到的灰色点默认权值为0 先来分析己方的棋型，我们从棋盘 最左上角的绿色点出发，向右逐行搜索 ， 如果遇到己方的子则记录然后继续，如果遇到对方的子、空白点或边界就停止查找。 左边完成后再向右进行同样的操作；最后把左右两边的记录合并起来，得到的数据 就是该点横向上的棋型，然后把棋型的编号填入到computerxyn中就行了 （x、y 代表坐标，n=0、1、2、3 分别代表横、竖、左斜、右斜四个方向）。而其 他三个方向的棋型也可用同样的方法得到，当搜索完整张棋盘后，己方棋型表也就 填写完毕了。 然后再用同样的方法填写对方棋型表。 一个位置横竖撇捺有 4 个方向的棋型，棋子种类分为黑白，因此一个棋盘的棋型可 以保存在一个 3 维数组 board22,4,256中，单行棋型分为， 0，活 1，活 2，冲 3，活 3，冲 4，连冲 4，活 4，活 5，长连，44 共 11 种，五子棋要分析的是棋型 组合，将单行 棋型进行 11 取 4 的组合，即可得到组合棋型： 0，活 1，活 2，冲 3，跳 3，活 3，连活 3，33，冲 4，连冲 4，43，433，44，活 4，活 5，长连。 建表：在此制定一个 映射表，所有棋型的编号都要事先定义好 ，方便调取对 比,如图 4.2 所示： 18 活 2 活 3 眠 3 冲 3 冲 4 连冲 4 胜 5 映射表 0 5 15 17 20 25 0 图 4.2 映射表 提前存储一张单行棋型 -组合棋型的映射表，每次计算好单行棋型就可以直接 查表得到多行棋型 。 在但棋型的基础上，组合多棋型，如果遇到死棋则为0 值，如果不为死棋则 累加计算出权值。 基本算法结构如下所示： int sqsum(int n1, .) va_list arg_ptr; int nsqsum = 0, n = n1; va_start(arg_ptr, n1); while (n 0) nsqsum += (n * n); n = va_arg(arg_ptr, int); va_end(arg_ptr); return nsqsum; int n=7,r=2,i,k; double p1,p2,p3,p4; double x8= 5, 7, 9,11,13,15,17,19; double y8=0.4794,0.6442,0.7833,0.8912,0.9636,0.9975,0.9917,0.9463; double p0=-0.4794,pn=-0.9463,u3=0.6,0.8,1.2,s3; 19 double h7,a8,c7, g8,af8,ba7,m8; for(k=0;k =0;i-) mi=gi-bai*mi+1; for(i=0;i xk+1) k+; p1=(hk+2*(ui-xk)*pow(ui-xk+1),2)*yk)/pow(hk,3); p2=(hk-2*(ui-xk+1)*pow(ui-xk),2)*yk+1)/pow(hk,3); p3=(ui-xk)*pow(ui-xk+1),2)*mk/pow(hk,2); p4=(ui-xk+1)*pow(ui-xk),2)*mk+1/pow(hk,2); si=p1+p2+p3+p4; 4.3 a-b 剪枝剪枝 为了进一步优化算法， 我们不用把每个节点都搜索一遍也可获得和极大极小 权值的走步，不搜索分支节点而舍弃该分支的过程叫剪枝。常用的剪枝方法是- 剪枝算法。 在极大极小搜索的过程中，存在着一定程度的数据冗余。如下图4.3 所示左 半部的一棵极大极小树的片断，节点下面为该节点的值，设a 为极大值节点，节 点 b 的值为 18，节点 d 的值为 16，由此可以判断节点 c 的值将小于等于 16(取 极小值)；而节点 a 的值为节点 max(b，c)，是 18，也就是说不再需要估节点 c 的其他子节点如 e、f 的值就可以得出父节点 a 的值了。这样将节点 d 的后继 兄弟节点减去称为 alpha 剪枝( 剪枝)。如图 4.3 所示： 20 18 a bc def a 取最大值 16 图 2：alpha 剪枝( 剪枝) 图 4.3 alpha 剪枝 同样道理在图 4.4 右半部一棵极大极小树的片段中，设 a 为极小值节点，节点 b 的估值为 8，节点 d 的估值为 l8，由此可以判断节点 c 的值将大于等于 18(取极大值)； 而节点 a 的值为 min(b，c)，是 8。也就是说不再需要求节点 c 的其他子节点如 e、f 值就可以得出父节点 a 的值了。这样将节点 d 的后继兄弟节点剪去称为 beta 剪枝( 剪枝)。如图 4.4： a bc def a 取最小值 8 18 图 3：beta 剪枝( 剪枝) 图 4.4 beta 剪枝 将 alpha 剪枝和 beta 剪枝加入极大极小搜索，就得到 - 搜索算法。 经过了上面的介绍，我们再回到五子棋问题上来。 上边讲到了极大极小搜索，以及搜索时产生子结点的顺序。五子棋的静态估值函数 有多种方法得到，具体如何实现除了要有一定的五子棋知识外，还要能运用这些知识 正确地给出对一个五子棋当前局面的估值。可以进行全局搜索，对棋盘的每一个点判 断棋形计算得分，最后综合得到全局得分，优先选择分值最高的走步。若对五子棋比 21 较熟悉，可以在程序中规定几个下棋定式，根据定式判断当前局势得分。 根据极大极小搜索中给出的判断棋形所设的得分值，搜索整个棋盘得出共有多少个 活一，死一，活二，最后把各部分得分求和，得到当前局势的评价值。这个静态 估值函数的好坏直接决定了程序智能的高低。可以在实践中不断调整得分值，使其智 能更高。 而对于搜索时产生子结点的顺序，这关系到程序运行的快慢，倘若在 - 剪枝过程 中，很早就得到一个较大的值，则在其后的搜索过程中，剪枝数目增加，程序效率也 会提高。产生子结点的顺序，光靠说不行，还需要在实际中慢慢体会，得出一个较优 方案。在这里我暂且假设它从(0，0)点开始到(14，14)为止产生结点，对于每一次预 测走步，我们假设白棋从(0，0)开始的第一个无子的点开始预测(假设电脑为白棋)， 再轮到黑棋走，再轮到白棋走，一直向后预测 n 步后用静态估值函数对整个局面打分， 再选择另一个位置，再为局面打分，重复此过程对深度为 n 的搜索树进行 - 剪枝搜 索。 现在假设五子棋问题深度为 3 的搜索树给出 - 剪枝算法，用类 c 语言对其进行描 述： 设电脑为 max，人为 min，初始时 为-， 为+；函数 evalue()返回对当前局 面的估值 int max(point p,) 在 p 处下白子； if(deep ) return ;) return ;) min： int min (point p, , ) if(deepdata); if(queuefront-lchild!=null) rear+;queuerear=queuefront-lchild; if(queuefront-rchild!=null) 23 rear+;queuerear=queuefront-rchild; void printtlr(bintree tt) bintree t=tt; if(t!=null) printf(“%4c “,t-data); printtlr(t-lchild); printtlr(t-rchild); void printltr(bintree tt) bintree t=tt; if(t!=null) printltr(t-lchild); printf(“%4c“,t-data); printltr(t-rchild); void printlrt(bintree tt) bintree t=tt; if (t!=null) printlrt(t-lchild); printlrt(t-rchild); printf(“%4c“,t-data); vcf 搜索法为强制全深度搜索法，但是在搜索到第一个 vcf 点之后即可停止运算，不要求完 全遍历搜索所有 vcf 点，进而减少了时间的消耗。 4.54.5 综合算法综合算法 本章主要介绍在基础算法的基础之上综合各种算法的优缺点，进行合理处理，在不 同情况之下，采取最优处理方法。主要逻辑如下所示： （1）首先运行四色算法的优化，然后是单层次的权值计算，接着是 vcf 的搜索， 到此为止第一部分准备工作结束； 结构实现主程序如下所示： #define infinity int_max #define max_vertex_num 20 typedef int boolean; typedef char vertextype20; typedef int vrtype; 24 typedef int qelemtype; typedef struct qnode qelemtype data; struct qnode *next; qnode, *queueptr; typedef struct queueptr front; queueptr rear; linkqueue; status initqueue(linkqueue *q) (*q).front=(*q).rear=(queueptr)malloc(sizeof(qnode); if (!(*q).front) exit(overflow); (*q).front-next=null; return ok; （2）, 剪枝优化算法，在优化过后按结果值进行深层权值计算 结构实现主程序如下所示： status queueempty (linkqueue q) if (q.front=q.rear) return true; else return false; status enqueue(linkqueue *q, qelemtype e) queueptr p; p=(queueptr)malloc(sizeof(qnode); if (!p) exit(overflow); p-data=e; p-next=null; (*q).rear-next=p; (*q).rear=p; return ok; status dequeue(linkqueue *q, qelemtype *e) queueptr p; if (*q).front=(*q).rear) return error; p=(*q).front-next; *e=p-data; (*q).front-next=p-next; if (*q).rear=p) (*q).rear=(*q).front; free(p); return ok; 25 typedef struct arccell vrtype adj; arccell, adjmatrixmax_vertex_nummax_vertex_num; typedef struct vertextype vexsmax_vertex_num; adjmatrix arcs; int vexnum,arcnum; mgraph; void creategraph(mgraph *g) int i,j,k; vertextype v1,v2; printf(“ninput mg vexnum,arcnum:“); scanf(“%d,%d“, printf(“input %d vexs:“,(*g).vexnum); for(i=0;ivexnum;i+) puts(g-vexsi); for(i=0;i=0; w=nextadjvex(g,v,w) if(!visitedw) dfs(g,w); void dfstraverse(mgraph g) int v; for (v=0; v=0; w=nextadjvex(g,u,w) if (!visitedw) visitedw=true; printf(“%s“,g.vexsw); enqueue( 28 5 5 系统测试系统测试 5.15.1 测试环境测试环境 visual c+ 6.0：简称 vc 或者 vc6.0，是微软推出的一款 c+编译器，将“高级语 言”翻译为“机器语言（低级语言）”的程序。visual c+是一个功能强大的可视化软件 开发工具 5.25.2 测试过程及结果测试过程及结果 （1）进入主界面（如图 5.1 所示）： 图 5.1 主界面 （2）第一次落子（如图 5.2 所示）： 图 5.2 输入 玩家按照格式输入第一颗子（7,7），等待电脑运算出下一步 （3）ai 落子：等待计算机运算一段时间之后，计算机落子（如图 5.3 所示）： 图 5.3 ai 落子 电脑运算结果（8,8），后重新返回主循环界面，轮到玩家落子。 （4）交换：换棋操作，按照步骤，本应该轮到玩家落子，但是交换之后就轮到电 脑落子，由电脑计算下一步棋，结果如图 5.4 所示： 29 图 5.4 交换 上图中，输入 1 之后，与电脑环棋，电脑运算出下一步棋（8,7），重新返回主循 环界面，轮到玩家落子。 （5）查询：查看当前棋子颜色，以及棋谱，如图 5.5 所示： 图 5.5 查询 上图中，输入 2 之后，显示当前棋子颜色，并显示棋谱，重新返回主循环，轮到玩 家落子。 （6）悔棋：退回上一步，然后玩家落子，如图 5.6 所示： 30 图 5.6 悔棋 如上图，悔棋输入之后，提示玩家当前棋子颜色，并自动显示当前棋谱 31 结论结论 经过多次运行测试，本设计非常成功得实现了所有功能要求。在中期局势混乱的关 键时期，发挥出了非常有成效的作用，vcf 的连杀能力，攻击点的寻找能力都是非常 成功的。基本上能够满足辅助玩家进行落子考虑的能力。交换、查询、悔棋的功能也 能很好的帮助控制棋局进程，经过多个非职业玩家的实际测试之后，得到了许多宝贵 的建议，比如完善界面、增加控制功能、增加 ai 与玩家的互动等等。总之是得到了足 够认可的同时也得到了许多的实践意义。 软件本身最大的不足在于开局时的被动和简单思维，太容易被玩家的骗棋所骗，但 是到了中盘就能够非常完美的发挥出自身的优势，强势的进攻性预判，让玩家措手不 及。所以为了弥补这个最大的弱势项，采取了人工辅助开局的方法，由人的经验进行 开局，在交换功能以及悔棋功能的合作之下，能够简单做到这一点。一旦到了中期， 玩家就能够足够信任软件的运算能力。 软件经过实际测试之后，确认了本软件能够适合部分人群，但是不适合所有玩家。 对于对连珠五子棋有一定了解，对禁手规则熟悉的玩家来说，使用上来说就没有太大 的问题，也能很好得满足作为辅助软件的需要，帮助玩家分析棋局。而作为一个初学 者，不太了解禁手规则，对开局的定式又不太熟悉的玩家，就很难勉强他们具有下盲 棋的水平，况且因禁手规则而出现的胜负场合也没有任何的提示。作为高端玩家的上 限，因为没有考虑“三手可换”、“五手两打”这些大型比赛的正规竞赛规则，所以 就没有成为职业玩家的工具的基本能力。 速算型的优点适合用于对时间需求比较高的场合，不同于长考型的严谨，速胜型更 加像是一个机会主义着，有机会获胜就绝不轻易放弃机会。所以很适合即使对弈的娱 乐，却不适用于理论研究的辅助。不同的软件都有自身的特性，没有完美的程序，也 没有完美的软件，重要的在于适用它的人，把它用在适当的地方才能够散发出它本身 的光芒！ 当然还有许多可以提升的地方，例如可以依靠外置棋谱来弥补开局的弱项，更加可 以引进具有自我学习功能的