基本信息
- 项目名称：
- 六子棋
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 科技发明制作B类
- 简介：
- 目前已经出现六子棋的论坛以及比赛的平台，但只限于人人对弈。真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著(Threats)的胜利策略，但是对于其计算机博弈问题没有给出更加深刻的阐述，同时也没有全面解决六子棋计算机博弈问题。本文正是对六子棋计算机博弈技术的一个探索。
- 详细介绍：
- 1.研究目标 六子棋计算机博弈系统可以分为四个主要部分：搜索引擎、走法生成、评估函数和开局库。搜索引擎模块包含了比较成熟的搜索算法，以及对他们的结合和优化；走法生成模块是对搜索的结果进行比较处理，确定当前的走法；评估函数模块中本文根据棋型特征构建了着子棋力的评估函数并提出用 算法来做评估函数参数的调整与优化的方法；开局库存储了大量的专家棋谱，可以避免在开局时由于搜索深度的不足而带来战略上的失误，同时大大提高了对战的效率。 2.内容介绍 六子棋是“信息完备”的游戏，因为游戏双方面对的局面是同一个局面，任何一方所掌握的棋子及其位置的信息是一样的。除了六子棋，象棋、围棋等也可属于这一范畴。 人机对弈的程序, 至少应具备以下5个部分: ①某种在机器中表示棋局的方法，能够让程序知道博弈的状态； ②产生合法走法的规则，以使博弈公正地进行，并可判断人类对手是否乱走； ③从所有合法的走法中选择最佳的走法技术(博弈搜索)； ④一种评估局面优劣的方法(评估函数)，用以同上面的技术配合做出智能的选择； ⑤一个人机界面，计算机博弈程序才能使用。 2.开发与运行环境 针对上述介绍的六子棋的特性，利用现有资源选用如下的配置，当然在正式比赛中最好选用配置更高的计算机，以便系统在有限的时间里可以搜索更深的深度。特别指出，为方便演示，本论文中提到的源码搜索深度最多只到第四层，采用如下配置运行该系统，搜索时间最多不超过10秒。 开发环境 ? Intel PentiumⅣ? 2.8GHz CPU 1.00G内存 100G硬盘 ? Microsoft Windows? XP Professional Service Pack3 ? Microsoft Visual Studio.NET 2005 运行环境(最低配置) ? Intel PentiumⅢ? 以上733MHz CPU 256M以上内存 4G以上硬盘 ? Microsoft Windows98 操作系统 ? 800*600或以上的屏幕分辨率 3. 系统功能设计 六子棋博弈程序的可以分为五个部分：数据表示，走法生成，搜索引擎，核心估值和用户界面。下面我们将概要介绍一下各部分的实现过程。 3.1人机界面 任何计算机博弈程序都需要一个人机界面，由于六子棋刚刚兴起，还没有类似象棋中的UCCI之类的统一的界面协议和引擎，现在都还是六子棋爱好者单独开发的。总体来说，人机界面是为了方便棋手的操作，并且提供难度选择、计时器、走棋记录等功能。 3.2棋盘表示 要让计算机下棋首先需要解决的就是棋盘和棋局的数字表示。目前所有棋类常用的表示方法有比特表示(又称位棋盘)和矩阵表示，本文中提到的程序采用的是矩阵表示。比如棋盘是由9路9行形成81个交叉点, 它很容易用9×9 的棋盘数组矩阵 表示出棋子与坐标的对应关系。要表示棋局则首先要给棋子编码，应该说编码的方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码。如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是有研究的余地。 以六子棋为例，我们需要把屏幕上看到的棋子位置、颜色、价值等信息、用计算机语言表示出来。本程序的棋盘数据表示如图2-1所示，棋盘数据由一个19*19的二位数组表示，其中用 1 代表黑子，2 表示白子，而 0代表该节点没有棋子。 3.3着法生成 当前流行的着法生成方法有棋盘扫描法、模板匹配法和预置表法，通常还结合使用。六子棋中，合法走法是棋盘上没有落子的结点，即m_Dream6Board[i][j]=0。简述如下： ①模板匹配法：通常是一些优秀的走法定式，期盼数组按照这种方法落子，赢得机会很大。这些大多是一些大师公认的棋谱，存储在数据库中，方便迅速落子，节约时间。 ②预置表法：它是最为经常的着法生成方法，基本思想是用空间换时间，为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何位置(提址)，针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法。当然，六子棋无吃子情况，但是确存在已经有三个或四个连成一条线的棋子，把这些地方引入预置表是一种常见思路。 ③棋盘扫描法：在着法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落子状况，确定有哪些结点可以落子。根据六子棋的规则，棋盘有效区域内的所有空白的交点都是可行落子点。目前的规则中还不存在禁手(五子棋对弈有三?三、四?四等禁手的规则)，即所有未落棋子点都是扫描区域。在着法的表达上，棋盘扫描法最为直观，但时间开销巨大。 所以本程序中把上述三种方法结合起来运用，尤其是对棋盘扫描法，本程序中分别采用压缩存储空间(根据对称性)和缩小扫描范围(根据脱离战场必败的思想)两种独特的方法，在开局不久尤为有效。 3.4 博弈树 任何棋类游戏都要定义一棵有根的树(即博弈树)，一个结点就代表棋类的一个局面，子结点就是这个局面走一步可以到达的一个局面。 搜索引擎的作用就是借助评估函数从“上往下搜”，然后从“后(叶)往前看”，最终选出一条“最佳”路径。如果在竞赛时间固定的情况下，通过衡量剩余时间来分配每一步的搜索时间，以此来约束搜索深度。通常情况下，开局时调用开局库中已有的模式可以节约时间，但是后期由于局面较复杂，可能必须安排更多的时间加强搜索深度。 一般来说，博弈树的根结点应该有很多子结点，先根据对称性去掉一些结点(俗称剪枝)来压缩存储空间，然后把这颗普通树转化成完全二叉树，便于计算机处理。如果同样的棋盘是由两个不同的搜索引擎同时搜索形成的，那么我们就建立两棵普通树，然后把这两棵树组成的森林转化成完全二叉树。假设博弈树是有限的，这样我们就不会遇到永无止境的棋局或者一步有无限多种着法的棋局。 一般搜索树中有三种类型的结点(当乙执黑时)： ①偶数层的中间结点，代表棋手甲要走的局面； ②奇数层的中间结点，代表棋手乙要走的局面； ③叶子结点，代表棋局结束的局面，即棋手甲或棋手乙获胜，或者是和局。 我们由图2－2可见，本程序采用的算法是“两步并一步”的方法，所以也会有上述其他棋类中提到的奇数层和偶数层棋手交替表示的方法。 3.5搜索算法 搜索算法是博弈树求解的灵魂，有效的搜索算法能在有限的时间内找到正确的结点。我们无法搜索到最终的胜负状态，于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而又不剧烈波动的最佳状态(棋局)，从当前状态出发到达最佳状态的路径便为最佳路径(Principal Continuation)，它代表着理智双方精彩对弈的系列着 法。而最佳路径上的第一步棋便成为当前局面的最佳着法(The best move)。所谓 “不剧烈波动”就是说最佳棋局不是在进行子力交换与激烈拼杀的过程当中。 3.6评估函数 对于博弈树求解有了良好的搜索算法还只是问题的一个方面，问题的另一个方面就是评估函数。只有有了优秀的评估函数才能保证较快地找到合适结点。而评估函数是对棋局的综合评估，该函数的好坏直接决定棋力的强弱。通常一个优秀的棋手总有一个良好的对棋局的判断能力，能够协调各棋子的关系、恰当取舍，合理组织棋子的进攻步调，控制棋局的发展。因此如果要把这一整套的思维物化成一个数值函数来评估，本身就是一个相当复杂的问题。 (1)整体考虑 评估函数综合了大量跟具体棋类有关的知识，把局面的情况衡量成一个数字，这同样也是评估函数在该结点的返回值。评估的指标取决于对六子棋的熟练程度，评估越复杂，包含的代码可能越多，时空复杂度也可能就越大。 (2) 组合评估要素 把评估要素组合起来，评估函数就成为一个多项式的和，每一项又可能是一个函数，它负责找到局面中的某个特定因素，绝大多数学者主张在这里运用模糊数学中的层析分析法来解决类似综合的问题。通常来说，棋类程序的评估函数是在不断尝试中逐渐修正、磨合出来的，包括快攻获胜和残局获胜中的很多“不确定”因素。如果黑方很快获胜的可能性用 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 通过和类似上面的公式把若干单独概率结合起来，在评估函数中是一种常见的估计概率的思路。每种概率是否估计得好，这就需要用程序的估计来和开局库中棋局的真实结果来做比较，同时需要让程序具有基本判断的能力。 (3)评估函数的指标 有必要把下列不同类型的评判指标组合起来： ①子力(Material)：在国际象棋中，它是子力价值的和，在围棋或黑白棋中，它是双方棋盘上棋子的数量。这种评价通常是有效的，但其他像六子棋这样的游戏，子力是没有多大作用的，因为棋力的好坏仅仅取决于棋子在棋盘上的位置； ②空间(Space)：在某些棋类中，棋盘可以分为一方控制的区域，另一方控制的区域，以及有争议的区域。空间的评价就是把这些区域加起来，如果某个结点比其他结点重要的话，那么就用必须添加加区域重要性的因素，比如调整该结点的权重； ③机动(Mobility)：具备越多选择余地的着法，越有可能找到最优落子点能取得较好的局势，也即强迫算法不要在“死角”或者更本不可能赢的区域落棋子； ④着法(Tempo)：这与机动性有密切联系，它指的是在黑白棋或连四子棋中(以及某些国际象棋残局中)，某方被迫作出使局面变得不利的着法，这种思路更多运用在对己方不利的残局，“无奈之下的落子”迫使局面更加混乱，当然出现这样的状况对双方都不利，但是在发现赢棋已经无望的时候，逼和总是比束手就擒要好的多。 ⑤威胁(Threat)：对一些已经被大家公认的具有威胁的棋的套数出来的时候，必须提高这种局面的优先级，让搜索引擎首先检索这些结点，或者采用一些预先存储在数据库中的定式，直接避过搜索，套用历史上一致公认的好棋路，直接落子。这种情况很常见，不如被对方棋子逼入死角或者对方已经有可能形成三?三、四?四等局面； ⑥形状(Shape)：与威胁类似，局面中的棋子已经出现某种特殊的形状，必须优先处理，或者己方局面有利于形成某种比较好的定式的形状，优先分析这些结点。当然某些形状就是一个陷阱的警告，必须提醒系统有效回避。 (4)获取评估函数的数值解的方法 以下给出一些获取评估函数中数值的方法： ①爬山法(Hill-Climbing)：通过不断的对弈，调整局面和棋形的权重，每次对权重作很小的改变，测试改变后的表现，仅当成绩提高时才采纳这个改变，需要重复很多次。于此类似的是模拟退火法(Simulated Annealing)。也是对权重做出改变来提高成绩，即使改变没有提高成绩，有时候也采纳改变，这种方法试图跳出全局最优的情况； ②神经网络(Neural Networks)：这种方法的好处在于它不需要很懂得太多的棋类知识，就可以让程序有个比较好的评价函数。实际上这更多地是一种评价函数的类型，而不仅是用来选择权重的，于此类似的方法有遗传算法，它可以得到几组不同的好的权重值，并且不断增加新的组合跟原来的结果做比较，通过淘汰坏的组合来控制种群的数量。在后文中将简要描述这种方法在本程序中的应用。
作品图片
作品专业信息
设计、发明的目的和基本思路、创新点、技术关键和主要技术指标
- 本文中提出的六子棋计算机博弈系统可以分为四个主要部分：搜索引擎、走法生成、评估函数和开局库。搜索引擎模块包含了比较成熟的搜索算法，以及对他们的结合和优化；走法生成模块是对搜索的结果进行比较处理，确定当前的走法；评估函数模块中本文根据棋型特征构建了着子棋力的评估函数并提出用 算法来做评估函数参数的调整与优化的方法。
科学性、先进性
- 本文对六子棋计算机博弈系统进行了测试与评价，包括评估函数的准确度、搜索算法的效率以及系统的整体性能，同时简单分析了运用更高性能的服务器，通过互联网与棋类爱好者实现人机对弈的可操作性。
获奖情况及鉴定结果
- 无
作品所处阶段
- 生产阶段
技术转让方式
- 可以代理转让
作品可展示的形式
- 实物 产品 图纸 现场演示 图片 录像
使用说明,技术特点和优势,适应范围,推广前景的技术性说明,市场分析,经济效益预测
- 这套六子棋程序采用C++开发，可以嵌入到手机里做为手机游戏，可以进行人机对抗，机-机对抗。可以推广到手机的桌面小游戏的行列中。
同类课题研究水平概述
- 在过去的半个世纪里,世界各地的学者花费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子棋、 围棋进行研究。这是因为计算机博弈是人工智能的一块试金石，然而棋类游戏又是计算机博弈的一个标准性问题，各种搜索算法、模式识别及智能方法在计算机博弈中都可以得到广泛的应用。在长时间的研究中,涌现出大量令人震惊的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就在全世界范围内引发了震动，其他很多棋类的计算机水平都已达到了世界冠军的水平。 目前，对于像五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对成熟，六子棋作为一个刚刚兴起不久的棋类游戏，其计算机博弈算法的研究还相对较少。即使目前已经出现六子棋的论坛以及比赛的平台，但只限于人人对弈。真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著(Threats)的胜利策略，但是对于其计算机博弈问题没有给出更加深刻的阐述，同时也没有全面解决六子棋计算机博弈问题。本文正是对六子棋计算机博弈技术的一个探索。
