目录
摘 要 I
Abstract II
1 绪论 1
1.1引言 1
1.2 本课题研究内容 1
1.2.1 项目开发背景 1
1.2.2 项目研究内容 2
1.3 本文主要章节内容 2
2 多线程与计算机博弈 4
2.1 多线程 4
2.1.1 多线程的概念 4
2.1.2 多线程的优点 4
2.2 计算机博弈的基本思想 4
2.3 六子棋多线程的发展 5
3 六子棋多线程博弈策略的分析与设计 6
3.1六子棋的基本规则 6
3.2系统各功能模块结构 6
3.2.1 平台功能结构（ConnectSixGame） 6
3.2.2 搜索引擎结构（Engine） 7
3.2.3通信功能结构（UCCI） 9
4 六子棋多线程博弈策略关键类设计 11
4.1六子棋棋局要素类 11
4.1.1棋局要素--点（Postion） 11
4.1.2棋局要素--路（Road） 11
4.1.3棋局要素--棋盘（Board） 12
4.1.4棋局要素--棋谱（Manual） 12
4.1.5棋局要素—下棋（MakeMove） 12
4.2 六子棋棋局要素分析类 13
4.2.1历史启发类（History Heuristic） 13
4.2.2置换表（TransPosition Table） 13
4.2.3 估值（Evaluation） 13
4.2.4棋形分析类(ChessTypeAnalyse) 13
5 六子棋多线程博弈策略关键算法 15
5.1 极小极大算法(Minimax Algorithm) 15
5.2 A-B算法 15
5.3极小窗口搜索(Minimal Window Search) 15
5.4负极大值算法(Negamax Algorithm) 16
6 六子棋多线程博弈策略的改进 17
6.1原搜索策略概述 17
6.2搜索策略的改进 19
6.2.1 多线程搜索简介 19
6.2.2多线程搜索策略的实施 20
6.3绝杀VCF策略的改进 20
6.4增加后台搜索策略 26
7 系统的测试 28
7.1 实施环境的配置 28
7.2 系统功能的测试 28
7.2.1测试工具介绍 28
7.2.2 VCF策略的测试 29
7.2.2 多线程策略的测试 30
7.3 小结 31
7.4 展望 31
致谢 33
参 考 文 献 34
附录 36
文 献 综 述 45
摘 要
计算机的发展越来越快速,一般的计算机性能也是越来越高，各种各样多核CPU计算机也是层出不穷。也正是因为这样，产生了多线程[1]这样一种编程思想。
六子棋是本篇文章的重点，从2003年的提出到现在已经将近12年了，随着这些年的发展，六子棋计算机程序战胜普通的六子棋选手已经不是梦了，越来越多的六子棋计算机程序展现出他们棋力强盛的一面。而本系统的六子棋也是最先进行研究队伍中的一个，近些年来获得了较好的口碑。也正是因为这样,更加不能停止不前，本着对研究工作负责的态度，也是为了六子棋更好的发展，本人在前辈们的基础上继续研究，争取为六子棋的发展做自己的一份贡献。
本篇文章主要从三个方面来描述本人所做的工作：
第一方面的工作是对原有的VCF[3]策略进行修改，加入多个绝杀着法，使得VCF策略效率提高，着法更加准确有力。通过测试可知，在对以前的引擎情况下能够有六成左右的胜率。
第二方面的工作是将原有的搜索引擎由单线程改为多线程，并添加了一个后台搜索策略，使得着法的平均时间由之前的一分钟左右减少到当前的十秒左右，提高了系统资源的使用效率。
第三方面的工作是为六子棋的测试添加了一个自动测试的工具，在该工具上本六子棋引擎可以进行相应的自动测试功能。还能对定式进行相应的测试，找到相应的着法。
关键字：多线程 绝杀 自动测试 六子棋
Abstract
The development of the computer is more and more quickly, the general computer performance is also more and more high, all kinds of multi-core CPU computer is also emerge in endlessly. It was also because of this, the multithreading a programming ideas.
Connect-Six is the key point of this article, from 2003 to now have nearly 12 years, with the development of these years, Connect-Six computer program over ordinary chess player six children already is not just a dream, a growing number of chess computer program six children show their QiLi strong side. And the sixth chess of this system is also the first one of the research team, in recent years has won a good reputation. It was also because of this, more can't stop, in line with the attitude of responsible for the work, but also to Connect-Six better development, I on the basis of the predecessors to continue study, six for the development of the child is to do an own contribution.
This article mainly from the three aspects to describe my work:
The first on the one hand, the work is to modify the original VCF strategy, participate in multiple dead method, resulted in more efficient VCF strategy, the method is more precise. Through test, before the engine to be able to have about sixty percent of the odds.
The second part of my job is to the original search engine from single thread to multithreading, and add a background search strategy, by the method of average time that before a minute or so to reduce to the current ten seconds, raise the efficiency of the use of system resources.
Third party is the work of six connect test adds an automatic testing tool, the sixth is the engine in the tool can perform the corresponding automatic testing function. Also can carry on the corresponding to the pattern of the test, find the corresponding method.
Key words: multi-threaded dead automatic test Connect-Six
1绪论
1.1引言
六子棋有时也叫做连六棋，现在公认的是台湾的吴毅成教授首先提出来的，在全国范围以致全球范围内都有很多研究六子棋的和下六子棋的。在国内主要是各个大学的创新实验室在进行研究，本系统的六子棋也是其中的一部分。任何棋种的竞赛都有时间的限制，六子棋也不例外。如何在有限的时间内进行有效的设置行棋着法是每个研究六子棋人所要达到的目标。为了达到这个目标，本人的学长们已经做了相当多的工作，而我是在他们的肩膀上进行研究的。本着实际出发，通过与队友与学长们的讨论,发现原有引擎在着法在选择上和时间的控制上有着部分的缺陷，所以本人决定从这两个方面分别入手，与队友一起努力，以期达到设定的目标。最终提出来了为VCF添加绝杀着法和将整体搜索策略修改为多线程的改进思路，以及为了充分利用时间，提出了后台思考的策略。希望本人的研究与开发工作能够为六子棋的发展做出一份贡献。
论文专业用语说明：为了更好的说明论文中的一些知识，通常将一些专业性很强的用语进行简化，这样更好的理解文章的内容，以下作一些说明：
①Alpha-Beta：本文为A-B
②双破：本文为VCF
1.2 本课题研究内容
1.2.1 项目开发背景
本校计算机博弈创新实验室的六子项目由来已久，多次参加国内的博弈比赛，均获得较好的成绩。本人有幸加入其中参加六子棋的研究工作，在其中担任项目负责人。2013年博弈比赛后，本人就从学长手上接过该项目，担任该项目组长。主要的工作就是在现有的基础上，发现现有系统的不足并进行改进。主要从六子棋的策略方面和比赛方面进行相应的研究和开发。结合自己本专业的要求，根据自己本身的情况，也是为了给实验室的创新活动增加一点动力，通过与指导老师的讨论，最终确立了当前的毕业设计题目。
综上可见，本课题是具有实际应用研究的意义。
1.2.2 项目研究内容
首先，本课题所研究的内容为多线程博弈策略体系的开发。所以说研究的内容有两个，一个是多线程，一个是博弈策略体系。其次，本着对系统整体的思考，添加了后台思考和自动测试两个部分。
本人于2013年参加六子棋的全国比赛，通过比赛总结以及同队友的讨论发现现有系统存在的不足，立足与学长的基础上，提出了以下几个方面的改进的建议，也是本文工作的研究内容：
①系统进攻力不足，考虑从双破策略及VCF策略入手，修改完善策略。
②系统在搜索时间上花费太多，考虑从整体架构上入手完善（最后确定为多线程的结构）。
③系统需要有自动化测试的工具。
④考虑到在对手思考的时间内本引擎是没有工作的，所以添加后台思考充分利用这段时间。
1.3 本文主要章节内容
本文主要分为7个章节，章节结构按照系统开发的结构顺序编排，也准确地描述了整个毕业设计的实际开发顺序。
绪论：主要对六子棋进行简单的介绍，介绍项目开发的背景和文章的内容。
多线程与计算机博弈：介绍了多线程以及计算机博弈的思想以及多线程在计算机博弈上面当前的进展。
六子棋多线程博弈策略的分析与设计：简单的介绍了六子棋的规则，详细介绍了整个系统的各个功能模块以及系统实现的情况。
六子棋多线程博弈策略关键类设计：详细介绍了在实现系统的时候所使用的关键的类。
六子棋多线程博弈策略关键算法的改进：简单的介绍了在系统中使用的较为关键的算法以及在六子棋中的改进。
六子棋多线程博弈策略的改进：详细描述了六子棋多线程博弈策略的改进，VCF搜索的策略的改进以及增加的后台搜索的部分。
系统的测试：测试当前的系统中实现的情况，包括VCF策略，自动测试，整体的测试，以及对整个系统做的总结，还有就是包括自己对六子棋未来发展的一个展望。
2 多线程与计算机博弈
2.1 多线程
2.1.1 多线程的概念
一个线程是一个执行流通过程的程序代码，类似于用它自己的程序计数器，寄存器和堆栈的系统。一个线程也被称为轻量级进程。线程提供了一种方法，通过并行处理提高应用程序的性能。每个线程都代表一个单独的控制流，单线程只有一个控制流,而多线程则有多个控制流,但是这多个控制流受控于主进程。
多线程中每个线程都是独立存在的，但是他们又受限于同一个主进程。从中可以看到，多线程是为了提高资源的使用效率来提高系统的效率的，而不是提高程序的运行效率来提高效率。可以这样打一个比方，把整个进程看成是一辆火车，线程就如同里面的一节节车厢，当需要运送很多东西的时候，可以用一节车厢慢慢的运，也可以使用多节车厢同时运送。总的来说多线程的出现就是为了提高效率。
2.1.2 多线程的优点
1、可以使用后台处理占据时间较长的程序中的任务
2、可以把数据处理和界面处理分开，使用户操作更加的便捷，用户体验度高
3、使用多线程很有可能使程序的运行速度加快
4、可以使一些等待的任务单独出来，而不去影响其他的任务执行。这种情况的话就可以释放一些珍贵的资源了。
5、在软件开发中多线程技术也是有相当重要的位置。
6、其他的还有很多的用处就不一一说明了
2.2 计算机博弈的基本思想
所谓博弈，其实是一个选择的过程，而计算机博弈呢，则是用计算机进行选择的过程。而在进行计算机博弈的时候，一般情况下是通过人为的方式来让计算机理解到底要怎么做。通常情况下，计算机博弈一般会使用树来进行表示，称这棵树叫做“博弈树”。通过建立博弈树来进行博弈是现代计算机博弈的基本思想。通常在“树”中，每个节点都表示一个局面，也就是棋局当前的情况。而计算机博弈的目的就是通过不断的在节点中寻找，直到找到叶子节点（最终局面）。而它该怎么找就是通过每个设计者的博弈思路来给计算机提示了。而这其中的思想则是最为精髓的了，可谓整个博弈的灵魂。
但是通过证明可以知道，要想将整个博弈局面通过博弈树的方式建立起来几乎是不可能的，至少在现在看来。所以在每次选择的时候就要通过人为的知识来进行相应的控制，进行相应的剪枝。但是人们也有这样的想法，将整个博弈树全部建立，这样的话，整个博弈都将是在可知的范围内进行了，老实说，这样就没有了博弈的乐趣了，但是这也是我们所追求的目标。关于剪枝的算法，在第五章中进行比较清楚的描述。这里了解一下六子棋在多线程方面的发展情况。
2.3 六子棋多线程的发展
本人于2013年和2014年连续两年参加全国大学生计算机博弈大赛，通过与其他学校的参赛队伍的交流，在参加的比赛的全国队伍中，没有发现有队伍使用多线程技术的，而且在中国知网等多家权威机构上也没有搜索到将六子棋和多线程结合起来的有关文章。从这个方面看来，至少可以说明本课题是具有一定新颖性的。
3 六子棋多线程博弈策略的分析与设计
3.1六子棋的基本规则
六子棋的详细规则在文献[8]中可以看到，这里简单的介绍下如何进行下棋，达到能够行棋的地步。
玩家：类似于围棋等，有黑方和白方
玩法：由黑方先下一子，之后双方轮流各下两子，在各个方向连成六子（或以上）者获胜。
和局：假如棋盘全部填满并且没有胜负，规定为和局。
3.2系统各功能模块结构
整个系统一共有三个部分。首先是界面部分，比较直观的显示出当前的博弈情况，便于操作；另外一个是搜索引擎，用于搜索设置当前局面应该走的着法；还有一个就是通信部分，用于连接平台和搜索引擎。这三个部分结合起来组成了整个博弈系统。
图3-1 系统结构图
3.2.1 平台功能结构（ConnectSixGame）
六子棋多线程博弈系统中的平台是用于方便对弈时候用的，在平台上的主要功能是为了控制整个系统进行正常的运转如图3-2所示，可以看到在基本功能中有开始、暂停、重新开始、后退和前进五个功能；在棋谱部分有保存棋谱和打开棋谱两个功能；角色部分有黑白双方的设置功能，可以加载引擎进行人与电脑对战，也可以进行电脑与电脑对战，即让两个电脑引擎进行对弈。
图3-2平台界面图
3.2.2 搜索引擎结构（Engine）
任何的博弈系统的搜索引擎都是整个博弈系统的大脑，六子棋也不例外，没有了大脑，整个系统就没有办法思考，在界面上所显示的每一步都是从搜索引擎里里面搜索出来的，所以说搜索引擎是最为重要的一部分。当前的搜索引擎主要是由以下几部分组成的：开局库，后台搜索策略、双破策略、单破策略、五位迭代策略、正常迭代策略、防守策略和正常搜索策略一共八个策略组成，而他们之间的关系如图3-3和图3-4所示：
