北方工业大学继续教育学院本科毕业论文（设计）

3. 帮助模块；游戏规则、有关本软件的介绍。 本系统的主要功能模块，如下图2.9所示

五子棋游戏游戏选项新游戏人机对战人人对战退悔认出棋输

图2.9系统主要功能模块图

8

北方工业大学继续教育学院本科毕业论文（设计）

3 总体设计

3.1 系统环境要求

服务器：要求处理器为Pentium III 兼容处理器或更高速度的处理器，处理器速度最低要求：600 MHz，推荐使用：1 GHz 或更高，80GB或以上可使用硬盘空间内存最低要求：512 MB，推荐使用：1 GB 或更大，最大：操作系统最大内存。

客户机：要求处理器为Pentium III 兼容处理器或更高速度的处理器，处理器速度最低要求：600 MHz，推荐使用：1 GHz 或更高，内存最低要求：512 MB，推荐使用：1 GB 或更大，最大：操作系统最大内存。

3.2 总体设计过程

总体设计过程通常由四个主要阶段组成：系统体系结构设计，确定系统的具体体系结构实现方案；系统模块设计，确定系统模块层次；结构算法设计，确定软件结构和典型算法；交互设计，确定系统的交互界面。

高效率的程序基于良好的数据结构与算法，一般来说，数据结构与算法就是一类数据的表示及其相关的操作。从数据表示的观点来看，存储在数组中的一个有序整数表也是一种数据结构。算法是指对数据结构施加的一些操作。一个算法如果能在所要求的资源限制范围内将问题解决好，则称这个算法是有效率的。一个算法如果比其他已知算法所需要的资源都少，这个算法也称为是有效率的。算法的代价是指消耗的资源量。一般来说，代价是由一个关键资源，例如时间或空间来评估的。

3.3 系统的算法设计

五子棋游戏的开发在搜索算法方面，可以有多种选择。通过从不同的角度分析各种搜索方法的效率，来考虑本系统的算法应用。

下面详细地介绍一些算法： 3.3.1

博弈树

设想下五子棋的情形，两人对弈，我们将其中一位叫做甲，另一位叫做乙。假定现在该甲下棋，甲可以有225种走法（不论好坏）；而对甲的任一走法，乙也可以有与之相对的若干种下法。然后又轮到甲走棋，对乙的下法甲又有若干种方法应对。如此往复。显然，我们可以依此构建一棵博弈树，将所有的走法罗列出来。在这棵树的

9

北方工业大学继续教育学院本科毕业论文（设计）

根部是棋局的初始局面。根的若干子节点则是由甲的每一种可能走法所生成的局面，而这些节点的子节点则是由与之相对的乙的每一种可能走法所生成的局面。在这棵树的末梢，是结束的棋局，甲胜或者乙胜或者是双方都无法取胜的平局。如果我们令甲胜的局面值为WIN，乙胜的局面值为LOST，而和局的值为DRAW。当轮到甲走时，甲定会选择子节点值为WIN或DRAW（如果没有值为WIN的子节点的话）的下法；而轮到乙时，乙则会选择子节点值为LOST或DRAW（如果没有值为LOST的子节点的话）的下法。对于中间节点的值可以有如下计算方法：如果该节点所对应的局面轮到甲下棋，则该节点的值是其所有子节点中值最佳（对甲而言）的一个的值；如果该节点所对应的局面轮到乙走棋，则该节点的值是其所有子节点中值最差（对甲而言）的一个的值。这样看来从这棵树的叶子节点倒推向根部，就可以得出所有节点的值。双方就可以从其所面临的棋局中选择一步好棋。然后一步步走向胜利。博弈树是从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树，这里称为完全搜索树。Neill Graham形容此过程类似于在一个状态图中寻求从初始状态通向终了状态的过程。只是状态图搜索仅有一个主体参加，仅是单方面做出的路径选择。而博弈树的搜索则有对立的双方参加，一方只能做出一半选择，而这一半选择的目的是使对方远离其竭力靠近的目标。也就是说状态图搜索是纯粹的或树（OR tree），而博弈树搜索是与或树（AND/OR tree）。

但是在五子棋游戏中，我们没有建立完全搜索树的可能。一方面是因为很多情形根本就到达不了叶子节点。另一方面，这棵树上的节点数量也已多到了无法处理的程度。所以我们需要其它的算法来减少搜索的数量。 3.3.2

极大极小值算法（Minimax Algorithm）

在上面的博弈树中，如果我们令甲胜的局面值为1，乙胜的局面值为-1，而和局的值为0。当轮到甲下棋时，甲定会选择子节点值最大的下法；而轮到乙时，乙则会选择子节点值最小的下法。所以，对于中间节点的值可以有如下计算方法：如果该节点所对应的局面轮到甲下棋，则该节点的值是其所有子节点中值最大的一个的值。而如果该节点所对应的局面轮到乙下棋，则该节点的值是其所有子节点中值最小的一个的值。

对博弈树的这个变化仅仅是形式上的，本质上丝毫未变，但是这个形式更容易推广以运用到一般实际的情形。

10

北方工业大学继续教育学院本科毕业论文（设计）

既然建立整棵的搜索树不可能，那么，为当前所面临的局面找出一步好棋如何？也就是通过少量的搜索，为当前局面选择一步较好的走法。

在通常的棋局当中，一个局面的评估往往并不像输、赢、平3种状态这么简单，在分不出输赢的局面中棋局也有优劣之分。也就是说，要用更细致的方法来刻画局面的优劣，而不是仅仅使用1、-1、0三个数字刻画3种终了局面。假定我们有一个函数可以为每一局面的优劣评分。例如甲胜为+∞；乙胜为-∞；和局为0；这样我们可以建立一棵固定深度的搜索树，其叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子节点的最小值。这个评分的函数称作静态估值函数（Static Evaluation Function）。用以取代超出固定深度的搜索。显然，我们无法拥有绝对精确的静态估值函数。否则，只要这个静态估值函数就可以解决所有的棋局了。估值函数给出的只是一个较粗略的评分，在此基础上进行的少量搜索的可靠性，理论上是不如前述的WIN，LOST，DRAW三种状态的博弈树的，但这个方法却是可实现的。利用具体的知识构成评估函数的搜索叫做启发式搜索（Heuristic Search）。估值函数在有些文献中也称为启发函数（Heuristic Function）。

在博弈树搜索的文献当中，极大极小方法往往指的是基于静态估值函数的有限深度的极大极小搜索。MinMax算法是对弈的基础思想。 3.3.3

负极大值算法（Negamax Algorithm）

普通的极大极小值算法看起来有一点笨，既然一方试图取极大值而另一方试图取极小值——也就是说——我们总要检查哪一方要取极大值而哪一方又要取极小值，以执行不同的动作。Knuth和Moore在1975年提出了负极大值（Negamax）方法，消除了两方的差别，而且简洁优雅。使用负极大值方法，博弈双方都取极大值。 3.3.4

Alpha-Beta搜索

在极大极小搜索的过程中，存在着一定程度的数据冗余。举一个最简单的例子：在象棋博弈的过程中，如果某一个节点轮到甲走棋，而甲向下搜索节点时发现第一个子节点就可以将死乙（节点值为最大值），则剩下的节点就无需再搜索了，甲的值就是第一个子节点的值。这个过程，就可以将大量冗余的（不影响结果的）节点抛弃。

将上述这个情形推广一下，设想有如图3.1左半部所示的一棵极大极小树的片断，节点下面数字为该节点的值，节点B的值为18，节点D的值为16，由此我们可以判

11