本科毕业论文节选——基于C++的棋类游戏自动生成工具的设计与实现

本博文是我本科毕业论文的节选，目录和论文目录不对应。

有极少量的内容改动。

因为源代码已丢失，所以我决定重写代码。

 

1，摘要

目前市场上还只出现了很少一部分的棋类游戏的程序，大部分棋类没有对应的程序。这些棋类游戏的程序都是专门针对一个游戏开发出来的，没办法扩展成其他棋类游戏，因此每开发一种新的棋类游戏都需要不少的成本。实际上棋类游戏共性很强，因此设计并实现一个通用游戏框架是有必要的。

本课题对常见的100种棋类游戏进行了分析和抽象，提炼出了棋类游戏的通用逻辑和流程，并对流程中每个步骤的规则进行了总结和实现常见规则，利用回调函数机制和设计模式实现了可拓展性较强的框架，并在此框架基础上实现了五子棋、黑白棋和老虎棋这三种规则差别较大的棋，从而验证了框架的功能完备性。

利用本框架实现棋类游戏，简单的游戏可以自动生成整个游戏，复杂的游戏只需要提供描述特殊规则的函数也可以生成整个游戏，为了验证框架的性能本课题又实现了另外三种棋类游戏，结果表明本框架可以完成自动生成。

2，主要研究内容

（1）研究如何根据棋类游戏的分类和共性，抽象、提炼出棋类游戏的通用逻辑和流程。

（2）实现棋类游戏的通用编程框架。

（3）将每个步骤的规则进行总结并实现常见规则。

（4）在框架和已实现的规则基础上实现五子棋、黑白棋和老虎棋。

3，棋盘

棋盘不能太过于复杂，要选择可以用若干矩阵表示出来的棋盘。

常见的棋盘分为网络棋盘、点阵棋盘、容器棋盘。其中网络棋盘包括四边形棋盘、圆弧类棋盘、三角形棋盘、凸多边形棋盘、凹多边形棋盘、分枝类棋盘。对于某些棋盘可以做几何拓扑变换。例如下图展示了如何将西瓜棋的棋盘作拓扑变换。

这样的拓扑变换之后就可以用一个7*7的数组记录棋盘中的格点，要想记录连线还需要邻接矩阵。据《棋类游戏100种》一书中统计，在410种棋中，有186种是四边形棋盘。四边形棋盘是不需要拓扑变换的，其他224种棋类绝大部分也是可以通过拓扑变换变成矩阵可存储的格式的。

4，棋位

对于网络棋盘来说，棋位分为三种，顶点式棋位、格式棋位、线段式棋位。其中线段式棋位非常少见，不纳入考虑范围。

顶点式棋位（以网络棋盘的各个顶点作为棋位，如五子棋）和格式棋位（以网络棋盘的各个格作为棋位，如圈叉棋）都很常见，本质上差别不大，实际上即使是线段式棋位也可以通过变换变成顶点式棋位，但是会影响下棋的思路，不可取。

5，棋面符号

按照棋面符号的数量，可以分为无符号棋类、单一符号棋类和多符号棋类。无符号棋类就是所有棋子都是双方共用，单一符号棋类就是双方各一种棋子，多符号棋类就是类似象棋有多种棋子。无符号棋类不太常见，但是和单一符号棋类共性很强，可以纳入考虑范围，多符号棋类不纳入考虑范围。

例如五子棋这种只有黑棋和白棋的游戏，再例如老虎棋，只有老虎和羊2种棋子，都可以纳入考虑范围，而像象棋这种棋子复杂的棋本课题不考虑。

6，着法

棋类游戏的着法包括布子方式、走子方式、吃子方式等。

布子方式有一次性布子、轮流布子、分段布子三种，三种布子方式的不同只在于游戏初始化和下棋之后对棋盘的更新不同，所以都可以纳入考虑范围。

走子方式分为步行和跳行两类，而步行中最常见的两种是直行和斜行，这两种走子方式要考虑，其他的走子方式暂时可以不考虑。

吃子方式包括很多种，其中较常见的是围吃、走吃、跳吃、夹吃等，吃子方式不用限制，框架中有一个专门的函数判断每种局面情况下，被吃掉的所有棋子，并返回一个数组，所以这个不需要限制约束。

7，特殊规则

特殊规则分为两大类：第一类是为了保证游戏正常进行所必须的，例如围棋中的劫争禁手点，第二类是为了维护游戏的公平性和趣味性等，例如五子棋中的黑棋禁手。

如果去掉第一类特殊规则，那么游戏规则体系将是不完备的，会出现下棋下到程序崩溃的情况，但是如果去掉第二类特殊规则，游戏规则体系还是完备的。

在简化复杂度的需求之下，可以考虑去掉第二类特殊规则。实际上，市场上很多很多五子棋程序也是不考虑黑棋禁手的。可能是因为考虑到很多用户并不了解黑棋禁手，也有可能是有些程序员自己都不懂黑棋禁手，又或者可能是为了降低程序复杂度（尤其是带AI的程序）而不考虑黑棋禁手。

8，设计

8.1，解析模块的设计

（1）棋盘

目前只考虑2类最常见的棋盘，一种是矩形棋盘，另一种是在水平竖直线的基础上加上若干个米字型格点的棋盘，这2种棋盘涵盖的范围非常广，对于没有涵盖到的情况，也可以直接拓展，不影响框架的使用。这样，只需要初始化board[maxr][maxc]和ismi[maxr][maxc]这2个数组，即可记录棋盘的所有信息。board数组记录每个格点的信息，有4种取值，0表示一方的棋子，1表示另外一方的棋子,-1表示空，-2表示无效格子。ismi记录每个格点是否是米字型格点，有了board和ismi这2各数组，就可以确定所有的相邻关系，从而确定整个棋盘。

（2）棋规

棋规对应的是下棋模块的功能，下棋模块涉及到非常复杂的函数调用关系，这也是本框架的核心所在，即将复杂的逻辑总结并实现出来，使用本框架时就不需要再考虑这些复杂的逻辑了。如图显示了下棋模块的详细流程。

本框架并没有实现将各种不同的行棋规则抽象成数据可描述的程度，本框架只是将棋类游戏的核心逻辑和流程抽象并实现，而流程的每一个具体的步骤，每个棋类游戏都不尽相同，本框架采用桥接模式解决这个问题，在主流程中有若干抽象函数，而各个棋类游戏负责提供具体函数，这样就完成了整个游戏。然而实际上，每个步骤对应的规则都有常见的几种，不同的棋类游戏其实就是每个步骤的不同规则的组合，所以本框架拟总结并实现每个步骤中常见的规则，这样，描述一个棋类游戏的棋规只需要一些id和参数，每个id对应一个步骤的某个具体规则，这样，由解析模块解析这些id就可以描述整个棋规。为了实现这个架构，本框架采用函数指针数组和回调机制，每个步骤就对应一个函数指针数组，数组中每个函数指针都是一个具体函数，在抽象函数中利用解析到的id即可回调。

8.2 棋盘模块的设计

根据解析模块得到的棋盘信息（board[maxr][maxc]和ismi[maxr][maxc]这2个数组）即可完成自动绘制棋盘，棋盘有2大类（一种是矩形棋盘，另一种是在水平竖直线的基础上加上若干个米字型格点的棋盘），分别采取不同的方案进行绘制，都是采用制表符，一种方案是紧密型棋盘，每个格点要么画棋子，要么画棋盘，格点之间紧密相连，这种方案适合矩形棋盘。另一种方案是松散型棋盘，每个格点要么画棋盘，要么打印空格，格点和相邻的格点之间全部用线条连接，这种方案适合在水平竖直线的基础上加上若干个米字型格点的棋盘，实际上所有棋盘都可以用这种方案来绘制，只是对于相邻关系比较复杂的棋盘需要拓展数据结构才能描述相邻关系，但这个绘制棋盘的方案仍然是可行的。

8.3 下棋模块的设计

下棋模块包括解析输入、判断能否落子、落子、判断胜负这4个步骤，每个步骤都根据解析模块解析出的id来确定对应的规则。下面一一讲述每个步骤是如何设计的。

（1）解析输入

行棋方式如果是落子就需要输入2个整数，行棋方式如果是移子就需要输入4个整数，有些游戏的双方，一方是落子而另一方是移子，所以为了统一数据结构，对于解析输入、判断能否落子、落子、判断胜负这4个步骤，每个步骤都需要2个id，分别表示下棋双方对应的规则。

（2）判断能否落子

行棋方式包括落子和移子两种，但是根据博弈论的思想，为了更加统一地表述，可以把移子理解并表述为在一个四维空间落子，所以这里的判断能否落子实际上指的是判断能否落子或移子，下面将分别讨论本框架是如何抽象出统一的逻辑的。

本框架将判断在目标坐标处能否落子的逻辑总结如下：首先，目标坐标必须在棋盘范围内，而且必须是空的，即没有双方棋子。其次，有些游戏还有其他附加规则，有些游戏没有。例如五子棋，没有其他规则，而黑白棋，附加规则是在目标坐标处落子之后，必须改变其他地方的至少一个棋子，否则不能落子。本框架将黑白棋的这种规则进行抽象，不需要具体判断落子会改变哪些棋子，而只需要调用落子函数，然后比较前后差异即可。

本框架将判断能否移子的逻辑总结如下：（为了表述方便，把移子表述成将出发坐标处的棋子移动到目标坐标处）首先，出发坐标和目标坐标必须在棋盘范围内，而且目标坐标必须是空的，而出发坐标必须有正在下棋方的棋子。其次，每种棋子移动的规则都不一样，但是可以归为三类：移动到相邻位置、跳吃子、固定方式的路线。这里的跳吃子指的是沿着一个方向跳过对方棋子并降落在空处，同时吃掉对方棋子。

（3）落子

这里的落子也是包含两种情况，一种是狭义的落子，一种是移子。

对于第一种情况，落子，落子函数只负责在指定坐标处落子，不负责其他任何功能。落子函数不做任何有关判断能否落子的计算，更不能调用判断能否落子的函数，否则会造成逻辑循环，可能会导致程序死循环。因为在判断能否落子时可能会调用落子函数，也就是落子函数接收的坐标不一定是真实可以落子的坐标，但一定是棋盘范围内的坐标，所以不需要对坐标做范围检测，但是必须保证程序不会造成死循环。

对于第二种情况，移子，因为判断能否落子时不需要调用落子函数，所以这里的落子函数可以调用判断能否落子的函数，因为有些棋子不止一种移子方式，所以需要调用判断能否落子的函数。

（4）判断胜负

判断胜负的函数，需要在任何时刻判断当前局面游戏是否已经结束，如果结束了，判断是先手胜还是后手胜还是平局。判断胜负是棋类游戏最多样的地方，几乎所有棋类游戏之间判断胜负的规则都不一样，不过本框架还是对最常见的几种情况进行了抽象并实现。最常见的几种情况是：第一种，如果还能落子就继续游戏，不能落子就判为负方。第二种，如果还能落子就继续游戏，不能落子就换对方落子，对方也不能落子就结束游戏。第三种，一方棋子数量到达某个范围就结束游戏。第四种，成形目棋类，一方形成某种棋形就结束游戏，否则就按照前三种情况的某一种来处理。除了这四种最常见的情况之外，也有其他特殊复杂规则，但是都类似于第四种情况，先判断特殊规则，如果没有结束游戏的话再按照前三种规则判断。

8.4 棋谱和悔棋模块的设计

完整的棋谱，应该包括两部分，每一步是谁下，每一步下的位置。因为有些棋并不是严格地双方轮流下，例如黑白棋，所以记录每一步是谁下能更好地显示信息。但是这并不是必须的，因为棋谱的最重要两个功能是方便调试和用来实现悔棋功能，调试的时候需要支持把整个棋谱粘贴到控制台，然后自动地执行每一步行棋，而悔棋就是直接读取棋谱中的数据然后执行每一步行棋。为了方便调试（实际上不仅是调试，当下棋者需要回顾之前的某一步的时候，也是同样的道理，利用棋谱直接粘贴跳转到需要的那一步，比不断悔棋方便些），在显示棋谱的时候要依次输出每一步下的位置，然后调试者（或者下棋者）可以直接复制棋谱，然后粘贴即可。所以，显示棋谱的时候是不能带每一步是谁下的信息的，棋谱可以存这个信息，但不能打印出来，而把棋谱直接粘贴到控制台的时候，程序就必须支持运行时自动判断每一步是谁下，所以棋谱是完全不需要存每一步是谁下的。这样，棋谱的设计就完成了，只存储每一步下的位置。下一章将详细介绍各个功能是如何实现的。

悔棋功能就是从开局开始，按照棋谱处理除掉最后一步的每一步，这样就实现了悔棋功能。有些游戏可以按照落子规则进行回溯，不需要棋谱即可实现悔棋，例如五子棋，只需要知道最后一步下的位置即可实现悔棋，当然，要实现连续不限次数的悔棋的话还是需要存棋谱，但是仍然不需要从开局开始一步步处理，这样时间效率就比较高。但是，有些游戏是无法按照落子规则进行回溯的，例如黑白棋，即使知道当前局面和最后落子位置，也无法推断出落子之前的局面，因为可能会有多种情况。所以，为了实现统一的悔棋功能，本框架采用的方案是所有游戏悔棋都利用棋谱从开局开始一步步处理。

9，实现

别人家的APP：

我的实现：

10，测试

（1）五子棋

测试项目	测试用例编号	操作步骤	预期结果	测试结果
五子棋	test017	打开五子棋，输入“7 7      6 6  6 7 5 7 7 5 7 6      8 6  6 8 9 7  6 4  10 8  11 9  8 7 10 7 8 5  8 4  8 8  8 9  9 5  6 5  9 8  11 8 9 6  9 4  9 9”	先手胜	成功
五子棋	test018	打开五子棋，输入“7 7      7 8  6 7  6 8  8 7   8 8  9 7  9 8  5 8  10 8”	后手胜	成功
五子棋	test019	打开五子棋，输入构造的和局的棋谱（下图）	和局	成功

 

 

 

 

 

 

 

 

 

 

 

（2）黑白棋

测试项目	测试用例编号	操作步骤	预期结果	测试结果
黑白棋	test020	打开黑白棋，输入构造的先手被全灭且包含连下操作的棋谱（图4-6）	先手被全灭，后手胜，进行连下操作	成功
黑白棋	test021	打开黑白棋，输入构造的下满棋盘，先手胜的棋谱（图4-6）	下满棋盘，先手胜	成功
黑白棋	test022	打开黑白棋，输入构造的双方都不能下，结束游戏的棋谱（图4-6）	双方都不能下，结束游戏	成功
黑白棋	test023	打开黑白棋，输入构造的和局的棋谱（图4-6）	和局	成功

 

 

 

 

 

 

 

 

 

 

 

（3）老虎棋

测试项目	测试用例编号	操作步骤	预期结果	测试结果
老虎棋	test024	打开老虎棋，输入构造的老虎胜的棋谱（图4-7）	老虎胜	成功
老虎棋	test025	打开老虎棋，输入构造的羊胜的棋谱（图4-7）	羊胜	成功