本文作者(刘雅靖),请您在阅读本文时尊重作者版权。
计算机博弈之六子棋的主要技术分析
摘要：该文主要介绍了六子棋博弈的四个主要部分：状态表示，走法生成，评估函数以及搜索算法，并分析了当前的主要技术及其优缺点。而且对搜索算法进行了一定的优化，为计算机博弈研究提供了一定的参考。
关键词：计算机博弈；六子棋；数据结构；走法生成；搜索算法Main Technologies Analysis of Connect6 in Computer Game
LIU Ya-jing
(Dalian Jiaotong University, Software Colledge, Dalian 116021, China)
Abstrct: This article mainly introduced the four main parts of Connect6:state representation, move generation,evaluation function, searching algorithm, and analyzes the main teconology in current and their advantages and disadvantages. Also I optimized the searching algorithm, and provided a certain reference for the Computer Game.
Key words: computer game; connect6; data structure; move generation; searching algorithm
计算机博弈是智能性行为游戏，五六十年代，它一度是人工智能的带头领域，至今在人工智能界仍非常受重视。计算机博弈种类很多，像国际象棋，围棋，中国象棋等，研究相对成熟。而六子棋是2005年台湾交通大学资讯工程系的吴毅成教授提出的一系列K子棋中的一种。由于其特殊性，每次每方走两颗棋子，直观看，其状态空间复杂度及博弈树的复杂度会成倍提高，因此以六子棋作为研究平台，不仅能促进六子棋这项活动，而且能为计算机博弈技术带来新的发展。
六子棋（ Connect6）,规则是第一手黑方先下一颗子，第二手开始，双方轮流每次下两子，在横向，竖向，斜向先连成六子或六子以上为赢，若全部棋盘下完仍未分胜负，判和。
由于六子棋刚兴起不久，国内外研究相对较少，但是作为计算机博弈的一种，它与象棋围棋的研究有一定的相似处，因此它的主要技术要点也包括这些项：状态表示，走法生成，评估函数，博弈树搜索等，下面我就分析一下。
1 状态表示
我们在用计算机解决任何实际问题之前，必须要将具体问题表示成计算机能够处理的数据。在这里我们需要将六子棋的棋局状态，棋局的变化以及棋局局部特征低占用率高速度的表示出来。
下面有两种方法我们可以尝试来表示棋局状态：
1.1 矩阵表示法（又叫数组表示法）
六子棋棋盘通常为19×19，因此可以用二维数组Board[19][19]表示。当然也能用一维数组表示，占用空间361B。
1.2 比特棋盘表示法
在高性能的博弈程序里，比特棋盘 被广泛应用，在六子棋中，棋盘上每个交叉点用2个bit位来表示，即00为黑，01为白，10为空，11其他，每个横线上19个点共需38bit，用一个8B的长整型来表示，那19行就有19×8B，即152B，比数组表示法占的空间要小。
六子棋的局部特征表示方法也有很多种：
1.3 用字符串结构来表示特征
我们用”OO OO”来表示，其中“O”代表有棋，“ ”代表空位，采用字符串模式匹配算法来提取局部特征，这种方式很直观，但没有区分黑白棋，因此特征不明显，而且取一种特征需遍历整个棋盘，运行速率很低。
1.4 用一个状态数组来表示特征
我们以当前棋子位置为中心，分别向相反的方向定长扫描6个点，得到长度为13的状态数组，而每个数组元素有四个可能状态：黑，白，空或棋盘外，如图1。
这种方法棋型种类巨大，数据冗余严重，尽管简单直观。
1.5 一种新的6-8窗口法
经过对六子棋深入研究，有人提出6-8窗口法，如图2。
6窗口主要功能是提取棋型信息并判断是否同色， 8窗口主要功能用于辅助判断是否存在迫著点，取完一个棋型后，窗口向前移动，然后提取下一个，直到遍历完整个棋盘。该方法优点是遍历完一次可统计完一种棋型的数量，完成局面估值，而且棋型少很多。但是不够直观，代码编写也较困难。
所以一种好的状态表示方法对加快搜索效率非常重要。
2 走法生成
走法生成就是将所有可能的走法罗列出来，并告知下一步走哪。
走法生成过程中常伴随着搜索进行，因此好的走法生成，可以提高搜索效率。走法生成主要有这几种：棋盘扫描法，模板匹配法，预置表法以及这些方法的结合。
棋盘扫描法：就是在棋盘内反复搜索有效区域，制约条件以及落子状况，从而确定有哪些地方可以落子，这种方法时间开销巨大。
