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

中国象棋计算机博弄

关含L技术分析

褥心和

东北大学人工智能与机器人研究所

xuxinhe@

2006.4.5

中象机器博鼻的关键技术分析

A棋局表示

A看法生成

A评估曲数

»博弄拽奈

A系绕开发

东北大学人工智能与机器人研究所

余统建模基本约定

立

足

红

方

向

上

进

攻

东北大学人工智能与机器人研究所

中国象棋棋局演化过程

状态演化方程：

s〃+i—snq几+i

SF=SQ-qcq2-...-qF=SQ-Q

0={%%夕3•…外}——棋谱

={0%・・・・}（红方）。—={%夕4•…}（黑方）

东北大学人工智能与机器人研究所

棋局状态展开示意图

东北大学人工智能与机器人研究所

红方走棋时展开深度为4的博弃树

Depth0

Depth1

Depth2

Depth3

红方Depth4

东北大学人工智能与机器人研究所

象棋博弃软件的基本构成

•人机界面

•棋局表示与数组管理

­看法生成与博弃树饭开

•棋局评估翦数

•博奔拽奈引擎

•开局库

・我局庠

•太统总控

东北大学人工智能与机器人研究所

棋局表示

BoardRepresentation

•通常我们使用状态集合来表示〃时刻的棋局状

忠;o即

Sn={S^S^P^Bn,...}

s'----棋局状忠矩阵

s”——棋子状忠矩阵

PM——棋子住置矩阵

B----比特棋盘矩阵

东北大学人工智能与机器人研究所

棋盘表示与棋盘矩阵

MB=\mB~

LJ」10x9

矩阵元素为教偶,

表示棋盘座标值。

1,11,21,31,41,51,61,71,81,9

2,12,22,32,42,52,62,72,82,9

3,13,23,33,43,53,63,73,83,9

4,14,24,34,44,54,64,74,84,9

MB—5,15,25,35,45,55,65,75,85,9

1V1一

6,16,26,36,46,56,66,76,86,9

7,17,27,37,47,57,67,77,87,9

软!)④&磁曲分8,18,28,38,48,58,68,78,88,9

9,19,29,39,49,59,69,79,89,9

10,110,210,310,410,510,610,710,810,9

行向

东北大学人工智能与机器人研究所

棋子表示法

国际象棋KingRookKnightCannonQueenBishopPawn

中国象棋KingRookHorseCannonGuardElephantPawn

红子帅车马炮仕相兵Null

字母代号krhCbeP

兵种编码12345670

象棋明星

兵种靖玛020408060c0aOe

黑子将4(4)马（玛）炮（砌士象率

字母代号KRHCBEP

兵种编吗-1-2-3-4—5-6-7

象棋明星

兵种编码121418161clale

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

东北大学人工智能与机器人研究所

初始棋局状态的表示

兵种红帅红车红马红炮红土红相红兵无子

编码12345670

兵种黑将黑车黑马黑烟黑士黑象黑兵

编码—1-2-3-4-5—6-7

-2-3—5—6—1—6—5-3-2

000000000

0-400000-40

-70-70-70-70-7

路

000000000

向S”

000000000

707070707

040000040

000000000

卷4）高出为曲卷235616532

行向

东北大学人工智能与机器人研究所

初始棋子状态的表示

编玛12345678910111213141516

棋子黑将黑车黑马黑烟黑土黑象黑兵

编玛17181920212223242526272829303132

棋子以坤红车红马红炮红土红相红兵

一24108191153_

000000000

060000070

12013014015016棋局状态矩阵

000000000SB--

S"

000000000棋子状态矩阵

28029030031032s'--

02200000230

000000000

182026241725272119

东北大学人工智能与机器人研究所

棋子住置矩阵表示法

k12345678910111213141516

黑将息车黑马黑烟黑土黑象息兵

k17181920212223242526272829303132

红帅红车红马红炮红土红相红兵

尸〃二［Pjx32

对于初始棋局

1111133111144444

以=

5192828463713579

1010101010881010101077777

5192828463713579

第1行表示编号为人的棋子在棋盘矩阵中的行号，

第2行表示编号为人的棋子在棋盘矩阵中的列（路）号。

东北大学人工智能与机器人研究所

比瞪棋盘表示法

1s..w0

B-\b]ab..={'

Lzj」1in0x9i，J’0s..=0

l，J

一旷

:/-「

B=i=s........

•--J

RHg

L510J向

注意：B：路向比特向量(Vertical)含④血&4港©查靖

BH行向比特向量(Horizon)行向

#表示计算比特向量（二进制敷）对应的十进制整数

东北大学人工智能与机器人研究所

比特棋盘与棋局的布东条件

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

•如果比特棋盘中对应某一格的核是“1”，那么这一格

上的条件就是否;如果是“0”则对应的条件就是

Mo

•布东条件就是在“邺些格子上符合你所定义的条件”。

•比如，“棋盘哪些优置有棋子？”“棋盘哪些住置有

红棋棋子？”“棋盘邺些核置有车？”.

•这给计算机上的表示带来很大方便：12个字节，96佳

便可以表示一种条件（离6住为0）o

•比特棋盘预置表法在看法生成中具有重要的地住，而

且在评估中可以方便地判断棋子相互的联余和威胁。

东北大学人工智能与机器人研究所

初始行、路出特向量对应数值

甘靖=#[111111111]=511

#3/=#[1001001001]T=585

H

#B2=#[000000000]=0

#B；=#[1010000101]T=645

#=#[010000010]=130

#=#[1001001001]T=585

#B4H=#[101010101]=341

#3；=#[1000000001]T=513

H

nB5=#[000000000]=0

#=#[1001001001]T=585

#=#[000000000]=0

#B；=#[1000000()01]T=513

#B-Jff=#[101010101]=341

#B/=#[1001001001]T=585

#=#[010000010]=130

ff#=#[1010000101]T=645

#B9=#[000000000]=0

H#By=#[1001001001]T=585

#B[0=#[111111111]=5119

东北大学人工智能与机器人研究所

#B——比特向量奈引值

•一个10住（9住）比特向量3可以表示一路，行）

棋子的分布，它又可以有一个正整数#5作为奈

引，这将为今后的棋盘分析带来巨大方便；

•表示路向棋子全部可行分布情况的奈引依范围

为0一21。・1=1023；

•表示行向棋子全部可行分布情况的未引依范围

为0-294=511；

•这样通过奈引值就可以找到相应棋子的分布情

况。

东北大学人工智能与机器人研究所

棋局的”希数(8)与色希变换

黑将黑车黑马黑炮黑土黑象黑兵

k12345678910111213141516

-1-2-2-3-3-4-4-5-5-6-6-7-7-7-7-7

红帅红军红马红炮红土红相红兵

k17181920212223242526272829303132

1223344556677777

HashTransfjrm

哈希变换pMnH

生成64枚随机救

M

hk-Random64(kM,P/\左=1,2,…32

东北大学人工智能与机器人研究所

棋局的益希救⑻与吟希变换

由当前棋局生版64枚电机救

hk-Random64(kM?)5k=1,2,…32

形成治希教(依)

32

〃=㊉/㊉为异或算符，”为64佳教

k=l

〃便构成刍前棋局的奈引值，与棋局形成单向对应,

即由P可以生品”，但由H无曲产生P。

会布变换没有反变换！

东北大学人工智能与机器人研究所

看法生成原理

MoveGeneration

看法生成是博弃树展开的关键环节

东北大学人工智能与机器人研究所

看法的表示

•相对着法：马八进七，炮5平2——非完整信息，需要

与当前局面结合

•看法算子的运算功能：提■动■落■吃

q—[frommovedtokilled]

•提址----from即此着的出发伐置；

•动子----moved(chessmanmoved)即夫动的棋子；

•落址——to即看法的到达住置；

•吃子----killed(chessmanCaptured)即吃掉的棋子。

•对看法的要求：合法性、完整性、有序性

东北大学人工智能与机器人研究所

看法生成的棋盘扫描法

1.确定走动的棋子(moved)

2.找到该棋子的当前住置(from)

3.根据象棋规则，扫描棋盘，逐个找到全部合

理落址(to)(考虑制约条件、有效区域、

本方占伉、对方占优等)

4.如果落址为本方棋子，则不可行；若为对方

棋子，则可以吃子(Captured)

5.如果到达落址，构成“将军”(叫杀)，则

应该给对方以提示——“将！”

东北大学人工智能与机器人研究所

看法生成的棋盘扫描规则

•区域定义：

•定义棋盘有效区域^^{(Z,7)|1<Z<10,1<J<9}

•定义红方半区^^{(z,y)|6<z<10,l<y<9}

•定义黑方半区^={(Z,J)|1<Z<5,1<J<9}

•定义红方九含

APR={(iJ)\8<i<WA<J<6}

•定义黑方九啻^^{(Z，7)|1<Z<3,4<7<6}

李符说明：A-area,R-red,B-black,P-palace

东北大学人工智能与机器人研究所

提址为（7,J）的动子看法生成规则

棋子落址有效制约条件吃子

movedto区域SubjecttoCaptured

1

5Jtk、、k=L■M•••

本方子则止

举；A

对方子则吃

u±=1,

(，±L、/+2)A(</+l)无子

0±Lj-2)一4(<,—1)无子

本方子则止

翦；

对方子则吃

G+2J±Da+ij)无子

Q-2J±DA(Tj)讦

东北大学人工智能与机器人研究所

提址为(7,j)的动子看法生成规则

棋子落址有效制约条件吃子

movedto区域SnbjecrTOCaptured

。±1,力

本方子则止

帅/将将帅不见面

对方子则吃

(D±D

(7+2,7+2)(/+Lj+1)无了

(7+2..T)U+Lj-D钎

本方子则止

相/象办J/'为J

对方子则吃

(TJ+2)(7—LJ+1)无子

0-2,j-2)d-i)计

本方子则止

位'士►，J±1)

对方子则吃

东北大学人工智能与机器人研究所

提址为(7,j)的动子看法生成规则

棋子落址有效制约条件吃:子

movedto区域SubjecttoCaptured

AQ(j^4)

兵IBS

色j±1)

n本方子则止

对方子则吃

G+LJ)

卒

0，J±D

(jrj±k^,k=1,2...遇壬殿止不吃子

及内联团B路向

本方子则止

8,J士后射线扫描遇第2

对方子则吃

子步距

炮A

a土无,/),止=12..谩壬殷止不吃子

K的抽壬到行向

本方子则止

(i士匕J)射线扫描遇第2

对方子则吃

子步距

东北大学人工智能与机器人研究所

棋盘扫描法遇到的问题

•虽然在看法的表达上，棋盘扫描法索为直观,

简洁，但实战意义不强。

1为扫描过程大量耗时:扫描动子、提址、制

约条件，合理区域，双方占住、吃子等都是劫

忠生成的，尤其区域判新和棋子种类检测等，

时间开箱巨大。

•对于吃子看法和未吃子看法无法分别生成,只

能全部生成，再做舞选。

东北大学人工智能与机器人研究所

模板匹配法

•可以为某些动子设计

“模板”，只要匹配到00

提址，便可以迅速找到

落址。0X0

•通过单项比特矩阵比对,X马X

实现“本方子则止，对0X0

方子则吃”，完成“提00

-动-落-吃”内参的确定O

•比较适合使用模板的动

走马匹配模板

子为马和相（豪）O

东北大学人工智能与机器人研究所

预置表法

•棋盘状态确定之后，各子的可行看法是确定的。

•预置表的思想是把某种棋子在棋盘每个合理核置

上，所有可能的棋盘状态下的合理石法预先存储

起来，生成一个小型数据表集合。

•在生成看法时，通过查询，取代各种计算。

•预置表的实质是用空间换时间，即牺胜一定的内

存空同加速程序的运行速度。

•预置表初始化很随时，但只需在程序开始运行时

初始化一次，而且占用内存会间不大。

东北大学人工智能与机器人研究所

预置表法

炮行看法预置表项举例

动子为炮提址为伍6）

子落圮二）口吃子落如二二）

•棋子布局的布东行向量形式[101000010]

•非吃子看法的雄址为[000110100]

•可能的吃子看法的落址为[100000000]

东北大学人工智能与机器人研究所

炮看法的预置表总的交间占用计算

•每一行棋子的可行挑列数恰好对应于9枚二进

制教（有子为1,无子为0）,即29=512种情

况（项）O

•考虑到炮在行向的9种可能住置，预置表的规

模即为9*512项。

•分别考虑吃子看法与非吃子普法C24J

•考虑路向情况，则总表规模为

2*9*512+2*10*1024=29696项

•每项占用4季节,则总空间占用量为116k

东北大学人工智能与机器人研究所

预置表的使用

•已知动子(炮)的提址(ij)

•由第，行的比特向量和炮在第j住置查找对应

的预置表项，分别得到吃子看法的比特向量和

非吃子看法的比特向量；吃子看法仅为“可

能”，还要轲断“本方子则止，对方子则吃”；

•查找该行本方棋子比特向量，与吃子看法比特

向量“与”，输出为1则为非法看法；

•查找该行对方棋子比特向量，与吃子看法比特

向量“与”，输出为1则为合法吃子看法，得

到落址；

•由该落址便可以得到“吃子”。

东北大学人工智能与机器人研究所

评估曲教

•在难以判断输赢的情况下短别棋局的好坏，可

行的办法就是对局面进行量化

•通过为棋局“打分”，评判棋局的好坏。

•由于评估需要大量的象棋知诙，仁者见仁，智

者见智；

•评估曲数的设计便成为机器博弃中录为人性化

和模糊化的部分。

•同前对于评估后数取得其短的观点，应该包括

如下部分：

东北大学人工智能与机器人研究所

固定子力评估值一40)

•车-600,

•炮-285,马-270

•相-120,±-125

•兵、4-20

•帅、将无空大值，具体数值可以给6000

•红方为正值，黑方为负值

东北大学人工智能与机器人研究所

棋子住置评估值一。2（也切

•各兵种左棋盘的不同住置上权值不同

•可由三维数组给出：

•三维数组可以按兵种分解为若干个二维教组,

而且要区分红方和黑方

♦（北［•"）=）%加

m=x

X分别为各兵种代巧

东北大学人工智能与机器人研究所

红车佳置评估值O=r）

141412181618121414

162018242624182016

121212181818121212

121816222222161812

121412181818121412

°2（加=厂）-

121614202020141612

61081414148106

486141214684

84816816848

-2106141214610-2

车生大堂分值景焉!

东北大学人工智能与机器人研究所

红马佳置评估值（碗=町

~4816124121684

410281681628104

121416201820161412

8241824202418248

6161418161814166

,2（加=〃）—

4121614121416124

2686106862

428848824

0244-24420

0—400000—40

马窝心和马卧楷大不相同!

东北大学人工智能与机器人研究所

红炮住置评估值（M=c）

640-10-12-10046

220-4-14-4022

220—10—8-10022

00-24104-200

000282000

0426240-2

000242000

4086106804

024666420

002666200

当头炮分值较高!

东北大学人工智能与机器人研究所

4r兵住置评估值（旭子）

一0369129630一

1836568012080563618

142642608060422614

102030344034302010

6121818201818126

，2(〃2=p)一

208080802

00-2040-200

000000000

000000000

000000000

可见进入九包的兵顶大车!

东北大学人工智能与机器人研究所

棋子灵活度评估值一。3

•对各兵种而言，每多一个可走住置

就加上一定分值。

•如设定：兵・15

士-1

象-1

4-6

马-12

炮-6

将・0

东北大学人工智能与机器人研究所

棋子配合评估值一Q

•重点是车马炮的配合与牵制。

•过河兵牵手可加120分。

•连环马、担子炮、霸王车等都可以考虑加分。

将帅安全评估值一打

•此项多从盘势上加以考虑。

•多子归边、空头炮、当头炮、沉底炮，将帅住置

等，都要给予一定的惩罚或奖励分。

东北大学人工智能与机器人研究所

评估改数的计算

NNT

ER=^Ek=WMJ

k=lk=l1=1

NNT

EB=£E：端

k=lk=\l=\

■本方为正值，对方为负值，其代教和即为当前局面评

估值。

•显然,总值为正对我方有利，负值对对方有利。绝对

值的大小说明双方棋势的差距。

•不难看出，评估函数中涉及到的权值余数可能多达上

千个，却需要认真选择与权衡。——余统开发难点。

东北大学人工智能与机器人研究所

博鼻披奈引擎

(Gamesearchengine)

东北大学人工智能与机器人研究所

基本定义、概念与称谓

博弃树/对局树（Gametreej

状态空间（Statespace）状忠、初始

状态、同标状忠

故奈会同（Searchspacej

方----走棋方/对方，红方/黑方，Max/Min

节点（局面）——极节息,祖父节点/人节点/

子节点/册节点，叶节点

回合----连续两个看法＞2步为一个回合

看法得分（评估值）

东北大学人工智能与机器人研究所

博弃技索引擎

•拽奈策略r度优先（Breadth-firstsearchj

深度优先fDepth-firstsearchj

迭代深化^Iterativesearchj

•梗奈技巧一机新/剪枝（cut-off）

剪枝（pruning；

拧展/延伸（extendedj

•按奈结果一返回值/倒推值/局面评估值

豪佳路包/当前看法fThebestmoveJ

东北大学人工智能与机器人研究所

f度优先拽素——近极为先

东北大学人工智能与机器人研究所

深度优先拽素——运极为先

东北大学人工智能与机器人研究所

红方走棋时展开深度为4的博弃树

Depth0

Depth1

Depth2

Depth3

红方Depth4

东北大学人工智能与机器人研究所

博弃树分析

•博弃树上的每一个节点都代表一个棋局,棋手

就是要在众多的叶子节点上挑选一个“最佳的

路桎与局面”作为4己的选择，从而反推到当

前的看法。

•中国象棋博弃树的庞大是可以想象的。

•如果桧照每一步平均有45种可行着法，每局棋

平均走90步，那次开始局面展开到分出席负，

则要考虑4590«10150种局面。

•据说，这一天文教李要比地球上的原子教同还

要多，即使用世界上景快的计算机进行计算，

直到地球毁天也无法算出第一步的看法。

东北大学人工智能与机器人研究所

技奈法是求斛此类图模型的基本方法

•无法披未到景终的胜负状态，只能靠评估。

■披奈的同标——如何在有限深度的博弄树中找到评估

值最嵩而又不剧烈波动的聚佳棋局-同标状态。

•最佳路位^Principalcontinuationj------从当前状态出

发到达景佳状态的路位，它代表案理智双方精形对弃

的系列着法。

•聚佳看法fThebestmovej------崇佳路桎上的第1步棋。

•所谓“不剧烈次动”就是说最佳棋局不是在进行子力

交换与激烈拼杀的过程当中。

东北大学人工智能与机器人研究所

拽奈策唯的划分

•A类----穷尽技奈fExhaustivesearchJ

•B类----选择性拽奈^SelectivesearchJ

•C类----目标导向技奈（Goaloriented

searchj

・“一着不慎，满盘皆输99

•于是，看得遮（搜奈的深），看得准（真正战

到指定深度内的聚佳的平稳棋局），便成为搜

奈算法的基本着眼点O

•显然穷尽技亲成为人们首选的故奈策略。

东北大学人工智能与机器人研究所

蜜力拽素CBrutesearchJ

•一般采用广度优先技奈

•一层层展开，一层层技奈，因为“毋尽”而没有风险,

不会漏掉展开深度内的聚优斛。

•假设计算机技奈节点速率为1M/秒，中国象棋B=45

（分枝因子B=40〜50）

•下表为左不同的给定时间内达到的按奈层数。

给定时间1秒1分1小时1天1年10年100年

搜索层数3.634.705.786.628.178.779.36

东北大学人工智能与机器人研究所

出路在哪里？

•由于完整的博弃树过于庞大，盲目技奈所能达

到的层数十分有喉，在象棋博弃中几乎没有实

用价值O

•若想在指定时间内将披奈深度加以提高，一方

面需要砍进硬件与优化程序代玛，提高草住时

间内披奈的节点数；

•另一方面就需要像人类棋手一样有选择性地进

行技奈，即对博弃树进行必要的耗剪fcut-

of^pruningj。

东北大学人工智能与机器人研究所

奠基者——香侬教授

・香侬(ClaudeShannon)教授平在1950年首先提

出了极大■极小算法(MinimaxAlgorithmJ,

从而真定了计算机博弃的理论基础。

•Shannon,ClaudeE.,Programmingacomputer

forplayingchess[J],

PhilosophicalMagazine,

Vol.41:256-275,1950.

东北大学人工智能与机器人研究所

博弃树聘点分析

•博弃树不同于一般的拽奈树,它是由对弃双方

共同产生的一种“变性”梗奈树。

•红方为走棋方，它在偶效层的看法选择是要在

其全部子节点中找到评估值最大的一个，即卖

行“Max拽奈”o红方称为MAX方。

•而其应对方——黑方在奇教层的看法选择则是

在其全部子节点中要找到评估值录小的一个，

即实行“Min搜奈”o黑方称为MIN方。

东北大学人工智能与机器人研究所

MaxMin拽素(1)

由此产生最佳路役和最佳看法

MAX

MIN

MAX

东北大学人工智能与机器人研究所

MaxMin拽素(2)

由此产生最佳路桎和景住着法

MAX

MIN

MAX

东北大学人工智能与机器人研究所

a-B剪枝拽素

•一种基于剪枝（a-pcut-offJ的深度优先技

奈(depth-firstsearchj。

•将走棋方定为MAX方，因为它选择看法时总

是对其子节点的评估值取极大值，即选择对自

己景为有利的看法；

•将应对方定为MIN方，因为它走棋时需要对其

子节点的评估值取极小值，即选择对走棋方景

为不利的、素有钳制作用的看法。

东北大学人工智能与机器人研究所

a秀枝(1)

由此产生最佳路位和景佳看法

MAX4a=4

MIN

MAX584623

东北大学人工智能与机器人研究所

•在对博弃树采取深度优先的技奈策略时，从左

路分枝的叶节点倒推得到某一层MAX节点的

值,可表示到此为止将以“落实”的看法景佳

值,记为a。

•显然此值可作为MAX方看法招标的下界。

•在按奈此MAX节点的其它子节点，即探讨另

一看法时,如果发现一个回合（2步余）之后

评估值变差，即处节点评估值低于下界a值，

则便可以剪掉此枝（以该子节点为根的子树）,

即不再考虑此“软着”的延伸。

•此类剪枝称为。剪枝。

东北大学人工智能与机器人研究所

a剪枝(2)

由此产生豪佳路程和景佳看法

MAX

MIN

MAX

东北大学人工智能与机器人研究所

剪枝效果差别很大

•不难发现，和豪佳看法关余密切

•什么是景佳看法？

•怎样找到聚佳看法？

⑴(2)

东北大学人工智能与机器人研究所

小剪枝门）

由此产生景佳路位和景佳看法

MIN

MAX

MIN

东北大学人工智能与机器人研究所

•同理，由左路分枝的叶节点倒推得到某一层

MIN节点的值，可表示到此为止对方看法的钳

制值，记为m

•显然此0值可作为MAX方无法实现看法器标的

上界。

•在梗奈该MIN节点的其它子节点，即探讨另外

看法时，如果发现一个回合之后钳制局面减耨,

即抽节点评估值高于上界P值，则便可以剪掉

此枝，即不再考虑此“软着”的延伸。

•此类剪枝称为P剪枝。

东北大学人工智能与机器人研究所

小篁枝C2J

由此产生景佳路位和景佳看法

MIN

MAX

MIN

东北大学人工智能与机器人研究所

B剪枝和a剪枝具有同样规律

剪枝效果与景枝着法的伐置密切相关

与博弃树展开的顺序密切相关

东北大学人工智能与机器人研究所

需要指出的是

•a-U剪枝是根据极大-极小披奈规则的进行

的,虽然它没有遍历某些子树的大量节

点,但它仍不失为空尽技奈的本性。

•a-P剪枝技巧的发现，一下便为博弃树技

奈效率的提高开创了崭新的局面。

东北大学人工智能与机器人研究所

Knuth和Moore重要贡故

•1975年姓出了af算法正确性的教学证明。

•a-P剪枝算法的效率与子节点犷展的先后顺序

相关。在景理想情况下（极小树）,其生成的

节点数同为