民間棋類計算機博棄

徐心和徐長明

東北大學機舞博棄研究重

2007年7月

主要內＜

?:?什么是計算機悔棄r機賽博界）?

機器博棄的艱苦歷程與輝煌成果

?:?氏同棋類計算機博界

——機器博棄的入門課

?:?計算機是如何實現博棄過程的？

?:?機器博棄的技術構成與內涵

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

東北大學機器博弈研究室

什么是計算機博弈?

討算機博棄，機器悔界

ComputerGames

主要是指計算機下棋、航牌

----像人一樣的思維

景先提出的就是計算機下

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

東北大學機器博弈研究室

機器博弈是一個特殊的研究領域

?:?它是非常實際的計算機科學與技術的研究課題

?:?它是非常畬于挑戰性的人工智能領域的研究方向

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

?:?它是現代博棄論所不能斛決的動態博棄技術

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

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

。它具有廣闊的應用前景——對策問題

（控制，決策、對策）

東北大學機器博弈研究室

機器博弈的艱苦歷程與辱煌成果

國際象棋——

?景先提出的計算機應用課題之一

?計算機前聚所關注的研究課題

?半個世紀的艱苦拼砂

?IBM深藍的輝煌業績

?繼續向新的高峰攀譽

東北大學機器博弈研究室

追尋歷史的蹤跡

?:*1946年第一臺電子計算機

問世于美國。

馮?諾依曼

g教學家

g計算機之父

g提出極大極小定理

g為除征機器的正確性和性能，

首先為它編寫了象棋程序

東北大學機器博弈研究室

?Programmingacomputerforplayingchess》,

Shannon,1950

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

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

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

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

步棋，進而走棋”

?：?現代計算機博棄的理論基礎

東北大學機器博弈研究室

許多人在努力

東北大學機器博弈研究室

他們來自于何方？

?Canada、America、England、China、

Japan>Holland>Mexico....

UniversityofAlberta,Universityof

Wisconsin,UniversityofMaryland,

MIT,UniversityofTokyo,University

ofAlbama,UniversityofCalifornia,

ErasmusUniversity,Cambrige

University.......

東北大學機器博弈研究室

世紀之戰

8深藍之父

61997年深藍戰觸

卡斯帕羅夫

東北大學機器博弈研究室

東北大學機器博弈研究室

電腦棋手：永不停歇的挑戰!

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

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

棋手。

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

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

戰平。

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

羅夫在紐約較量，3比3戰平。

東北大學機器博弈研究室

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

連續三屆奧林匹克冠軍Kramnik2-4DeepFritz

的公回…皿

EMANN

TheDuel：manmachine

Kramnikvs.

DeepFritzHES

須知：深弗里茨比當年“深藍”運算能力快2個數量級

東北大學機器博弈研究室

棋類機器博弈的發展

機基博寺涉及的范倒:

Othello臭塞羅

Checkers西譯跳棋

Go-moku五子棋

Chess國際象棋

Chinesechess中國象棋

Shigo日本將棋

Go圈棋

東北大學機器博弈研究室

領域在延伸

?Checkers的譯跳棋

?Chinesechess中國象樵

?Go圈棋

?Shogi0本將棋，目本象棋

Poker紙牌游戲

Othello

。Sokoban

?LinesofactionHexAwariAmatons

RosamboDomineering...

東北大學機器博弈研究室

機器博弈的艱苦歷程與輝煌成果

?中國象棋----

被愛情遺忘的角落

?:?機器博棄工作者新的挑戰

?可喜的初戰勝利

?:?還有很長的路要走

?:?圍棋的機器博棄水平還彳艮低

東北大學機器博弈研究室

臺灣電腦象棋之父

前臺灣大學

資訊工程余教授

許舜欽

80年代開始

機器博奔研究

“Elephant”

現在臺南長榮大學

東北大學機器博弈研究室

中國電腦圍棋的驕傲

中山大學化學系

陳志行教授

“手微”

一匯編語言

1995J996J997

連續3年

6項世界冠軍

v電腦圈棋小洞天〉

東北大學機器博弈研究室

新的挑戰-----connect6

?臺灣交通大學教授吳故成

g六子棋發明人

儂公平的游戒

?：?六子棋相關網站

/web

東北大學機器博弈研究室

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

C2004.5.14J

東北大學機器博弈研究室

10thCOMPUTEROLYMPIAD

棋天大圣

勇奪

世界第三

東北大學機器博弈研究室

挑戰特級象棋大師卜風迎

東北大學機器博弈研究室

ComputerOlympiad11奪冠

東北大學機器博弈研究室

浪潮杯首屆中國計算機博弈錦標賽

棋天大圣

勇奪

全國冠I軍

2006.8.8

東北大學機器博弈研究室

浪潮杯首屆中國象棋人機大戰

對陣5佳象棋大師

卜風波

徐天紅

柳大華

法強

注譯

2006年8月90

國家臭林匹克中心

綜合編

東北大學機器博弈研究室

人機大戰終極PK(2006815)

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

東北大學機器博弈研究室

ComputerOlympiad12奪冠

東北大學機器博弈研究室

棋天大圣獲得

又一個世界冠軍

并與臺灣棋王吳貴臨

國際大師戰成平局

2007年7月

東北大學機器博弈研究室

民間棋類計算機博弈

?:?最簡單的機器博棄項國

——機器博棄入門課

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

?:?從一個實例出發----牛角棋

東北大學機器博弈研究室

民間棋類的特點

規則簡單，假家易入門；

不受專業知短限制；

?:?棋盤小,棋子少，復雜度不高;

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

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

?：?人工智能的“果蠅”O

東北大學機器博弈研究室

牛角棋

牛角棋廣泛見于各地，別

名較多，如憋死牛、憋死

井、娃娃下山、娘子下山

等。

?:?棋盤形狀及棋佳數同也稍

有差異。但是棋子、棋規

都相同。

東北大學機器博弈研究室

牛角棋棋規

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

一次一步,只能走向空優,

不得重合與跳躍3

?藍子只上不下，可左可右,

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

不得重合與跳跳；

?:?勝負到新：憋無憋不死？

東北大學機器博弈研究室

紅先紅勝（7步）

東北大學機器博弈研究室

紅先藍雁

（18步）

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

東北大學機器博弈研究室

博棄思維過程紅方先手

展開博棄樹

紅

方

走

ll\\IIW棋

東北大學機器博弈研究室

計算機是如何實現博弈過程的？

計算機如何進行博棄思維?

如何編寫機器博棄程序？

東北大學機器博弈研究室

計算機如何進行博弈思維?

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

局、博棄樹

?:?如何判新局面的勝負？

?:?如何展開博棄樹？

?:?如何選擇當前的看法？

?:?如何褊寫程序？

?:?如何總結博棄的規律？

東北大學機器博弈研究室

如何存儲思維信息?

編瑪----數據結構

?棋盤編瑪r棋佳編嗎）

?棋子編瑪

?初始局面的表示

棋枚向量:(100000023)

?棋子向量:(089)

東北大學機器博弈研究室

S°=(0,8,9)

棋局演化的形式化描述

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

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

?狀態障化方程S〃-1

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

?:?著法規則：

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

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

東北大學機器博弈研究室

看法的形式化描述

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

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

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

產琛|=廳一1,P；「P；-2e[0,9]

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

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

東北大學機器博弈研究室

如何判斷局面的勝負？

?:?紅雁：“逃出”

P->P-orb>P；

?:?藍雁：“憋死”

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

和棋----

局面的無限次重復

東北大學機器博弈研究室

如何展開博弈樹?

紅方先手

紅

方

走

棋

東北大學機器博弈研究室

如何表示博弈樹?

(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

東北大學機器博弈研究室

兩種不同的展開方式

廣度

優先

東北大學機器博弈研究室

兩種不同的展開方式

深皮

優先

東北大學機器博弈研究室

廣度優先的展開與存儲

東北大學機器博弈研究室

深度優先的展開與存儲

東北大學機器博弈研究室

如何選擇當前的看法？

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

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

的棋局,而在考慮對方（藍方）走棋時,

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

的博親者，不應該抱有任何僥幸的心理。

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

是MAX方，藍方便是MIN方。

東北大學機器博弈研究室

深度為3的博弈樹

層教

Ply=O

Ply=1

Ply=2

Ply=3

圖例：

東北大學機器博弈研究室

極大極小搜索

找到最佳路役與最佳看法

MAX

MIN

MAX

東北大學機器博弈研究室

從極大極小搜索到負極大值搜索

CurrentbestPVandbestmove

Alpha剪枝

找到最佳路徑與最佳看法

MAX4a=4

MIN

MAX584623

東北大學機器博弈研究室

B■剪枝ru

由此產生豪佳路位和景佳看法

MIN

MAX

MIN

東北大學機器博弈研究室

B■剪枝C2J

由此產生豪佳路位和景佳看法

MIN

MAX

MIN

負極大值形式的Alpha-beta梗素

?:.Alpha的含義：當前方已經存在某個看法,

其估值至少為alpha；

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

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

?負極大值形式的alpha-beta剪枝只有beta剪

枝。

東北大學機器博弈研究室

(alpha,betaJ窗口

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

東北大學機器博弈研究室

(alpha,betaJ窗口

An

東北大學機器博弈研究室

博弈樹枝索過程

BestPV

MoveGeneration

MakeMove

Cutoff

Meration

131189

ove

ation

東北大學機器博弈研究室

人

機

對

,弈

信

息

流

程

東北大學機器博弈研究室

計算引擎主要模塊

基本模塊

數

據

著法博弈樹局面

結

構

相關搜索估值

「

,、

靜

基

子

棋

啟

態

力

盤

著

著

著

本

發

同

歷

子

棋

配

法

法

法a

式

型

史

生

子

選

力

排

8合

表

搜

表

序

成

擇

表

估

估

搜

索

示

值

值

索

東北大學機器博弈研究室

計算引擎程序的編寫

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

?:?然后考慮算法的實現與編程

r編程語言，設計，編碼,調試）

?:?遵照軟件工程學的思想

?:?在程序設計方法學上下功夫

。學習人工智能的先進理論與技術

—這是所有專業所於需的！

東北大學機器博弈研究室

東北大學機器博弈研究室

棋子的表示

#defineREDSTONE0

#defineBLUESTONE11

#defineBLUESTONE22

東北大學機器博弈研究室

局面的表示（一）

初始局面的表示

intboard[10]=

(

REDSTONE,

0,0,0,0,

0,0,0,

BLUESTONE1,

BLUESTONE2,

｝；

東北大學機器博弈研究室

局面的表示（二）

?初始局面的表示

記錄有子的交叉點編號

(stoneIntersectionisi)

intsi[3]=

(

0,8,9

｝；

(注意off-by-one^

東北大學機器博弈研究室

等價的局面表示

等價的初始局面

intsi[3]=

(

0,8,9

｝；

intsi[3]=

(

0,9,8

東北大學機器博弈研究室

看法的表示

絕對看法的三個要素

Piece:哪個棋子

From：出發點編號

To：I標點的編號

東北大學機器博弈研究室

著法的表示

相對看法更方便

Piece：哪個棋子

To：同標點的編號

涵義：PieceTo

佳：543210

東北大學機器博弈研究室

看法生成

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

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

?:?著法生成是博棄程序中一個相當復雜而且耗

費運算時間的部分

?:?通過前好的數據結構(棋盤表示，看法表

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

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

之后,還要恢復到父節A(unmakemove)

東北大學機器博弈研究室

看法生成（一）

棋盤掃描法

〃以紅子為例

for(eachpiece)

(

if((piecej+l<=9)

&&NoStoneAt(piecej+1))

*moveList++=piecCj+1;

if((O<=piecerl)

&&NoStoneAt(piecej-1))

*moveList++=piece”；

東北大學機器博弈研究室

看法生成（二）

預置表法

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},

）；

東北大學機器博弈研究室

看法生成(二)

使用預置表法須注意：

根據牛角棋的規則，從預

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

法性判斷：

preTablefcolor][from][i]!=

si[j]；

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

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

東北大學機器博弈研究室

博弈樹的展開與恢復

生成子節點局面

MakeMove()

椒鋪子節點局面

r恢復到父節點)

UnmakeMove()

東北大學機器博弈研究室

牛角棋的搜索算法

負極大值形式的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;

東北大學機器博弈研究室

基

本

搜

索

流

程

東北大學機器博弈研究室

算法優化

?博棄樹是根在上部向下遹歸產生的一棵

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

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

態

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

比如重復出現的局面（狀思J

東北大學機器博弈研究室

東北大學機器博弈研究室

循環局面的處理

技奈過程中循環局面的出現

若i<4則無循環,注意

Path[i]與Path[i-4]的關余

Path

16926927917916900000

0123456789

東北大學機器博弈研究室

循環局面的處理

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

但每次披奈前將唯一表示當前局面的值存入表中

e若當前層為i,到新Path[i]是否等于Path[i-4]

e若相等，則剪枝，不等則繼續技奈

e搜親結束，將Path[i]賦值為0

e較復雜棋類，如象棋，一般用hash表實現循環局面的處

理。

東北大學機器博弈研究室

評估(-)

利條件

紅方勝的條件：

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

藍方雁的條件：

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

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

東北大學機器博弈研究室

棋局評估一勝負提前判別

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

可以整理判據，放到程序當中。

東北大學機器博弈研究室

評估（二）

?：?其它人類知M

GS影響府負的重要條件

8局勢細微變化的索件

GS舉例

1)紅子突破，紅勝

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

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

2J藍走紅勝

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

東北大學機器博弈研究室

如何編寫機器博弈程序？

會下棋，下好棋——了解規則，槿得棋局的好壞，

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

敗之地。

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

數據結構，著法生成與棋局評估，悔棄樹，果佳路

役與景佳看法等。

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

詳細設計，褊瑪調試，設計文才我軟件維護，條統

優化等等。

東北大學機器博弈研究室

計算引擎程序的編寫

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

然后考慮算法的實現與編程

r編程語言，設計，編瑪，調試j

?：?■照軟件工程學的思想

?:?/■程序設計方法學上下功夫

?:?學習人工智能的先進理論與技術

——這是所有專業所必需的！

東北大學機器博弈研究室

如何總結博弈的規律？

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

（10步