中国象棋计算机博弈关键技术分析

中国象棋计算机博弈关键技术分析

中国象棋计算机博弈 关键技术分析

中国象棋计算机博弈关键技术分析

中象机器博弈的关键技术分析 棋局表示 着法生成 评估函数 博弈搜索 系统开发

中国象棋计算机博弈关键技术分析

系统建模基本约定立 足 红 方 向 上 进 攻

中国象棋计算机博弈关键技术分析

中国象棋棋局演化过程

状态演化方程：

S n 1 S n qn 1 S F S0 q1 q2 ... qF S0 QQodd q1q3.... (红方)

Q q1q2 q3.... qF

Qevn q2 q4 .... (黑方)

—— 棋谱

中国象棋计算机博弈关键技术分析

棋局状态展开示意图

中国象棋计算机博弈关键技术分析

红方走棋时展开深度为4的博弈树红方Depth 0

黑方

Depth 1

红方Depth 2 黑方 Depth 3

红方

Depth 4

中国象棋计算机博弈关键技术分析

象棋博弈软件的基本构成 人机界面 棋局表示与数组管理 着法生成与博弈树展开 棋局评估函数 博弈搜索引擎 开局库 残局库 系统总控

中国象棋计算机博弈关键技术分析

棋局表示 Board Representation 通常我们使用状态集合来表示 n 时刻的棋局状 态。即

S n {S , S , P , Bn ,...}B n M n M n

S B ——棋局状态矩阵 S M —— 棋子状态矩阵 P M ——棋子位置矩阵 B

——比特棋盘矩阵

中国象棋计算机博弈关键技术分析

棋盘表示与棋盘矩阵行向

M m B

B i , j 10 9

矩阵元素为数偶， 表示棋盘坐标值。路 向 1,1 1, 2 1,3 1, 4 1,5 1, 6 1, 7 1,8 1,9 2,1 2, 2 2,3 2, 4 2,5 2, 6 2, 7 2,8 2,9 3,1 3, 2 3,3 3, 4 3,5 3, 6 3, 7 3,8 3,9 4,1 4, 2 4,3 4, 4 4,5 4, 6 4, 7 4,8 4,9 5,1 5, 2 5,3 5, 4 5,5 5, 6 5, 7 5,8 5,9 MB 6,1 6, 2 6,3 6, 4 6,5 6, 6 6, 7 6,8 6,9 7,1 7, 2 7,3 7, 4 7,5 7, 6 7, 7 7,8 7,9 8,1 8, 2 8, 3 8, 4 8,5 8, 6 8, 7 8,8 8,9 9,1 9, 2 9,3 9, 4 9,5 9, 6 9, 7 9,8 9,9 10,1 10, 2 10,3 10, 4 10,5 10, 6 10, 7 10,8 10,9

中国象棋计算机博弈关键技术分析

棋子表示法国际象棋 中国象棋 King King Rook Rook Knight Horse Cannon Cannon Queen Guard Bishop Elephant Pawn Pawn

红子字母代号 兵种编码 象棋明星 兵种编码

帅 k 1 02

车 r 2 04车(砗)

马 h 3 08马(码)

炮 c 4 06炮(砲)

仕 b 5 0c

相 e 6 0a

兵 p 7 0e

Null 0

黑子字母代号 兵种编码 象棋明星 兵种编码

将K -1 12

士B -5 1c

象E -6 1a

卒P -7 1e

R -2 14

H -3 18

C -4 16

黑子中的砗、码、砲将在不便区分车、马、炮的红黑方时使用

中国象棋计算机博弈关键技术分析

初始棋局状态的表示兵种编码 兵种 编码

红帅1 黑将 -1

红车2 黑车 -2

红马3 黑马 -3

红炮4 黑炮 -4

红士5 黑士 -5

红相6 黑象 -6

红兵7 黑兵 -7

无子0

2 3 5 6 1 6 5 3 2 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 4 0 7 0 7 0 7 0 7 0 7 0 0 0 0 0 0 0 0 0 S0B 0 0 0 0 0 0 0 0 0 7 0 7 0 7 0 7 0 7 4 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 2 3 5 6 1 6 5 3 2

中国象棋计算机博弈关键技术分析

初始棋子状态的表示编码 棋子 编码

棋子 1 黑将 17 红帅 2 3 4 5 6 7 8 9 10 11 12 13 14 黑兵 28 29 30 红兵 31 32 15 16 黑车 18 19 黑马 20 21 黑炮 22 23 黑士 24 25 黑象 26 27

红车

红马

红炮

红士

红相

S0M

2 4 10 8 1 9 0 0 0 0 0 0 0 6 0 0 0 0 12 0 13 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 28 0 29 0 30 0 0 22 0 0 0 0 0 0 0 0 0 0 18 20 26 24 17 25

3 0 0 0 0 7 0 15 0 16 0 0 0 0 0 0 31 0 32 0 23 0 0 0 0 27 21 19 11 5

S B 棋局状态矩阵 S M 棋子状态矩阵

中国象棋计算机博弈关键技术分析

棋子位置矩阵表示法k k1 黑将 17 红帅 2 3 4 5 6 7 8 9 10 11 12 13 14 黑兵 28 29 30 红兵 31 32 15 16 黑车 18 19 黑马 20 21 黑炮 22 23 黑士 24 25 黑象 26 27

红车

红马

红炮

红士

红相

P [ pk ]2 32M

对于初始棋局 1 1 1 1 1 3 3 1 1 1 1 P0M 5 1 9 2 8 2 8 4 6 3 7 10 10 10 10 10 8 8 10 10 5 1 9 2 8 2 8 4 6 4 1 10 3 4 3 10 7 4 5 7 1 4 7 7 3 4 9 7 5 7 7 7 9

第1行表示编号为k的棋子在棋盘矩阵中的行号， 第2行表示编号为k的棋子在棋盘矩阵中的列(路)号。

中国象棋计算机博弈关键技术分析

比特棋盘表示法B [bi , j ]10 9 B1H B B1V H B10

1 bi , j { 0 B9V

si , j 0 si , j 0

BiV 注意： BiH

路向比特向量 ( Vertical )行向比特向量 ( Horizon )

# 表示计算比特向量(二进制数)对应的十进制整数

中国象棋计算机博弈关键技术分析

比特棋盘与棋局的布尔条件 比特棋盘用以记录棋局的某些布尔条件。

如果比特棋盘中对应某一格的位是“1”,那么这一格 上的条件就是“真”;如果是“0”则对应的条件就是 假。 布尔条件就是在“哪些格子上符合你所定义的条件”。 比如，“棋盘哪些位置有棋子？” “棋盘哪些位置有 红棋棋子？” “棋盘哪些位置有车？” ……

这给计算机上的表示带来很大方便：12个字节，96位 便可以表示一种条件(高6位为0)。 比特棋盘预置表法在着法生成中具有重要的地位，而 且在评估中可以方便地判断棋子相互的联系和威胁。

< …… 此处隐藏：942字，全部文档内容请下载后查看。喜欢就下载吧 ……