基于一种新算法的人工智能五子棋

更新时间：2024-04-13 15:11:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

人工智能是一种算法推荐度：
相关推荐

本科毕业设计(论文)

GRADUATION DESIGN (THESIS)

题目基于一种新算法的人工智能五子棋

学生姓名万文韬

指导教师余腊生

学院信息科学与工程学院

专业班级物联网工程1103班

本科生院制

2015年6月

基于一种新算法的人工智能五子棋

摘要

五子棋是一种简单的黑白棋，历史悠久，起源于中国，后传入日本，在日本被称为“连珠”，五子棋在日本获得了长足的发展，规则进一步得到完善，而后，传遍世界，在欧美国家也有很多爱好者，他们称五子棋为“Gobang”或者FIR（five in a row）。

人工智能五子棋属于人工智能中人机博弈的一种，人工智能应用广泛，比如自然语言处理能帮忙建造自动翻译机器，生物模式识别能帮助实现更先进的加密方法，应用于各种需要加密的场所，语音识别技术能帮忙实现快速将语音输入准确转换为文字输入，总之，人工智能是促进未来人类科技和生活重大改变的一门学科。

本篇论文主要是有关智能五子棋的算法及其实现。在介绍完相关背景后，主要详细介绍了智能五子棋的四种算法：神经网络强化学习算法，博弈树算法，极大极小值搜索算法和α-β剪枝算法，真正的系统实现采用的是剪枝算法，并且在此基础上提出了自己的优化策略，实现了创新。

关键词：人工智能五子棋算法博弈

基于一种新算法的人工智能五子棋

An artificial intelligence gobang system based on a new

arithmetic

Abstract

Gobang is a simple kind of reversi ,it has a long history , it derives its origin from China, then it was introduced to Japan, in Japan, they call it “LianZhu”. The Gobang has got much development in Japan, its rule became complicated and then it was introduced all around the world,it also has many fans in Europe and America, who call it “Gobang” or “FIR”(five in a row).

The artificial intelligence gobang is one kind of Man-Machine game which is also the one domain of artificial intelligence. Artificial intelligence has widespread applications, for example: natural language processing can help building the automatic translator, biological pattern recognition can help realizing more advanced cryptosystem, and speech recognition technology can help realizing change phonetic input to accurate wordy input quickly. In short, artificial intelligence is one science which may make great difference in human’s life and the progress of technology.

This paper is to discuss the arithmetic and realization of artificial intelligence Gobang. After introducing the relevant background, it describes four different arithmetic of artificial

基于一种新算法的人工智能五子棋

intelligence gobang in detail: neural network reinforcement learning algorithm, game tree algorithm, minimax value search algorithm and alpha-beta pruning algorithm. The pruning algorithm has been chosen to realize the real system, and I added my own optimizing strategy on it realizing the innovation.

Keyword: Artificial intelligence

Gobang Algorithm Game

基于一种新算法的人工智能五子棋

第1章绪论 .............................................................................................................................. 1

1.1 智能五子棋研究背景与意义 .................................................................................. 1

1.2.1 五子棋的发展现状 ...................................................................................... 2 1.2.2 人工智能的研究现状 .................................................................................. 3 1.2.3 人机对弈的研究现状 .................................................................................. 4 1.2.4 领域内学术会议与期刊 .............................................................................. 5 1.3 本课题研究内容 ...................................................................................................... 6 1.4 本论文组织结构 ...................................................................................................... 7 第2章需求分析和系统设计 ................................................................................................ 9

2.1 需求概述 .................................................................................................................. 9

2.1.1 任务 .............................................................................................................. 9 2.1.2 目标用户及特点 ........................................................................................ 10 2.2 需求规范 ................................................................................................................ 10

2.2.1 对功能的要求 ............................................................................................ 10 2.2.2 对性能的要求 ............................................................................................ 10 2.2.3对代码质量的要求 ....................................................................................... 11 2.3 运行环境 ................................................................................................................ 13 2.4 结构设计 ................................................................................................................ 13

2.4.1 系统结构设计 ............................................................................................ 13 2.4.2数据结构设计 ............................................................................................... 14

第3章神经网络强化学习算法 .......................................................................................... 15

3.1 算法概述 ................................................................................................................ 15 3.2 算法具体过程 ........................................................................................................ 16 3.3 实现和性能 ............................................................................................................ 21 3.4 本章小结 ................................................................................................................ 22 第4章博弈树算法及其优化 .............................................................................................. 23

4.1 算法概述 ................................................................................................................ 23

基于一种新算法的人工智能五子棋

4.2 博弈树算法具体过程 ............................................................................................ 24 4.3 优化 ........................................................................................................................ 28

4.3.1 极大极小值搜索算法 ................................................................................ 28 4.3.2 α-β剪枝算法 .......................................................................................... 30 4.4 本章小结 ................................................................................................................ 32 第5章系统构建过程细节论述 .......................................................................................... 33

5.1 游戏界面 ................................................................................................................ 33 5.2 游戏步骤 ................................................................................................................ 33 5.3 判断棋型 ................................................................................................................ 34 5.4 落子估值方式 ........................................................................................................ 38 5.5 棋局估值函数 ........................................................................................................ 41 5.6 α-β剪枝算法的伪代码: .................................................................................... 42 5.7 其它优化思考 ........................................................................................................ 42 第6章结论 .......................................................................................................................... 43

6.1 总结 ........................................................................................................................ 43 6.2 展望 ........................................................................................................................ 44 结束语 ...................................................................................................................................... 45 参考文献 .................................................................................................................................. 47

基于一种新算法的人工智能五子棋

第1章绪论

人工智能五子棋具有人机对弈的特征，属于人工智能的范畴，可以运用各种人工智能领域的方法来处理该问题，同时由于五子棋游戏规则简单，通俗易懂，流行度高，所以人工智能五子棋研究的门槛不高，软件系统规模不大，对硬件的要求不高，单台PC机可以完成一般的测试，然其又不失重要性和典型性，以上种种都使之成为研究人工智能的很好入门选择。

本章先介绍研究人工智能五子棋的背景和意义，之后较为详细的介绍目前该领域的研究现状，然后介绍该领域及相关领域的学术会议和期刊，之后介绍本课题的研究重点，最后简单介绍整篇论文的组织架构。

1.1 智能五子棋研究背景与意义

五子棋是一款简单益智的竞技棋类游戏，本课题研究用计算机实现五子棋博弈功能。人机博弈一直以来是人工智能的主要研究方向之一。人工智能是研究，开发用于模拟、延伸和拓展人的智能的理论、方法、技术及应用系统的一门科学和技术。旨在用人工实现智能。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

53 页第 1 页共

基于一种新算法的人工智能五子棋

当前人工智能分为“强人工智能”和“弱人工智能”，“强人工智能”希望探讨智能的本质，实现真正的类人智能，其研究目前处于瓶颈状态，“弱人工智能”则采用工程学方法，已解决具体问题为目的的，实现表面的貌似智能[1]。目前这一研究方向有众多成果，像“自然语言处理”“机器证明”“专家系统”“人机博弈”等领域目前都用的是“弱人工智能”的方法，比如“神经网络算法”“遗传算法”“蚁群算法”“博弈树搜索”等等。

人机博弈是人工智能的重要分支之一，研究的是人与机器的博弈，同常的人机下棋便属于此，其已有一段历史。1997年，当时世界排名第一的国际象棋棋手加里·卡斯帕罗夫以2.5：3.5（1胜2负3平）负于IBM超级计算机“深蓝”更是将人机博弈推向新的高潮。

本课题便是在此背景下提出的，旨在初步学习人机博弈理论，构建一个五子棋人机博弈系统。随着改革开放的发展，中国人民的物质生活水平大大提高，开始越来越追求精神层面的享受。五子棋作为一种怡情益智类游戏，有陶冶情操，开发智力的作用，人工智能五子棋作为人机博弈的一种，研究它，无疑具有相关的科学意义，对自己而言，也具有学习意义。

1.2 研究现状

[2]

1.2.1 五子棋的发展现状

五子棋起源于中国，原始规则很简单两方棋手分别执黑白两色棋子交替落子于类似围棋的棋盘，只要有一方先走成在横、竖、斜方向上的五颗同色棋子就赢得比赛。一般

53 页第 2 页共

基于一种新算法的人工智能五子棋

是黑方现行，但是这样使得黑方总可以找到必胜下法，所以，后来五子棋规则有了很多发展变化，其目的都是为了抵消黑方的先行优势，比如：在开局后的第三手，白方拥有“三手交换”权利，即：如果白方觉得下完三手棋后黑方棋型很厉害，可以要求自己与对手黑白互换；“五手两打”即在第五手黑方应接连下两子，然后由白方决定在这两子中留下哪一子，“禁手规则”这是针对黑方的，白方无禁手，黑方有“三、三”“四、四”“长连”禁手，禁手判负，黑方只能以“四、三”取胜。

除了规则的发展外，五子棋的下法也不断的成熟，已经发展出各种成熟下法：在棋型中存在着：活四、冲四、活三、跳活三，二又存在好几种连活二，跳活二，大跳活二，其次还有眠二和死二。三也能分好几种：有两种类型的活三，针对它们有各自不同的防守点，另外还有眠三和死三。此外有各种开局，局中走法和做杀技巧。总之，五子棋游戏无论是规则还是走法策略现阶段都已发展的相当成熟。

1.2.2 人工智能的研究现状

人工智能被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一，当前主要的研究成果主要还是集中于“弱人工智能”领域。近年来出现了一些可喜的成果：

搜索引擎得到了新的发展和完善：首先是算法的不断改进，这方面的工作首推美国的谷歌公司。其次是搜索的对象得到了扩展，不再局限于传统的文本搜索，新增了图像搜索，语音搜索甚至情感搜索，可以实现“以图搜图”“用语音搜索”，以及“心理搜索”。再次是搜索领域得到拓宽，人工智能技术使得搜索引擎的搜索领域不再局限于互

53 页第 3 页共

基于一种新算法的人工智能五子棋

联网范围而是扩展到整个物联网范围和云平台，可以对各种实现了智能感知的物品实现在线状态搜索。

当前学术界认为有三种发展人工智能的路线：一、以专家系统为代表的以功能模拟为目的的符号主义路线；二、以机器连接和人脑仿生为代表的连接主义；三、从进化角度出发的行为主义。但是，最热的研究领域是基于人工神经网络的深度学习技术，各大互联网公司都在积极发展这一技术，并开发基于机器学习的各种应用，以挖掘其应用价值。譬如，谷歌的技术人员之前已经依靠这一技术能是机器学会了自动识别视频中的猫脸。机器深度学习技术之所以能够发展的这么快，和计算机领域的近年发展方向有关，随着，CPU和存储器的工业制造成本不断下降，计算和存储的成本也随之下降，在加上移动互联网和物联网时代的到来，人类社会已经悄然步入了被业界称之为“大数据时代”的一个新的时代，在数据体量大幅增加，数据产生和交流的速度更快，渠道更通畅，机器学习的可操作对象、空间都得到了极大扩展，极大便利了机器学习的发展，甚至我们不得不考虑，也许发展到后来，基于超大数据的大型计算也许是实现人工智能的一个途径。

1.2.3 人机对弈的研究现状

人机对弈分属于人工智能，广义的人机对弈指的是，人和机器就某一在通常看来需要人类智力才能解决的问题的博弈，这种博弈往往具有竞赛性质，最后要么是人，要么是机器取得胜利。狭义上人机对弈的研究主要集中于一些可以明显人人对弈的传统对弈游戏，只不过是机器来充当人类的对手。比如最常见的就是各种人机对弈的棋类游戏。

53 页第 4 页共

基于一种新算法的人工智能五子棋

就人机对弈研究现状而言，目前在五子棋，中国象棋，国际象棋等领域计算机都已经超过人类棋手的棋力水平，但是在围棋领域计算机却和人类差距甚远。

2011年在北京农业大学的人机大战上，俞斌与国内顶尖级围棋程序“本手”在九路棋盘上以让两子的方式与之交战，两盘都以半子告负，事后，他说“本手”达到了业余二段的水平。但是如果在十九路棋盘上，计算机的棋力可以说是根本不足以和人对抗的。主要是因为围棋的状态空间复杂度是10的170次方，远远高于象棋的复杂度（大约是10的48次方）。计算机处理下棋问题，还是按预定程序，考虑所有的可能，然后选最优解，复杂度一大起来，计算机所能考虑的情况所占比例就明显下降，与之对应，计算机的棋力也明显下降，而人类棋手的处理却不同，他虽然不可能像计算机那样严密的计算，考虑那么远，但是人能很好的处理图形，识别模式，可以避开一些显然的危险和显然的不用浪费时间的走步，同时，长期训练得到的经验，灵感，全局观，以一种目前难以量化和说清楚的方式帮助着人类棋手。人类似乎在以一种更智能的方式考虑着问题。

简言之，目前人机对弈的研究还是以各种算法为主，然后，采取针对性的优化措施。但当棋的空间状态复杂度上升后，计算机就显得力不从心。

1.2.4 领域内学术会议与期刊

本领域重要的学术会议有：International Joint Conference on Artificial Intelligence(IJCAI), AAAI Conference on Artificial Intelligence(AAAI), IEEE Conference on Computer Vision and Pattern Recognition(CVPR), International Conference on Machine Learning(ICML), International Conference on Computer

53 页第 5 页共

基于一种新算法的人工智能五子棋

Vision(ICCV), 人工智能和工业应用国际学术会议（AIIA），中国计算机学会人工智能会议（CCFAI），中国人工智能学会（CAAI），人工智能与软件工程国际学术会议（AISE）等。

本领域重要的期刊有：Artificial Intelligence(AI),IEEE Trans on Pattern Analysis and Machine Intelligence(TPAMI), Machine Learning, Neural computation, Computational Linguistics, Journal of AI Research(JAIR), Ieee Trans on Evolutionary Computation(TEC), Intelligent Data Analysis(IDA), Applied Intelligence, Natural Language Engineering(NLE), Journal of Machine Learning Research(JMLR), International Journal of Computer Vision(IJCV),Computational Intelligence, Cognitive Science, IEEE Trans on Neural Networks(TNN), Evolutionary Computation, IEEE Transaction on Speech and Audio Processing, Pattern Recognition, Computer Vision and Image Understanding(CVIU)。

1.3 本课题研究内容

本课题以人工智能为研究领域，具体研究的是其中的人机对弈领域的人工智能五子棋，主要研究构造人工智能五子棋的算法及算法优化问题。利用基于剪枝优化策略的博弈树算法实现了一个人工智能五子棋系统，并进行了其它方面的优化。同时考察研究了人工智能的发展历程，深入学习了解了其它用于人机对弈的各种算法。

53 页第 6 页共

基于一种新算法的人工智能五子棋

1.4 本论文组织结构

依据研究目的和步骤、内容，本论文按如下结构来组织：

第1章：本章为绪论，介绍了人工智能五子棋的研究背景和意义，从大到小，从宽到窄地介绍了人工智能、人机博弈领域的研究现状，之后列出了本领域的顶级学术会议和学术期刊，最后介绍本课题的研究内容和本文的组织结构。

第2章：本章介绍了人工智能五子棋系统的需求分析和系统设计。在需求分析部分详细介绍了任务，目标用户及其特点，在需求规范部分介绍了对功能、性能和代码质量的要求。之后介绍了该智能五子棋系统的运行环境，最后介绍了结构设计，分别介绍了系统的结构模块和数据结构的设计。

第3章：本章深入介绍了神经网络学习算法，阐述了算法的思想来源，具体步骤，以智能五子棋为例介绍了本算法的具体实现，随后介绍了本算法的性能。

第4章：本章深入介绍了另一种也是应用的最为广泛的人机博弈算法——博弈树算法，阐述了算法的原理，思想来源，具体步骤，和应用实例，以及该算法所存在的缺陷。之后深入介绍了基于博弈树算法的优化算法——极大极小值搜索算法和α-β剪枝算法，阐述了算法的数学原理，具体步骤和改进的空间。

第5章：本章详细介绍了本课题的智能五子棋系统的具体构建过程，描述了在构建过程中遇到的一系列问题及具体的解决方案，给出了相关的实验截图和数据，验证了前面所提的算法理论，并且提出了进一步的优化思考。

53 页第 7 页共

基于一种新算法的人工智能五子棋

第6章：结论和展望，总结了整篇论文和整个毕业设计的工作，提出了未来的研究展望。

53 页第 8 页共

基于一种新算法的人工智能五子棋第2章需求分析和系统设计

2.1 需求概述

2.1.1 任务

本课题要通过实现一个人工智能五子棋系统已研究相关的算法，具体的系统实现包括以下任务：

（1）完整的游戏界面：

要实现完整的游戏界面，包括能在上面下棋的棋盘，用于下棋的棋子，用于悔棋，重开新局，选择难度等级，基本设置，返回上一级等功能按钮，棋盘上要随着游戏双方下棋的步骤显示相应棋子。（2）下棋功能：

也即计算机和人都能实现顺利的下棋功能，包括计算机下棋AI功能，这个待会着重讨论，控制程序轮流切换下棋权开关，双方只要是合法走步，都能顺利下棋，只要是非法走步，都不能顺利下棋，且有相应对话框提示。下棋过程1）中提到的功能按钮都能被按下并实现相应功能。（3）战绩显示：

要能够查询到不同玩家以及电脑的战绩——分别胜负和的局数。

53 页第 9 页共

基于一种新算法的人工智能五子棋第3章神经网络强化学习算法

3.1 算法概述

神经网络的强化学习算法是基于一位能够指示此网络是否在一个好的状态而不是直接教它怎样到达一个好的状态的外部教师的有效性的。通常，成功或者失败这样的定量强化信号被提供用来评估网络的行为，但网络得自己综合使用试探，错误和延迟的奖励信号来探测环境以获得可能要进行行为改变的定向信息。[5]

强化学习的一块有趣而富有挑战性的领域是电脑棋类游戏[6]，在此强化信号（“赢”或者“输”）也许得等到一系列的动作发生后才能获得。此时，网络必须以某种方式分配信任或者个体地归责于导致最终结果的一系列动作的每一步，等等。它必须提供一种解决暂时信任分配问题的方案[4]。

若干提供关于游戏参与的强化学习技术已见诸文献。例如，“暂时差异化”学习方法[11]被用于Samuel利用西洋棋进行的早起机器学习研究中[9]以及在Schraudolph等人发明的围棋人工智能算法中[10],在Yee等人提出的一字棋人工智能算法中以及Tesauro的西洋双陆棋网络中[15,16]。其中Tesauro的西洋双陆棋网络比他之前的基于反向传播算法的神经理论系统[12,14]表现的更好并且在能运行于精确的水平之上，这接近当今世上最好的人类棋手。

53 页第 15 页共

基于一种新算法的人工智能五子棋

本文中，基于强化学习的神经网络被提出用来玩五子棋。五子棋游戏，也叫GO-MOKU，是由两个人在十九剩以十九的方格上进行，使用黑色或白色形状相同的棋子。

棋手轮流每次在棋盘上下一粒棋子。有一方率先在水平，垂直或者斜线方向连成己方颜色的五粒棋子便获胜。

游戏规则简单且策略上比之前提及的围棋简单的多。虽然有人讨论过先下子的一方（黑子方）可以百分百赢得比赛，只要他或她每一步都下得恰到好处，但所有试图通过程序来展现这一技能的尝试都以失败告终。先前的机器下五子棋方法乃是基于传统的人工智能方法，比如通过游戏树搜索算法或者特征情况存储/分析方法来评估落棋位置的重要性[1,3，18]，但是目前这个问题还没有被采取神经网络算法处理过。

本文提出的方法基于发展一套丰富的网络体系结构来评估每一处尚未落子的棋盘位置以判决下一步的动作。此（神经）网络是这样学习发展评估函数的：通过玩一系列以软件或者人类为对手的游戏并使用（获得的）结果来相应地修改连接权重以达到提升性能的目的。我们将会看到，训练过的网络能在与商业五子棋程序或者经过训练的人类棋手的对抗中取得好成绩。

3.2 算法具体过程

（1）网络体系结构

将神经网络用于五子棋游戏是受如下事实启发：当人类棋手潜意识地试图识别棋盘上的棋子形成的特定模式时，他或她是为了记住一系列通往顺利赢得比赛（至少是不输）的步骤。

53 页第 16 页共

基于一种新算法的人工智能五子棋

我们方法的基本思想是设计一种神经体系结构，它能够允许从两种不同视角评估棋盘上每一空地，从神经网络的自己的视角和从对手的视角。这种双方型视角通过两种同结构化子网络的树形编排实现，每一子网络带一输出单元其启动值决定放置棋子于当前评估位置的重要性，如图1所示。子网络的两个输出单元（层次L4）与整个网络的输出单元（位于层次L5的该树的根节点）。层次L5和L4之间的连接被固定了，但是指定进攻或是防守趋势的

可能的不同权重会发挥作用。这些权重的恰当设置可以避免那些经常出现的显著影响，那就是在有利局势下大多数人类棋手会急于进攻而忽略防守。网络输出单元附加结合L4中的赋权启动单元来决定当前研究棋盘位置的最终输出结果。

在所有的空闲位置被以这种方式评估后，具有最高网络输出值的棋盘位置被选为下一步落子位置。如果同时有好几个最高值，尤其是在游戏的早期阶段遇到这种情况，那

53 页第 17 页共

基于一种新算法的人工智能五子棋

就从中随机选取一个。

因为树中的两个子网络是按同一模式操作的，所以仅描述其中之一的功能便足够了。为了评估给定的棋盘空闲位置（x,y），其周围的56个棋盘空闲位置，如图2所示，会被考虑。

这56个棋盘位置包含所有水平，垂直以及对角线方向上与（x,y）距离在4个棋子以内的位置，也即可能导致赢得游戏的位置。因为（x,y）周围的这样一个星型环境并不能包括所有可能的获胜情况，所以（x,y）周围的其它位置也需要被考虑。在（x,y）周围的窗型环境中的所有棋盘位置都会被恰当的编码，产生一个矢量，其每一组件代表一个特殊的位置，同时具有不同的值已表明该位置是否为空（0.25），是否在棋盘边界外（0.0）如果（x,y）靠近边界的话，是否已被己方颜色棋子占用（1.0）或被对方颜色棋子占用（0.0）。对于棋盘上每一个未落子位置（x,y）都有一个这样的向量被提交给子网络的输入单元。

这些输入单元和层次L2中的单元之间有不同数目的连接；他们因此被称为II-单元

53 页第 18 页共

[8]

基于一种新算法的人工智能五子棋

，也就是说，它们的输出以相连输入的加权积的形式被计算。这40个单元的每一个都

和输入单元的子集有4或者5个连接以反映所有可能的沿横，竖或对角方向同一颜色五子链的组合，取决于（x,y）是该链条的一部分（4个连接）或者不是（5个连接）。L2中的单元也非对称地连接到层次L3中的24个II-单元来代表其他重要的模式，这些模式是以各种五子链条形成的。图3展示了一个被评估棋盘位置的环境中因为匀称被提交8次的三种模式。

这些模式至关重要，因为落子于（x,y）处可能不会立即赢但也许会为稍后的胜利埋下伏笔。II-单元两层的连通有值为1.0的固定连通优势，因为网络必须被迫识别相关联模式的重要性。既然我们的编码方案中棋盘位置以0到1之间的值代表，II-单元具有的连接数量越多（在L3中连接会上升到14个）得到的启动越弱。为了抵消此影响，启动会通过取决于连接数量的归一化因子来增加。

子网络的最终层是带有上文描述过的单一输出单元的输出层。它和前置层L3中的所有单元有可训练的连接，并且和L2层中II-单元的一部分有固定连接（1.0），这代表了（x,y）的星型环境中的五子链条（包括（x,y）位置在内）。如果网络要选（x,y）位置作为下一处落子位置来赢得（或者不输）比赛，那么这些固定的连接优势是必须的。

53 页第 19 页共

基于一种新算法的人工智能五子棋

某种意义上而言，这些有固定连接优势的连接也许可以被看做提供给网络的关于此游戏的一些基本知识，类似于解释给人类新手的比赛规则。固定的连接权重实现了如下功能：只有那些允许形成己方颜色五子连珠的那些棋链会被认为是重要的，然后对方的一个棋子将会通过它的0.0编码产生一个相应II-单元中值为0.0的启动。（2）学习如何比赛

学习是为了优化网络对棋盘位置的评估。具体按如下步骤进行。第一步，L3和L4之间的连接权重被初始化为随机值，然后网络和传统的、讲规则的五子棋程序或者人类选手进行多盘比赛。第二步，所有这些比赛中的步骤被记录下来并被用作训练阶段的输入向量。然后所有的比赛由网络再次单独玩一遍。由于不可能知道那些步骤对最终的输赢有影响，所以被网络丢失的对手的所有步骤也要考虑，结合当前那些权重，一个针对当前情况的评估便产生了。如果由网络决定的步骤不同于由对手决定的步骤，网络的步骤被惩罚并且对手的步骤被奖励。这样一个奖-惩机制以一个特定的加强学习算法——比较训练的变种实现，来修改L3和L4之间的连接权重。为了能这么做，网络输出间的不同和对手的步骤都会被计算。这些不同的绝对值会根据针对II-单元的偏差反向传播程序（[8]中有描述）分发给L3中的单元以便计算L3中单元i产生的相应偏差?i。针对对方的步骤，偏差?i赋正号，因为估值一定是增加的，对于网络提出的步骤?i赋负号。最终，L3和L4之间的连接权重wi按下式修正：

其中?>0是学习参数，y（t）是L4中单元的输出。

53 页第 20 页共

基于一种新算法的人工智能五子棋

用这种方法，网络学习获胜的对手的更好的下棋步骤，因此能提高自身表现。此外，不仅不同的步骤，而且网络和对手相同的步骤会以一个小的带正号偏差的形式被学习以奖励网络做出了一个已经正确的步骤。这种奖励也被应用到网络获胜的比赛的所有步骤中。

3.3 实现和性能

所述网络已经在C在不同的机器上实现（APOLLO DN 4000, SUN Sparcstation SLC, IBM RS 6000）。此外，一个玩五子棋游戏的简单的用户图形界面也已经成熟。

网络的性能已经在一系列的比赛中被测试过。他们都由两个阶段组成。第一阶段，随机初始化的网络和五子棋程序或者人类进行50场对抗赛，并且输赢的数目被记录下来。第二阶段，进行总共400场对抗赛，每一场比赛后根据之前章节描述的程序进行相应步骤的学习。在接下来的一系列比赛中这两个阶段被一直重复。在IBM RS 6000机上运行完一个系列比赛的这两部需要6.5小时（步骤1要30分钟，步骤2要6个小时）。第一个对手是一个简单的五子棋程序，它仅仅通过考虑4子的星型环境来评估棋盘空闲位置。网络开始分数是50场中赢21场，但在两轮比赛后增加到赢29场。当一个更适当（依然是随机）的初始化网络一开始就表现的比对手好时，这种针对对手棋力的适应性能被观察到。例如，网络在经过两轮训练后会减弱棋力从最初赢30场到后来赢25场。这并不奇怪，因为用到的学习模式取决于对手的棋力。在神经网络输掉的比赛中，对手的落子步骤被认为比网络的步骤要好，这样，网络的棋力会一直提高到和其相匹配。在

53 页第 21 页共

[7]

基于一种新算法的人工智能五子棋

用来训练的对手的棋力较次的情形中，网络的性能因此也会下降。这就是为什么在后续测试中当神经网络和自己的副本对抗时，棋力不会有大的提升，虽然网络最终实现在这一系列比赛中赢31场，而不是像在最初用简单的五子棋程序训练时赢29场。然而，没有理由据此认为网络从自身学到了什么，这种差异也许仅仅是由随机的位置选择具有等量的高估值。在最终的测试中，训练最好的神经网络接受了与商业五子棋软件的对决：10场比赛胜9场；也和高级人类选手进行了对决，以7：3胜出。

3.4 本章小结

本章提出了一种可以学习玩五子棋游戏的神经网络。一种适当的网络体系结构被发展用来评估棋盘上每一空闲位置以决定下一步。通过加强学习算法——比较训练的一种变体，来学习和提高估值函数，并应用在一系列与五子棋程序对抗的游戏中。在这种学习方法中，网络的棋力取决于对手。已被展示，经训练的网络能在和商业五子棋软件以及专业人类棋手中取得好成绩。

不过此算法也可有改进之处：首先，具有相等的高估值的随机选择程序要经过分析，对网络表现的观察揭示了某些情况下，网络表现的更好。第二，应该研究空闲棋盘的位置和编码方式，这也许会扩展重要模式的数目。第三，在训练阶段，对对手棋力的固有依赖应该减少，但这将要求发展一套完全不同的学习方案。[2]最后，暂时信任分配问题的解决方案，也就是使所有游戏步骤对最终赢输同等负责必然可以改良。当然，这将要求详细分析大量的比赛情形，并且重要和有大影响的步骤也许难以鉴别。

53 页第 22 页共

基于一种新算法的人工智能五子棋

第4章博弈树算法及其优化

4.1 算法概述

博弈树是一种处理人机对弈问题的算法，在这里，我们首先申明博弈的概念。博弈本意是指下棋，后来引申为：在一定规则下，一个或多个绝对理性团队从各自能选择的策略中选择策略并实施以经行对抗，最后承担从每一步所实施的策略中获得的损益及最终损益。在本课题中我们虽然用的是博弈的本意，但是，博弈树算法却可以应用于政治，经济，生活中的各种博弈过程，博弈的三大特点是：对抗、多步和相应损益。

博弈树算法基于以下的思想：当前状态下所选择的博弈策略是好是坏，能带来多少损益，在当前状态下并不是显而易见的，但随着博弈另一方做出反应，己方在反应，多步之后才会变得清晰，而当前的这一步就像是一个状态开关，决定了接下来所有可能的状态集，每一步的策略都具有这样的特征，从而使得不确定性逐渐坍缩为确定性的损益（回环情况除外，其实这也是一种状态坍缩）。这相当类似于人类在博弈（比如下棋）时的思维过程：这一步有哪几种下法，每一步下面又可以有哪几种可能，这样考虑多步之后，上面的这些步骤为最终损益所带来的贡献才会被明朗意识到。形式化的表示出来正好符合数据结构里树的形象，故而得名博弈树。

53 页第 23 页共

基于一种新算法的人工智能五子棋

博弈树算法的大致运作过程如下：树根节点为当前状态或初始状态，每一博弈方按博弈中的顺序规则占据接下来的相应每一层，例如，如果规定根节点是第一层，且假设只有两方博弈，则第2n（n为正整数）层为博弈一方（这里简称A方），第2层的所有节点都是根节点的孩子，每一个节点代表A当前情况下采用一种合法博弈策略后所形成的状态空间，第2层将穷尽所有这样的节点。第2n+1（n为正整数）层为博弈另一方（这里简称B方），第3层的所有节点都是第二层相应节点的孩子，例如：第2层的第一个节点下面的孩子就是这样的节点：设第2层第一个节点表示的状态为状态a，则其所有孩子节点就是B在状态a下采用所有合法博弈策略后产生的状态构成的节点。这样一直交替下去，直到达到博弈的结局。

4.2 博弈树算法具体过程

下面以一个典型而又简单的例子——“捡石子游戏”来介绍博弈树算法的具体过程。游戏规则如下：在黑箱子里方N（N为正整数且已知）颗石子儿，A、B两方参与博弈，轮流从黑箱中取出石子儿，每次可取1,2,3颗，取出最后一颗石子的一方则输了这场博弈。“捡石子游戏”只能有一种结局，那就是黑箱子里的石子儿被全部取光。所以这场博弈在有限步后一定有一方胜，有一方负。下面图5.2是关于这个游戏N=6时的一颗

完

全

博

弈

树

。

53 页第 24 页共

基于一种新算法的人工智能五子棋

2 博弈者A捡石子博弈者B捡石子 1 A A B B 图5.2 N=6的“捡石子游戏”的完全博弈树 A B B A A A A A A B B B 3 1 2 1 2 3 1 2 3 3 A B B B B A A B

53 页第 25 页共

基于一种新算法的人工智能五子棋

下面具体分析有了这颗博弈树后如何取得最后的胜利，我们假设会导致A获胜的状态节点值为WIN，会导致B获胜的状态节点值为LOST，会导致平局的状态节点值为DRAW。我们先遵守一定的规则为树中的每个节点赋值，然后考虑具体选择哪个节点作为博弈策略，当A选择时，他肯定会选择值为WIN或DRAW的节点，当B选择时，他肯定会选择值为LOST或DRAW的节点。这样我们得到一种给节点赋值的策略——倒推法：

每一个叶子节点对应的是博弈的终局，而且我们可以明显得出此节点的值是WIN还是LOST（本博弈无DRAW终局状态），接下来为叶子节点的父亲节点赋值，如果倒数第二层对应的是轮到A走步，只要其孩子节点中有一个或一个以上WIN节点，则A会选WIN节点进而导致WIN状态的出现，所以该父亲节点应被赋值于WIN，当其孩子节点中没有WIN节点，有一个以上（包括一个）DRAW节点，则A会考虑DRAW节点，此时该父亲节点的值应被赋为DRAW。同理，如果父亲节点的所有子节点都是LOST节点，则该父亲节点的值只能是LOST。反之，如果倒数第二层轮到B走步，只要其孩子节点中有一个或一个以上的节点值为LOST，则B必然会选择该节点，从而导致最终的局面值为LOST，所以该父节点的值应该被赋值为LOST；如果其孩子节点中没有值为LOST的节点，但是有一个或一个以上值为DRAW的节点，则B必然会选择值为DRAW的节点，从而导致最后的局面值为DRAW，所以该父亲节点的值应该被赋值为DRAW；如果其孩子节点中所有节点的值全都为WIN，则节点B不管选哪个合法策略都会导致最后的局面值为WIN（对应于A胜B输），所以该父亲节点的值应该被赋值为WIN。这样根据叶子节点的值可以将倒数第二层的节点全部赋值，进而可以一层层倒推，将整棵博弈树的节点全部进行赋值。之所以能够用倒推法为博弈

53 页第 26 页共

基于一种新算法的人工智能五子棋

树进行赋值，是基于博弈定义中的一个条件：博弈各方具有理性也就是会追求各自利益自大化的特点。

博弈树是一棵从上往下考虑博弈全部可能出现情况而递归的一棵搜索树，因为考虑了所有的情况，所以被称之为完全搜索树。

但是，有些步骤根本走不到终局，如棋局中的循环走步，就算去除掉那些循环走步节点，博弈树算法也往往体量过于庞大，超出了存储空间和硬件运算速度所能承受的范围。从刚才可以看出一个仅仅N为6的简单“捡石子游戏”的完全博弈树就已经有众多节点了，这主要因为博弈树在完全搜索的情况下考虑的是所有的可能，所以，树中的节点数目随着层数增多将呈现“指数爆炸”现象。当游戏每一步可选策略多一些或者要比较多步才到达终局时，整棵树的体量将是大的惊人了。所以实际上大多数棋类游戏都没有构建完全搜索博弈树的可能，以五子棋为例，博弈树的复杂度为10的70次方，状态空间的复杂度为10的105次方，因此即使电脑的运算速度已经很快了，又有强有力的启发式搜索技术，但是要完成如此复杂的搜索也是不可取的，所以博弈树算法面临着优化问题。

比较实际的优化方法是：不走到棋局的终局，走到中间的某一步，把它当做叶子节点，然后赋值，想办法走出“较好”的走步——极大极小值搜索算法。还有就是对于某些不必要赋值的节点直接忽略，因为有时那些明显不好的节点可以直接放弃，这样原本属于它的子节点就也不用考虑了——α-β剪枝算法。

53 页第 27 页共

基于一种新算法的人工智能五子棋

4.3 优化

4.3.1 极大极小值搜索算法

极大极小值搜索算法是基于博弈树算法的一种优化算法。它基于博弈树搜索算法，但不会走到棋局终局，故而复杂度不会有那么大。具体步骤是这样的：

(1)生成极大极小值搜索树（不完全搜索树）

此处的方法同博弈树算法中生成搜索树，不同点是，博弈树算法中生成的搜索树是完全搜索树，一直到棋局终结而结束。但此处生成的搜索树是不完全搜索树，按照预先设定好的搜索层数，停在棋局中间某一处，（除非棋局快到终点，否则一般不会走到终点）所以此树的叶子节点是棋局中间的状态。

(2)对极大极小值搜索树赋值

极大极小值搜索算法的赋值方法也是从博弈树算法中演化过来的，被称作“极大极小化”过程。在此处依然是利用倒推的方法，（依旧设博弈双方为A、B）但是，由于这里的树多数情况小是一棵不完全搜索树，叶子节点是棋局中间的状态，不能简单的赋以WIN、LOST、DRAW三种值，但不同的棋局的好坏显然还是有区别的（以博弈的一方A为视角来看），为了给不同棋局的叶子节点赋值，这里需要引入静态估值函数f(q)的概念，静态估值函数是一种函数，输入值为棋的不同局面，输出值为该局面所对应的估值。棋局有利于A时f(q)取正值，棋局有利于B时f(q)取负值，当棋局对于双方损益相同时，f(q)取0值。如果f(q)=+∞(具体操作中为计算机定义数据类型中的最大值),则表示A

53 页第 28 页共

基于一种新算法的人工智能五子棋

赢，若f(q)=- ∞（具体操作中为计算机定义数据类型中的最小值），则表示B赢。因为棋局千变万化，且未到终局难以精确估计不同局面真正的损益程度，所以不会有百分百精确的静态估值函数，通常做法是：为每一种标准棋型规定一个对应分值，然后从带估值节点对应的棋局局面中分解出这些棋型，分别将己方和对方的棋型对应的分值求和，再用己方和减去对方和便得到最终该节点的估值。

用静态估值函数为所有叶子节点估值后，再利用倒推法为非叶子节点赋值，具体做法如下：若该节点对应的棋局轮到A下棋，则取该节点孩子节点分值的最大值赋值于该节点；若该节点对应的棋局轮到B下棋，则取该节点孩子节点分值的最小值赋值于该节点。如此倒推直至为整棵极大极小值搜索树赋值完毕。

(3)走步

经过第2步后，这颗极大极小值搜索树（不完全搜索树）目前所有的节点都已经被赋值了，接下来轮到走步策略了，假如A方是电脑，我们只要负责A方走步策略的选择，具体方法如下：因为赋值时我们是以A方为视角出发的，所以，当轮到A走步时，A在其孩子节点中选择分值最大的一个节点（记为节点X）所对应的棋局为其下一步的走步策略，然后等待B方走步，等B走完后，再看当前棋局与X节点的哪一个孩子节点（记为节点Y）的对应棋局相同，则Y便是当前状态节点，此时又轮到A走步，重复上述走步策略，直到状态节点为该棵树的叶子节点。

(4)重复上述步骤直至棋局终结

53 页第 29 页共

基于一种新算法的人工智能五子棋

接着步骤3，以该叶子节点为根节点重新构造一棵极大极小值搜索树，重复上面的过程，直至棋局终结——有一方取胜。

可改进处：

1.此处第三步一直走步到叶子节点再往下延伸出一棵新的搜索树，但由于对叶子节点的评分是单纯地基于基于静态评估函数，没有考虑后续可能影响，而整棵树的评分是基于叶子节点分值倒推的，上层节点所考虑的后续影响明显多于下层节点，当棋局走到快接近叶子节点时，此时算法显得短视了，可以有这样的修正方法：当搜索树被赋值后往下走步至一定深度，（不等其走至叶子节点处）就以该节点为根重新延伸出一棵极大极小值搜索树，然后对新树采用上述4个步骤进行博弈，这样能一定程度避免算法的“短视”效应，提高了棋力，但会带来降低性能的负面影响。

2.极大极小值搜索算法另一个大的缺陷是有些明显可以不用考虑的节点它也考虑了，从而带来了性能上的负担，这是可以优化的，接下来介绍一种基于极大极小值搜索算法的优化算法——α-β剪枝算法

4.3.2 α-β剪枝算法

极大极小值搜索算法的一大缺陷是它考虑下一步骤的所有可能的状态节点，而且搜索树的生成和对节点的赋值是分开进行的，其实这是不必要的。比如，在我们的五子棋中，假如下一步就可以做出一个双杀，让对方无法防御，那么直接走这一步好棋即可，而不用考虑所有的情况，还有，一般开局时占据棋盘中间部位的点明显好于占据棋盘边

53 页第 30 页共

基于一种新算法的人工智能五子棋

缘的点，所以，也不用考虑开局时棋盘边缘的点。所以还可以对极大极小值搜索算法进行优化。

举一个简单的例子来形象的说明这个问题，如图5.3.2，在α剪枝示例中，A节点的值取B、C节点的极大值，也即f(A) = max(f(B),f(C)),又因为f(C)=min(f(D),f(E),f(F)),所以f(C)<= f(D) = 14,又因为f(B) = 20,所以f(B)> f(C)，所以f(A) = f(B) = 20。形象的来说可以将以C这一孩子节点分支从搜索树中减去，这便是α剪枝,同理在β剪枝示例中因为A取孩子节点极小值，而C的值必然不小于10，所以A可直接取5，也即可以直接减去C这一分支。

取极大值的节点 A 取极小值的节点 B C B C A 20 5 D D E F 14 10 E F α剪枝示例 β剪枝示例图5.3.2 α-β剪枝法示例

一般化规律如下：设奇数层为取极大值的节点，偶数层为取极小值的节点，当第2n（n为正整数）层存在节点A值大于某2n+1层的节点C值，则可以从2n层减去节点C

53 页第 31 页共

基于一种新算法的人工智能五子棋

的父亲节点B的整个分支，是为α剪枝。当第2n+1层存在节点C值小于第2n+2层的节点E的值，则可以从第2n+1层减去节点E的父亲节点D的整个分支，是为β剪枝。此算法合称“α-β剪枝算法”[11]。

减掉分支后，不仅被减去节点不用考虑，而且也可以停止考虑其下的所有子孙节点（包括生成和赋值），这大大缩小了待考虑节点的规模，所以，α-β剪枝算法较极大极小值搜索算法有了很大的性能改进，它至今仍是博弈树算法的基础技术，是应用最为广泛的搜索算法。

4.4 本章小结

本章提出了智能五子棋的另一类算法：博弈树算法，并介绍了基于这种算法的优化算法极大极小值搜索算法和进一步的优化——α-β剪枝算法。使用博弈树来存储未来可能的状态，基于此进行分析并取舍。

53 页第 32 页共

基于一种新算法的人工智能五子棋

第5章系统构建过程细节论述

本课题在构建人工智能五子棋系统时采用的主体AI算法是α-β剪枝算法。下面叙述具体的构建过程：

5.1 游戏界面

本游戏界面采用java Swing开发，如图：

5.2 游戏步骤

a. 先设置游戏的参数，可以选择模式（双人、单人、双机），智能（估值函数、估值函数+搜索树），搜索树（层数、每层节点），再开始游戏；

b. 在棋盘上单击鼠标左键，落下棋子；

53 页第 33 页共

基于一种新算法的人工智能五子棋

c. 在棋盘上单击鼠标右键，查看该点的估值； d. 可以显示落子顺序和悔棋；

e. 使用搜索树AI时，控制台显示搜索过程； f. 某方胜利后，游戏结束。

5.3 判断棋型

这里判断棋型主要目的是从盘面上的棋子布局，识别出各种五子棋经典棋型，例如：“眠二”“活三”“冲四”，以便于下一步利用静态评估函数为其赋值。原本的想法是从四个方向上取棋子，取到一个非空棋子，以此为起点考虑其后的几个点是否能和它组合成各种棋型，但发现这样的方法太过麻烦，改用正则表达式处理，因为我的棋局存储时用的就是多维数组，0,1,2分别代表空，黑，白。所以取出横竖撇捺四个方向的数组值，直接用正则表达式跟现成的棋型匹配，看是否能匹配上，这样效率有所提高。如图：

总结出来的棋型：

长连至少五颗同色棋子连在一起 11111（1黑，2白，0空下同）

53 页第 34 页共

基于一种新算法的人工智能五子棋

活四有两个连五点（即有两个点可以形成五），图中白点即为连五点 011110

冲四有一个连五点 011112 0101110 0110110

活三可以形成活四的三 01110 010110

53 页第 35 页共

基于一种新算法的人工智能五子棋

眠三只能够形成冲四的三 001112 010112 011012 10011 10101 2011102

活二能够形成活三的二 00110 01010 010010

眠二能够形成眠三的二 000112

53 页第 36 页共

基于一种新算法的人工智能五子棋

001012 010012 10001 2010102 2011002

（图不全）

死四两头都被封堵的四 211112 （图缺）

死三两头都被封堵的三 21112 （图缺）

死二两头都被封堵的二 2112 （图缺）

53 页第 37 页共

基于一种新算法的人工智能五子棋

5.4 落子估值方式

分析：棋子落在哪里最好？

1. 需要考虑落下后会在四个方向各形成什么棋型，是否形成组合棋型，然后进行初步打分；

2. 同时还要考虑落子位置，一般同分情况下越中心的点越好； 3. 可以分析对攻击效果、防守效果、综合效果。

初步打分：

就是按照威胁程度给每种棋型打分，在理解棋型后，试验了多组估分方式，最后确定效果最好的一组打分方式如下：

棋型（含组合棋型）长连活4、双冲4、冲4活3 双活3 活3眠3 眠4 活3 分值 100000 10000 5000 1000 500 200

53 页第 38 页共

基于一种新算法的人工智能五子棋双活2 眠3 活2眠2 活2 眠2 死4 死3 死2

100 50 10 5 3 -5 -5 -5 再统计在四个方向各形成什么棋型，是否形成组合棋型，取最高分为初步打分的结果。

落子位置：

根据棋盘分布问题，越中心的点分值应当越高。 private static int[][] position = {

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 }, { 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 },

53 页第 39 页共

基于一种新算法的人工智能五子棋

{ 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 }, { 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 }, { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

例如，对下图A点，如果放白子，在四个方向分别会形成活3、活2、眠2，形成两种棋型（组合棋型）活3和活2眠2，最高分为活3对应的200分，再加上位置分值6分，就是206分；如果放黑子，同理是25分。因此，当要在J9落下白子时，可获得攻击分206，防守分25，综合分231。

53 页第 40 页共

基于一种新算法的人工智能五子棋

5.5 棋局估值函数

函数描述：

有了落子估值方式后，可以针对某一棋局，分析一定棋盘范围内的各个可落子点的落子估值，将最大综合分作为该棋局的估值。

简单智能:

利用估值函数，即可实现简单智能，即只考虑当前局面下的最佳落子点，并落子。例如，人机对战：

优点是速度快，眼前胜利绝不放过，缺点也是显而易见的，对于埋伏了多步的杀法，这种只顾“近忧”的智能无能为力。因此，就需要搜索算法增加“远虑”。

53 页第 41 页共

基于一种新算法的人工智能五子棋

5.6 α-β剪枝算法的伪代码: