六子棋博弈研究与引擎实现(毕业论文13800字)
【摘要】
计算机博弈的研究已经为人工智能领域带来了很多重要的方法和理论，并且产生了广泛的社会影响，同时也应用于许多棋类游戏的研究和实现中。六子棋是最近几年才兴起并发展起来的棋类运动，它已经被越来越多的人所接受，但其计算机博弈的研究还相对较少。本文所设计的系统主要分为走法输入与输出、走法生成、搜索函数、评估函数等模块。本文以现有的计算机博弈理论为基础， 并将α-β搜索算法应用于六子棋系统中采用C++开发六子棋程序。系统开发平台为visual studio2008，应用传统的MFC技术设计系统总体框架和相关功能。
【关键词】
计算机博弈；六子棋；搜索技术；棋局评估
Connect6 Game Research and Engine Implementation
Abstract:
A lot of important methodological and theoretical computer game for the field of artificial intelligence, and a wide range of social impacts, are also used in the research and implementation of many board games. Six sub-chess is a chess movement, before the rise in recent years and developed it has been accepted by more and more people, but the computer game is still relatively small. The designed system consists of input and output moves, moves generated, the search function, evaluation function modules. This article is based on the existing computer game theory, and alpha-beta search algorithm is applied to six sub-game system using C + + developers to six sub-chess program. System development platform the Visual studio2008, the application of traditional MFC technical design of the overall framework and related functions.
Key words:
computer game;connect6;search technology;state evaluation
目 录
【摘要】 i
Abstract: ii
引言 - 1 -
1.六子棋的常识 - 1 -
1.1六子棋的历史 - 1 -
1.2六子棋博弈规则 - 1 -
1.3六子棋的基础棋型 - 2 -
1.3.1迫着（threat）的概念 - 2 -
1.3.2棋型描述 - 3 -
1.4六子棋的公平性论证 - 3 -
1.4.1 K子棋的定义 - 3 -
1.4.2公平性概念 - 4 -
1.4.3六子棋的公平性 - 5 -
1.5复杂度 - 5 -
2.六子棋博弈程序设计理论与方法 - 5 -
2.1总体设计思想 - 5 -
2.1.1搜索算法 - 5 -
2.1.2评估函数 - 6 -
2.2基本组成 - 6 -
2.2.1人机界面 - 6 -
2.2.2棋盘和棋局的表示 - 6 -
2.2.3走法生成 - 7 -
2.2.4机器博弈、搜索技术 - 8 -
2.2.5评估函数 - 12 -
3.六子棋计算机博弈系统的实现 - 15 -
3.1实现语言与工具 - 15 -
3.2系统构建 - 15 -
3.2.1棋盘状态空间表示 - 15 -
3.2.2六子棋计算机博弈问题描述 - 16 -
3.2.3搜索引擎 - 17 -
3.2.4走法生成 - 19 -
4.系统设计总结 - 22 -
4.1现阶段小结 - 22 -
4.2系统目前存在的问题和不足 - 23 -
4.3结语 - 23 -
参考文献 - 24 -
致谢 - 25 -
引言
人工智能诞生60周年以来，在知识工程、模式识别、机器学习、进化计算、专家系统、自然语言处理、数据挖掘、机器人、图像识别、人工生命、分布式人工智能等各个领域得到了蓬勃的发展。而计算机博弈作为人工智能领域的一个重要分支，也得到了极其快速的发展，并为人工智能带来了很多重要的方法和理论，同时也产生了广泛的社会影响和学术影响以及大量的研究成果。代表计算机博弈技术的各种棋类游戏在其各自的计算机博弈技术研究中已经取得了相应的成果，且其计算机博弈系统也日趋完善，基本上能达到大师级水平。六子棋作为最近几年才兴起的棋类游戏，其计算机博弈技术和算法的研究相对较少。本文设计的六子棋博弈系统也正是对六子棋博弈技术的一次尝试。
1.六子棋的常识
1.1六子棋的历史
六子棋最早由台湾交通大学的吴毅成教授提出，源自于五子棋。某一天，教授和自己的女儿在家下五子棋，女儿异想天开地提议“每人每次落两子，连成六子就胜利”。女儿的建议启发了吴教授，考虑出了第一手黑子下一子，随后轮流下两子的走法，并且认为这或许可以克服五子棋的不公平性。经过反复地论证和理论研究，吴教授发现这是个相当复杂且有趣的游戏。在他的推广下，六子棋就这样传开了，成为了一种棋类游戏。
1.2六子棋博弈规则
（1）六子棋，英文名称为connect6。参与六子棋的双方，一方持黑子一方持白方在棋盘上进行着手的对弈。
（2）棋盘：理论上的六子棋的棋盘可以是无限大小，本文采用19×19大小的棋盘，它是由19条直线与19条横线组成，有361个交点。其中有中央天元与八个星位参考点。
（3）术语介绍：
着手：即对弈双方在棋盘的空白点上落子。
线：是由同一种颜色棋子形成的组合，方向为横向、纵向和斜向。特别注意的是，在组合中可以有空子，但不能有对手棋子。
连线：线中没空子。
（4）对弈进行：对弈双方一方持黑子，一方持白子，黑子先下。持黑子者的第一手落一子后双方轮流落两子于棋盘上，直至分出胜负。
（5）着手的完成：在棋盘的空白点上放置该放棋子，或采用虚手时，着手就完成了。
（6）棋局的胜负：在对弈过程中，首先练成六连子或者长连方则获胜。在有时间限制的比赛中，棋手也可证明对手方时间用尽，或者在规定时间内没有落子完成，同样宣告胜利。对方主动宣告投降时，也能获得胜利。
（7）和局：当棋盘上所有的空子交点被填满，且对弈双方认为分出胜负，则宣告比赛平局。还有几种情况：对弈双方皆同意和局时，或者当一方虚手后另一方紧接着虚手时。要注意的是在一方提出和局提议后便启动对手的落子计时器。对手可以表示同意和局或者利用落子表示拒绝和局。
1.3六子棋的基础棋型
1.3.1迫着（threat）的概念
在很多棋类游戏中都存在着迫着的概念，简单地说就是当前局面处于有利于一方需要另一方防守的情况，在六子棋中，可以简单的描述为对弈的一方在不能形成连六情况下，当且仅需要落s颗子来阻止对手取得下一步的胜利，即可说对手有s个迫着。
图1-1 图1-2
图1-3 图1-4
图1-5
图1-6
单迫着，即本方在这一步后有一个迫着；双迫着，即本方有两个迫着。三个及以上迫着是六子棋的赢棋策略，因为对弈一方若存在三个及以上迫着，对方则同时需要三个以上的棋子去防守，由于六子棋每部每步只有两字可下，显然不能成功防御。图1-1、图1-2为单迫着，图1-3、图1-4为双迫着，图1-5、图1-6为三个及以上个迫着。
1.3.2棋型描述
棋型就是棋局的一种状态描述，是描述棋盘上不同棋子的分布状态。采用状态矩阵可以比较清楚地描述某个时刻，在博弈进程中棋局状态和棋子状态的变化，如何有意识地控制这个变化发展方向，并使得朝有利于己方赢棋的方向发展，是本六子棋系统需要解决的核心问题。
本文描述了其中15种棋型：六连（获胜）、长连（获胜）、活五、眠五、死五、活四、眠四、死四、活三、眠三、朦胧三、死三、活三、眠二、死二，并将这些棋型的描述放入决策支持系统的知识库，形成了计算机博弈决策系统推理的基础，下面对其中重要的常见棋型解释如下
①六连，C6：在棋盘的纵向、横向或斜向的任意一条线上，形成的连续相连的6颗同色棋子
②活五，A5：在同一直线上的5颗同色棋子，符合“对方必须用两手棋才能”的条件
③活四，A4：在同一直线上的4颗同色棋子，符合“对方必须用两手棋才能挡住”的条件
④眠四，S4：在同一直线上的4颗同色棋子，符合“对方用一手起就能挡住”的条件
⑤死四，D4：在同一直线上的4颗同色棋子，它们已无法形成六连或长连
⑥朦三，I3：在同一直线上的3颗同色棋子，符合“再下一手棋终能形成眠四，但如果再下两手棋的话就能形成活五”的条件
1.4六子棋的公平性论证
1.4.1 K子棋的定义
K子棋被定义为：Connect(m,n,k,p,q)，其中：
mn——棋盘大小为m×n；
k——对弈一方首先能在棋盘的横向、纵向、斜向某一方向上形成连续己方的棋子便可取得游戏的胜利；
q——对弈开始时第一方（默认为黑方）落子个数；
p——此后对弈双方每次落子个数。
所以，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)已被证明双方平手，所以不是单调不公平的。
定义三：经验上不公平性(empirical unfairness)：若大多数棋士尤其是专业棋士经过实际的下棋经验认定一方必胜或有极高胜率，则此游戏可称为经验上不公平。例如：在早期用一般规则的五子棋及了连珠棋，已被一般棋士认定是黑方必胜；因此在当时可称为经验上不公平。
定义四：潜在公平性(potential fairness)：若该游戏尚未被证明出或论证为明确不公平、单调不公平、经验上不公平的话，则此游戏可称为潜在公平。依据此定义，一个目前为潜在公平的游戏，不见得能持续在未来仍为潜在公平；一个有能持续为潜在公平愈久，则成为公平的机会就愈高。
1.4.3六子棋的公平性
从直观上看，六子棋的公平来自于——每当对弈的一方完成本轮落子，在棋盘上总比对手多出一子，且该种情况会随着对弈过程轮流出现，直至一方获胜为止。
虽然截至今日依然无法证明六子棋是绝对公平的，但可以有以下论点证明六子棋潜在的公平性:
①目前，尚无人能证明六子棋是明确不公平
②目前，尚无人能证明六子棋是单调不公平
③目前，尚无人能证明六子棋是经验上不公平
当然，对于六子棋公平性的讨论，还需要时间来找到更多有力的依据。
1.5复杂度
六子棋的复杂度远远高于五子棋且能和围棋、象棋匹敌，状态空间复杂度和博弈树复杂度分别为10^172和10^140。所以在这么复杂的空间中寻找可行性的走法的算法势必要求有很高的速度与质量。本系统计算机智能的级别还相对较低，算法的速度和质量与期望达到的效果还有一定的距离。
2.六子棋博弈程序设计理论与方法
2.1总体设计思想
本文所设计的六子棋博弈系统 分为走法输入与输出、走法生成、搜索函数、评估函数等模块。在搜索函数中采用什么样的搜索算法，在走法生成模块中怎么确定走法，在评估函数模块中如何确定参数以及怎样确定适应度函数，这些问题在本文都有了一定的解答。其中，搜索算法和评估函数是在本文设计程序过程中重点讨论的问题。
2.1.1搜索算法
系统中所牵扯的六子棋博弈问题可以用博弈树来描述。博弈树是把计算机和用户所有可能的走法和局面罗列出来的一棵树。黑白双方交替地按合理走法把树展开，树的每一个节点都表示某个特定局面。根节点表示的是当前需要计算的局面，中间节点表示的是对弈过程中的某个局面，叶子节点是树的最底端，表示可以推导的局面。叶子节点和根节点之间的最大距离，称为搜索深度。整个博弈树描述的是从当前局面出发，包含所有可能的对弈过程的搜索过程。这就牵扯到搜索算法，而且根据当前的棋局状态以及规定的搜索深度和宽度，在博弈树中找到一条最佳路径。系统的搜索模块完成以下两部分的工作：确定采用α-β搜索算法、尽可能缩小博弈树的规模而避免冗余计算。同时这是其他棋类计算机博弈也需考虑的问题。
而由于六子棋的特殊性，每次每方走两颗棋子，所以必须考虑两步的综合效用。在搜索算法模块中将两步当作一步做了处理，“两步”向“一步”转化的过程是做了一种算术和处理，即将两步棋的评估值做了简单的算术和处理，实际情况可能没那么简单。
2.1.2评估函数
模式识别和智能算法在评估函数中应用最为广泛。评估函数需要考虑的因素有很多，结合六子棋以及其他连珠棋的特点，这里考虑了两个因素：固定子力值和棋子灵活度值。固定子力值即是对胜利的有利程度；棋子灵活度值即是对于后续发展的应变能力。
在六子棋中，一步棋周围相同颜色越多就越容易实现连珠，该棋子的固定子力值就很高，同时如果该棋子周围有很多空缺位置，则该棋子的可发展空间就很大，棋子灵活度值就很高，相反的只要周围有不同颜色的棋子则可发展的空间就很小，形成连珠的概率就很小，棋子灵活度值就很低。在根据这两个值计算出权重值，在这里用了表的方式得到权重值的。
2.2基本组成
2.2.1人机界面
人机界面对于本系统来说是必不可缺的一部分，由于六子棋刚刚兴起，还没有类似象棋中的ucci之类的统一的界面协议和引擎，而在我的系统中，人机界面提供了走棋的后退、前进，棋盘连线用不同颜色的连线标示的功能，难度选择则是通过加载不同的引擎来实现的。同时还可以对当前的棋局进行备份，或者载入其他未下完的棋局继续对弈。
2.2.2棋盘和棋局的表示
要让计算机看懂棋盘这就需要一种数据结构对棋盘进行描述，并将各棋子的分布精确的表示出来。方法如下：
矩阵表示
比如棋盘上面有19路19行形成361个交叉点，它很容易用19×19的棋盘数组矩阵M19*19表示与坐标的对应关系。
要表示棋局则首先要给棋子编码。应该说方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码。如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是具有研究的余地。
以六子棋为例，使用位棋盘的话，因为变量是布尔值，所以每个格子只能表示有没有棋子。所以可以用两张位棋盘分别表示黑方和白方的子力分布情况。使用位棋盘的好处就是可以将走法表示成变换矩阵的形式，这样进行数学运算就比较方便。
矩阵表示六子棋棋盘，每个矩阵坐标上至少需要3中编码表示棋盘上各个格子的状态以保证可区分性。每个棋子因其先后顺序不同所以可以用数字顺序表示来唯一区分它们。一个棋局可能会有几种不同的矩阵来表示。图2-1 就表示为：
{0，0，0，0，0，0，0，0}
{0，0，0，0，0，0，0，0}
{0，0，2，1，1，1，0，0}
{0，1，2，1，2，1，0，0}
{0，0，0，1，2，2，2，0}
{0，0，0，2，2，0，0，0}
{0，0，0，0，0，0，0，0}
图2-1
其中0表示无子，1表示黑子，2表示白子
这种方法实现起来方便易行，且理解起来比较直观。
2.2.3走法生成
走法生成方法一般有棋盘扫描、模板匹配法和预置表法，时常还结合使用。
①棋盘扫描法
在走法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落子状况，确定有哪些地方可以落子。
根据六子棋的规则，棋盘有效区域内的所有空白的交点都是可行落子点，一般不是距离前两子其中任一子为6格距离的范围。六子棋、五子棋、围棋一类的棋类设计中最常用，在走法的表达上，棋盘扫描法最为直观，但时间开销巨大。本系统即是使用这种方法。
②模板匹配法
以象棋为例，当动子即当前落子确定之后，其落址与提址的相对关系便被固定下来。于是可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址。比如走马这一步，当马对准提址，根据蹩马点的具体分布，很容易判断可能的落址。
然而在六子棋中，不存在提址问题，只有落子位置，而且所有当前无子的位置都是有效的走法，所以在六子棋中用模板匹配法并不实用。
③预置表法
预置表法是使用最为经常的着法生成方法。它的基本思想就是用空间换时间。为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何位置(提址)、针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法。当然，六子棋无吃子情况。当然这种方法对于特殊情况的走子，可以快速的生成应对措施，在六子棋中，开局的走法比较固定且应对措施也比较固定所以采用预置表法效率比较高，而且开局时的形势是最不明朗的时候，采用棋盘扫描法生成的可行走法就比较多，从中选出最优走法的花费比较大。采用预置表法就形成了开局库。
综上所述，本系统采用了棋盘扫描法和预置表法相结合的方法。
2.2.4机器博弈、搜索技术
①博弈树
任何棋类游戏都要定义一棵有根的树（即“博弈树”），一个节点就代表棋类的一个局面，子节点就是这个局面走一步可以到达的一个局面。
②搜索算法
搜索算法是博弈树求解的灵魂，只有有了有效的搜索算法才能在有限的时间内找到正确的解。搜索算法是求解此类图模型的基本方法。我们无法在有限的时间内搜索到最终的胜负状态，于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而且变动最不大的最佳状态，于是从当前状态出发到达最佳状态的路径便称为最佳路径(Principal continuation),它代表着理智双方精彩对弈的系列着法。而最佳路径上的第一步棋便成为当前局面的最佳着法(The best move)。
需要注意的是博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。所以搜索到的最佳路径有两种，一种是有利于黑方的，一种是有利于白方的，对弈的过程就可表示成在不同深度的那层节点间寻找不利于对方且有利于己方的节点。
1）极大极小搜索
假设六子棋的两个玩家对弈，黑白方分别对应极大极小算法中的MAX方和MIN方。MAX先走，之后两人交替走步直到游戏结束。由于不可能对完整解图进行搜索，利用本文所定义的评估函数对当前局面进行估值，规定有利于MAX的估值很大，有利于MIN的估值则很小。下图为极大极小算法过程。
int MiniMax(position p,int d)
{
int bestvalue,value
if(GameOver)//检查棋局是否结束
return evaluation(p);//棋局结束，返回估值
if(depth<=0)//是否有叶子节点
return evaluation(p);//叶子节点，返回估值
if(p.color==black)//是否轮到黑子走
bestvalue=-INFINITY；//是，令初始最大值为极小
else
bestvalue=INFINITY;//否，令初始最小值为极大
for(each possibly move m)//对每一可能的走法m
{
makeMove(m);//产生第i个局面（子节点）
value=MiniMax(p,d-1);//递归调用MiniMax向下搜索
unMakeMove(m);//恢复当前局面
if(p.color==black)
bestvalue=max(value,bestvalue);//取最大值
else
bestvalue=min(value,bestvalue);//取最小值
}
return bestvalue;//返回最大、最小值
}
图2-2 极大极小搜索
2）α-β剪枝搜索
剪枝就是把不需要搜索的节点删除的过程，通常该节点之后情况与所期望的结果相反。
α-β剪枝搜索的基本方法还是极大极小搜索，所不同的是它对极大极小搜索过程进行了优化处理。
假设当前走棋方为MAX方，因为它选择着法是总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；将应对方定为MIN方，因为他走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有牵制作用的着法。
α剪枝：在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最佳值，记为α。显然此α值可作为MAX方着法指标的下界。在搜索此MAX节点的其它子节点，即探讨另一着法是，如果发现一个回合之后评估值变差，即孙节点评估值低于下界α值，则便可以剪掉此枝（以该子节点为根的子树），即不再考虑此“软着”的延伸。此类剪枝称为α剪枝。下图给出了搜索和剪枝过程，最后得到如粗箭头所示的最佳路径片断。
β剪枝：同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的牵制值，记为β。显然此β值可作为MAX方可能实现着法指标的上界。在搜索该MIN节点的其它子节点，即探讨另外时，如果发现一个回合之后牵制局面减弱，即孙子节点评估值高于上界β值，则便可以剪掉此枝，即不再考虑此“软着”的延伸。此类剪枝称为β剪枝。下图给出了搜索和剪枝过程，最后得到最佳路径片断。
需要指出的是，α-β剪枝是根据极大极小搜索规则而进行的，虽然它没有遍历某些子树的大量节点，但它仍不失穷尽搜索的本性。剪枝技巧的发现，一下便使博弈树搜索效率产生了质变。
有人将α-β剪枝作用延伸到多个回合之后，于是又出现了深层α-β剪枝(Deep α-βcut-off)算法[1]，也取得很好效果,本系统所用的α-β剪枝搜索算法伪代码如下：
AlphaBeta(nPly,nAlpha,nBeta)
IF 游戏结束
return 估值
ENDIF
IF 搜索到叶子节点
return 估值
ENDIF
IF 当前节点是取极小值的节点
FOR 生成每一可能的走法m
扩展生成下层结点
score=AlphaBeta（nPly-1，nAlpha，nBeta）；
删除搜索过的节点
IF score<nBeta
nBeta=score
IF nAlpha>=nBeta return nAlpha
ENDIF
ENDIF
ENDFOR
return nBeta
ELSE 当前节点是去极大值的节点
FOR 生成每一可能的走法m
扩展生成下层结点
score=AlphaBeta（nPly-1，nAlpha，nBeta）；
删除搜索过的节点
IF score>nAlpha
nAlpha=score
IF nAlpha>=nBeta return nBeta
ENDIF
ENDIF
ENDFOR
return nAlpha
ENDIF
END AlphaBeta
图2-5 α-β搜索算法
3）迭代深化搜索
文献[4][11]中对迭代深化搜索做了详细的描述。迭代深化的思想是搜索博弈树时先搜索该博弈树的子树，然后一次向上层树节点搜索。该方法的好处是搜索子树的时间要比搜索父树的时间少，这样可以再有限的时间内先比较可行的最佳路径。这种方法适用在对计算机生成给出走棋有时间限制的情况。对α-β剪枝采用迭代加深，本系统中所设的MaxDepth为6，相应代码如下：
While(i<MaxDepth)
{
AlphaBeta(i,nAlpha,nBeta);
if(time>60seconds)
Break;
i++;
}
图2-6 添加迭代深化
2.2.5评估函数
对于博弈树求解有了良好的搜索算法还只是问题的一个方面，问题的另一个方面就是评估函数。只有有了良好的评估函数才能保证较快地找到正解。而评估函数是对棋局的综合评估，该函数的好坏直接决定解题能力强弱。通常一个优秀的棋手总有一个良好的对棋局的判断能力，能够协调各棋子的关系、取舍，有机地组织个棋子的进攻步调，控制棋局的发展。因此如果要把这一整套的思维物化成一个数值函数来评估，就成了一个相当复杂的问题。
①整体考虑
评估函数综合了大量跟具体棋类有关的知识。本系统的评估函数从以下两个基本假设出发。
1）局面的性质能量化成一个数字。例如，这个数字可以是对取胜的概率做出的估计。
2）其中一方对这个性质的衡量应该跟对手衡量的性质是一样的，如果其中一方认为处于优势，那么反过来对手认为他处于劣势。真实情况并非如此，但是这个假设可以让我们的搜索算法正常工作，而且在实战中它跟真实情况非常接近。
文献[1]中就对影响评估函数的复杂程度的因素做了说明。评估可以是简单的或复杂的，这取决于在程序中加了多少知识。评估越复杂，包含知识的代码就越多，程序就越慢。通常，程序的质量（棋力）可以通过知识和速度的乘积来评估，如图2-7所示。
②组合评估要素
把评估要素组合起来，评估函数是很多项的和，每一项是一个函数，它负责找到局面中的某个特定因素。
棋类程序应该充分尝试各种可能的评估函数：把各种胜利的可能性结合起来，包括很快获胜(考虑进攻手段)，很多回合以后能获胜，以及在残局中获胜的可能性，然后把这些可能性以适当的方式结合起来。如果黑方很快获胜的可能性用bs表示，而白方用ws，在很多回合以后获胜（即不是很快获胜）的可能性事bm或wm，而在残局中获胜的可能性事be或we，那么整个获胜的可能性就是：
黑方：bs+（1-bs-ws）*bm+（1-bs-ws-bm-wm）*be
白方：ws+（1-bs-ws）*wm+（1-bs-ws-bm-wm）*we
通过和类似上面的公式把若干单独概率结合起来，在评估函数中或许是个很好的估计概率的思路。每种概率是否估计得好，这就需要程序的估计来和数据库中棋局的真实结果来做比较，这就需要让程序具有基本判断的能力（判断某种攻击是否起到效果）。
③评估函数中所需加入的信息
本文设计的评估函数加入了两个因素的信息：
1）子力（Material）：在国际象棋中，它是子力价值的和，在围棋或黑白棋中，它是双方棋盘上棋子的数量。这种评价通常是有效的，但其他像五子棋一样的游戏，子力是没有作用的，因为好坏仅仅取决于棋子在棋盘上的位置，看它是否能发挥作用。
2）空间（Space）：在某些棋类中，棋盘可以分为一方控制的区域，另一方控制的区域，以及有争议的区域。例如在围棋中这个思想被充分体现。而包括国际象棋在内的一些棋类也具有这种概念，某一方的区域包括一些格子，这些个字被那一方的棋子所攻击或保护，并且不被对方棋子所攻击或保护。在黑白棋中，如果一块相连的棋子占据一个角，那么这些棋子就被吃不掉了，成为该棋手的领地。空间的评价就是简单地把这些区域加起来，如果有说法表明某个格子比其他格子重要的话，那么就用稍复杂点的办法，增加区域重要性的因素。
④获取评估函数中权重值的方法
局面评价中的很多函数，把这些函数加起来就可以组合成评估函数。但是权重值从哪里来呢？获取评估函数中权重值的方法有很多种。
这里采用了人工设置的规格化方法。该方法是人为给出权重值，因此这些权重值的设置比较僵硬，为了能很好使评估函数比较精确地估值，这些权重值之间的差设置的很大。在一些特殊棋类中为了提高评估函数的准确性，会采用一种模拟实际情况的方法来对这些权重值进行调整。
3.六子棋计算机博弈系统的实现
3.1实现语言与工具
实现语言为C++，因为是棋类程序，所以对程序的执行效率有很高的要求，C++在编程语言中有很高执行效率。它很好的继承了C语言的有效性 、灵活性以及便于移植等特点，扩展了对面向对象思想的支持，且结构清晰、易于扩充，适合绝大数场合的编程要求，是一种理想的程序设计语言。
开发工具：Visual Studio 2008
3.2系统构建
3.2.1棋盘状态空间表示
要让计算机能够下棋，首先就要把下棋问题表示成计算机可理解的形式，即把六子棋博弈问题形式化，存在计算机中，并能让搜索、估值等算法对这些数据进行操作。需要在计算机中表示的主要问题有棋盘局势状态、落子的顺序表示等。
（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减一。
3.2.2六子棋计算机博弈问题描述
本文的六子棋博弈问题时用博弈树进行描述的。博弈树是把计算机和用户所有可能的走法和局面罗列出来的一颗树。黑白双方交替地按合理走法把树展开，树的每一个结点都表示某一个特定局面。根节点表示的是当前需要计算的局面，中间节点表示的是对弈过程中的某一个局面，叶子节点是树的最底端，表示可以推导的局面。叶子节点和根节点之间的最大距离，称为搜索深度。整个博弈树描述的是从当前局面出发，包含所有可能的对弈过程的搜索树。六子棋计算机博弈问题也就转化为寻求最佳路径的问题。
对于树中的每一个节点来说，黑白双方都会从子节点中选择最有利于自己的分枝。因为博弈树中值的传递是由下至上的，这就要求对叶子节点表示的局面必须有一个极为准确的打分。对于局面最为准确的估计莫过于已经分出胜负的情况，即建立在叶子节点分出胜负的完全博弈树。六子棋的完全博弈树大概有10765个节点，建立这个博弈树已经远远超出了当代计算机的处理能力。唯一的解决方法就是让博弈树扩展到计算机运算可以接受的深度，然后对没有分出胜负的叶子节点给出一个最为准确的打分，表示此局面下取得胜利的可能性。而对于节点的打分就是有评估函数计算得到的。
走法生成模块的功能就是按照六子棋的走法规则生成合理走法将博弈树展开；搜索引擎模块的功能则是尽可能缩小树的规模，避免一切冗余的计算。
3.2.3搜索引擎
计算机要选择有利于它的最佳下法，就要判断哪种形势对它最为有利。但往往对一个形势的判断是很难做到准确的，特别是一盘棋刚开始的时候，棋盘的形势很不明朗，即使是专家也很难做出准确的判断。为了判断哪种下法最有利，这里采用了向后多算几步的方法，估计一下多走几步后面局面的形势如何。这样的思维方式在对弈过程中是很自然的事，显然运用到计算机中有一定启发作用。上文已经提到，棋局的不断向后计算，形成了一颗博弈树，“多算性”的思想即是对博弈树的搜索过程，这就是博弈树的极大极小搜索算法。然后在极大极小值的搜索过程中，遍历了整颗博弈树，每个结点都访问了一次，这样的搜索算法粗糙，搜索量非常大，而使搜索效率低下。
为了尽可能缩小树的规模，避免一些冗余的过程，从而提高搜索效率，必须对博弈树中的节点进行筛选，过滤掉一些不必要搜索的节点。由此，本系统的搜索引擎模块中采用了α-β剪枝搜索算法，并且根据六子棋的特点，加入了一些启发式信息。
（1）α-β剪枝搜索算法
本文在上面已经对α-β剪枝搜索算法的原理做了简单的介绍，现将α-β剪枝搜索算法引入到六子棋计算机博弈系统的搜索引擎模块。
首先定义一个α、β节点的枚举类型：
enum ALPHABERTANODETYPE
{
ALPHA,BETA
}
图3-3 分类α、β节点
表示搜索中是α节点还是β节点。
然后定义一个结构用来表示用α-β剪枝搜索算法搜索某一方该走哪两颗棋的搜索结果：
struct PossibleStep
{
Step[] step;//走两步棋
int priority;//该走法的优先级
}
图3-3 走法结构
系统中定义了一个递归函数来实现α-β剪枝过程：
public static PossibleStep AlphaBetaRecursion(StepStatus[][] chessBoardStatus,int player,int width,int depth,ALPHABETANODETYPE nodeType,int[] depthValues)//alphabeta剪枝递归函数
图3-5 α-β剪枝函数参数定义
其中，α-β剪枝的递归函数包括6个参数：
StepStatus[][]chessBoardStatus //当前棋盘状态
int player //搜索的宽度
int width //搜索的深度
ALPHABETANODETYPE nodeType //是α节点还是β节点
Int[] depthValue //两步棋的打分数组
图3-6 参数说明
函数返回值为一个PossibleStep的结构，指明某一方该走哪两颗棋。
这里需要指出的是，以上所使用的α-β剪枝搜索算法，在博弈树的搜索过程中，如果所有节点的打分或者说估值都是准确的，并且都以该估值为依据。但实际上，这样的估值肯定是有误差的。
在上述的α-β剪枝搜索算法中，搜索的深度和宽度决定了搜索的时间以及搜索的精度。如果搜索的深度越深，宽度越宽，那么搜索的时间就越长，但是搜索的精度就越高，AI的智能就越高，但这是以牺牲时间作为代价的；反之，如果搜索的深度越浅，宽度越窄，那么搜索的时间就越短，但是搜索的精度就越低，AI的智能也相对较低。
由此，需要在搜索时间以及搜索精度上作综合考虑，既不能让搜索的时间过长，也不能让搜索的精度过低。本文在搜索算法的设计中，在保证搜索时间符合要求的情况下，尽可能增加搜索深度和宽度，以提高搜索精度，提高AI的智能。程序在设计过程中，也是以搜索的深度和宽度的不同来设定AI的智能等级的。
（2）启发式信息
在六子棋计算机博弈系统的搜索引擎模块中，已经引入了α-β剪枝搜索算法。现有棋类的计算机博弈中，完全靠单一的搜索算法来搜索很难得到理想的搜索结果，达不到理想的效果，因而一般都采用两种或几种搜索算法的相结合的方法，或者以一种搜索算法为主，同时根据棋类知识加入一些启发式信息，以获得较为理想的搜索结果。
本文在以α-β剪枝搜索算法为主要搜索算法的基础上，根据六子棋的特点，加入了一些启发式信息，主要是对一些诘棋的判断。如果α-β剪枝搜索算法在搜索的过程中，发现当前的局面与预先定义的诘棋的某一个局面相符，那么直接调用其对应的最简单的解法。本系统使用表结构来存储一些典型的诘棋局面和其对应的解法。
在α-β剪枝搜索算法通过“剪枝”缩小博弈树的规模后，同时加入一些基于诘棋的启发式信息可以进一步缩小博弈树的规模，避免一些冗余的过程，使搜索效率和准确性得到提高。
3.2.4走法生成
走法生成是指将一个局面的所有可能的走法罗列出来的那一部分程序，也就是用来告诉其它部分下一步可以往哪里走的模块。对于六子棋来说，由于双方只有黑白各一种棋子，并且在走子的过程中，双方轮流走子，只要有一方首先在棋盘的水平、垂直、斜线方向上形成连续的六颗棋子，就获得胜利。因此，棋盘上的任意空白位置都是合法的走法。但在实际中，并不一定要找到所有的空白位置，如果在开局时就把那些边界的空白位置当作下一步的走法，这样就会导致脱离战场的危险，对于走棋的一方是非常不利的。因此，本系统在走法生成模块中限定了所生成走法的数量，去掉了那些显然不可走的走法，保留了一些好的走法。
首先定义一个函数，来得到规定数量的合法的走法：
public static PossibleStep[] GetLimitedPossibleSteps(int[] stepValue,int count,int player)
函数包括3个参数：
int[] stepValues //两步棋的打分数组
int count //生成合法走法的数量
int player //是黑方还是白方走棋
图3-7 走法生成函数参数示意
函数返回值为一个为一个PossibleStep的结构数组，数组的长度为count，表示了生成合法走法的数量，数组中每一个元素是一种合法的走法，包括某一方走两步棋子。
本文所设计的α-β剪枝搜索算法就是要在返回的PossibleStep结构数组中找到一种最好的走法。
在走法生成模块中，还需要对搜索引擎模块的搜索结果进行分析和处理。
由于六子棋的特殊性，每次走两步棋，那么不得不考虑两步棋的综合效用。但在α-β剪枝搜索算法中又必须把两步当作一步处理，这就涉及到一个映射问题。本文采取了把两步棋的棋盘坐标映射到一维空间的方法，用下式计算综合两步的StepValue：
stepValues[((i*19+j)*19+k)*19+l]=tempvalue1+tempvalue2
其中，（i，j）和（k，l）分别表示第一步和第二步的棋盘坐标，tempvalue1和tempvalue2分别表示第一步和第二部的估值， “两步”到“一步”的问题就得到了解决。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系统设置对话框。
4.系统设计总结
4.1现阶段小结
本文以当前的六子棋游戏为研究对象设计了其计算机博弈系统，其中主要部分为搜索引擎、走法生成和评估函数模块。
在搜索引擎模块中使用了α-β剪枝算法，该算法过程就是对博弈树的求解最优路径的过程，一般的博弈树搜索算法也是该过程，但α-β剪枝删除了不必要搜索的节点，有一定的效率性。走法生成模块中扫描棋盘有效位置得出有效走法，通过评估函数评估得出评价最高的走法。评估函数通过对子力值和空间灵活度值计算出当前局面评价值。
系统已初具雏形，部分功能还有待完善，界面是应用MFC支持所设计的为上文所述，能实现人与人、人机对弈功能。
4.2系统目前存在的问题和不足
到目前为止，本系统已基本实现，而且具有一定的棋力。但是本系统还存在以下问题和不足：
一、对两步棋的综合评估值是对两步棋分别评估值的相加，虽然绝大多数情况是如此，但对于一些特殊情况，还必须考虑到相加后的加权或加权后的相加。
二、在搜索引擎模块，每次搜索是做的是全盘扫描，影响了搜索效率。没有对α-β剪枝搜索算法做更进一步的优化。
后续的工作就是对上述问题的研究与解决。
4.3结语
希望本文能给关心和支持六子棋运动的人们带来一些有用的启示，也希望读了这篇文章的人能了解文中的算法思想，并将其运用到自身学习的领域中去。
参考文献
[1]李果，六子棋计算机博弈及其系统的研究与实现，重庆大学硕士学位论文，2007.4
[2]徐长明、马宗民、徐心和，一种新的连珠棋局表示法及其在六子棋中的应用，东北大学学报第30卷第4期，2009.4
[3]吴毅成等，六子棋，ICGA Journal，2005.12
[4]张振、庞海，机器博弈及其搜索算法的研究，软件导刊第7卷第7期，2008.7
[5]George Eluder.Artifical Intelligence:Structures and Strategies fo Complex Problem Solving,Fifth Edition.机械工业出版社，2005
[6]Yen S J,Chen J C,Yang T N. Computer Chine∞chess[J].ICGA Journal,2004
[7]I-Chen WU and Dei-Yen Huang.A New Family of k-in-a-low Games.Hsinchu,Taiwan
[8]蔡自兴，徐光佑.人工智能及其应用（第三版）.清华大学出版社，2003.
[9]六子棋主页.http://www.connect6.org/.
[10]王小春.PC游戏编程（人机博弈）.重庆大学出版社,2003.
[11]安涌.六子棋机器博弈研究与开发.沈阳航空工业学院硕士论文，2008.01.
[12]Nils J.Niisson,郑扣根，庄越挺译，潘云鹤校.人工智能.北京：机械工业出版社,2000
[13]黄继平，苗华，张栋.用遗传算法实现六子棋评估函数参数优化.重庆工学院学报，2009.11.
[14]黄继平，苗华，张栋.六子棋智能博弈系统的研究与实现.电脑知识与技术.2009.09
[15]张小川，陈光年，张世强，孙可均，李祖枢.六子棋博弈的评估函数.重庆理工大学学报（自然科学），2010.02.
[16]李红，吴粉侠，刘小豫.博弈树搜索算法研究.长春工程院学报，2007年第8卷第2棋.
[17]闫海艇.基于UML的五子棋的分析语设计.安徽理工大学学报,2007年12月第7卷第4期.
|
