象棋游戏课程设计

2021年1月27日发(作者：姜胜玲)
算法设计与分析


目

录

1
引

言

......................... ............................ 1

1.1

问题的提出
...............................................
1

2.

需求分析
................................................ 3

2.1
系统运行环境

.
............. ................................
4

2.2
问题描述

.
..................... ............................
4

3
概要设计

.
....................... ............................
6

4
系统流程图
................................................. 7

5
详细设计

..................... .............................. 9

5.1

棋盘棋子表示
.............................................
9

5.2
着法生成

.
........... .....................................
1
1

5.3

搜索算法
................................................
1
3

5.4
置换表

.
....... ...........................................
1
7

5.5

调试分析
................................................
1
8

6
源程序
.................. .................................. 18

7
心得体会
.................................................. 32

参考文献

.......................... ..........................
3
3



I
算法设计与分析

1
引

言

1.1
问题的提出

计算机博弈是人工智能研究的 一个重要分支，被专家门称为人工智能
界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成 果，这
些成果在人工智能领域产生了重要影响。国际象棋计算机博弈研究已经有
了五十多年的历 史，
IBM
公司在
1997
年开发出了超级计算机“深蓝”战胜
了当 时世界公认第一的国际象棋大师卡斯帕罗夫，标志其水平已超过国际
象棋世界冠军。而中国象棋的历史更 为悠久，早在
2000
多年前的战国时代
就已经有了关于象棋的记载。中国象棋计算机 博弈的难度绝不会低于国际
象棋，图
1.1
是几种棋类游戏空间复杂度和树复杂度对比 ，其中中国象棋
的空间负责度是国际象棋的
100
倍，而树复杂度则达到了
1 0
27
倍。

表
1.1
几种棋类空间复杂度和树复杂度对比



中国象棋计算机博弈起步 晚，七十年代末才有相关的研究文献，比国
际象棋晚了近
20
年，相对国际象棋计算机 博弈技术还不够成熟。但近年来
通过许多中国象棋软件编程爱好者和多个象棋开发团队的努力，使中国象
棋软件水平有了长足的进步，慢棋已达到业余大师水平，快棋可以和象棋
大师对抗。但要设计出 打败人类的中国象棋软件，还需要一段发展过程。

许多学者认为，对于人工智能研究而言，象棋的重要作用相当于遗传

1
算法设计与分析

学研究的果蝇。就是说人类对机器博弈的研究衍生了大量的研究成果 ，这
些成果对更广泛的领域产生了重要影响。人工智能的先驱者们曾认真地表
明
:如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心
;
那些能
够存在于下 棋活动中的重大原则，或许就存在于其它任何需要人类智能的
活动中。因此对于中国象棋人机博弈问题的 研究意义重大。



2

算法设计与分析

2.

需求分析


1.
走棋和吃子
< br>对局时，
由执红棋的一方先走，
双方轮流各走一着，
直至分出胜、
负、
和，对局即终了。轮到走棋的一方，将某个棋子从一个交叉点走到另一个
交叉点，或者吃掉对方 的棋子而占领其交叉点，都算走一着。双方各走一
着，称为一个回合。


2
、各种棋子的走法

?
帅（将）：
帅和将是棋中的首脑， 是双方竭力争夺的目标。它只能在

九宫

之内活动，可上可下，可左可右，每次 走动只能按竖线或横

线走动一格。
帅与将不能在同一直线上直接对面，否则走方判负。

?
仕（士）：
仕（士）是帅（将）的贴身保镖，它也只能在九宫内走动。它
的行棋路径只能是九 宫内的斜线。

?
相（象）：
相（象）的主要作用是防守，保护自己的帅（将 ）。它的走法
是每次循对角线走两格，俗称

象走田

。相（象）的活动 范围限于

河界

以
内的本方阵地，
不能过河，
且如果 它走的

田

字中央有一个棋子，
就不能走，
俗称
塞象眼

。

?
车：
车在象棋中威力最大，无论横线、竖 线均可行走，只要无子阻拦，步
数不受限制。因此，一车可以控制十七个点，故有

一车 十子寒

之称。

?
炮：
炮在不吃子的时候，走动与车完全相 同。炮与被吃子之间必须隔一个
棋子，进行跳吃，俗称

架炮

或

炮打隔子

。


3
算法设计与分析

?
马：
马走动的方法是一直一斜，即先横着或直着走一格，然后再斜着走一
个 对角线，俗称

马走日

。马一次可走的选择点可以达到四周的八个点，故
有

八面威风

之说。如果在要去的方向有别的棋子挡住，马就无法走过去，< br>俗称

蹩马腿

。

?
兵（卒）：
兵（ 卒）在未过河前，只能向前一步步走，过河以后，除不能
后退外，允许左右移动，但也只能一次一步。< br>
3
、吃子：
任何棋子走动时，如果目标位置上有对方的棋子，就可以把对方< br>的棋子拿出棋盘，再换上自己的棋子（即

吃子

）。

2.1
系统运行环境

(1)
硬件环境

本系统适 用于那种
Inter386
以上计算机，
内存容量为
128M
，应配备，
键盘，
鼠标，显示器等外部设备。

(2)
软件环境


本系统的设计采用
Visual C++6.0
编写。在
Windows XP SP2
环境下测试
通过

(3)
本游戏软件在
Windows
平台下都可以运行。

2.2
问题描述

象棋是一种双方对阵的竞技项目。棋子共有三十二个，分为 红黑两组，各
有十六个，由对弈的双方各执一组。兵种是一样的，分为七种：


红方：红方有帅一个，仕、相、车、马、炮各两个，兵五个。


黑方
:
黑方有将一个，士、象、车、马、炮各两个，卒五个。


其中帅与将；仕与士；相与象；兵与卒的作用完全相同，仅仅是为了
4

算法设计与分析

区别红棋和黑棋而已。


棋子活 动的场所，叫作

棋盘

。在长方形的平面上，绘有九条平行的
竖线和十 条平行的横线相交组成，共有九十个交叉点，棋子就摆在交叉点
上。中间部分，也就是棋盘的第五，第六 两横线之间末画竖线的空白地带
称为“河界”。两端的中间，也就是两端第四条到第六条竖线之间的正方
形部位，以斜交叉线构成“米”字方格的地方，叫作“九宫”（它恰好有
九个交叉点）。


整个棋盘以“河界”分为相等的两部分。为了比赛记录和学习棋谱方
便起 见，现行规则规定：按九条竖线从右至左用中文数字一
-
九来表示红方
的每条竖线，用 阿拉伯数字‘1’～‘9’来表示黑方的每条竖线。对弈开
始之前，红黑双方应该把棋子摆放在规定的位 置。任何棋子每走一步，进
就写“进”，退就写“退”，如果像车一样横着走，就写“平”。


任何棋子在走动时，如果乙方棋子可以到达的位置有对方的棋子，就
可以把对 方棋子拿出棋盘
(
称为吃子
)
而换上自己的棋子。只有炮的

吃子

方式与它的走法不同：它和对方棋子之间必须隔一个子（无论是自己的还
是对方的 ），具备此条件才能

吃掉

人家。一定要注意，中隔一个棋子，
这个棋 子俗称“炮架子”。帅和将被吃或不能动弹即输棋。下面是具体的
界面：






5
算法设计与分析

3
概要设计

首先将棋盘的每一格坐标化，横坐标从
01
开 始到
09
。纵坐标从
01
开
始到
10
，初始横坐标
01
行上摆放红子棋子，
01
放车、
02
放马、
0 3
放象、
04
放士、
05
放帅，
06
、
0 7
、
08
、
09
对称放士、象、马、车。横坐标
03
行
02
、
08
列放炮，横坐标
04
行
01
、
03
、
05
、
07
、
09
列放兵。绿 子旗子和红
子棋子对称放在对面。在这个初始化的坐标上每一个棋子都对应的有一个
点，
并且对应一个数，
红子棋子从车
（
i=0
）
开始一直到帅，
for(i=0;i<5;i++);
x[i][1]=x[10-i][1]=i+10;
既从车到帅对应的数为：
11
，
12
，
13
，
1 4
，
15
；
兵为
17
，炮为
16
；绿子棋 子：
x[i][10]=x[10-i][10]=i+20;
既从车到帅
对应的数 为：
21
，
22
，
23
，
24
，
25
；卒为
27
，炮为
26
；具体如下图：





6

算法设计与分析

4
系统流程图

7


算法设计与分析

5
软件系统结构图


界面框架模块

中国象棋通用引擎协议层
(UCCI)
着

法

生

成

棋

盘

估

值

搜

索

引

擎



棋盘数据结构



8

算法设计与分析

5
详细设计

5.1
棋盘棋子表示

使用位棋盘技术，我们的棋盘是一个大小为
16x16
的二维数组，即程
序里的
ucpcSquares[256]
。象棋只有
10x9
的大小，用
16x16
的二维数组
似乎有些浪费，然而这给程序带 来了很多好处。


(1)
，免去了烦琐的边界判断
(
只要 预先给
10x9
外的其他棋格赋值一
个非空的虚拟棋子即可
)
。

(2)
，我们可以根据棋子的位置数字
potion(0-255)
快速得到行列信
息，

行号
= potion>>4
；

列号

=
(potion<<4) >> 4














9
算法设计与分析

00

01

02

03

04

05

06

07

08

09

0a

0b

0c

0d

0e

0f

10

11

12

13

14

15

16

17

18

19

1a

1b

1c

1d

1e

1f

20

21

22

23

24

25

26

27

28

29

2a

2b

2c

2d

2e

2f

30

31

32

33

34

35

36

37

38

39

3a

3b

3c

3d

3e

3f

40

41

42

43

44

45

46

47

48

49

4a

4b

4c

4d

4e

4f

50

51

52

53

54

55

56

57

58

59

5a

5b

5c

5d

5e

5f

60

61

62

63

64

65

66

67

68

69

6a

6b

6c

6d

6e

6f

70

71

72

73

74

75

76

77

78

79

7a

7b

7c

7d

7e

7f

80

81

82

83

84

85

86

87

88

89

8a

8b

8c

8d

8e

8f

90

91

92

93

94

95

96

97

98

99

9a

9b

9c

9d

9e

9f

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

aa

ab

ac

ad

ae

af

b0

b1

b2

b3

b4

b5

b6

b7

b8

b9

ba

bb

bc

bd

be

bf

c0

c1

c2

c3

c4

c5

c6

c7

c8

c9

ca

cb

cc

cd

ce

cf

d0

d1

d2

d3

d4

d5

d6

d7

d8

d9

da

db

dc

dd

de

df

e0

e1

e2

e3

e4

e5

e6

e7

e8

e9

ea

eb

ec

ed

ee

ef

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

fa

fb

fc

fd

fe

ff

图“出棋制胜”软件的棋盘表示



10

算法设计与分析

5.2
着法生成


由于采取了
16x16
的棋盘数组来表示棋子位置，所以一步着法可以表
示成：
sGX< br>，
sGY
，
eGX
，
eGY4
个
[0
到
15]
之间的数字，
合并成一个则为
0-65535
之间的整数 。


(1),
我们将在图
5.2
这个棋盘上演绎马是如何走棋的


首先，我们预置一个常量数组
ccInBoard[256]
，表示哪些 格子在棋
盘外
(
紫色格子，填
0)
，哪些格子在棋盘内
(< br>浅色格子，填
1)
，所以就没有
必要使用
x >= X_LEFT && x <= X_RIGHT && y >= Y_TOP && y <= Y_BOTTOM
之类的边界判断语句了，取而代之的是
ccInBoard[sq] != 0
。



其次，一维数组的好就是上下左右关系非常简明——上面一格是

sq - 16
，下面一格是
sq + 16
，左面一格是
sq - 1
，右面一格是
sq + 1
。
马可以跳的点只有
8
个，终点相对起点的偏移值是固定的：



const
char
ccKnightDelta[4][2]
=
{{-33,
-31},
{-18,
14},
{-14,
18}, {31, 33}};


而对应的马腿的偏移值是：


const char ccKingDelta[4] = {-16, -1, 1, 16};


这个数组之所以命名为
ccKingDelta
，是因为它也是帅
(
将
)
的偏
移值。

这样，找到一个马的所有走法就容易很多了。 首先判断某个方向上的
马腿是否有子，然后判断该方向上的两个走法是否能走：

(2)
，界面模块用户着法合法性判断


11
算法设计与分析



如果让用引擎的着法生成器生成所有着法看是 否包含用户的着
法则太浪费时间，“出棋制胜”用了一个小技巧，下面看最负责的马象着
法合法 性判断，
(sGX,sGY)
是着法起始坐标，
(eGX,eGY)
是着法结 束坐标。

(3)
，判断将军


中国象棋的胜负标准就 是帅
(
将
)
有没有被将死或困毙，我们的做法
很简单——生成所有走 法，如果走任意一步都会被将军，那么该局面就是
将死或困毙的局面，棋局到此结束。



那么如何来判断是否被将军呢？我们有两种做法：



A.
让对方生成全部走法，看看其中有没有走法可以吃掉自己的帅
(将
)
；



B.
按照判断走法是否符合规则的思路，采用更简单的做法。



第 一种做法没有什么不对的，但电脑象棋程序每秒种需要分析上
万个局面，对每个局面都去生成全部走法显 然太花时间了，所以我们要尝
试第二种做法。其实判断帅
(
将
)
是否 被将军的过程并不复杂：



(1)
假设帅
(
将
)
是车，判断它是否能吃到对方的车和将
(
帅
)(
中国
象棋中有将帅不能对脸的规则
)
；



(2)
假设帅
(
将
)
是炮，判断它是否能吃到对方的炮；



(3)
假设帅
(
将
)
是马，判断它 是否能吃到对方的马，需要注意的
是，帅
(
将
)
的马腿用的数组是< br> ccAdvisorDelta
，而不是
ccKingDelta
；



(4)
假设帅
(
将
)
是过河的兵
(
卒
)
，判断它是否能吃到对 方的卒
(
兵
)
。



这样，
一个复杂的走法生成过程
(
方案
A)
就被简化成几个简单的走
12

算法设计与分析

法判断过程
(
方案
B)
。


5.3
搜索算法


（
3.1
）

博弈树的基本概念


如果参加博弈的不是一个主体，而是对抗性的敌我双方 ，则搜索的
进程不仅仅取决于其中一方的意愿，而是取决于对方应付的策略。由此而
产生的搜索 树，
通常称为博弈树
[5]
。
图
2.2
就是一颗红方走棋时 展开的
4
层
博弈树。



红方走棋时展开的
4
层博弈树



博弈树搜索的目标是在博弈的任何一个中间阶段，站在博弈双方其
中一方的立场上，可以构想一颗博弈 树。这颗博弈树的根节点是当前时刻
的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点 是从

13
算法设计与分析

儿子节点的棋局再行棋一步的各种棋 局，以此类推，构造整棵博弈树，直
到可以分出胜负的棋局。像这样从根部向下递归产生的一棵包含所有 可能
的对弈过程的搜索树，成为完全搜索树。像这样的完全搜索树是非常庞大
的，正如表
1.1
所示，中国象棋的完全搜索树复杂度是
10
150
，
IBM
公司目
前正在制造全球运算速度最快的超级计算机，估计峰值操作突破一千万亿
(即
10
15
)
浮点运算的限制。则计算如此一颗完全搜索树需要的时间是
10
135
妙，约
3*10
127
年。所以不可能建立到棋 局结束的完全搜索树，搜索也不必
真地进行到分出胜负的棋局，只需要在一定深度范围内对局面进行评价 即
可。当搜索进行到一定深度，用局面评价机制来评价棋局，按照极大极小
的原则选出最优，向 上回溯，给出这一局面的父亲节点的价值评价，然后
再继续向上回溯，一直到根节点，最优走步就是这样 搜索出来的。

（
3.2
）极大极小算法


极大极小值算法是解决博弈树问题的基本方法。


在象棋博弈中，极大极小 值算法体现在始终站在博弈一方的立场选
择着法。因为一方所追求的利益恰是另一方极力避免的，所以在 这一方行
棋的时候，选择价值极大的儿子节点着法，另一方行棋则选择价值极小的
儿子节点着法 。这就是一个极大极小过程。


当然，程序不能也没有必要做到搜索整棵博弈树的所 有节点，对于
一些己经确定为不佳的走步可以将以它为根节点的子树剪掉。在这个过程
中，最为 重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和
空间损耗来达到寻找高价值的走步。但是 真的想要博弈程序棋力提高，还
必须有一个好的局面评价机制，即估值算法作后。就是说，用这个估值算
14

算法设计与分析

法评价的局面价值必须是客观的、正确的 ，可以确凿的评价局面的优劣以
及优劣的程度。如图
2.3
就是一颗结合估值算法搜索
5
层的完全极大极小
博弈树。



图

极大极小搜索



在图
2.3
中，
最底 层为当前搜索深度
(5
层
)
下对各个可能出现的棋面
进行估值的结果 ，按照由底向上推理，先由黑方选择从第
5
层各个子节点
中选择较小的值推出第
4
层各个父节点，然后红方从第
4
各个节点中选择
教大的值向上推出第3
层各个父节点，依次交替类推，推出第一层的节点
值，从而选择出博弈路径。


(3.3)
负极大值法


普通的极大极小值算法有点 麻烦，一方试图取极小值，而另一方试
图取极大值，也就是说我们总要检查哪一方要取极大值。负极大值 法是一
种可以避免此类判断的算法，负极大值算的值是各子节点的值的负数的极

15