民間棋類計算機(jī)博弈

民間棋類計算機(jī)博棄

徐心和徐長明

東北大學(xué)機(jī)舞博棄研究重

2007年7月

主要內(nèi)＜

?:?什么是計算機(jī)悔棄r機(jī)賽博界）?

機(jī)器博棄的艱苦歷程與輝煌成果

?:?氏同棋類計算機(jī)博界

——機(jī)器博棄的入門課

?:?計算機(jī)是如何實現(xiàn)博棄過程的？

?:?機(jī)器博棄的技術(shù)構(gòu)成與內(nèi)涵

?:?開梭機(jī)器博棄活動的意義與展篁

東北大學(xué)機(jī)器博弈研究室

什么是計算機(jī)博弈?

討算機(jī)博棄，機(jī)器悔界

ComputerGames

主要是指計算機(jī)下棋、航牌

----像人一樣的思維

景先提出的就是計算機(jī)下

國際象棋、勒嬋的棋等各種棋類

東北大學(xué)機(jī)器博弈研究室

機(jī)器博弈是一個特殊的研究領(lǐng)域

?:?它是非常實際的計算機(jī)科學(xué)與技術(shù)的研究課題

?:?它是非常畬于挑戰(zhàn)性的人工智能領(lǐng)域的研究方向

?:?它來不得任何理想化和虛假成分

?:?它是現(xiàn)代博棄論所不能斛決的動態(tài)博棄技術(shù)

?:?它是需求牽引的典型課題，具有很強(qiáng)的泛化能力

1為它是人工智能的基本問題

。它具有廣闊的應(yīng)用前景——對策問題

（控制，決策、對策）

東北大學(xué)機(jī)器博弈研究室

機(jī)器博弈的艱苦歷程與辱煌成果

國際象棋——

?景先提出的計算機(jī)應(yīng)用課題之一

?計算機(jī)前聚所關(guān)注的研究課題

?半個世紀(jì)的艱苦拼砂

?IBM深藍(lán)的輝煌業(yè)績

?繼續(xù)向新的高峰攀譽

東北大學(xué)機(jī)器博弈研究室

追尋歷史的蹤跡

?:*1946年第一臺電子計算機(jī)

問世于美國。

馮?諾依曼

g教學(xué)家

g計算機(jī)之父

g提出極大極小定理

g為除征機(jī)器的正確性和性能，

首先為它編寫了象棋程序

東北大學(xué)機(jī)器博弈研究室

?Programmingacomputerforplayingchess》,

Shannon,1950

?“用極大極小值算法可以找到想下的棋,

但由于這個游戲的變化太多，不可能披奈

到終結(jié)點，所以就要尋找一種合逡的方法

只技奈部分節(jié)點，然后就可以到新該走哪

步棋，進(jìn)而走棋”

?：?現(xiàn)代計算機(jī)博棄的理論基礎(chǔ)

東北大學(xué)機(jī)器博弈研究室

許多人在努力

東北大學(xué)機(jī)器博弈研究室

他們來自于何方？

?Canada、America、England、China、

Japan>Holland>Mexico....

UniversityofAlberta,Universityof

Wisconsin,UniversityofMaryland,

MIT,UniversityofTokyo,University

ofAlbama,UniversityofCalifornia,

ErasmusUniversity,Cambrige

University.......

東北大學(xué)機(jī)器博弈研究室

世紀(jì)之戰(zhàn)

8深藍(lán)之父

61997年深藍(lán)戰(zhàn)觸

卡斯帕羅夫

東北大學(xué)機(jī)器博弈研究室

東北大學(xué)機(jī)器博弈研究室

電腦棋手：永不停歇的挑戰(zhàn)!

?2001年“更弗里茨”擊敗了除了克拉

姆尼克之外的所有排名世界前十佳的

棋手。

?:BOOZ年10月“更弗里茨”與世界棋王

克拉姆尼克在巴林交手,雙方以4比4

戰(zhàn)平。

年1至2月“更年少者”與卡斯帕

羅夫在紐約較量，3比3戰(zhàn)平。

東北大學(xué)機(jī)器博弈研究室

克拉姆尼科最新賽事(2006.11)

連續(xù)三屆奧林匹克冠軍Kramnik2-4DeepFritz

的公回…皿

EMANN

TheDuel：manmachine

Kramnikvs.

DeepFritzHES

須知：深弗里茨比當(dāng)年“深藍(lán)”運算能力快2個數(shù)量級

東北大學(xué)機(jī)器博弈研究室

棋類機(jī)器博弈的發(fā)展

機(jī)基博寺涉及的范倒:

Othello臭塞羅

Checkers西譯跳棋

Go-moku五子棋

Chess國際象棋

Chinesechess中國象棋

Shigo日本將棋

Go圈棋

東北大學(xué)機(jī)器博弈研究室

領(lǐng)域在延伸

?Checkers的譯跳棋

?Chinesechess中國象樵

?Go圈棋

?Shogi0本將棋，目本象棋

Poker紙牌游戲

Othello

。Sokoban

?LinesofactionHexAwariAmatons

RosamboDomineering...

東北大學(xué)機(jī)器博弈研究室

機(jī)器博弈的艱苦歷程與輝煌成果

?中國象棋----

被愛情遺忘的角落

?:?機(jī)器博棄工作者新的挑戰(zhàn)

?可喜的初戰(zhàn)勝利

?:?還有很長的路要走

?:?圍棋的機(jī)器博棄水平還彳艮低

東北大學(xué)機(jī)器博弈研究室

臺灣電腦象棋之父

前臺灣大學(xué)

資訊工程余教授

許舜欽

80年代開始

機(jī)器博奔研究

“Elephant”

現(xiàn)在臺南長榮大學(xué)

東北大學(xué)機(jī)器博弈研究室

中國電腦圍棋的驕傲

中山大學(xué)化學(xué)系

陳志行教授

“手微”

一匯編語言

1995J996J997

連續(xù)3年

6項世界冠軍

v電腦圈棋小洞天〉

東北大學(xué)機(jī)器博弈研究室

新的挑戰(zhàn)-----connect6

?臺灣交通大學(xué)教授吳故成

g六子棋發(fā)明人

儂公平的游戒

?：?六子棋相關(guān)網(wǎng)站

/web

東北大學(xué)機(jī)器博弈研究室

聘靖許峰雄博士報告、名譽教授、顧問

C2004.5.14J

東北大學(xué)機(jī)器博弈研究室

10thCOMPUTEROLYMPIAD

棋天大圣

勇奪

世界第三

東北大學(xué)機(jī)器博弈研究室

挑戰(zhàn)特級象棋大師卜風(fēng)迎

東北大學(xué)機(jī)器博弈研究室

ComputerOlympiad11奪冠

東北大學(xué)機(jī)器博弈研究室

浪潮杯首屆中國計算機(jī)博弈錦標(biāo)賽

棋天大圣

勇奪

全國冠I軍

2006.8.8

東北大學(xué)機(jī)器博弈研究室

浪潮杯首屆中國象棋人機(jī)大戰(zhàn)

對陣5佳象棋大師

卜風(fēng)波

徐天紅

柳大華

法強(qiáng)

注譯

2006年8月90

國家臭林匹克中心

綜合編

東北大學(xué)機(jī)器博弈研究室

人機(jī)大戰(zhàn)終極PK(2006815)

中國象棋第一人許銀川VS棋天大圣

東北大學(xué)機(jī)器博弈研究室

ComputerOlympiad12奪冠

東北大學(xué)機(jī)器博弈研究室

棋天大圣獲得

又一個世界冠軍

并與臺灣棋王吳貴臨

國際大師戰(zhàn)成平局

2007年7月

東北大學(xué)機(jī)器博弈研究室

民間棋類計算機(jī)博弈

?:?最簡單的機(jī)器博棄項國

——機(jī)器博棄入門課

?:?麻雀雖小，五臟俱全

?:?從一個實例出發(fā)----牛角棋

東北大學(xué)機(jī)器博弈研究室

民間棋類的特點

規(guī)則簡單，假家易入門；

不受專業(yè)知短限制；

?:?棋盤小,棋子少，復(fù)雜度不高;

?:?輸贏家易識別,局面京易判斷;

?:?完全信息，編程相對簡單；

?：?人工智能的“果蠅”O(jiān)

東北大學(xué)機(jī)器博弈研究室

牛角棋

牛角棋廣泛見于各地，別

名較多，如憋死牛、憋死

井、娃娃下山、娘子下山

等。

?:?棋盤形狀及棋佳數(shù)同也稍

有差異。但是棋子、棋規(guī)

都相同。

東北大學(xué)機(jī)器博弈研究室

牛角棋棋規(guī)

紅子可上可下，可左可右,

一次一步,只能走向空優(yōu),

不得重合與跳躍3

?藍(lán)子只上不下，可左可右,

一次一步,只能走向會住,

不得重合與跳跳；

?:?勝負(fù)到新：憋無憋不死？

東北大學(xué)機(jī)器博弈研究室

紅先紅勝（7步）

東北大學(xué)機(jī)器博弈研究室

紅先藍(lán)雁

（18步）

為什么輸贏？需要不斷地摸索經(jīng)除，試瞼所有的局面。

東北大學(xué)機(jī)器博弈研究室

博棄思維過程紅方先手

展開博棄樹

紅

方

走

ll\\IIW棋

東北大學(xué)機(jī)器博弈研究室

計算機(jī)是如何實現(xiàn)博弈過程的？

計算機(jī)如何進(jìn)行博棄思維?

如何編寫機(jī)器博棄程序？

東北大學(xué)機(jī)器博弈研究室

計算機(jī)如何進(jìn)行博弈思維?

?:?如何存儲思維信息？棋盤、棋子、棋

局、博棄樹

?:?如何判新局面的勝負(fù)？

?:?如何展開博棄樹？

?:?如何選擇當(dāng)前的看法？

?:?如何褊寫程序？

?:?如何總結(jié)博棄的規(guī)律？

東北大學(xué)機(jī)器博弈研究室

如何存儲思維信息?

編瑪----數(shù)據(jù)結(jié)構(gòu)

?棋盤編瑪r棋佳編嗎）

?棋子編瑪

?初始局面的表示

棋枚向量:(100000023)

?棋子向量:(089)

東北大學(xué)機(jī)器博弈研究室

S°=(0,8,9)

棋局演化的形式化描述

?狀思變量S0=(P：,P；,P：)棋子向量表示

初始狀態(tài)S。=(0,8,9)

?狀態(tài)障化方程S〃-1

.：.其中力+1為棋子i第〃+7步的看法r算子)

?:?著法規(guī)則：

紅子可上可下，可左可右，一次一步，只能走向空位，不得重合與跳躍；

藍(lán)子只上不下，可左可右，一次一步，只能走向空位，不得重合與跳躍；

東北大學(xué)機(jī)器博弈研究室

看法的形式化描述

/：幾=月±1,EH*e[0,9]

q?：瑤]=尸一1,P'=P、2e[0,9]

P\=，2+iG[2,8]cP；=even

產(chǎn)琛|=廳一1,P；「P；-2e[0,9]

P：1=￡.3+1G[2,8]nP：=even

通過掃描棋盤，如果“落址”為空住，便是合法看法（算子）O

東北大學(xué)機(jī)器博弈研究室

如何判斷局面的勝負(fù)？

?:?紅雁：“逃出”

P->P-orb>P；

?:?藍(lán)雁：“憋死”

Se=(?/，用=(0,2)D(0,2,1)

和棋----

局面的無限次重復(fù)

東北大學(xué)機(jī)器博弈研究室

如何展開博弈樹?

紅方先手

紅

方

走

棋

東北大學(xué)機(jī)器博弈研究室

如何表示博弈樹?

(0&9)

(2&9)(1,8,9)

(2,7,9)?(2,6,9)?(2,&7)

。z—-s^3Z4*sx。-s―z—3X4-z-0*s-3s4

333s3■93339s?

777766668888

393933939?3?

999999997777

東北大學(xué)機(jī)器博弈研究室

兩種不同的展開方式

廣度

優(yōu)先

東北大學(xué)機(jī)器博弈研究室

兩種不同的展開方式

深皮

優(yōu)先

東北大學(xué)機(jī)器博弈研究室

廣度優(yōu)先的展開與存儲

東北大學(xué)機(jī)器博弈研究室

深度優(yōu)先的展開與存儲

東北大學(xué)機(jī)器博弈研究室

如何選擇當(dāng)前的看法？

?在展開的博棄樹中披親——博棄技奈引擎

?:?如果紅方走棋，他總要找到博棄樹中最好

的棋局,而在考慮對方（藍(lán)方）走棋時,

就要考慮最壞的局面，因為雙方都是理智

的博親者，不應(yīng)該抱有任何僥幸的心理。

?:?如果給每個棋局打分，邢紅方可以稱得上

是MAX方，藍(lán)方便是MIN方。

東北大學(xué)機(jī)器博弈研究室

深度為3的博弈樹

層教

Ply=O

Ply=1

Ply=2

Ply=3

圖例：

東北大學(xué)機(jī)器博弈研究室

極大極小搜索

找到最佳路役與最佳看法

MAX

MIN

MAX

東北大學(xué)機(jī)器博弈研究室

從極大極小搜索到負(fù)極大值搜索

CurrentbestPVandbestmove

Alpha剪枝

找到最佳路徑與最佳看法

MAX4a=4

MIN

MAX584623

東北大學(xué)機(jī)器博弈研究室

B■剪枝ru

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

MIN

MAX

MIN

東北大學(xué)機(jī)器博弈研究室

B■剪枝C2J

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

MIN

MAX

MIN

負(fù)極大值形式的Alpha-beta梗素

?:.Alpha的含義：當(dāng)前方已經(jīng)存在某個看法,

其估值至少為alpha；

?:*Beta的含義：對手存在著某個看法，令當(dāng)前

方的著法的估值無論如何也越不過beta。

?負(fù)極大值形式的alpha-beta剪枝只有beta剪

枝。

東北大學(xué)機(jī)器博弈研究室

(alpha,betaJ窗口

?負(fù)極大值條件下的(alpha,betaJ窗口

東北大學(xué)機(jī)器博弈研究室

(alpha,betaJ窗口

An

東北大學(xué)機(jī)器博弈研究室

博弈樹枝索過程

BestPV

MoveGeneration

MakeMove

Cutoff

Meration

131189

ove

ation

東北大學(xué)機(jī)器博弈研究室

人

機(jī)

對

,弈

信

息

流

程

東北大學(xué)機(jī)器博弈研究室

計算引擎主要模塊

基本模塊

數(shù)

據(jù)

著法博弈樹局面

結(jié)

構(gòu)

相關(guān)搜索估值

「

,、

靜

基

子

棋

啟

態(tài)

力

盤

著

著

著

本

發(fā)

同

歷

子

棋

配

法

法

法a

式

型

史

生

子

選

力

排

8合

表

搜

表

序

成

擇

表

估

估

搜

索

示

值

值

索

東北大學(xué)機(jī)器博弈研究室

計算引擎程序的編寫

?:?首先需要解決的算法分析與設(shè)計

?:?然后考慮算法的實現(xiàn)與編程

r編程語言，設(shè)計，編碼,調(diào)試）

?:?遵照軟件工程學(xué)的思想

?:?在程序設(shè)計方法學(xué)上下功夫

。學(xué)習(xí)人工智能的先進(jìn)理論與技術(shù)

—這是所有專業(yè)所於需的！

東北大學(xué)機(jī)器博弈研究室

東北大學(xué)機(jī)器博弈研究室

棋子的表示

#defineREDSTONE0

#defineBLUESTONE11

#defineBLUESTONE22

東北大學(xué)機(jī)器博弈研究室

局面的表示（一）

初始局面的表示

intboard[10]=

(

REDSTONE,

0,0,0,0,

0,0,0,

BLUESTONE1,

BLUESTONE2,

｝；

東北大學(xué)機(jī)器博弈研究室

局面的表示（二）

?初始局面的表示

記錄有子的交叉點編號

(stoneIntersectionisi)

intsi[3]=

(

0,8,9

｝；

(注意off-by-one^

東北大學(xué)機(jī)器博弈研究室

等價的局面表示

等價的初始局面

intsi[3]=

(

0,8,9

｝；

intsi[3]=

(

0,9,8

東北大學(xué)機(jī)器博弈研究室

看法的表示

絕對看法的三個要素

Piece:哪個棋子

From：出發(fā)點編號

To：I標(biāo)點的編號

東北大學(xué)機(jī)器博弈研究室

著法的表示

相對看法更方便

Piece：哪個棋子

To：同標(biāo)點的編號

涵義：PieceTo

佳：543210

東北大學(xué)機(jī)器博弈研究室

看法生成

?:?著法生成是和棋類知M關(guān)系最為緊密的部分

?:?看法生成是博棄樹展開和技奈的先決條件

?:?著法生成是博棄程序中一個相當(dāng)復(fù)雜而且耗

費運算時間的部分

?:?通過前好的數(shù)據(jù)結(jié)構(gòu)(棋盤表示，看法表

示),可以顯著地提高生成的速度

?:?看法生成、實現(xiàn)(makemove)、評估、選擇

之后,還要恢復(fù)到父節(jié)A(unmakemove)

東北大學(xué)機(jī)器博弈研究室

看法生成（一）

棋盤掃描法

〃以紅子為例

for(eachpiece)

(

if((piecej+l<=9)

&&NoStoneAt(piecej+1))

*moveList++=piecCj+1;

if((O<=piecerl)

&&NoStoneAt(piecej-1))

*moveList++=piece”；

東北大學(xué)機(jī)器博弈研究室

看法生成（二）

預(yù)置表法

intpreTabIel21|10][5]=

/*redstonemovestable*/

{2,1,INV},{2,3,0,INV),

(4,3,1,0,INV},(5,4,2,1,INV},

{6,5,3,2,INV),{7,6,4,3,INV),

{8,7,5,4,INV),{9,8,6,5,INV},

{9,7,6,INV},{8,7,INV),

/*bluestonemovestable*/

{INV},{0,INV),

{3,1,0,INV},{2,1,INV),

{2,3,5,INV),{3,4,INV),

{4,5,7,INV},{5,6,INV),

{6,7,9,INV},{7,8,INV},

）；

東北大學(xué)機(jī)器博弈研究室

看法生成(二)

使用預(yù)置表法須注意：

根據(jù)牛角棋的規(guī)則，從預(yù)

置表中提取的看法需做如下合

法性判斷：

preTablefcolor][from][i]!=

si[j]；

(其中,0<=/<=4;j=0,1,2)

[piece,from]->[piece,to]

東北大學(xué)機(jī)器博弈研究室

博弈樹的展開與恢復(fù)

生成子節(jié)點局面

MakeMove()

椒鋪子節(jié)點局面

r恢復(fù)到父節(jié)點)

UnmakeMove()

東北大學(xué)機(jī)器博弈研究室

牛角棋的搜索算法

負(fù)極大值形式的alpha-beta按奈算法

intSearchfintdepth,intalpha,intbeta,intwtm)

Iif(depth<0)

ReturnEvaluation;

if(gameOver)

returnEvaluation;

〃逐一展開各子樹

for(eachMovem)

(

MakeMove(m);

val=-Search(depth-l,-beta,-alpha,!vvtm);

UnmakeMove(m);

-if(alpha<val)〃找到更好的看法

alpha=val;

if(alpha>=beta)//剪枝

returnalpha;

returnalpha;

東北大學(xué)機(jī)器博弈研究室

基

本

搜

索

流

程

東北大學(xué)機(jī)器博弈研究室

算法優(yōu)化

?博棄樹是根在上部向下遹歸產(chǎn)生的一棵

包含所有可能的對棄過程的技素樹，是

完全技素樹，包含了所有可能的博棄狀

態(tài)

?:?但是，有些情況我們不希堡重復(fù)救奈，

比如重復(fù)出現(xiàn)的局面（狀思J

東北大學(xué)機(jī)器博弈研究室

東北大學(xué)機(jī)器博弈研究室

循環(huán)局面的處理

技奈過程中循環(huán)局面的出現(xiàn)

若i<4則無循環(huán),注意

Path[i]與Path[i-4]的關(guān)余

Path

16926927917916900000

0123456789

東北大學(xué)機(jī)器博弈研究室

循環(huán)局面的處理

e建立一個順序表，命名為Path。

但每次披奈前將唯一表示當(dāng)前局面的值存入表中

e若當(dāng)前層為i,到新Path[i]是否等于Path[i-4]

e若相等，則剪枝，不等則繼續(xù)技奈

e搜親結(jié)束，將Path[i]賦值為0

e較復(fù)雜棋類，如象棋，一般用hash表實現(xiàn)循環(huán)局面的處

理。

東北大學(xué)機(jī)器博弈研究室

評估(-)

利條件

紅方勝的條件：

(sifREDSTONE]==8)||(sifREDSTONE]==9))

藍(lán)方雁的條件：

((si[REDSTONE]==0)&&

((sifBLUESTONEl]+si[BLUESTONE2])==3))

東北大學(xué)機(jī)器博弈研究室

棋局評估一勝負(fù)提前判別

不難看出，短兵相接，誰動誰輸。

可以整理判據(jù)，放到程序當(dāng)中。

東北大學(xué)機(jī)器博弈研究室

評估（二）

?：?其它人類知M

GS影響府負(fù)的重要條件

8局勢細(xì)微變化的索件

GS舉例

1)紅子突破，紅勝

((si[REDSTONE]>si[BLUESTONEl])||

(si[REDSTONE]>si[BLUESTONE2]))

2J藍(lán)走紅勝

((wtm==BLUE)&&

((si[REDSTONE]&1==0)&&

((si[BLUESTONEl]==si[REDSTONE]+l)&&

(si[BLUESTONE2]==si[REDSTONE]+2)||

(si[BLUESTONEl]==si[REDSTONE]+2)&&

(si[BLUESTONE2]==si[REDSTONE]+l))))

東北大學(xué)機(jī)器博弈研究室

如何編寫機(jī)器博弈程序？

會下棋，下好棋——了解規(guī)則，槿得棋局的好壞，

區(qū)分看法的好壞，如何能夠克敵制勝，如何立于不

敗之地。

?:?掌援計算機(jī)博棄的基本知出----棋局與看法表示的

數(shù)據(jù)結(jié)構(gòu)，著法生成與棋局評估，悔棄樹，果佳路

役與景佳看法等。

?:?按照軟件工程靖寫程序——需求分析，總體設(shè)計，

詳細(xì)設(shè)計，褊瑪調(diào)試，設(shè)計文才我軟件維護(hù)，條統(tǒng)

優(yōu)化等等。

東北大學(xué)機(jī)器博弈研究室

計算引擎程序的編寫

?:?首先需要解決的算法分析與設(shè)計

然后考慮算法的實現(xiàn)與編程

r編程語言，設(shè)計，編瑪，調(diào)試j

?：?■照軟件工程學(xué)的思想

?:?/■程序設(shè)計方法學(xué)上下功夫

?:?學(xué)習(xí)人工智能的先進(jìn)理論與技術(shù)

——這是所有專業(yè)所必需的！

東北大學(xué)機(jī)器博弈研究室

如何總結(jié)博弈的規(guī)律？

?:?通過博奔樹展開，考慮到分校教不大4,階雙教有限

（10步