五子棋游戏人机对奕中AI算法研究论文.docx

五子棋游戏人机对奕中AI算法研究论文.docx

《五子棋游戏人机对奕中AI算法研究论文.docx》由会员分享，可在线阅读，更多相关《五子棋游戏人机对奕中AI算法研究论文.docx（46页珍藏版）》请在冰点文库上搜索。

五子棋游戏人机对奕中AI算法研究论文

摘要

本系统将利用五子棋游戏作为研究对象，通过设计出一个能够实现两种不同对战模式的五子棋游戏。

并对所涉与到的相关技术进展初步的探讨，将重点放在人机对奕中AI算法研究方面。

游戏中提供两种选择模式：

人机对战和人人对战。

在人机对战中玩家通过选择不同的AI等级和电脑一决高低。

在人人对战中双方可以进展下棋，并通过禁手算法实现禁手规如此

关键词五子棋、博奕AI算法、ios

Abstract

ThissystemwilluseRenjuasresearchobjects,passingtodesignaRenjugamethatcanprovidetwokindsofdissimilaritiestotheplaymode.toinvolvetooftherelatedtechniquecarryonthestudyofthefirststep,playmoreattentionintheAIcalculatewayresearchaspect.

Itprovidetwokindsofchoicemodesinthegame:

Person'smachinetothewarandtheeveryonetowar.TheplayerpassestochoosethedifferentAIgradeandputerinperson'smachinetherightnessthewaradefinitelysuperiority.Bothpartiescancarryonplaychessintheeveryonetherightnessthewar。

Keywords　Renju,AI,IOS

不要删除行尾的分节符，此行不会被打印

2.4.1系统主要功能模块

2.4.2系统主要流程

2.5.1欢迎界面

2.5.2游戏主界面

3.1.1开发环境

3.1.2运行环境

3.1.3IOS简介

3.1.4Objective-C简介

3.6.1知识准备

3.6.2算法的主要设计思路

千万不要删除行尾的分节符，此行不会被打印。

在目录上点右键“更新域〞，然后“更新整个目录〞。

打印前，不要忘记把上面“Abstract〞这一行后加一空行

第1章绪论

1.1课题背景

计算机运算速度一直遵循着摩尔定律在飞速的开展，随着这些技术的快速开展，使得大规模的运算得以在很短的时间内实现。

正是基于这些技术，近年来各式各样的棋类游戏软件也纷纷出现在了电脑荧屏上，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。

所以如果能设计一款兼有人工智能和网络联机的五子棋软件如此对五子棋棋迷们来说无疑是个“福音〞。

在人机智能方面其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝〞便是最具说服力的代表；其它像围棋的“手淡〞、象棋的“将族〞等也以其优秀的人工智能深受棋迷喜爱；

本系统将重点放在人工智能方面，采用不同的策略将人工中的智能分为不同的等级。

选择五子棋游戏作为本设计的课题，是因为该游戏的规如此简单，所涉与的方向比拟少。

这样才能将问题的重点放在人工智能解决上，而非规如此的解决，有更多的精力放在高效算法和通信过程的优化。

希望能通过本次系统的设计，整合所学的知识，实现从理论到实践上的升华。

1.2课题来源、目的和意义

苹果的IOS平台已经占据了全球智能手机系统市场份额的30%，在美国的市场占有率为43%。

为IOS编程是我们大学生未来充满机遇的开展方向之一，所以了解IOS开发流程，学会使用XCODE编程工具,掌握IOS开发语言Objective-C，学习IOS应用功能实现以与硬件功能的调用，是学生选用IOS平台开发五子棋的重要原因。

五子棋是最受欢迎的休闲游戏之一，其不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。

五子棋既有现代休闲的明显特征“短、平、快〞，又有古典哲学的高深学问“阴阳易理〞；它既有简单易学的特性，为人民群众所喜闻乐见，又有高深的技巧和高水平的国际性比赛；它的文化源远流长，具有东方的神秘和西方的直观；既有“场〞的概念，亦有“点〞的连接。

它是中西文化的交流电，是古今哲理的结晶。

通过此次在IOS平台开发五子棋，除了完成人机对战和在无线局域网间对弈外，尽可能多的实现IOS平台提供的功能，从而加深对IOS平台的了解，为个人开展打下根底。

在人机对弈中通过深度搜索和估值模块，来提高电脑棋手的智能。

分析估值模块中的影响精准性的几个要素，以与提出假如干提高精准性的方法，以与对他们搜索的节点数进展比拟，在这些算法的根底上分析一些提高电脑AI方案，如递归算法，电脑学习等。

算法的研究有助于理解程序结构，增强逻辑思维能力，在其他人工智能方面也有很大的参考作用。

1.3国内外研究现状

现在iPhone的众多游戏都是来自中国的游戏开发者，苹果ios游戏开发已经悄然在中国形成一个产值过亿的庞大产业。

在过去两年中，苹果向全球的ios游戏开发者累计分成达到10亿美元，根据中国开发者提供的下载量、收入情况等数据测算，其中1亿美元被中国开发者获得。

有预测称，这一收入份额还可能在未来三年内占到全球的15%-20%。

 此外，数据还显示，苹果ios游戏开发年收入额排名全球前100的开发公司中，中国公司有4家，而年收入500万美元以上的中国团队，也至少有5-7支。

 苹果应用软件的开发在中国的增速极为迅猛，这一产业在2008年苹果进入中国后达到了3亿美元的市场规模，2009年超过10亿美元，有预测称，今年将可能突破40亿美元。

而ios游戏开发作为苹果应用软件中最受欢迎的一局部，将会分到近70%的利润。

“从中国市场的开展来看，目前ios游戏开发者中个人开发者占到45%，3人以下小团队占到56%，10人规模以下的工作室或个人共占80%。

随着竞争的激烈，拥有更多资源和人才的公司将更占优势。

目前在其开发的ios游戏中，单机小游戏占据最大的份额，达到90%，剩下的10%如此是社交类游戏和一些大型高端游戏产品。

像《疯狂的小鸟》这种单机游戏容易制作、投入相对较少，因此一旦成功无疑是一本万利；而大的制作如此需要消耗巨大的人力、物力、财力，产出较低。

苹果ios游戏开发为中国市场带来巨大的机遇显而易见。

虽然现在其他平台也开始参与竞争，但苹果这一平台至少会在5年内保持世界上的领先地位。

苹果ios游戏开发必然会吸引更多的创业者参加，使得整个产业的开展更为迅速。

1.4主要研究内容

1、制定合法规如此，能够判断出非法操作，以使博弈公正地进展并分出胜负；

2、支持人机对弈、能够让计算机按照游戏规如此通过人工智能自行选择最优走法；

3、支持人人对弈；

4、设计算法，实现三三禁手。

5、具有精美的操作界面，能播放音乐，方便用户操作和使用；

1.5本文结构

本文主要内容如下：

第1章：

绪论局部，首先介绍了课题背景、来源、目的和意义，接着给出了本论文的主要研究内容和论文的结构。

第2章：

需求分析，按照软件工程的理论给出了系统开发的根本思想和方法。

在对系统的需求进展详细分析后，给出了系统所要完成的根本功能。

并介绍了系统的软硬件开发环境与开发工具。

第3章：

系统设计，对系统的各种结构和功能结构的设计做了描述。

第4章：

系统的实现与测试，介绍个功能模块的详细实现以与系统测试的方法和过程。

双击上一行的“1〞“2〞试试，（本行不会被打印，请自行删除）

第2章IRC协议根底与相关技术和理论

2.1IRC协议

2.1.1IRC协议的历史

IRC的全称是InternetRelayChat，缩写为IRC，中文名称一般为互联网中继聊天，它是由芬兰人JarkkoOikarinen于1988年首创的一种网络聊天协议[7]。

1988年，芬兰OULU大学的JarkkoOikarinen开始一个新的尝试，他制作了一个多用户版的UNIX"TALK"工具：

"INTERNETRELAYCHAT"。

UNIX的TALK工具是一种允许两个用户通过键盘进展实时笔谈交流的程序,现在仍然广泛地存在于许多运行LINUX系统的计算机中，你的谈话出现在计算机屏幕的上半部，而另一个人的信息如此显示在屏幕的下半部。

Oikarinen创造出了我们今天所熟悉的IRC环境。

起初，许多用户登录到位于Oulu的一个单独的服务器，而后三个芬兰的服务器互联在一起成为世界上第一个IRC网络，到1988年年底，IRC网络已经延伸到Internet世界的各个角落。

经过数年的开展，目前世界上有超过60个国家提供了IRC的服务。

2.1.2IRC消息传递原理

IRC的中文名称为互联网中继聊天，“中继〞是IRC网络聊天的核心。

所谓“中继〞即“中转〞。

我们来做一个比拟说明.假设，A与B要交谈.如果不采用中转，那么A直接建立一条到达B的通信隧道，二者通过这条通信隧道进展信息交流，信息流的方向为：

A->B和B->A；如果采用中转，如此需要有一个第三方来担任中转角色，设为C，A建立一条到达C的通信隧道，B也建立一条到达C的通信隧道，然后A与B通过C来间接进展通信，信息流的方向为：

A->C->B和B->C->A。

C就起着A与B间的中转站的作用。

中转有什么优点呢？

中转的最大优点是使"群聊"能够方便地进展。

恰当地说，中转模式为信息广播提供了方便。

我们来举例子，假设A，B和D三者要一起聊天.如果没有C的中转，那么A要将所说的每句话分别发给B和D；如果有C做中转，那么A将所说的话发给C，然后C将A的话分别发给B和D。

可见，当没有中转时，每个参与聊天的计算机都要执行信息广播的任务，当存在中转时，信息广播的任务全由中转者来执行。

中转站C的存在使得信息交流过程中的工作任务发生别离，可以把网络环境好、机器配置高的计算机作为中转站来提供服务功能。

这就形成了IRC的客户端/服务器模型，聊天者作为客户端，连接到中转站服务器上[8]。

图2-1IRC网络简单示例

在上图中，A、B、C、D和E为服务器，1、2、3、和4为客户端，

（1）客户端1和2之间的通信是通过服务器A传递的，A接收到1的信息直接传递给2。

（2）客户端1和3之间的信息通过服务器A和B进展传递，对于其他的客户端和服务器是不可见的。

（3）客户端2和4之间的信息，只对服务器A、B、C和D可见[9]。

2.1.3IRC结构

一个典型的IRC网络，如图2-2所示。

客户端

客户端

服务器

客户端

客户端

服务器

客户端

服务器

图2-2IRC网络结构图

2.1.3.1IRC服务器

IRC是一个分布式的客户端/服务器结构。

通过连接到一个IRC服务器，我们可以访问这个服务器以与他所连接的其他服务器上的频道。

概括地说，聊天网络上的每个服务器都是一个中转站，当它从一个服务器或客户收到一条消息时，就将该消息转发给其它服务器，同时也根据具体情况，决定是否将消息转发给连接到自己的用户。

要使用IRC网络聊天，必须先登陆到一个IRC服务器上，最常见的为。

2.1.3.2IRC频道

频道存在于一个IRC服务器上。

频道的本质是广播组。

用户可以进入一个频道，也可以离开一个频道。

当一个用户朝频道说话时，频道里的其他用户都能收到他的话〔由服务器中转〕。

当第一个用户进入频道时，频道被创建，当最后一个用户离开频道时，频道被取消。

因此，从用户的角度看，频道就是聊天室。

频道名称必须以#符号开始，例如#irchelp。

2.1.3.3IRC客户端

客户端通常是一个连接到服务器的客户端程序。

每个客户端都由一个唯一的昵称进展区分，昵称最大长度为9个ASCII字符。

用户通过客户顿登陆IRC服务器[10]。

常见的IRC客户端如下：

（1）mIRC被认为是Windows操作系统下最受欢迎，应用最广泛的IRC客户端软件。

（2）XChat是跨平台的IRC客户端软件。

（3）HydraIRC是GPL授权对应Windows系统的IRC客户端软件。

（4）KVIrc是一款注重图形的GPL授权IRC客户端软件，基于Qt。

（5）Irssi是类UNIX系统下console界面的IRC客户端，常常与Screen一起搭配使用。

（6）Colloquy是MacOSX下的免费IRC客户端，界面设计友好，还有Console可以监控背后针对每个频道执行所有IRC命令[11]。

2.1.4IRC命令

根据统计数据IRC命令是用情况如表2-1所示。

IRC命令

使用情况

PRIVMSG

25.31%

PONG

12.37%

PING

JOIN

9.87%

QUIT

8.37%

MODE

7.75%

NOTICE

5.79%

LIST

5.15%

WHOIS

3.68%

PART

2.87%

WHO

2.00%

LINK

1.05%

CTCP

0.92%

DCC

0.40%

表2-1IRC命名使用情况统计表

由上表可以看出IRC最主要的命令式PRIVMSG、PING和PONG，因为PRIVMSG是私人消息命令，是IRC协议本身最根本的功能。

而PING和PONG如此是用来判断客户端在空闲状态下，服务器是否连接的[12]

2.2网络数据包捕获技术

2.2.1网络数据的捕获原理

通常在同一个网段的所有网络接口都有访问在物理介质上传输的所有数据的能力，每个网络接口还应该有一个硬件地址，该硬件地址是唯一的，不同于网络中存在的任何其他网络接口的硬件地址，同时，每个网络还至少需要一个广播地址[13]。

当有一个站点发送数据时，网络中的其他站点总处于侦听状态，数据帧可被任何站点收到，否如此丢弃。

网卡的接收模式一般有四种：

（1）广播模式：

该模式下的网卡能够接收网络中的广播信息。

（2）组播模式：

该模式下的网卡能够接收组播数据。

（3）直接模式：

该模式下只有目的网卡才能接收数据。

（4）混杂模式：

该模式下的网卡能够接收一切通过它的数据。

一般网卡只承受两种数据帧：

发给自己的帧、网络中的广播帧，所以通过将网卡设置为混杂模式可接收到所有流经网卡的数据帧，然后将其传给上层的网络层，而不管地址是否与自己匹配[14]。

2.2.2Libpcap数据捕获开发包简介

Libpcap是英文PacketCapturelibrary的缩写，即数据包捕获函数库。

该库提供的C函数接口可用于需要捕获经过网络接口（只要经过该接口，目标地址不一定为本机）数据包的系统开发上。

由Berkeley大学LawrenceBerkeleyNationalLaboratory研究院的VanJacobson、CraigLeres和StevenMcCanne编写。

该函数库支持Linux、Solaris和BSD体统平台。

Libpcap是一个平台独立的网络数据包捕获技术。

由于Libpcap与操作系统的类型无关，可以独立的访问网络链路层，并读取连路程数据，所以Libpcap有着非常广泛的应用，几乎涉与到网络数据包的捕获功能，都可以使用Libpcap开发包。

Libpcap的过滤机制是BPF，支持DLPI和SOCKPACKET，基于内核的过滤模块。

它可以捕获自己感兴趣的数据包，而过滤掉不需要的数据包。

Libpcap还可以将捕获到的数据包保存到文件中，也可以随时从文件中读取数据包的信息，且读出数据的结果和从网络上捕获的数据包数据完全一致[15]。

2.3Qt开发框架简介

Qt是一个跨平台的C++应用程序开发框架。

广泛应用于GUI程序开发，这种情况下又被称为部件工具箱。

也可用于开发非GUI程序，比如控制台工具和服务器。

它目前是诺基亚的QtDevelopmentFrameworks部门的产品。

Qt使用标准的C++。

通过语言绑定，其他的编程语言也可以使用Qt。

Qt是自由且开放源代码的软件，在GNU较宽松公开许可证条款下发布。

所有版本都支持广泛的编译器，包括GCC的C++编译器和VisualStudio。

2.3.1Qt简史

HaavardNord和EirikChambe-Eng于1991年开始开发“Qt〞，1994年3月创立公司，最早名为QuasarTechnologies，然后更名为TrollTech，然后再更名为Trolltech，中文名是“奇趣科技〞，2008年6月被NOKIA公司收购，以增强该公司在跨平台软件研发方向的实力，更名为QtSoftware。

该工具包名为Qt是因为字母Q在Haavard的Emacs字体特别漂亮，而“t〞代表“toolkit〞，灵感来自Xt，Xtoolkit。

2009年5月，诺基亚QtSoftware宣布Qt源代码管理系统面向公众开放，Qt开发人员可通过Qt以与与Qt相关的项目贡献代码、翻译、示例以与其他内容，协助引导和塑造Qt未来的开展。

为了便于这些内容的管理，QtSoftware启用了给予Git和Gitorious开源项目的Web源代码管理系统。

在推出开放式Qt代码库的同时，QtSoftware在其发布了其产品规划。

其中概述了研发项目中的新功能，展现了现阶段对Qt未来开展方向的观点，以期鼓励社区提供反响和贡献代码，共同引导和塑造Qt的未来。

2.3.2Qt支持平台

使用Qt开发的软件，一样的程序代码可以在任何支持的平台上编译与执行，而不需要修改源代码。

会自动依平台的不同，表现平台特有的图形界面风格。

●Linux/X11：

用于XWindowSystem〔如Solaris、ATX、Linux、HP-UX、Linux、BSD〕。

支持KDevelop和EclipseIDE集成。

●Mac：

用于AppleMacOSX。

基于Cocoa框架。

支持UniversalBinary。

支持以Xcode编辑、编译和测试。

●Windows：

用于MicrosoftWindows。

支援VisualStudio集成。

●EmbeddedLinux：

用于嵌入式Linux。

可以透过编译移除不常使用的组件与功能。

透过自己的视窗系统QWS，不需依赖XWindowSystem，直接写入Linux帧缓冲。

可以减少内存消耗。

并提供虚拟帧缓冲QVFb，方便在桌面系统上进展嵌入式测试。

●WindowsCE/Mobile：

用于WindowsCE。

●Symbian：

用于Symbianplatform。

●Maemo/MeeGo：

用于Maemo。

●Wayland：

用于Wayland显示服务器，Qt应用程序可以在运行时切换图形后端，如X与Wayland。

2.3.3授权模式

Qt开放源代码，并且提供自由软件的用户协议。

使得它可以被广泛地应用在各平台上的开放源代码软件开发中。

Qt提供三种授权方式。

三种授权方式的功能、性能都没有区别，仅在于授权协议的不同。

LGPL和GPL是免费发布，商业版如此需收取授权费。

●Qt商业版：

Qt商业授权适用于开发专属和商业软件。

此版本适用于不希望与他人共享源代码，或者遵循GNU宽通用公共许可证〔LGPL〕2.1版或GNUGPL3.0版条款的开发人员。

提供了技术支持服务。

可以任意的修改Qt的源代码，而不需要公开。

●GNULGPLv.2.1：

与以后的版本开始遵循GNULGPL。

LGPL允许链结到它的软件使用任意的许可证，可以被专属软件作为类库引用、发布和销售。

可以购置支援服务。

●GNUGPLv.3.0：

如果您希望将Qt应用程序与受GNU通用公共许可证〔GPL〕3.0版本条款限制的软件一同使用，或者您希望Qt应用程序遵循该GNU许可证版本的条款，如此此版本Qt适用于开发此类Qt应用程序。

可以购置支援服务。

2.4MySQL数据库简介

MySQL是一个开放源码的关联式数据库管理系统，原开发者为瑞典的MySQLAB公司，该公司于2008年被Sun公司收购。

2009年，甲骨文公司〔Oracle〕收购Sun公司，MySQL成为Oracle旗下产品。

MySQL是一种关联数据库管理系统，关联数据库将数据保存在不同的表中，而不是将所有数据放在一个大仓库内。

这样就增加了速度并提高了灵活性。

MySQL的SQL“结构化查询语言〞。

SQL是用于访问数据库的最常用标准化语言。

MySQL软件采用了GPL〔GNU通用公共许可证〕。

由于其体积小、速度快、总体拥有本钱低，尤其是开放源码这一特点，许多中小型为了降低总体拥有本钱而选择了MySQL作为数据库。

2.5QWT简介

QWT，全称是QtWidgetsforTechnicalApplications,是一个基于LGPL协议的开源项目，可生成各种统计图。

它为具有技术专业背景的程序提供GUI组件和一组实用类，其目标是以基于2D方式的窗体部件来显示数据，数据源以数值，数组或一组浮点数等方式提供，输出方式可以使Curves〔曲线〕，Slider〔滚动条〕，Dials〔圆盘〕，passes〔仪表盘〕等等。

该工具库基于Qt开发，所以也继承了Qt的跨平台特性。

QWT常用基类：

（1）QwtAbstractScale：

包含刻度尺的所有类的抽象基类；

（2）QwtAbstractScaleDraw：

绘制刻度尺的抽象基类；

（3）QwtAbstractSlider：

滑块部件的抽象类；

（4）QwtAbstractColorMap：

可以改变颜色的alpha值；

（5）QwtAnalogClock：

时钟模拟类；

（6）……

利用Qwt可以画出多种统计图，如图2-3、图2-4所示。

图2-3曲线图

图2-4cpu性能图

2.6本章小结

本章首先介绍了有关IRC协议的根底知识，包括IRC协议的历史、消息传递原理、IRC网络的结构和IRC命令概括。

随后介绍了基于Libpcap的网络捕包技术、Qt程序开发框架和MySQL数据库以与可以做出比拟没关图表的Qwt开发包，为IRC协议命令关键字分析系统的设计和实现奠定了理论根底。

第3章系统设计

3.1开发环境

主机：

普通PC。

操作系统：

Ubuntu11.10。

开发语言：

C语言。

开发工具：

Libpcap、Qt。

数据库：

MySQL。

3.2系统功能架构设计

在软件设计中，通常采用模块化的设计思想，这样的设计比拟合理，在开发阶段也比拟容易实施。

模块化的过程一般是根据功能来进展的，把系统的主要功能分配成几个关键模块，然后分别加以实现，而且通常需要结合分层设计的思想。

即由顶层模块调用它的各个子模块来实现整个的功能，而每个下层模块再调用它的子模块，以此类推。

最根底最具体的功能如此由最下层的模块来完成。

根据以上原如此，按照功能，IRC协议关键字分析系统可分为捕获和分析模块，系统的总体结构如图3-1所示

图3-1系统功能模块总体结构

系统各功能介绍如下：

（1）数据包捕获模块：

包括网卡的选择和配置，并从选择的网卡进展数据包捕获。

（2）数据包过滤模块：

设置过滤表达式，过滤掉不符合条件的数据包。

（3）数据存储模块：

没有经过分析的原始数据以文件的形式存放，经过分析提取的数据包信息，如数据包捕获时间、端口等信息存放到数据库中。

（4）数据库操作模块：

可以查看数据库中存放的所有捕获到的数据包的信息，并且可以执行删除和导入文件操作。

（5）关键字统计模块：

当打开某个原始文件时，统计此文件中关键字的名称和相应的数量。

（6）前台数据显示模块：

根据数据包协议的格式分析出各个数据包捕获时间、长