中國象棋計算機博弈關(guān)鍵技術(shù)分析

中國象棋計算機博弄

關(guān)含L技術(shù)分析

褥心和

東北大學(xué)人工智能與機器人研究所

xuxinhe@

2006.4.5

中象機器博鼻的關(guān)鍵技術(shù)分析

A棋局表示

A看法生成

A評估曲數(shù)

?博弄拽奈

A系繞開發(fā)

東北大學(xué)人工智能與機器人研究所

余統(tǒng)建?；炯s定

立

足

紅

方

向

上

進

攻

東北大學(xué)人工智能與機器人研究所

中國象棋棋局演化過程

狀態(tài)演化方程：

s〃+i—snq幾+i

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

0={%%夕3?…外}——棋譜

={0%????}（紅方）?！?{%夕4?…}（黑方）

東北大學(xué)人工智能與機器人研究所

棋局狀態(tài)展開示意圖

東北大學(xué)人工智能與機器人研究所

紅方走棋時展開深度為4的博棄樹

Depth0

Depth1

Depth2

Depth3

紅方Depth4

東北大學(xué)人工智能與機器人研究所

象棋博棄軟件的基本構(gòu)成

?人機界面

?棋局表示與數(shù)組管理

-看法生成與博棄樹飯開

?棋局評估翦數(shù)

?博奔拽奈引擎

?開局庫

?我局庠

?太統(tǒng)總控

東北大學(xué)人工智能與機器人研究所

棋局表示

BoardRepresentation

?通常我們使用狀態(tài)集合來表示〃時刻的棋局狀

忠;o即

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

s'----棋局狀忠矩陣

s”——棋子狀忠矩陣

PM——棋子住置矩陣

B----比特棋盤矩陣

東北大學(xué)人工智能與機器人研究所

棋盤表示與棋盤矩陣

MB=\mB~

LJ」10x9

矩陣元素為教偶,

表示棋盤座標(biāo)值。

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

行向

東北大學(xué)人工智能與機器人研究所

棋子表示法

國際象棋KingRookKnightCannonQueenBishopPawn

中國象棋KingRookHorseCannonGuardElephantPawn

紅子帥車馬炮仕相兵Null

字母代號krhCbeP

兵種編碼12345670

象棋明星

兵種靖瑪020408060c0aOe

黑子將4(4)馬（瑪）炮（砌士象率

字母代號KRHCBEP

兵種編嗎-1-2-3-4—5-6-7

象棋明星

兵種編碼121418161clale

黑子中的碎、碼、硝將在不便區(qū)分車、馬、炮的紅黑方時使用

東北大學(xué)人工智能與機器人研究所

初始棋局狀態(tài)的表示

兵種紅帥紅車紅馬紅炮紅土紅相紅兵無子

編碼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

行向

東北大學(xué)人工智能與機器人研究所

初始棋子狀態(tài)的表示

編瑪12345678910111213141516

棋子黑將黑車黑馬黑煙黑土黑象黑兵

編瑪17181920212223242526272829303132

棋子以坤紅車紅馬紅炮紅土紅相紅兵

一24108191153_

000000000

060000070

12013014015016棋局狀態(tài)矩陣

000000000SB--

S"

000000000棋子狀態(tài)矩陣

28029030031032s'--

02200000230

000000000

182026241725272119

東北大學(xué)人工智能與機器人研究所

棋子住置矩陣表示法

k12345678910111213141516

黑將息車黑馬黑煙黑土黑象息兵

k17181920212223242526272829303132

紅帥紅車紅馬紅炮紅土紅相紅兵

尸〃二［Pjx32

對于初始棋局

1111133111144444

以=

5192828463713579

1010101010881010101077777

5192828463713579

第1行表示編號為人的棋子在棋盤矩陣中的行號，

第2行表示編號為人的棋子在棋盤矩陣中的列（路）號。

東北大學(xué)人工智能與機器人研究所

比瞪棋盤表示法

1s..w0

B-\b]ab..={'

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

l，J

一曠

:/-「

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

?--J

RHg

L510J向

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

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

#表示計算比特向量（二進制敷）對應(yīng)的十進制整數(shù)

東北大學(xué)人工智能與機器人研究所

比特棋盤與棋局的布東條件

?比特棋盤用以記錄棋局的某些布東條件。

?如果比特棋盤中對應(yīng)某一格的核是“1”，那么這一格

上的條件就是否;如果是“0”則對應(yīng)的條件就是

Mo

?布東條件就是在“鄴些格子上符合你所定義的條件”。

?比如，“棋盤哪些優(yōu)置有棋子？”“棋盤哪些住置有

紅棋棋子？”“棋盤鄴些核置有車？”.

?這給計算機上的表示帶來很大方便：12個字節(jié)，96佳

便可以表示一種條件（離6住為0）o

?比特棋盤預(yù)置表法在看法生成中具有重要的地住，而

且在評估中可以方便地判斷棋子相互的聯(lián)余和威脅。

東北大學(xué)人工智能與機器人研究所

初始行、路出特向量對應(yīng)數(shù)值

甘靖=#[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

東北大學(xué)人工智能與機器人研究所

#B——比特向量奈引值

?一個10?。??。┍忍叵蛄?可以表示一路，行）

棋子的分布，它又可以有一個正整數(shù)#5作為奈

引，這將為今后的棋盤分析帶來巨大方便；

?表示路向棋子全部可行分布情況的奈引依范圍

為0一21。?1=1023；

?表示行向棋子全部可行分布情況的未引依范圍

為0-294=511；

?這樣通過奈引值就可以找到相應(yīng)棋子的分布情

況。

東北大學(xué)人工智能與機器人研究所

棋局的”希數(shù)(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

東北大學(xué)人工智能與機器人研究所

棋局的益希救⑻與吟希變換

由當(dāng)前棋局生版64枚電機救

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

形成治希教(依)

32

〃=十/十為異或算符，”為64佳教

k=l

〃便構(gòu)成芻前棋局的奈引值，與棋局形成單向?qū)?yīng),

即由P可以生品”，但由H無曲產(chǎn)生P。

會布變換沒有反變換！

東北大學(xué)人工智能與機器人研究所

看法生成原理

MoveGeneration

看法生成是博棄樹展開的關(guān)鍵環(huán)節(jié)

東北大學(xué)人工智能與機器人研究所

看法的表示

?相對著法：馬八進七，炮5平2——非完整信息，需要

與當(dāng)前局面結(jié)合

?看法算子的運算功能：提■動■落■吃

q—[frommovedtokilled]

?提址----from即此著的出發(fā)伐置；

?動子----moved(chessmanmoved)即夫動的棋子；

?落址——to即看法的到達住置；

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

?對看法的要求：合法性、完整性、有序性

東北大學(xué)人工智能與機器人研究所

看法生成的棋盤掃描法

1.確定走動的棋子(moved)

2.找到該棋子的當(dāng)前住置(from)

3.根據(jù)象棋規(guī)則，掃描棋盤，逐個找到全部合

理落址(to)(考慮制約條件、有效區(qū)域、

本方占伉、對方占優(yōu)等)

4.如果落址為本方棋子，則不可行；若為對方

棋子，則可以吃子(Captured)

5.如果到達落址，構(gòu)成“將軍”(叫殺)，則

應(yīng)該給對方以提示——“將！”

東北大學(xué)人工智能與機器人研究所

看法生成的棋盤掃描規(guī)則

?區(qū)域定義：

?定義棋盤有效區(qū)域^^{(Z,7)|1<Z<10,1<J<9}

?定義紅方半?yún)^(qū)^^{(z,y)|6<z<10,l<y<9}

?定義黑方半?yún)^(qū)^={(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

東北大學(xué)人工智能與機器人研究所

提址為（7,J）的動子看法生成規(guī)則

棋子落址有效制約條件吃子

movedto區(qū)域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)訐

東北大學(xué)人工智能與機器人研究所

提址為(7,j)的動子看法生成規(guī)則

棋子落址有效制約條件吃子

movedto區(qū)域SnbjecrTOCaptured

?！?,力

本方子則止

帥/將將帥不見面

對方子則吃

(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)

對方子則吃

東北大學(xué)人工智能與機器人研究所

提址為(7,j)的動子看法生成規(guī)則

棋子落址有效制約條件吃:子

movedto區(qū)域SubjecttoCaptured

AQ(j^4)

兵IBS

色j±1)

n本方子則止

對方子則吃

G+LJ)

卒

0，J±D

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

及內(nèi)聯(lián)團B路向

本方子則止

8,J士后射線掃描遇第2

對方子則吃

子步距

炮A

a土無,/),止=12..謾壬殷止不吃子

K的抽壬到行向

本方子則止

(i士匕J)射線掃描遇第2

對方子則吃

子步距

東北大學(xué)人工智能與機器人研究所

棋盤掃描法遇到的問題

?雖然在看法的表達上，棋盤掃描法索為直觀,

簡潔，但實戰(zhàn)意義不強。

1為掃描過程大量耗時:掃描動子、提址、制

約條件，合理區(qū)域，雙方占住、吃子等都是劫

忠生成的，尤其區(qū)域判新和棋子種類檢測等，

時間開箱巨大。

?對于吃子看法和未吃子看法無法分別生成,只

能全部生成，再做舞選。

東北大學(xué)人工智能與機器人研究所

模板匹配法

?可以為某些動子設(shè)計

“模板”，只要匹配到00

提址，便可以迅速找到

落址。0X0

?通過單項比特矩陣比對,X馬X

實現(xiàn)“本方子則止，對0X0

方子則吃”，完成“提00

-動-落-吃”內(nèi)參的確定O

?比較適合使用模板的動

走馬匹配模板

子為馬和相（豪）O

東北大學(xué)人工智能與機器人研究所

預(yù)置表法

?棋盤狀態(tài)確定之后，各子的可行看法是確定的。

?預(yù)置表的思想是把某種棋子在棋盤每個合理核置

上，所有可能的棋盤狀態(tài)下的合理石法預(yù)先存儲

起來，生成一個小型數(shù)據(jù)表集合。

?在生成看法時，通過查詢，取代各種計算。

?預(yù)置表的實質(zhì)是用空間換時間，即犧勝一定的內(nèi)

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

?預(yù)置表初始化很隨時，但只需在程序開始運行時

初始化一次，而且占用內(nèi)存會間不大。

東北大學(xué)人工智能與機器人研究所

預(yù)置表法

炮行看法預(yù)置表項舉例

動子為炮提址為伍6）

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

?棋子布局的布東行向量形式[101000010]

?非吃子看法的雄址為[000110100]

?可能的吃子看法的落址為[100000000]

東北大學(xué)人工智能與機器人研究所

炮看法的預(yù)置表總的交間占用計算

?每一行棋子的可行挑列數(shù)恰好對應(yīng)于9枚二進

制教（有子為1,無子為0）,即29=512種情

況（項）O

?考慮到炮在行向的9種可能住置，預(yù)置表的規(guī)

模即為9*512項。

?分別考慮吃子看法與非吃子普法C24J

?考慮路向情況，則總表規(guī)模為

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

?每項占用4季節(jié),則總空間占用量為116k

東北大學(xué)人工智能與機器人研究所

預(yù)置表的使用

?已知動子(炮)的提址(ij)

?由第，行的比特向量和炮在第j住置查找對應(yīng)

的預(yù)置表項，分別得到吃子看法的比特向量和

非吃子看法的比特向量；吃子看法僅為“可

能”，還要軻斷“本方子則止，對方子則吃”；

?查找該行本方棋子比特向量，與吃子看法比特

向量“與”，輸出為1則為非法看法；

?查找該行對方棋子比特向量，與吃子看法比特

向量“與”，輸出為1則為合法吃子看法，得

到落址；

?由該落址便可以得到“吃子”。

東北大學(xué)人工智能與機器人研究所

評估曲教

?在難以判斷輸贏的情況下短別棋局的好壞，可

行的辦法就是對局面進行量化

?通過為棋局“打分”，評判棋局的好壞。

?由于評估需要大量的象棋知詼，仁者見仁，智

者見智；

?評估曲數(shù)的設(shè)計便成為機器博棄中錄為人性化

和模糊化的部分。

?同前對于評估后數(shù)取得其短的觀點，應(yīng)該包括

如下部分：

東北大學(xué)人工智能與機器人研究所

固定子力評估值一40)

?車-600,

?炮-285,馬-270

?相-120,±-125

?兵、4-20

?帥、將無空大值，具體數(shù)值可以給6000

?紅方為正值，黑方為負(fù)值

東北大學(xué)人工智能與機器人研究所

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

?各兵種左棋盤的不同住置上權(quán)值不同

?可由三維數(shù)組給出：

?三維數(shù)組可以按兵種分解為若干個二維教組,

而且要區(qū)分紅方和黑方

?（北［?"）=）%加

m=x

X分別為各兵種代巧

東北大學(xué)人工智能與機器人研究所

紅車佳置評估值O=r）

141412181618121414

162018242624182016

121212181818121212

121816222222161812

121412181818121412

°2（加=廠）-

121614202020141612

61081414148106

486141214684

84816816848

-2106141214610-2

車生大堂分值景焉!

東北大學(xué)人工智能與機器人研究所

紅馬佳置評估值（碗=町

~4816124121684

410281681628104

121416201820161412

8241824202418248

6161418161814166

,2（加=〃）—

4121614121416124

2686106862

428848824

0244-24420

0—400000—40

馬窩心和馬臥楷大不相同!

東北大學(xué)人工智能與機器人研究所

紅炮住置評估值（M=c）

640-10-12-10046

220-4-14-4022

220—10—8-10022

00-24104-200

000282000

0426240-2

000242000

4086106804

024666420

002666200

當(dāng)頭炮分值較高!

東北大學(xué)人工智能與機器人研究所

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

一0369129630一

1836568012080563618

142642608060422614

102030344034302010

6121818201818126

，2(〃2=p)一

208080802

00-2040-200

000000000

000000000

000000000

可見進入九包的兵頂大車!

東北大學(xué)人工智能與機器人研究所

棋子靈活度評估值一。3

?對各兵種而言，每多一個可走住置

就加上一定分值。

?如設(shè)定：兵?15

士-1

象-1

4-6

馬-12

炮-6

將?0

東北大學(xué)人工智能與機器人研究所

棋子配合評估值一Q

?重點是車馬炮的配合與牽制。

?過河兵牽手可加120分。

?連環(huán)馬、擔(dān)子炮、霸王車等都可以考慮加分。

將帥安全評估值一打

?此項多從盤勢上加以考慮。

?多子歸邊、空頭炮、當(dāng)頭炮、沉底炮，將帥住置

等，都要給予一定的懲罰或獎勵分。

東北大學(xué)人工智能與機器人研究所

評估改數(shù)的計算

NNT

ER=^Ek=WMJ

k=lk=l1=1

NNT

EB=￡E：端

k=lk=\l=\

■本方為正值，對方為負(fù)值，其代教和即為當(dāng)前局面評

估值。

?顯然,總值為正對我方有利，負(fù)值對對方有利。絕對

值的大小說明雙方棋勢的差距。

?不難看出，評估函數(shù)中涉及到的權(quán)值余數(shù)可能多達上

千個，卻需要認(rèn)真選擇與權(quán)衡?！嘟y(tǒng)開發(fā)難點。

東北大學(xué)人工智能與機器人研究所

博鼻披奈引擎

(Gamesearchengine)

東北大學(xué)人工智能與機器人研究所

基本定義、概念與稱謂

博棄樹/對局樹（Gametreej

狀態(tài)空間（Statespace）狀忠、初始

狀態(tài)、同標(biāo)狀忠

故奈會同（Searchspacej

方----走棋方/對方，紅方/黑方，Max/Min

節(jié)點（局面）——極節(jié)息,祖父節(jié)點/人節(jié)點/

子節(jié)點/冊節(jié)點，葉節(jié)點

回合----連續(xù)兩個看法＞2步為一個回合

看法得分（評估值）

東北大學(xué)人工智能與機器人研究所

博棄技索引擎

?拽奈策略r度優(yōu)先（Breadth-firstsearchj

深度優(yōu)先fDepth-firstsearchj

迭代深化^Iterativesearchj

?梗奈技巧一機新/剪枝（cut-off）

剪枝（pruning；

擰展/延伸（extendedj

?按奈結(jié)果一返回值/倒推值/局面評估值

豪佳路包/當(dāng)前看法fThebestmoveJ

東北大學(xué)人工智能與機器人研究所

f度優(yōu)先拽素——近極為先

東北大學(xué)人工智能與機器人研究所

深度優(yōu)先拽素——運極為先

東北大學(xué)人工智能與機器人研究所

紅方走棋時展開深度為4的博棄樹

Depth0

Depth1

Depth2

Depth3

紅方Depth4

東北大學(xué)人工智能與機器人研究所

博棄樹分析

?博棄樹上的每一個節(jié)點都代表一個棋局,棋手

就是要在眾多的葉子節(jié)點上挑選一個“最佳的

路桎與局面”作為4己的選擇，從而反推到當(dāng)

前的看法。

?中國象棋博棄樹的龐大是可以想象的。

?如果檜照每一步平均有45種可行著法，每局棋

平均走90步，那次開始局面展開到分出席負(fù)，

則要考慮4590?10150種局面。

?據(jù)說，這一天文教李要比地球上的原子教同還

要多，即使用世界上景快的計算機進行計算，

直到地球毀天也無法算出第一步的看法。

東北大學(xué)人工智能與機器人研究所

技奈法是求斛此類圖模型的基本方法

?無法披未到景終的勝負(fù)狀態(tài)，只能靠評估。

■披奈的同標(biāo)——如何在有限深度的博弄樹中找到評估

值最嵩而又不劇烈波動的聚佳棋局-同標(biāo)狀態(tài)。

?最佳路位^Principalcontinuationj------從當(dāng)前狀態(tài)出

發(fā)到達景佳狀態(tài)的路位，它代表案理智雙方精形對棄

的系列著法。

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

?所謂“不劇烈次動”就是說最佳棋局不是在進行子力

交換與激烈拼殺的過程當(dāng)中。

東北大學(xué)人工智能與機器人研究所

拽奈策唯的劃分

?A類----窮盡技奈fExhaustivesearchJ

?B類----選擇性拽奈^SelectivesearchJ

?C類----目標(biāo)導(dǎo)向技奈（Goaloriented

searchj

?“一著不慎，滿盤皆輸99

?于是，看得遮（搜奈的深），看得準(zhǔn)（真正戰(zhàn)

到指定深度內(nèi)的聚佳的平穩(wěn)棋局），便成為搜

奈算法的基本著眼點O

?顯然窮盡技親成為人們首選的故奈策略。

東北大學(xué)人工智能與機器人研究所

蜜力拽素CBrutesearchJ

?一般采用廣度優(yōu)先技奈

?一層層展開，一層層技奈，因為“毋盡”而沒有風(fēng)險,

不會漏掉展開深度內(nèi)的聚優(yōu)斛。

?假設(shè)計算機技奈節(jié)點速率為1M/秒，中國象棋B=45

（分枝因子B=40?50）

?下表為左不同的給定時間內(nèi)達到的按奈層數(shù)。

給定時間1秒1分1小時1天1年10年100年

搜索層數(shù)3.634.705.786.628.178.779.36

東北大學(xué)人工智能與機器人研究所

出路在哪里？

?由于完整的博棄樹過于龐大，盲目技奈所能達

到的層數(shù)十分有喉，在象棋博棄中幾乎沒有實

用價值O

?若想在指定時間內(nèi)將披奈深度加以提高，一方

面需要砍進硬件與優(yōu)化程序代瑪，提高草住時

間內(nèi)披奈的節(jié)點數(shù)；

?另一方面就需要像人類棋手一樣有選擇性地進

行技奈，即對博棄樹進行必要的耗剪fcut-

of^pruningj。

東北大學(xué)人工智能與機器人研究所

奠基者——香儂教授

?香儂(ClaudeShannon)教授平在1950年首先提

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

從而真定了計算機博棄的理論基礎(chǔ)。

?Shannon,ClaudeE.,Programmingacomputer

forplayingchess[J],

PhilosophicalMagazine,

Vol.41:256-275,1950.

東北大學(xué)人工智能與機器人研究所

博棄樹聘點分析

?博棄樹不同于一般的拽奈樹,它是由對棄雙方

共同產(chǎn)生的一種“變性”梗奈樹。

?紅方為走棋方，它在偶效層的看法選擇是要在

其全部子節(jié)點中找到評估值最大的一個，即賣

行“Max拽奈”o紅方稱為MAX方。

?而其應(yīng)對方——黑方在奇教層的看法選擇則是

在其全部子節(jié)點中要找到評估值錄小的一個，

即實行“Min搜奈”o黑方稱為MIN方。

東北大學(xué)人工智能與機器人研究所

MaxMin拽素(1)

由此產(chǎn)生最佳路役和最佳看法

MAX

MIN

MAX

東北大學(xué)人工智能與機器人研究所

MaxMin拽素(2)

由此產(chǎn)生最佳路桎和景住著法

MAX

MIN

MAX

東北大學(xué)人工智能與機器人研究所

a-B剪枝拽素

?一種基于剪枝（a-pcut-offJ的深度優(yōu)先技

奈(depth-firstsearchj。

?將走棋方定為MAX方，因為它選擇看法時總

是對其子節(jié)點的評估值取極大值，即選擇對自

己景為有利的看法；

?將應(yīng)對方定為MIN方，因為它走棋時需要對其

子節(jié)點的評估值取極小值，即選擇對走棋方景

為不利的、素有鉗制作用的看法。

東北大學(xué)人工智能與機器人研究所

a秀枝(1)

由此產(chǎn)生最佳路位和景佳看法

MAX4a=4

MIN

MAX584623

東北大學(xué)人工智能與機器人研究所

?在對博棄樹采取深度優(yōu)先的技奈策略時，從左

路分枝的葉節(jié)點倒推得到某一層MAX節(jié)點的

值,可表示到此為止將以“落實”的看法景佳

值,記為a。

?顯然此值可作為MAX方看法招標(biāo)的下界。

?在按奈此MAX節(jié)點的其它子節(jié)點，即探討另

一看法時,如果發(fā)現(xiàn)一個回合（2步余）之后

評估值變差，即處節(jié)點評估值低于下界a值，

則便可以剪掉此枝（以該子節(jié)點為根的子樹）,

即不再考慮此“軟著”的延伸。

?此類剪枝稱為。剪枝。

東北大學(xué)人工智能與機器人研究所

a剪枝(2)

由此產(chǎn)生豪佳路程和景佳看法

MAX

MIN

MAX

東北大學(xué)人工智能與機器人研究所

剪枝效果差別很大

?不難發(fā)現(xiàn)，和豪佳看法關(guān)余密切

?什么是景佳看法？

?怎樣找到聚佳看法？

⑴(2)

東北大學(xué)人工智能與機器人研究所

小剪枝門）

由此產(chǎn)生景佳路位和景佳看法

MIN

MAX

MIN

東北大學(xué)人工智能與機器人研究所

?同理，由左路分枝的葉節(jié)點倒推得到某一層

MIN節(jié)點的值，可表示到此為止對方看法的鉗

制值，記為m

?顯然此0值可作為MAX方無法實現(xiàn)看法器標(biāo)的

上界。

?在梗奈該MIN節(jié)點的其它子節(jié)點，即探討另外

看法時，如果發(fā)現(xiàn)一個回合之后鉗制局面減耨,

即抽節(jié)點評估值高于上界P值，則便可以剪掉

此枝，即不再考慮此“軟著”的延伸。

?此類剪枝稱為P剪枝。

東北大學(xué)人工智能與機器人研究所

小篁枝C2J

由此產(chǎn)生景佳路位和景佳看法

MIN

MAX

MIN

東北大學(xué)人工智能與機器人研究所

B剪枝和a剪枝具有同樣規(guī)律

剪枝效果與景枝著法的伐置密切相關(guān)

與博棄樹展開的順序密切相關(guān)

東北大學(xué)人工智能與機器人研究所

需要指出的是

?a-U剪枝是根據(jù)極大-極小披奈規(guī)則的進行

的,雖然它沒有遍歷某些子樹的大量節(jié)

點,但它仍不失為空盡技奈的本性。

?a-P剪枝技巧的發(fā)現(xiàn)，一下便為博棄樹技

奈效率的提高開創(chuàng)了嶄新的局面。

東北大學(xué)人工智能與機器人研究所

Knuth和Moore重要貢故

?1975年姓出了af算法正確性的教學(xué)證明。

?a-P剪枝算法的效率與子節(jié)點獷展的先后順序

相關(guān)。在景理想情況下（極小樹）,其生成的

節(jié)點數(shù)同為