五子棋游戏双人对战版软件设计

2012-2013学年第1学期“软件工程”课程设计报告

目录

第一章五子棋双人对战版软件问题描述 (4)

1.1 五子棋的相关介绍 (4)

1.1.1 五子棋的简介 (4)

1.1.2 五子棋规则 (4)

1.2 五子棋双人对战版软件 (4)

1.2.1 软件设计思想 (4)

第二章五子棋双人对战实现的算法分析 (5)

2.1传统五子棋算法介绍及初步实现 (5)

2.1.1 估值函数 (5)

2.1.2 Alpha–Beta 搜索 (6)

2.1.3 胜负判断 (8)

2.2 五子棋算法的优化 (8)

2.2.1 减少搜索范围 (8)

2.2.2 设置下棋风格 (9)

2.2.3 增大搜索层数 (9)

2.2.4 使用置换表 (9)

2.2.5 启发式搜索 (9)

第三章需求分析报告 (10)

3.1 介绍 (10)

3.1.1 目的 (10)

3.1.2 文档约定 (10)

3.1.3 面向的读者和阅读建议 (10)

3.1.4 参考文献 (11)

3.2 整体描述 (11)

3.2.1 功能需求 (11)

3.2.2 性能需求 (12)

3.2.3 数据流图 (13)

3.3 系统特点 (13)

3.3.1 系统特点 (13)

3.3.2 系统功能 (13)

3.4 外部接口需求 (14)

3.4.1 用户界面 (14)

3.4.2 硬件接口 (14)

3.4.3 软件界面 (14)

3.5 其他非功能需求 (14)

3.5.1 系统交付日期 (14)

3.5.2 系统需求 (14)

3.6 软件总流程图 (15)

第四章设计与实现 (16)

4.1 基本设计概念和处理流程 (16)

4.2 结构 (16)

4.3 功能设计 (17)

4.3.1 软件的基本功能设计 (17)

4.3.2 软件的附加功能设计 (17)

4.4 接口设计 (17)

4.4.1 用户接口 (17)

4.4.2 外部接口 (18)

4.4.3 内部接口 (18)

4.5 界面设计 (18)

4.5.1 界面设计运用的主要方法 (18)

4.6 系统数据结构设计 (20)

4.6.1 逻辑结构和物理结构设计要点 (20)

4.6.2 数据结构与程序的关系 (22)

4.7 系统出错处理设计 (23)

4.8 软件运行结果 (23)

第五章测试 (26)

5.1 黑盒测试 (26)

第一章五子棋双人对战版软件问题描述

1.1 五子棋的相关介绍

1.1.1 五子棋的简介

五子棋是一种两人对弈的纯策略型棋类游戏，棋具与围棋通用，是起源于中国古代的传统黑白棋种之一。发展于日本，流行于欧美。容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。

1.1.2 五子棋规则

无禁手玩法：黑先白后，谁先连五谁胜。

禁手玩法：黑先行棋，黑棋只能走冲四活三胜，黑双活三禁手双冲四禁手四三三禁手四四三禁手六连长连禁手；白后手，白棋无任何禁手，还可以抓黑棋的禁手点取胜。

职业规则玩法：三手交换五手两打，黑棋有禁手，意思是下到第三手棋执白方有权选择交换下黑棋或者继续行棋，下到第五手时执黑方给出两个打点让执白方选择去掉一个打点下剩下的打点。

1.2 五子棋双人对战版软件

1.2.1 软件设计思想

人对人游戏，其实只是对游戏规则的实现，我们只是利用五子棋游戏的规则以及五子棋的经典算法来编程，这些规则和算法，我们将用相应的函数来实现。

一个优秀的游戏软件必须有一个正确的设计思想通过合理地选择数据结构、操作系统以及开发环境构成一个完善的体系结构才能充分发挥计算机应用的优势。根据游戏玩家的实际需求本系统的设计按照下述原则进行：实用性、先进性、高可靠性、可维护性、可扩展性及灵活性、智能性。

第二章五子棋双人对战实现的算法分析

2.1传统五子棋算法介绍及初步实现

2.1.1 估值函数

不同的棋型，其优先级不同。例如，四个棋子连成一线且还能继续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或死三）好。要使计算机正确地做出这种判断，就要把第一种棋型的估值设高。事实上，对于每一种特定的棋型，都需要相应的估值来反映其优劣情况。另外，由于搜索模块频繁地调用估值函数，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。估值时，需要从四个方向上来考虑所下棋子对当前盘面的影响。这个方向分别是以该棋子为出发点，水平、竖直和两条为45 度角和135 度角的线。为方便分析棋盘上的格局，本文中约定以“A”代表黑子，“B”代表白子，“？”代表棋盘上空位。算法中关于棋子死活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤的出路，则称该棋型是活的。否则称该棋型是死的。比如关于活三的定义：不论对手如何落子，仍然至少有一种方法可以冲四。因此，B?AAA? B 中的三个A，不能算是活三；B?AAA??B 中的三A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能比较细致。

本文算法对特定棋型的估值如表1 所示。

表一：特定棋型的估值

2.1.2 Alpha–Beta 搜索

在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。一般地只生成一定深度的博弈树，然后进行极小极大搜索。极大极小搜索是指：在一棵博弈树中，当轮到甲走时，甲定会选择子节点值最大的走法；而轮到乙走时，乙则会选择子节点值最小的走法[3]。使用估值函数对博弈树的每一个局面进行估值后，就可以通过极大极小搜索在博弈树中寻找最佳的合法走法。在极大极小搜索的过程中，存在着一定程度的数据冗余。如图1 左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A 节点表示计算机走，由于A 是极大值点，根据极小极大搜索原理它要从B 和C 当中选最大的值。假设目前已经通过估值得出B 为18，当搜索C 节点时，因为C 是该人走，所以根据极小极大搜索原理要从D、E、F 中选取最小的值。此时如果估出D 为16，那么C 的值必小于或等于16。又因为已经得出B 的值为18，说明节点A 的值为Max（B，C）=18，也就是说无须求出节点C 的其他子节点如E、F 的值就可以得出父节点A 的值。这种将节点D 的后继兄弟节点剪去的方法称为Alpha 剪枝。同理，在图1右半部一棵极大极小树的片段中，将节点D 的后继兄弟节

点剪去称为Beta 剪枝。

图1 Alpha-Beta 剪枝

将Alpha 剪枝和Beta 剪枝加入极大极小搜索，就得到Alpha-Beta 搜索算法，该算法描述如下：

int AlphaBeta(int depth, int alpha, int beta)

{

if depth 为0，说明当前节点是叶子节点then返回对当前棋局的估值

else

while 还存在可能的走法

{

走一步棋，从对手角度进行-AlphaBeta(depth-1,-beta，-alpha)的递归搜索，记录返回值为val

撤消刚才走的一步

若 val 大于等于beta，则返回beta 的值

若 val 大于alpha，则修改alpha 的值为val

}

end while

end if

返回 alpha

}

其中depth 记录搜索的深度，alpha 记录搜索到的最好的值，beta 记录对于对手来说最坏的值。如果INFINITY 表示无穷大，则AlphaBeta(3, -INFINITY, INFINITY)表示完成一次3层的搜索。