.Rsf613 { display:none; } 六子棋博弈研究与引擎实现( 毕业论文 13800字) 【摘要】 计算机博弈的研究已经为人工智能领域带来了很多重要的方法和理论，并且产生了广泛的社会影响，同时也应用于许多棋类游戏的研究和实现中
六子棋是最近几年才兴起并发展起来的棋类运动，它已经被越来越多的人所接受，但其计算机博弈的研究还相对较少
本文所设计的系统主要分为走法输入与输出、走法生成、搜索函数、评估函数等模块
本文以现有的计算机博弈理论为基础， 并将α-β搜索算法应用于六子棋系统中采用C++开发六子棋程序
系统开发平台为visual studio2008，应用传统的MFC技术设计系统总体框架和相关功能
而计算机博弈作为人工智能领域的一个重要分支，也得到了极其快速的发展，并为人工智能带来了很多重要的方法和理论，同时也产生了广泛的社会影响和学术影响以及大量的研究成果
代表计算机博弈技术的各种棋类游戏在其各自的计算机博弈技术研究中已经取得了相应的成果，且其计算机博弈系统也日趋完善，基本上能达到大师级水平
六子棋作为最近几年才兴起的棋类游戏，其计算机博弈技术和算法的研究相对较少
本文设计的六子棋博弈系统也正是对六子棋博弈技术的一次尝试
某一天，教授和自己的女儿在家下五子棋，女儿异想天开地提议“每人每次落两子，连成六子就胜利”
女儿的建议启发了吴教授，考虑出了第一手黑子下一子，随后轮流下两子的走法，并且认为这或许可以克服五子棋的不公平性
经过反复地论证和理论研究，吴教授发现这是个相当复杂且有趣的游戏
在他的推广下，六子棋就这样传开了，成为了一种棋类游戏
1.2六子棋博弈规则 （1）六子棋，英文名称为connect6
参与六子棋的双方，一方持黑子一方持白方在棋盘上进行着手的对弈
（2）棋盘：理论上的六子棋的棋盘可以是无限大小，本文采用19×19大小的棋盘，它是由19条直线与19条横线组成，有361个交点
其中有中央天元与八个星位参考点
（3）术语介绍： 着手：即对弈双方在棋盘的空白点上落子
线：是由同一种颜色棋子形成的组合，方向为横向、纵向和斜向
特别注意的是，在组合中可以有空子，但不能有对手棋子
连线：线中没空子
（4）对弈进行：对弈双方一方持黑子，一方持白子，黑子先下
持黑子者的第一手落一子后双方轮流落两子于棋盘上，直至分出胜负
（6）棋局的胜负：在对弈过程中，首先练成六连子或者长连方则获胜
在有时间限制的比赛中，棋手也可证明对手方时间用尽，或者在规定时间内没有落子完成，同样宣告胜利
对方主动宣告投降时，也能获得胜利
（7）和局：当棋盘上所有的空子交点被填满，且对弈双方认为分出胜负，则宣告比赛平局
还有几种情况：对弈双方皆同意和局时，或者当一方虚手后另一方紧接着虚手时
要注意的是在一方提出和局提议后便启动对手的落子计时器
对手可以表示同意和局或者利用落子表示拒绝和局
1.3六子棋的基础棋型 1.3.1迫着（threat）的概念 在很多棋类游戏中都存在着迫着的概念，简单地说就是当前局面处于有利于一方需要另一方防守的情况，在六子棋中，可以简单的描述为对弈的一方在不能形成连六情况下，当且仅需要落s颗子来阻止对手取得下一步的胜利，即可说对手有s个迫着
三个及以上迫着是六子棋的赢棋策略，因为对弈一方若存在三个及以上迫着，对方则同时需要三个以上的棋子去防守，由于六子棋每部每步只有两字可下，显然不能成功防御
图1-1、图1-2为单迫着，图1-3、图1-4为双迫着，图1-5、图1-6为三个及以上个迫着
1.3.2棋型描述 棋型就是棋局的一种状态描述，是描述棋盘上不同棋子的分布状态
采用状态矩阵可以比较清楚地描述某个时刻，在博弈进程中棋局状态和棋子状态的变化，如何有意识地控制这个变化发展方向，并使得朝有利于己方赢棋的方向发展，是本六子棋系统需要解决的核心问题
所以，Connect(k,p,q)表示Connect(∞,∞,k,p,q)，即表示在一个无限大的棋盘上的K子棋
传统的五子棋就可以表示为Connect(15,15,5,1,1)
而本文所讨论的六子棋就可以表示为Connect(m,n,6,1,2)，而19×19或59×59的棋盘均适合比赛使用，本系统选择19×19的棋盘进行设计，可以表示为Connect(19,19,6,1,2)
1.4.2公平性概念 在学术界对于博弈游戏“公平性”给出过一个适当的定义，定义如下：若该游戏是平手的游戏，且双方犯错几率是相等的话，则可称此游戏是公平的
即便如此，由于数学模型的难以建立，“双方犯错几率是相等”就很难被证明
每当有新的下棋策略制定后，其犯错几率的衡量算法就会跟着改变，这就很容易影响公平性
相反，要证明一个游戏是不公平的则是比较容易且可行的
以下是吴毅成教授给出的定义[3]： 定义一：明确不公平性（definite unfairness）：若已经证明出一方必胜，则此游戏可称为明确不公平
例如：没有采用禁手规则的五子棋是明确不公平的
定义二：单调不公平性（monotonical unfairness）：若已经证明出一方必然不会必胜，但尚无法证明另一方必然不会必胜，则此游戏可称为单调不公平
例如：K子棋中Connect(m,n,k,p,q)，可用策略盗用论点（Strategy-stealing arguments），证明白方必然不会必胜；因此，Connect(6,1,1)、Connect(7,1,1)、Connect(6,2,2)等皆为单调不公平的
然而，因为Connect(8,1,1)已被证明双方平手，所以不是单调不公平的
例如：在早期用一般规则的五子棋及了连珠棋，已被一般棋士认定是黑方必胜；因此在当时可称为经验上不公平
定义四：潜在公平性(potential fairness)：若该游戏尚未被证明出或论证为明确不公平、单调不公平、经验上不公平的话，则此游戏可称为潜在公平
依据此定义，一个目前为潜在公平的游戏，不见得能持续在未来仍为潜在公平；一个有能持续为潜在公平愈久，则成为公平的机会就愈高
1.4.3六子棋的公平性 从直观上看，六子棋的公平来自于——每当对弈的一方完成本轮落子，在棋盘上总比对手多出一子，且该种情况会随着对弈过程轮流出现，直至一方获胜为止
虽然截至今日依然无法证明六子棋是绝对公平的，但可以有以下论点证明六子棋潜在的公平性: ①目前，尚无人能证明六子棋是明确不公平 ②目前，尚无人能证明六子棋是单调不公平 ③目前，尚无人能证明六子棋是经验上不公平 当然，对于六子棋公平性的讨论，还需要时间来找到更多有力的依据
1.5复杂度 六子棋的复杂度远远高于五子棋且能和围棋、象棋匹敌，状态空间复杂度和博弈树复杂度分别为10^172和10^140
所以在这么复杂的空间中寻找可行性的走法的算法势必要求有很高的速度与质量
本系统计算机智能的级别还相对较低，算法的速度和质量与期望达到的效果还有一定的距离
在搜索函数中采用什么样的搜索算法，在走法生成模块中怎么确定走法，在评估函数模块中如何确定参数以及怎样确定适应度函数，这些问题在本文都有了一定的解答
其中，搜索算法和评估函数是在本文设计程序过程中重点讨论的问题
2.1.1搜索算法 系统中所牵扯的六子棋博弈问题可以用博弈树来描述
博弈树是把计算机和用户所有可能的走法和局面罗列出来的一棵树
黑白双方交替地按合理走法把树展开，树的每一个节点都表示某个特定局面
根节点表示的是当前需要计算的局面，中间节点表示的是对弈过程中的某个局面，叶子节点是树的最底端，表示可以推导的局面
叶子节点和根节点之间的最大距离，称为搜索深度
整个博弈树描述的是从当前局面出发，包含所有可能的对弈过程的搜索过程
这就牵扯到搜索算法，而且根据当前的棋局状态以及规定的搜索深度和宽度，在博弈树中找到一条最佳路径
系统的搜索模块完成以下两部分的工作：确定采用α-β搜索算法、尽可能缩小博弈树的规模而避免冗余计算
同时这是其他棋类计算机博弈也需考虑的问题
在搜索算法模块中将两步当作一步做了处理，“两步”向“一步”转化的过程是做了一种算术和处理，即将两步棋的评估值做了简单的算术和处理，实际情况可能没那么简单
2.1.2评估函数 模式识别和智能算法在评估函数中应用最为广泛
评估函数需要考虑的因素有很多，结合六子棋以及其他连珠棋的特点，这里考虑了两个因素：固定子力值和棋子灵活度值
固定子力值即是对胜利的有利程度；棋子灵活度值即是对于后续发展的应变能力
在六子棋中，一步棋周围相同颜色越多就越容易实现连珠，该棋子的固定子力值就很高，同时如果该棋子周围有很多空缺位置，则该棋子的可发展空间就很大，棋子灵活度值就很高，相反的只要周围有不同颜色的棋子则可发展的空间就很小，形成连珠的概率就很小，棋子灵活度值就很低
在根据这两个值计算出权重值，在这里用了表的方式得到权重值的
2.2基本组成 2.2.1人机界面 人机界面对于本系统来说是必不可缺的一部分，由于六子棋刚刚兴起，还没有类似象棋中的ucci之类的统一的界面协议和引擎，而在我的系统中，人机界面提供了走棋的后退、前进，棋盘连线用不同颜色的连线标示的功能，难度选择则是通过加载不同的引擎来实现的
同时还可以对当前的棋局进行备份，或者载入其他未下完的棋局继续对弈
〖资料来源：56DOC.COM 毕业设计(论文)网〗 2.2.2棋盘和棋局的表示 要让计算机看懂棋盘这就需要一种数据结构对棋盘进行描述，并将各棋子的分布精确的表示出来
方法如下： 矩阵表示 比如棋盘上面有19路19行形成361个交叉点，它很容易用19×19的棋盘数组矩阵M19*19表示与坐标的对应关系
要表示棋局则首先要给棋子编码
应该说方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码
如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是具有研究的余地
以六子棋为例，使用位棋盘的话，因为变量是布尔值，所以每个格子只能表示有没有棋子
所以可以用两张位棋盘分别表示黑方和白方的子力分布情况
使用位棋盘的好处就是可以将走法表示成变换矩阵的形式，这样进行数学运算就比较方便
矩阵表示六子棋棋盘，每个矩阵坐标上至少需要3中编码表示棋盘上各个格子的状态以保证可区分性
每个棋子因其先后顺序不同所以可以用数字顺序表示来唯一区分它们
一个棋局可能会有几种不同的矩阵来表示
2.2.3走法生成 走法生成方法一般有棋盘扫描、模板匹配法和预置表法，时常还结合使用
①棋盘扫描法 在走法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落子状况，确定有哪些地方可以落子
根据六子棋的规则，棋盘有效区域内的所有空白的交点都是可行落子点，一般不是距离前两子其中任一子为6格距离的范围
六子棋、五子棋、围棋一类的棋类设计中最常用，在走法的表达上，棋盘扫描法最为直观，但时间开销巨大
本系统即是使用这种方法
②模板匹配法 以象棋为例，当动子即当前落子确定之后，其落址与提址的相对关系便被固定下来
于是可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址
比如走马这一步，当马对准提址，根据蹩马点的具体分布，很容易判断可能的落址
③预置表法 预置表法是使用最为经常的着法生成方法
它的基本思想就是用空间换时间
为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何位置(提址)、针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法
当然，六子棋无吃子情况
当然这种方法对于特殊情况的走子，可以快速的生成应对措施，在六子棋中，开局的走法比较固定且应对措施也比较固定所以采用预置表法效率比较高，而且开局时的形势是最不明朗的时候，采用棋盘扫描法生成的可行走法就比较多，从中选出最优走法的花费比较大
采用预置表法就形成了开局库
综上所述，本系统采用了棋盘扫描法和预置表法相结合的方法
2.2.4机器博弈、搜索技术 ①博弈树 任何棋类游戏都要定义一棵有根的树（即“博弈树”），一个节点就代表棋类的一个局面，子节点就是这个局面走一步可以到达的一个局面
②搜索算法 搜索算法是博弈树求解的灵魂，只有有了有效的搜索算法才能在有限的时间内找到正确的解
搜索算法是求解此类图模型的基本方法
我们无法在有限的时间内搜索到最终的胜负状态，于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而且变动最不大的最佳状态，于是从当前状态出发到达最佳状态的路径便称为最佳路径(Principal continuation),它代表着理智双方精彩对弈的系列着法
而最佳路径上的第一步棋便成为当前局面的最佳着法(The best move)
所以搜索到的最佳路径有两种，一种是有利于黑方的，一种是有利于白方的，对弈的过程就可表示成在不同深度的那层节点间寻找不利于对方且有利于己方的节点
1）极大极小搜索 假设六子棋的两个玩家对弈，黑白方分别对应极大极小算法中的MAX方和MIN方
MAX先走，之后两人交替走步直到游戏结束
由于不可能对完整解图进行搜索，利用本文所定义的评估函数对当前局面进行估值，规定有利于MAX的估值很大，有利于MIN的估值则很小
下图为极大极小算法过程
α-β剪枝搜索的基本方法还是极大极小搜索，所不同的是它对极大极小搜索过程进行了优化处理
假设当前走棋方为MAX方，因为它选择着法是总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；将应对方定为MIN方，因为他走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有牵制作用的着法
显然此α值可作为MAX方着法指标的下界
在搜索此MAX节点的其它子节点，即探讨另一着法是，如果发现一个回合之后评估值变差，即孙节点评估值低于下界α值，则便可以剪掉此枝（以该子节点为根的子树），即不再考虑此“软着”的延伸
此类剪枝称为α剪枝
下图给出了搜索和剪枝过程，最后得到如粗箭头所示的最佳路径片断
β剪枝：同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的牵制值，记为β
显然此β值可作为MAX方可能实现着法指标的上界
在搜索该MIN节点的其它子节点，即探讨另外时，如果发现一个回合之后牵制局面减弱，即孙子节点评估值高于上界β值，则便可以剪掉此枝，即不再考虑此“软着”的延伸
此类剪枝称为β剪枝
下图给出了搜索和剪枝过程，最后得到最佳路径片断
需要指出的是，α-β剪枝是根据极大极小搜索规则而进行的，虽然它没有遍历某些子树的大量节点，但它仍不失穷尽搜索的本性
剪枝技巧的发现，一下便使博弈树搜索效率产生了质变
迭代深化的思想是搜索博弈树时先搜索该博弈树的子树，然后一次向上层树节点搜索
该方法的好处是搜索子树的时间要比搜索父树的时间少，这样可以再有限的时间内先比较可行的最佳路径
这种方法适用在对计算机生成给出走棋有时间限制的情况
对α-β剪枝采用迭代加深，本系统中所设的MaxDepth为6，相应代码如下： While(i
只有有了良好的评估函数才能保证较快地找到正解
而评估函数是对棋局的综合评估，该函数的好坏直接决定解题能力强弱
通常一个优秀的棋手总有一个良好的对棋局的判断能力，能够协调各棋子的关系、取舍，有机地组织个棋子的进攻步调，控制棋局的发展
因此如果要把这一整套的思维物化成一个数值函数来评估，就成了一个相当复杂的问题
本系统的评估函数从以下两个基本假设出发
1）局面的性质能量化成一个数字
例如，这个数字可以是对取胜的概率做出的估计
2）其中一方对这个性质的衡量应该跟对手衡量的性质是一样的，如果其中一方认为处于优势，那么反过来对手认为他处于劣势
真实情况并非如此，但是这个假设可以让我们的搜索算法正常工作，而且在实战中它跟真实情况非常接近
文献[1]中就对影响评估函数的复杂程度的因素做了说明
评估可以是简单的或复杂的，这取决于在程序中加了多少知识
评估越复杂，包含知识的代码就越多，程序就越慢
通常，程序的质量（棋力）可以通过知识和速度的乘积来评估，如图2-7所示
②组合评估要素 把评估要素组合起来，评估函数是很多项的和，每一项是一个函数，它负责找到局面中的某个特定因素
棋类程序应该充分尝试各种可能的评估函数：把各种胜利的可能性结合起来，包括很快获胜(考虑进攻手段)，很多回合以后能获胜，以及在残局中获胜的可能性，然后把这些可能性以适当的方式结合起来
每种概率是否估计得好，这就需要程序的估计来和数据库中棋局的真实结果来做比较，这就需要让程序具有基本判断的能力（判断某种攻击是否起到效果）
③评估函数中所需加入的信息 本文设计的评估函数加入了两个因素的信息： 1）子力（Material）：在国际象棋中，它是子力价值的和，在围棋或黑白棋中，它是双方棋盘上棋子的数量
这种评价通常是有效的，但其他像五子棋一样的游戏，子力是没有作用的，因为好坏仅仅取决于棋子在棋盘上的位置，看它是否能发挥作用
2）空间（Space）：在某些棋类中，棋盘可以分为一方控制的区域，另一方控制的区域，以及有争议的区域
例如在围棋中这个思想被充分体现
而包括国际象棋在内的一些棋类也具有这种概念，某一方的区域包括一些格子，这些个字被那一方的棋子所攻击或保护，并且不被对方棋子所攻击或保护
在黑白棋中，如果一块相连的棋子占据一个角，那么这些棋子就被吃不掉了，成为该棋手的领地
空间的评价就是简单地把这些区域加起来，如果有说法表明某个格子比其他格子重要的话，那么就用稍复杂点的办法，增加区域重要性的因素
但是权重值从哪里来呢？获取评估函数中权重值的方法有很多种
这里采用了人工设置的规格化方法
该方法是人为给出权重值，因此这些权重值的设置比较僵硬，为了能很好使评估函数比较精确地估值，这些权重值之间的差设置的很大
在一些特殊棋类中为了提高评估函数的准确性，会采用一种模拟实际情况的方法来对这些权重值进行调整
3.六子棋计算机博弈系统的实现 3.1实现语言与工具 实现语言为C++，因为是棋类程序，所以对程序的执行效率有很高的要求，C++在编程语言中有很高执行效率
它很好的继承了C语言的有效性 、灵活性以及便于移植等特点，扩展了对面向对象思想的支持，且结构清晰、易于扩充，适合绝大数场合的编程要求，是一种理想的程序设计语言
开发工具：Visual Studio 2008 3.2系统构建 3.2.1棋盘状态空间表示 要让计算机能够下棋，首先就要把下棋问题表示成计算机可理解的形式，即把六子棋博弈问题形式化，存在计算机中，并能让搜索、估值等算法对这些数据进行操作
需要在计算机中表示的主要问题有棋盘局势状态、落子的顺序表示等
这与六子棋知识密切相关
这里用来描述棋盘及其上棋子信息的是一个二维数组
计算机要知道棋盘局势状态，就是要让它知道棋盘中哪些位置有黑棋，哪些位置有白棋，以及哪些位置还未走棋
本系统首先定义一个结构，表示棋盘中某个位置的信息如图3-1
#typedef struct StepStatus { bool used; int player; }StepStatus; 声明此结构的数组 StepStatus[][] chessBoardStatus = new StepStatus[19][19]; 图3-1 棋盘状态矩阵 接着在系统中定义了一个结构用来表示一步棋的棋子位置以及是何种棋： #typedef struct Step { int x; int y; int player; }Step; 图3-2 走法记录结构 （2）落子的顺序表示 棋盘中的落子有先后顺序，六子棋是黑棋先下一颗子后，从白棋开始以后双方各走两颗子，直到决出胜负或棋盘走满为止
那么这个下棋顺序也需要表示出来，本系统用了一个Step[]数组记录下棋过程，该数组的下标表示所下的是第几步棋，这个数值记录在全局静态变量NUM_order中
悔棋时只需将NUM_order减一
博弈树是把计算机和用户所有可能的走法和局面罗列出来的一颗树
黑白双方交替地按合理走法把树展开，树的每一个结点都表示某一个特定局面
根节点表示的是当前需要计算的局面，中间节点表示的是对弈过程中的某一个局面，叶子节点是树的最底端，表示可以推导的局面
叶子节点和根节点之间的最大距离，称为搜索深度
整个博弈树描述的是从当前局面出发，包含所有可能的对弈过程的搜索树
六子棋计算机博弈问题也就转化为寻求最佳路径的问题
对于树中的每一个节点来说，黑白双方都会从子节点中选择最有利于自己的分枝
因为博弈树中值的传递是由下至上的，这就要求对叶子节点表示的局面必须有一个极为准确的打分
对于局面最为准确的估计莫过于已经分出胜负的情况，即建立在叶子节点分出胜负的完全博弈树
六子棋的完全博弈树大概有10765个节点，建立这个博弈树已经远远超出了当代计算机的处理能力
唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个最为准确的打分，表示此局面下取得胜利的可能性
而对于节点的打分就是有评估函数计算得到的
走法生成模块的功能就是按照六子棋的走法规则生成合理走法将博弈树展开；搜索引擎模块的功能则是尽可能缩小树的规模，避免一切冗余的计算
但往往对一个形势的判断是很难做到准确的，特别是一盘棋刚开始的时候，棋盘的形势很不明朗，即使是专家也很难做出准确的判断
为了判断哪种下法最有利，这里采用了向后多算几步的方法，估计一下多走几步后面局面的形势如何
这样的思维方式在对弈过程中是很自然的事，显然运用到计算机中有一定启发作用
上文已经提到，棋局的不断向后计算，形成了一颗博弈树，“多算性”的思想即是对博弈树的搜索过程，这就是博弈树的极大极小搜索算法
然后在极大极小值的搜索过程中，遍历了整颗博弈树，每个结点都访问了一次，这样的搜索算法粗糙，搜索量非常大，而使搜索效率低下
为了尽可能缩小树的规模，避免一些冗余的过程，从而提高搜索效率，必须对博弈树中的节点进行筛选，过滤掉一些不必要搜索的节点
由此，本系统的搜索引擎模块中采用了α-β剪枝搜索算法，并且根据六子棋的特点，加入了一些启发式信息
（1）α-β剪枝搜索算法 本文在上面已经对α-β剪枝搜索算法的原理做了简单的介绍，现将α-β剪枝搜索算法引入到六子棋计算机博弈系统的搜索引擎模块
这里需要指出的是，以上所使用的α-β剪枝搜索算法，在博弈树的搜索过程中，如果所有节点的打分或者说估值都是准确的，并且都以该估值为依据
但实际上，这样的估值肯定是有误差的
在上述的α-β剪枝搜索算法中，搜索的深度和宽度决定了搜索的时间以及搜索的精度
如果搜索的深度越深，宽度越宽，那么搜索的时间就越长，但是搜索的精度就越高，AI的智能就越高，但这是以牺牲时间作为代价的；反之，如果搜索的深度越浅，宽度越窄，那么搜索的时间就越短，但是搜索的精度就越低，AI的智能也相对较低
由此，需要在搜索时间以及搜索精度上作综合考虑，既不能让搜索的时间过长，也不能让搜索的精度过低
本文在搜索算法的设计中，在保证搜索时间符合要求的情况下，尽可能增加搜索深度和宽度，以提高搜索精度，提高AI的智能
程序在设计过程中，也是以搜索的深度和宽度的不同来设定AI的智能等级的
现有棋类的计算机博弈中，完全靠单一的搜索算法来搜索很难得到理想的搜索结果，达不到理想的效果，因而一般都采用两种或几种搜索算法的相结合的方法，或者以一种搜索算法为主，同时根据棋类知识加入一些启发式信息，以获得较为理想的搜索结果
本文在以α-β剪枝搜索算法为主要搜索算法的基础上，根据六子棋的特点，加入了一些启发式信息，主要是对一些诘棋的判断
如果α-β剪枝搜索算法在搜索的过程中，发现当前的局面与预先定义的诘棋的某一个局面相符，那么直接调用其对应的最简单的解法
本系统使用表结构来存储一些典型的诘棋局面和其对应的解法
在α-β剪枝搜索算法通过“剪枝”缩小博弈树的规模后，同时加入一些基于诘棋的启发式信息可以进一步缩小博弈树的规模，避免一些冗余的过程，使搜索效率和准确性得到提高
3.2.4走法生成 走法生成是指将一个局面的所有可能的走法罗列出来的那一部分程序，也就是用来告诉其它部分下一步可以往哪里走的模块
对于六子棋来说，由于双方只有黑白各一种棋子，并且在走子的过程中，双方轮流走子，只要有一方首先在棋盘的水平、垂直、斜线方向上形成连续的六颗棋子，就获得胜利
因此，棋盘上的任意空白位置都是合法的走法
但在实际中，并不一定要找到所有的空白位置，如果在开局时就把那些边界的空白位置当作下一步的走法，这样就会导致脱离战场的危险，对于走棋的一方是非常不利的
因此，本系统在走法生成模块中限定了所生成走法的数量，去掉了那些显然不可走的走法，保留了一些好的走法
本文所设计的α-β剪枝搜索算法就是要在返回的PossibleStep结构数组中找到一种最好的走法
在走法生成模块中，还需要对搜索引擎模块的搜索结果进行分析和处理
由于六子棋的特殊性，每次走两步棋，那么不得不考虑两步棋的综合效用
但在α-β剪枝搜索算法中又必须把两步当作一步处理，这就涉及到一个映射问题
int[] stepValues解释为两步棋的打分数组
这样的存储应用了哈希表的结构，在表中存储的数值的下标也对应于相应走法坐标的四位19进制数，这样能直观上了解对应估值是什么走法的估值
应用了这种方法，利用走法生成模块便可以按照六子棋的走法规则生成合理走法将博弈树展开
图3-8 开局 图3-9 连三阻挡 图3-10 界面截图 图3-11 电脑赢棋策略 图3-12 五连线与四连线重叠效果 图3-13 设置 图3-9为开局时，当黑棋连三是白棋采取阻挡方式
图3-10为已开发的六子棋计算机博弈系统的界面截图，图3-11和3-12为对弈过程中的一些情况，图3-13系统设置对话框
在搜索引擎模块中使用了α-β剪枝算法，该算法过程就是对博弈树的求解最优路径的过程，一般的博弈树搜索算法也是该过程，但α-β剪枝删除了不必要搜索的节点，有一定的效率性
走法生成模块中扫描棋盘有效位置得出有效走法，通过评估函数评估得出评价最高的走法
评估函数通过对子力值和空间灵活度值计算出当前局面评价值
系统已初具雏形，部分功能还有待完善，界面是应用MFC支持所设计的为上文所述，能实现人与人、人机对弈功能
4.2系统目前存在的问题和不足 到目前为止，本系统已基本实现，而且具有一定的棋力
但是本系统还存在以下问题和不足： 一、对两步棋的综合评估值是对两步棋分别评估值的相加，虽然绝大多数情况是如此，但对于一些特殊情况，还必须考虑到相加后的加权或加权后的相加
二、在搜索引擎模块，每次搜索是做的是全盘扫描，影响了搜索效率
没有对α-β剪枝搜索算法做更进一步的优化
