编号：
毕业设计说明书
题目：基于IOS平台的游戏“五子棋”
程序设计
学院：计算机科学与工程学院
专业：网络工程
学生姓名：
学号：
指导教师：
职称：
题目类型：?理论研究?实验研究?工程设计?工程技术研究?软件开发
2012年 5月 30日
摘要
本论文主要阐述以iOS开发平台为基础，通过使用Xcode开发工具以及objective-c和c++语言开发的一款运行在iPad上的智力游戏“五子棋”。五子棋是一种两人对弈的纯策略型棋类游戏，棋具与围棋通用，是起源于中国古代的传统黑白棋种之一。近年来，随着智能手机的流行，出现了许多在移动操作系统上的手机应用。所以，开发一款可以在iOS系统上运行的五子棋游戏是非常有意义的。
在开发的过程中，我首先学习了objective-c语言的相关语法，objective-c语言是在C语言上进行一些面向对象的扩充，学习它大概用了一周的时间。接下来，开始学习iOS应用的构建原理（学习视图控制器与视图的使用方法，程序委托的使用等）以及一些常用控件的使用，并尝试在Xcode工具上搭建一些简单的界面。这时候的界面是用xib文件来搭建的，通过直接拖拉控件来产生界面。之后，开始尝试用代码写控件来代替xib文件。在做好这些基础的准备后，我开始动手搭建五子棋的界面，五子棋界面除了一些常用的控件（按钮以及标签）外，重要的是画出棋盘以及棋子，棋盘和棋子不能用普通控件来显示，需要使用绘图的方法把它画出来。在这些工作完成了之后，界面就可以显示出来了。
接下来，就要在棋盘类上面进行一些处理工作，比如点击各个按钮触发的事件，在游戏过程中玩家点击棋盘触发的事件，判断游戏输赢，悔棋和认输功能的实现等等。之后，就开始设计与实现五子棋算法了。经过多年的发展，五子棋的算法已经较为完善，我做的工作是在理解这些算法原理的基础上，用自己的话来实现，并加入一些新的东西。五子棋算法一般包括估值算法以及搜索算法，估值算法的实现虽然代码量较大但是理解起来不是特别难，而我在学习搜索算法的过程中却在一开始的时候无法理解他的alpha-beta剪枝以及负极大值算法的意思。而在一开始写完算法部分代码之后，也还是存在许多问题，无法搜索出正确的落子点，在经过一些排错与完善之后，算法的实现可以与前面的棋盘进行结合了。这样，整个设计就差不多完成了，接下来就需要进行测试并进行一些小的修改。
在本论文中，主要阐述了开发过程中的一些细节，遇到的问题，解决的方法以及自己的一些感悟。
关键词：objective-c;人工智能;算法
Abstract
This paper mainly expounded a mental game gobang .It is on the basis of iOS development platform, using the Xcode development tools and objective - c and c + + language to develop,and runed in the iPad. Gobang is a game of two pure strategy type chess game. Chess can be used in the game of go.Gobang is one of the traditional reversi which is originated from the ancient Chinese . In recent years, with the popularity of smart phones, Many mobile applications on mobile operating system appeared.So, developing a Gobang game can be run on iOS is meaningful.
In the process of development, the first thing is learning the syntax of objective-c language,the objective-c language is in the basis of c language and add some Object oriented expansion , it took me about a week's time to study.Next, I start to learn the building principle of iOS app (learning the usage of view controller and view , the use of application of delegate and so on ) and the use of some common controls, and try to make some simple interface on Xcode tool structures.At this time the xib file interface is used to build, through direct drag controls to generate the interface.Next, I began to try to replace the xib file by writting codes.After doing this things, I start to build gobang interface, in addition to some commonly used controls (buttons and labels), it is important to draw the chessboard and chess ,the board and chess can not use normal controls to display, I need to draw them.After the work finished, interface can be displayed.
Next, I should do some work on board, such as the events by click each button , the events by click board, the function of judes success ,giving up and regret and so on.Then,I began to design and realize the gobang algorithm. Gobang algorithm has been more mature, my work is understanding the algorithm and relize it, and I will add some new things.Gobang algorithm generally includes valuation algorithm and search algorithm, the code of valuation algorithm is large but I do not hard to undstand it .Instead ,I can't understand the alpha beta pruning and negative maximum value algorithm. And after finished the algorithm , it still exist many problems, it is unable to search the right move place, after some troubleshooting and improvement, the realization of the algorithm can be combined with the front board.So, the whole design is almost finished, you need to test and make a few small changes.
This paper mainly expounds some details in the development process, implementation methods, difficulties, and some of my own feeling.
Key words:objective-c;Artificial intellegence;algorithm
目录
引言 (1)
1 手机五子棋游戏介绍 (2)
1.1 五子棋游戏规则介绍 (2)
1.2 五子棋游戏术语介绍 (3)
1.3 手机五子棋特色 (3)
2 开发环境及工具介绍 (3)
2.1 开发环境 (3)
2.2 运行环境 (4)
2.3 工具介绍 (4)
2.3.1 iOS介绍 (4)
2.3.2 objective-c介绍 (4)
3 需求分析与总体设计 (5)
3.1 需求分析 (5)
3.2 系统设计思想 (5)
3.3 系统总体设计 (5)
3.4 系统模块及功能 (6)
3.4.1系统主要模块 (6)
3.4.2系统主要流程 (7)
4 五子棋AI算法分析与实现 (8)
4.1 算法总体概况 (8)
4.2 估值算法分析与实现 (8)
4.3 搜索算法的分析与实现 (13)
4.4 算法设计的不足以及改进方法 (18)
5 APP应用详细设计 (19)
5.1 APP设计介绍 (19)
5.1.1 main函数介绍 (19)
5.1.2 应用程序委托介绍 (19)
5.1.3 视图控制器介绍 (19)
5.1.4 视图类介绍 (20)
5.1.5 MVC模型介绍 (20)
5.1.6 主要框架介绍： (20)
5.2 详细设计概述 (20)
5.3 视图控制器类设计 (21)
5.3.1积分榜的设计 (21)
5.3.2委托类的设计与使用 (21)
5.3.3按钮的设计 (21)
5.4 棋盘类的设计 (22)
5.4.1棋盘类变量设计 (22)
5.4.2棋盘的绘制 (22)
5.4.3玩家和机器人下子 (22)
5.4.4棋子类的实现 (23)
5.4.5判断胜负功能 (23)
5.4.6游戏新局功能的实现 (24)
5.4.7认输功能的实现 (24)
5.4.8悔棋功能的实现 (24)
5.4.9人人对战的实现 (24)
6 开发过程中遇到的问题 (25)
6.1 五子棋AI算法设计问题 (25)
6.2 棋盘类设计遇到的问题 (25)
7 测试 (26)
8 总结 (31)
谢辞 (33)
参考文献 (34)
引言
随着科技的发展，智能手机的出现改变了我们一直以来对手机只是用于打电话和发短信的观点。在路上，车上，我们总能看见有人拿着手机来玩游戏，看电影，这一切都在改变我们的日常生活。也正是由于这些变化，移动互联网已经逐渐成为了互联网这个行业的重要组成部分。我们也能看到，传统的PC行业的增长已经开始放慢，国际上一些很大的传统PC厂家例如惠普，戴尔在PC行业的利润已经越来越少，它们都在积极的寻求转型。而反观智能机的领域，苹果，三星，HTC等企业都通过智能手机的销售取得了非常好的业绩。特别是苹果和三星，占据了整个智能手机领域的很大部分利润。
所谓智能手机，就是与传统的功能手机只可以用来打电话与发短信不同。它类似于电脑，有一个独立的操作系统，用户可以自行安装和卸载各种软件，这样手机的功能就得到了充分的扩充。在PC上的软件现在不断有了移动操作系统上的版本，例如QQ等聊天类软件，微博等社交类软件，甚至在手机上也出现了很多3D游戏，这些都有赖于移动操作系统的产生以及相关硬件的发展。在智能手机的行业中，诺基亚和黑莓曾经占据了非常重要的地位。塞班系统曾经非常成功，但是后来由于开源的Android 以及iOS系统的出现，加上触控技术的流行，塞班系统不断的失去了它的优势。同样，近年来也兴起了平板这种新的数码产品，这是一种崭新的产物。iPad是苹果公司推出的一款平板电脑，受到了市场的强烈反响。所以，我觉得在iPad上开发一款移动应用是一件非常有意义的事情。
五子棋是一种两人对弈的策略型游戏，起源于中国古代。五子棋的规则比较简单，上手比较容易，而且趣味横生，引人入胜。传统五子棋的棋具是与围棋通用的，一般是15*15的棋盘，棋子分黑白两种颜色，对弈的双方分别执一种颜色的棋子，棋子放置在棋盘线上的交叉位置，双方轮流下子，只要同一颜色的棋子能够有五个棋子在同一条线上，那么执这种颜色棋子的一方就赢得了这盘棋。
随着科技的发展，现在人们的物质生活越来越丰富，但是人们的生活压力也越来越大，所以在工作闲暇之余，来一盘五子棋，也不失为一种调节情绪，放松思考的机会。五子棋的规则简单，却往往可以开发人的思维，是一种非常有意义的游戏。五子棋现在已经发展为一种非常重要的棋盘游戏。
近年来，游戏产业得到了巨大的发展。而且随着手机的发展，游戏产业已经扩展到了手机上，这样大家就有了更多休闲娱乐的机会。棋类游戏具有益智，开发人大脑思维的功能也受到了大家的欢迎。手机上的棋类游戏往往分为人机对战和人人对战两种。特别是人机对战中的机器博弈，是PC和手机上的棋类游戏的一大特色。机器博弈是人工智能研究领域中一块非常重要的地方。
本文设计的是一款人机和人人对战的五子棋游戏软件，在人机对战模块中，提供了一定智力的机器人来和玩家进行博弈。机器人的功能通过估值，alphabeta剪枝搜索,负极大值等算法来实现。人人对战主要是提供一个界面美观的棋盘来给两个玩家切磋棋艺。另外，本软件还提供了下面的一些功能：1，重新开始功能，游戏模式选择功能，人机对战选择游戏难度功能，下棋先后手选择功能。
2，认输功能。
3，悔棋功能。
3，积分功能（胜负记录）。
4，判断胜负功能。
5，游戏状态提醒功能。
1 手机五子棋游戏介绍
1.1 五子棋游戏规则介绍
五子棋的标准棋盘大小是15*15，由双方各执一种颜色的棋子，分别在棋盘横竖线交叉的位置摆上棋子。最后有一方的棋子有五子可以连成同一根线就算执该颜色棋子的一方胜利。
由于在五子棋游戏过程中，先下子的一方非常占有很大的优势，所以五子棋游戏有两种下棋规则，禁手和无禁手。禁手规则是指先下子的一方需要一定的约束，通常有长连禁手，四四禁手，三三禁
手。这些都是对先下子一方的约束，来平衡先下子本身带来的不公平。无禁手规则是指双方都不需要约束下子的位置，国际比赛往往都有禁手规则。
1.2 五子棋游戏术语介绍
连珠：国际上五子棋的正式名称。
阳线：棋盘上可见的横线和竖线的总称。
阴线：棋盘的两条对角线及与它们平行的交叉点间不可见斜线的总称。
连：一条阳线或阴线上紧紧相连的同色棋子。
长连：一条阳线或阴线上紧紧相连的同色六枚或六枚以上棋子。
五连：一条阳线或阴线上紧紧相连的同色五枚棋子。
四：指活四和冲四。
活四：己方再加上一子，有两个点可以成五的单四。
冲四：己方再加上一子，只有一个点可以成五的四。包括连冲四和跳冲四。
三：指活三和眠三。
活三：己方再加上一子，可以形成活四的三。
眠三：己方再加上一子，可以形成冲四但不能形成活四的三。
二：指活二和眠二。
活二：己方再加上一子，可以形成活三的二。
眠二：己方再加上一子，可以形成眠三但不能形成活三的二。
死四、死三、死二由于在主方向已不可能成五，因此已不是四、三、二。
1.3 手机五子棋特色
便携性：在没有计算机和手机出现之前，要进行一场五子棋游戏都是需要使用真正的棋盘和棋子进行的。而随着计算机和网络的不断发展，五子棋已经完全可以脱离棋盘的限制。而近年来随着手机的发展，更加方便的手机版五子棋不断出现。它不仅具有电脑版五子棋的优势，而且更加的方便。
网络连接能力：由于手机或平板都有一定的网络连接能力，所以可以通过网络连接进行两人对战，这样就减少了距离的限制。
2 开发环境及工具介绍
2.1 开发环境
电脑硬件：处理器 2.7 GHz Intel
内存8 GB 1600 MHz DDR3
操作系统：软件OS X 10.8.2 (12C3103)
开发工具：xcode 4.6
2.2 运行环境
硬件：第一代iPad
操作系统：iOS 5.1
2.3 工具介绍
2.3.1 iOS介绍
iOS是一种闭源的系统，采用了混合内核，是苹果公司开发的一款手持设备的操作系统。苹果公司一开始是将这个系统用在了iPhone上，后来又逐渐的用在了iPod touch,iPad等产品上。它是以Darwin为基础的一种类Unix的操作系统，原本这个系统名为iPhone OS，直到2010年6月7日WWDC大会上宣布改名为iOS。
iOS的系统结构分为以下四个层次：核心操作系统（the Core OS layer），核心服务层（the Core Services layer），媒体层（the Media layer），Cocoa 触摸框架层（the Cocoa Touch layer）。
从功能角度来说，iOS和Android还是比较类似的，都具备触摸屏，高级图形显示以及上网功能。相较于Android，iOS运行更加流畅，对硬件的要求没有Android高，同时，它的应用的兼容性要比Android好。而Android在界面上更加注重搜索功能，它对Flash的支持也是一个优势。
2.3.2 objective-c介绍
在开发五子棋程序过程中，除了算法部分使用C++语言进行实现外，其他部分都需要使用Objective-C来实现。
Objective-C 是一种通用、高级、面向对象的编程语言。它扩展了标准的ANSI C 编程语言。将Smalltalk 式的消息传递机制加入到ANSI C 中。它是苹果的OS X 和iOS 操作系统，及其相关API、Cocoa 和Cocoa Touch 的主要编程语言。
Objective-C 最初源于NeXTSTEP 操作系统，之后在OS X 和iOS 继承下来。目前主要支持的编译器有GCC 和Clang，其中Clang 被应用于Xcode 4.0 中。
1980年代初，Brad Cox 与Tom Love 在其公司Stepstone 发明Objective-C，它以一种叫做SmallTalk-80 的语言为基础。Objective-C 创建在C 语言之上，意味着它是在C 语言基础上添加了扩展而创造出来的能够创建和操作对象的一门新的程序设计语言。对Objective-C 最主要的描述是他1986年出版的《Object-oriented Programming, An Evolutionary Approach》。1988年，NeXT Computer 公司获得了Objective-C 语言的授权，并开发出了Objective-C 的语言库和一个名为NEXTSTEP 的开发环境。1992年，自由软件基金会的GNU 开发环境增加了对Objective-C 的支持。1994年，NeXT Computer 公司和Sun Microsystem 联合发布了一个针对NEXTSTEP 系统的标准典范，名为
OPENSTEP。OPENSTEP 在自由软件基金会的实现名称为GNUstep。1996年12月20日，苹果公司宣布收购NeXT Software 公司，NEXTSTEP/OPENSTEP 环境成为苹果操作系统下一个主要发行版本OS X 的基础。这个开发环境的该版本被苹果公司称为Cocoa。
3 需求分析与总体设计
3.1 需求分析
本软件设计的是具有人机对战和人人对战功能的五子棋，相较于PC版的五子棋，在平板上运行的软件界面需要更加简洁，操作更加方便。在人机对战部分，由于CPU的主频不高，为了保证游戏的流畅性，在平板上运行的五子棋的算法实现需要较少的代码，但同时又要保证算法具有一定的智能性，否则就失去了益智的功能。
在整个软件中，需要提供以下功能：1，需要提供一个15*15大小并且可以添加棋子的棋盘。2，需要提供游戏开始功能（重新开始功能），选择游戏类型功能（人机对战和人人对战），提供下子先后手功能。3，人机对战需要提供一定水平的算法，但是算法在运行过程中不能花费太多的事件，同时，人机对战需要提供不同难度的选择。4，人机对战功能需要提供玩家悔棋功能。5，提供自动判断游戏胜利并且在界面上给予提示的功能。6，提供游戏积分榜功能，显示每一方胜利的局数，并且在每局游戏结束后可以马上更新，在应用重新打开时仍然可以正确显示。7，提供游戏认输功能，提供游戏状态（某一方下子，游戏结束等）提示功能。
3.2 系统设计思想
该软件设计的是一款可以在iPad上运行的五子棋游戏，软件打开后直接进入游戏主界面，然后用户通过选择游戏模式，游戏难度，下棋先后手之后开始进行游戏，在游戏过程中软件提供当前状态的提示，玩家在这个过程中可以进行认输，悔棋等操作，当程序判断游戏结束时，程序按照游戏结果更新积分榜。
3.3 系统总体设计
按照系统设计思想，系统的总体设计如下：
3.4 系统模块及功能
3.4.1系统主要模块
系统主要模块如下：
主视图初始化模块：创建并添加棋盘视图，添加积分榜模块视图，认输模块视图，棋盘初始化模块视图，悔棋模块视图。
棋盘初始化模块：清空表示棋子相应信息的数组，将棋盘上之前添加的棋子全部移除。
新游戏设置模块：选择游戏的类型（人机对战和人人对战），人机对战模式还需选择游戏难度，并且两种模式都要选择先后手。
主循环模块：转换下子的一方的颜色。
玩家点击棋盘模块：玩家点击棋盘后，系统根据玩家点击位置将棋子添加进棋盘。
机器人落子算法模块：该模块根据当前棋盘的信息，通过一定的算法，得出最适合下子的坐标。
机器人下子模块：程序根据落子算法模块得到最佳落子地点，然后将该点设置成机器人棋子的颜色。
判断游戏结束模块：玩家点击模块和机器人下子模块调用该模块，该模块通过判断是否有连续五颗同样颜色的棋子在同一条线上来决定是否结束游戏。
认输功能模块：提前结束游戏，并更新积分榜。
悔棋功能模块：在人机对战游戏中，只要游戏还没有结束，玩家就可以通过该模块撤销自己已经在棋盘上下的棋子。
游戏积分榜模块：显示人机对战和人人对战双方各胜利的局数，并在每次游戏结束时更新。
3.4.2系统主要流程
4 五子棋AI算法分析与实现
4.1 算法总体概况
首先介绍在该程序中棋盘的表示，我用char型的值来代表黑子和白字，黑子是机器人，白子是玩家。整个棋盘用一个char型的二维数组来表示。例如：假设这个数组是a[5][5]（棋盘有五行五列），’1’代表是黑子，’2’代表是白字，假如a[0][0]的值是’1’就代表这个棋盘第一行第一列是黑子。
五子棋的AI算法主要包括估值算法和搜索算法。估值算法是指通过一定的算法将棋盘盘面的值计算出来。而搜索算法是指在估值算法的基础上将盘面中最适合摆子的一点找出来。估值算法是基础，调用一次搜索算法就可能需要调用多次估值算法，所以估值的准确性和估值算法的精简性对算法质量的影响非常大。估值算法可以让你知道出现每一种棋局的重要性，而搜索算法就是要在估值的基础上找到真正适合你下子的那点。
4.2 估值算法分析与实现
估值算法就是将整个棋盘相应的分值计算出来。当然，这个分值是相对于某一方来说的。比如此时是玩家下棋，那么此时得到的这个分值就应该是相对于玩家的。假如是机器人下棋，那么此时得到的这个分值就应该是相对于机器人的。那么为什么会产生不同的分值，不同的分值又有什么重要的意义？产生不同的分值那是因为每一种不同的棋面对结果会产生不同的影响，比如该棋局某一方有五子相连，那么只要出现这个棋面，有五子相连的这一方就赢得了整个棋局。然后每一种不同的棋面都要通过分值表现出来，分值越高，出现这种棋盘就越重要。
棋盘的估值主要由三部分组成：棋盘不同点本身占有的分值，子力产生的分值以及己方与对方相邻产生的分值。棋盘中己方的分值和对方的分值就是通过这些部分的分值相加得出来的，在一般的情况下，最后的估值就是己方的分值减去对方的分值。
首先分析棋盘不同点本身创造的分值。这个分值来源于每个点的重要性不同，比如中间的点由于周边可以下子的点更加多所以肯定比边界的点更加重要。所以，中间点的估值最高，然后随着棋盘往外不断的减小。我们需要遍历整个棋盘，在有子的地方将该点的分值加进这个棋子一方的总分值。例如，最中间点的值是10，此时中间点刚好下的是黑子，所以黑子的分值就要加上10.
在五子棋中，有一些不同的子力，比如活四，冲四，活三等等。正是这些不同的子力以及子力的个数影响了棋盘分值的很大一部分。所以，需要通过子力来分析棋盘。
子力又分为己方子力和对方子力，每一种不同的子力有不同的分值。所以，我们先数出己方和对方每一种子力各有几种，然后计算出己方子力总的分值和对方子力的总的分值，在一般的情况下，我们在双方的总分值基础上加上各自的子力部分总分值就构成了最后估值的大部分。但是还有一些特殊的情况，比如出现了五子相连，比如出现了两个活四等，假如使用普通的计算方法，可能会出现问题。例如，假如己方出现了一个五子相连的棋型，这个时候说明己方已经赢得了这盘棋局。但是假如按照一般计算棋盘估值的方法，一个五子相连的棋型估值是100000，而假如对方出现若干个活三，每一个活三的
棋型估值是20000，那么只要出现五个活三，整个棋盘的估值就可能是负数。而假如估值是负数，那么最后得到的走棋的最佳落子点就不会是有可能最后出现这个棋局的那点，所以在这样的情况下使用一般的计算方法是错误的。在出现这种直接影响棋局胜负的特殊棋型时候，我们可以直接返回一个值，这个值就是最后的估值。
下面介绍计算每一方子力部分总分值的实现方法。最重要的是数出每一种不同子力的个数。下面的函数就是计算子力个数的主函数，代码如下：
void Evaluate::findStateNum( char board[ MAX_LINE ][ MAX_LINE ] )
{
//在水平和垂直方向搜索
for( int i = 0 ; i < MAX_LINE ; ++ i )
{
string src_row = "" , src_col = "" ;
for( int j = 0 ; j < MAX_LINE ; ++ j )
{
src_row += board[ i ][ j ] ;
src_col += board[ j ][ i ] ;
}
analyseLine( MYSELF , src_row ) ;
analyseLine( MYSELF , src_col ) ;
analyseLine( RIVAL , src_row ) ;
analyseLine( RIVAL , src_col ) ;
}
//左下-右上搜索(两部分）
for (int i = 0; i < MAX_LINE; i++) {
string src = "" ;
for (int a = 0; a <= i; a++) {
src += board[a][i-a];
}
analyseLine(MYSELF, src);
analyseLine(RIVAL, src);
}
for (int i = 1; i < MAX_LINE; i++) {
string src = "" ;
for (int a = i; a <= MAX_LINE -1 ; a++) {
src += board[a][MAX_LINE-1+i-a];
}
analyseLine(MYSELF, src);
analyseLine(RIVAL,src);
}
//左上-右下搜索（两部分）
for (int i = 0; i < MAX_LINE; i++) {
string src = "" ;
for (int a = 0; a<=MAX_LINE-1-i; a++) {
src += board[a][a+i];
}
analyseLine(MYSELF, src);
analyseLine(RIVAL, src);
}
for (int i = 1; i < MAX_LINE; i++) {
string src = "";
for (int a = i; a<=MAX_LINE-1; a++) {
src += board[a][a-i];
}
analyseLine(MYSELF, src);
analyseLine(RIVAL, src);
}
}
要找出棋盘每一种子力的个数，就要分析每一行的子力情况。由于我的棋子都是使用char类型表示的，所以很容易将一连串的棋子直接连接成一个字符串来表示。所以这个函数的功能主要就是将整个棋盘的每一行的棋子用字符串的形式表示出来，然后调用另一个方法去进行详细分析。下面介绍分析每一行子力情况的函数，部分代码如下：
void Evaluate::analyseLine( char player , string line )
{
char enemy = ( player == MYSELF ) ? RIVAL : MYSELF ;//对手
int current_player = player - '1' ;//将字符转换成int，以利于计算当前选手各种状态的个数
int line_size = line.size() ;//一行总共的个数
int nodeStates[ MAX_LINE ] ;//记录各个点是否被分析过
int leftEdge , rightEdge ;//标志一下搜索的过程中连续的左右边界
memset( nodeStates , UNANALYSED , sizeof( nodeStates ) ) ;//初始化为未被分析过
for ( int i = 0 ; i < line_size ; ++ i )
{
if ( line[ i ] == player && nodeStates[ i ] == UNANALYSED )
{
leftEdge = rightEdge = i ;
//向左搜索
while( leftEdge >= 0 )
{
if ( line[ leftEdge ] != player )
{
break ;
}
leftEdge -- ;
}
//向右搜索
while( rightEdge < line_size )
{
if ( line[ rightEdge ] != player )
{
break ;
}
rightEdge ++ ;
}
++ leftEdge , --rightEdge ;
for( int index = leftEdge ; index <= rightEdge ; ++ index )
{
nodeStates[ index ] = ANALYSED ;
}
if (leftEdge == rightEdge) {
nodeStates[leftEdge] = UNANALYSED;
}
//如果是五连xxxxx
if ( rightEdge - leftEdge > 3 )
{
numOfState[ current_player ][ FIVE ] ++ ;
}
//如果是4连
if ( rightEdge - leftEdge == 3 )
{
//如果是活四_xxxx_
if ( leftEdge > 0 && rightEdge < line_size - 1 && line[ leftEdge - 1 ] == EMPTY && line[ rightEdge + 1 ] == EMPTY)
{
numOfState[ current_player ][ FOUR ] ++ ;
}
//如果是冲四,则有且仅有一侧空，另一侧或者为边界或者为敌方棋子_xxxxo或者oxxxx_
else if ( ( ( leftEdge == 0 || (leftEdge > 0 && line[ leftEdge - 1 ] == enemy ) ) && (rightEdge < line_size - 1 && line[ rightEdge + 1 ] == EMPTY) ) || ( (rightEdge == line_size - 1 || ( rightEdge < line_size - 1 && line[ rightEdge + 1 ] == enemy )) && ( leftEdge > 0 && line[ leftEdge - 1 ] == EMPTY) ))
{
numOfState[ current_player ][ SLEEP_FOUR ] ++ ;
}
}
这个函数的功能主要就是分析每一行中对于某一方的子力的个数并且放入存放子力个数的数组中，函数传入两个参数，一个代表需要分析的代表棋子的字符串，另一个代表是计算哪一方的子力情况。整个方法的实现思路大概如下：将同一行棋子分为已经分析过的和未被分析过的两种，做一个循环，在这个循环中，从左到右找出连续的同一类的棋子一个区域，且这块区域的棋子都是之前未被分析过的，得到这块区域的左右边界，通过左右边界值的差来得到这块区域有这种类型棋子的个数，首先通过连续的同一类型的个数来区分不同子力的情况，比如左右边界的距离是四的话那一定是五子相连了，所以代表该玩家的代表五子相连的状态数需要加一。有一些不能仅仅通过左右边界就确定它的子力情况，这样就需要通过分析这个区域之外的棋子情况得到确认。已经分析过的区域需要将它的棋子状态设为已经分析过以防止这块区域进行重新分析。
除了前两个部分之外，还有另外一个部分那就是己方的棋子和对方的棋子若相邻也需要加上一定的分值，这个分值只是加在己方的分值上而不需要加在对方的分值中。己方的棋子和对方相邻虽然不一定是固定的子力，在计算子力分值时不会将它考虑进去，但是这样的局面确是有利于防守的，对于这个的作用不能简单的忽视。计算的方法是确定一个己方棋子与对方相邻为某一个分值，然后计算出有多少
个这样的相邻，再乘以原来的基数就是这一部分的分值，加到原来己方的分值中。最后将己方的分值与对方的分值相减就构成了最后这个棋局相对于那时刻下子那一方的估值了。
4.3 搜索算法的分析与实现
前面介绍了计算每一个棋面估值的算法以及实现。下面要介绍在估值算法上找出最佳落子点的搜索算法。
搜索算法是怎么起作用的？假设当我们进行下子时，我们可以计算出在每个可以下子的地方下子后棋面的估值，然后找出下子后棋面对于己方估值最高的下子点，并把该点作为最佳下子点。但是这存在一个很大的问题，那就是这个点在此时看似是最佳下子点。但是，走完若干步棋子后，此时估值最大的点未必就是最适合的点了。而搜索算法的目的就是通过分析走几步棋后的局面来找到最佳落子点。
首先介绍在搜索过程中的数据结构，这是一个树的结构，如下图3：
第一层不代表可以实际下子的点，从第二层开始每一层的节点都是代表一个下子点，第二层是己方下子，第三层就是对方下子。我们要找最佳下子点是存在于第二层中的点。这里假设每个父节点下面有两个子节点，即每次可以找出两个点拿来考虑。可以找的点有那么多，这两个点是怎么确定的。我们不可能找出所有的点拿来搜索，所以就通过函数找出两个估值比较大的点，在这个函数里面使用到了估值的算法。我们来模拟一下搜索的过程：首先轮到机器人下子，那么就通过方法找到两个估值最高的点，这两个点是机器人可能会走的。然后接下去到了第三层轮到玩家下子。我们假设玩家的考虑也是这样的，所以在第二层两个节点的每个节点下面各自寻找两个估值最高的点。同样的道理，第四层也是这样。在这里，我们假设只搜索到了第四层，那么第二层左边的点B.1在第三层就有两个点了，第三层的两个点C.1和C.2在第四层也各有两个点了。下面模拟一下搜索过程：首先，我们在D.1和D.2中找出估
值较大的那点，并把该估值转化为对于第三层下子一方的估值（若使用负极大值算法就需要转化），这个估值就是C.1的估值，C.2的估值也是这样。而B.1的估值就从C.1和C.2中得来。同样可以得到B.2节点的估值。最后，再用B.1的估值和B.2的估值进行比较找出他们中间估值较大的那点就是我们的最佳落子点，搜索的过程就类似于上面。
在这里有一个关键的点事如何表示每一层节点的估值，传统的方法时使用极大极小值算法。由于我们通过估值算法得到的是相对于某一方的分值，假设某一个局面对于机器人的分值是100分，那么它相对于玩家的分值就是-100分。极大极小算法就是把所有的节点的估值都转化为相对于机器人的分值，假如是机器人下子就无需转化。但是假如该点是玩家下子，该点使用估值算法得到的估值是相对于玩家的，在这里我们就需要将对于玩家的估值转化为对于机器人的估值，方法就是在原来的估值上面取负。所以，当机器人下子的时候，他就会找值最大的一点，就是极大值点，而当轮到是玩家下子时，他就会寻找值最小的一点，就是极小值点。在上图中，第二层和第四层都是极大值点，第三层是极小值点。第一层是寻找第二层中值最大的那点，所以也可以算是极大值点。
在上面的基础上，我们就可以搜索整棵树找到最佳下子点了。但是，在这样的算法下面，我们需要把整棵树都搜索一遍，耗费的时间很多，特别是当搜索的深度加深时，搜索的数量级是成倍增长的。在这样的基础上我们引进了alpha-beta减枝搜索算法。
如下图4:
上图中A和C所在的都是极大值点，B所在的点是极小值点。B.1的值是10，C.1的值是9。从左到由搜索，当搜索完B.1时，A点的值就是B.1的值。由于A点的值是极大值点，所以B.2得到的值必须要大于10。现在来看B.2的区域，B.2是一个极小值点，由于B.2的值必须要大于10才能作为A点的值，所以B下面的C点都必须要大于10。当我们搜索到C.1的时候，由于它的值是9，而B.2是极小值点。所以B.2的值必然是小于等于9，所以B.2的值必然不会被使用。那么搜索完C.1后就没有必要搜索C.2和C.3了，这就是alpha减枝。
而beta减枝的示例图如下图5：
上图中B.1的值是10，C.1的值是11。搜索完B.1之后，A的值是10，由于A点是极小值点，所以B.2的值就必须小于10才有用。B.2是极大值点，当搜索到C.1时，由于C.1的值是11，所以B.2的值是必然大于等于11，由于它需要小于10才有用，所以当搜索完C.1的值之后就没有必要再搜索C.2和C.3了，这就是beta搜索。
可以看出，alpha和beta搜索可以减少搜索时很多没有必要搜索的节点。但是这个是和节点的排列顺序有关。例如在上图beta减枝示例图中，C.2的值是9，而且是先搜索C.2而不是先搜索C.1，结果就是当搜索了C.2后由于C.2的值要小于B.1的值，所以他还会继续往下搜索，这就照成了不必要的时间损耗。假如搜索节点排列顺序不恰当，可能即使使用了alpha-beta减枝搜索算法也没有任何的时间优化。
在上面的介绍的方法中，是用了极大极小值和alpha-beta减枝搜索算法。但是假如使用极大极小值的话，就必须判断极大值点和极小值点。下面可以对极大极小值算法进行改进，改进后alpha-beta算法就不需要进行alpha减枝，而只需要进行beta减枝。
将极大极小值算法改为负极大值算法就可以实现这一点。在原来的极大极小算法中，需要区分极大值点和极小值点。而负极大值算法的每个节点都是极大值点。它的原理是这样子的：在原来的极小值点中，我们需要找到相对于机器人的值最小的一点，而相对于机器人估值较小的一点就是相对于玩家估值较大的一点，所以就可以转换为求相对于玩家估值较大的一点，这就是极大值点。那么当节点是玩家走棋时，它的节点估值都是相对于玩家的而不是像极大极小算法中都是相对于机器人的。在每个节点中，它的估值都是相对于该节点要下子的一方的，所以我们在不同层的节点之间传递值得时候就需要进行转换，方法就是取负数。极大极小值算法与负极大值算法其实非常类似。只不过是负极大值算法是将极大极小值算法中极小值点的变为极大值点，因为它的上下层值传递时进行了转换。
用了负极大值算法之后，alpha-beta剪枝算法只需要使用beta剪枝这一块了。因为alpha剪枝是极小值点剪去它下面的节点的搜索，而现在已经没有极小值点了，所以只需要用到极大值点。
搜索关键代码如下：
//alpha-beta减枝搜索算法
int Search::alphaBetaSearch( int search_depth , int alpha , int beta , char player )
{
int score ;//估值结果
Node *goodNodes = new Node[ numOfGoodNodes ] ;