六子棋機(jī)器博弈關(guān)鍵技術(shù)分析

1、徐長明、徐心和、王翠榮2011. 06. 13五子棋五子棋入手 起源于中國 發(fā)展在日本（棋型棋） Renju / Go-Moku 棋盤 1515五子棋機(jī)器博弈研究現(xiàn)狀五子棋機(jī)器博弈研究現(xiàn)狀入手 兩種常見的五子棋均已經(jīng)被成功破解 Go-moku(無禁手):于1994年解決 Renju(禁手):于2001年解決,花費(fèi)了9000小時(shí)=375天。 破解五子棋的重要因素 借助了機(jī)器博弈 當(dāng)時(shí)恰好發(fā)現(xiàn)新算法TSS（Threat Space Search）+PNS(Proof Number Search) 新的五子棋其規(guī)則變得復(fù)雜，致使趣味性大減六子棋簡介六子棋簡介入手 棋盤 1919 6子棋型為勝 復(fù)雜度

2、顯著提高吳毅成教授六子棋簡介六子棋簡介入手令connect(m, n, k, p, q) 代表一族k子棋，博弈的雙方分別執(zhí)黑和執(zhí)白，黑先。賦予connect(m, n, k, p, q)下述涵義：棋盤包含棋盤包含mn個(gè)交叉點(diǎn)。個(gè)交叉點(diǎn)。黑第一次下黑第一次下q枚棋子，此后，雙方輪流下枚棋子，此后，雙方輪流下p枚棋子。枚棋子。在在(水平的、垂直的、對角線方向的水平的、垂直的、對角線方向的)任何一條線上，任何一條線上，能率先形成本方連續(xù)不間斷的能率先形成本方連續(xù)不間斷的k子序列者取勝；若雙子序列者取勝；若雙方均無法取勝，判和。方均無法取勝，判和。 標(biāo)準(zhǔn)的六子棋是connect(19, 19, 6,

3、2, 1)，標(biāo)準(zhǔn)的五子棋是connect(15, 15, 5, 1, 1) 。復(fù)雜度復(fù)雜度入手二人博弈問題一般至少屬于NP-hard類，而且，多屬于PSPACE-complete(如奧賽羅) 或EXPTIME-complete(如中國象棋、西洋跳棋、國際象棋和圍棋等)類問題。在機(jī)器博弈問題中，如此分類稍顯粗糙。到底哪些棋類相對更難，以及難多少？復(fù)雜度復(fù)雜度入手狀態(tài)空間復(fù)雜度（從初始局面可達(dá)的）所有合法狀態(tài)的數(shù)目。博弈樹空間復(fù)雜度初始局面開始的解樹（Solution Tree）中所有結(jié)點(diǎn)的數(shù)目。影響棋類復(fù)雜程度的因素平均分枝因子一盤游戲的平均步數(shù)棋盤大小復(fù)雜度復(fù)雜度入手復(fù)雜度：計(jì)算復(fù)雜度為PSP

4、ACE-complete；平均分枝因子約為300；每盤棋平均30步。研究現(xiàn)狀：涉及到k子棋（如五子棋和六子棋）復(fù)雜度的文獻(xiàn)均高估了它的復(fù)雜度。零萬事開頭難，從哪里入手？1.六子棋 發(fā)明人吳毅成教授網(wǎng)站：/web/index.php?option=com_content&task=view&id=15&Itemid=26.簡評：介紹六子棋規(guī)則、歷史、理論、臺灣地區(qū)的六子棋活動等。其中，“六子棋教室”等欄目很有價(jià)值。參考文獻(xiàn)參考文獻(xiàn)入手簡評：很有價(jià)值的計(jì)算機(jī)博弈網(wǎng)站，里面有系統(tǒng)的入門資料。2.六子棋 的對弈網(wǎng)站：http:/ 黃晨

5、的象棋百科全書網(wǎng)站：http:/ Van den Herik, H.J. Uiterwijk, J.W.H.M. Van Rijswijck. Games solved: Now and in the future. Artificial Intelligence. 2002.簡評： 作者對計(jì)算機(jī)博弈有著深刻的認(rèn)識，該文預(yù)測了的幾種棋類的解決程度和大致時(shí)間，幾乎逐一應(yīng)驗(yàn)。參考文獻(xiàn)參考文獻(xiàn)入手簡評：很有價(jià)值的計(jì)算機(jī)博弈網(wǎng)站，里面有系統(tǒng)的入門資料。5. Wu, I.C. Huang, D.Y. A New Family of k-in-a-row Games. Advances in Comput

6、er Games. 2006.6. 黃晨的象棋百科全書：http:/ 棋盤 棋子 著法 規(guī)則 博弈樹 其它因素：玩家、進(jìn)攻、防守基本基本知識知識表示表示 啟發(fā)知識 殺手著法表 歷史著法表 臨時(shí)記憶的中間計(jì)算結(jié)果 置換表 拒絕表 長期記憶和維護(hù)的結(jié)論 開局庫（多基于經(jīng)驗(yàn)） 殘局庫（基于推理） 知識庫（多基于歸納）基本基本知識知識表示表示 完整的局面信息應(yīng)包含： 盤面上的棋子布局 走棋方是哪方局面的表示局面的表示知識表示棋盤的編碼棋盤的編碼 （舉例）二維數(shù)組表示法：建立平面坐標(biāo)系，如左圖 自底向上 自左向右 棋盤的表示方法 數(shù)組表示 bit棋盤 bit向量知識表示(0, 0) (0, 1) (0,

7、 2) (0,18) (1, 0) (1, 18)(18, 18)(18, 0)棋盤的編碼棋盤的編碼 （舉例）一維數(shù)組表示法：建立平面坐標(biāo)系，如左圖 行優(yōu)先 自左向右知識表示0 1 2 17 18 19 37360342棋盤的編碼（棋盤的編碼（13 13* *13 13棋盤為例）棋盤為例）知識表示程序的知識源于何處？n 專家（人類大師或?qū)I(yè)棋手）n 程序的自動推理其它的高級知識其它的高級知識知識表示K子棋數(shù)據(jù)表示存在的問題：n 基于交叉點(diǎn)的數(shù)據(jù)表示；n 缺乏從較高層級描述各個(gè)交叉點(diǎn)之間的緊密聯(lián)系的方法和手段；n 雖然可能引入了模式，但這樣的模式往往無法構(gòu)成局面描述的基本單位；n 模式知識一般是

8、不完整的，甚至主要依賴于程序設(shè)計(jì)者的個(gè)人經(jīng)驗(yàn)，具有隨意性。其它的高級知識其它的高級知識知識表示棋型棋型知識表示 在圍棋中，知識的表示用“模式”、串、龍等描述。這些知識是棋手總結(jié)的一些經(jīng)驗(yàn)，關(guān)注的是棋子之間的配合、聯(lián)絡(luò)、分割、圍地等。 六子棋比圍棋簡單得多。實(shí)際上，它在“模式”描述上要比圍棋容易得多；而且我們能找到辦法把那些可復(fù)用的知識描述和刻畫得更精確。問題解決的難度受其表示方法影響。棋型的抽取棋型的抽取知識表示 棋型及其諸屬性棋型及其諸屬性棋型 c棋型的顏色 color(c)棋型的長度 |c|棋型的形狀 |c|棋型的起點(diǎn)棋型的起點(diǎn) from(c) 棋型的方向棋型的方向 orit(c) 棋型的

9、威脅數(shù)棋型的威脅數(shù) th(c) 棋型的類型棋型的類型 ct(c)棋型的表示棋型的表示知識表示全部連珠共劃分為12個(gè)不相交的子集，即12種類型：(a) WIN；(b) DW；(c) L5；(d) D5；(e) L4；(f) S4；(g) D4；(h) L3；(i) S3；(j) D3；(k) L2； (l) O 。棋型的分類棋型的分類知識表示獲取棋型分類的方法獲取棋型分類的方法知識表示黑方怎樣獲勝？ 升變描述了在一個(gè)棋型中添加一枚同色棋子，它會演化為何種棋型。棋型間的演化棋型間的演化知識表示去除冗余的演化去除冗余的演化知識表示 某些威脅類型之間的升變是非理性的，因而是冗余的。連通度的計(jì)算連通度的

10、計(jì)算知識表示威脅數(shù)的計(jì)算威脅數(shù)的計(jì)算知識表示空交叉點(diǎn)的分類知識空交叉點(diǎn)的分類知識知識表示判斷上述棋型中各個(gè)交叉點(diǎn)的價(jià)值1. 下列4個(gè)棋型，用交叉點(diǎn)的狀態(tài)序列描述，交叉點(diǎn)上有黑子用X表示，交叉點(diǎn)空白用- 表示。請指出：下列棋型的類型；如果黑方足夠理性，哪個(gè)棋型是不可能出現(xiàn)的，為什么？(1) XX- - XXXX- XX- XXXX- XX(2) X- - XX- XXX- - XXX- - XX- 思考題思考題知識表示簡評：很有價(jià)值的計(jì)算機(jī)博弈網(wǎng)站，里面有系統(tǒng)的入門資料。2.六子棋 的對弈網(wǎng)站：http:/ 黃晨的象棋百科全書網(wǎng)站：http:/ 逐步生成。 基于預(yù)置表生成。著法排序的策略： 先將

11、著法分類。 再根據(jù)各個(gè)子類進(jìn)行排序。知識知識表示表示估值估值函數(shù)函數(shù)搜索搜索算法算法狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換三37估值函數(shù)設(shè)計(jì)的傳統(tǒng)方法 估值函數(shù)設(shè)計(jì)的一般方法 參數(shù)調(diào)整需高水平棋手的參與，且耗時(shí)甚巨； 容易出錯(cuò)且嚴(yán)重依賴設(shè)計(jì)者的棋類領(lǐng)域知識； 一種棋類的經(jīng)驗(yàn)難以推廣到其它棋類。 例：國際跳棋的世界冠軍程序Chinook的參數(shù)調(diào)整歷時(shí)5年。38TD學(xué)習(xí) TDTD學(xué)習(xí)學(xué)習(xí) 自動調(diào)整參數(shù)，無需人工干預(yù) 對領(lǐng)域知識要求甚少，可通過自學(xué)習(xí)提高水平 例：自學(xué)習(xí)訓(xùn)練150萬盤的西洋雙陸棋TD-Gammon其水平已經(jīng)全面超越人類頂尖高手。39TDLConn6的體系結(jié)構(gòu)圖圖 TDLConn6的體系結(jié)構(gòu)圖40TD學(xué)習(xí)算

12、法的執(zhí)行過程圖5.2 TD學(xué)習(xí)算法的執(zhí)行過程41權(quán)值調(diào)整自動化BP神經(jīng)元網(wǎng)絡(luò) 輸入層設(shè)計(jì) 隱藏層設(shè)計(jì) 輸出層設(shè)計(jì) Sigmoid函數(shù)的選擇 g(x)=1/(1+exp(-x) 用1.0表示取勝，0.5表示和棋，0.0表示輸棋42整合先驗(yàn)知識與神經(jīng)元網(wǎng)絡(luò)的估值函數(shù) 估值函數(shù) V(p) = S(p)+ NN(p)(SMax()SMin()/(NNMax() NNMin(); 其中， 優(yōu)點(diǎn)： 第一，兼顧了引入先驗(yàn)知識和自動調(diào)整權(quán)值的需求； 第二，通過先驗(yàn)知識粗略勾勒出估值函數(shù)，通過神經(jīng)元網(wǎng)絡(luò)精調(diào)估值函數(shù)的權(quán)值，先驗(yàn)知識有助于加速訓(xùn)練的收斂； 第三，通過參數(shù)來表達(dá)對先驗(yàn)知識的信心。43自學(xué)習(xí)訓(xùn)練樣本的

13、選擇圖5.4 可應(yīng)用TD學(xué)習(xí)的狀態(tài)序列知識知識表示表示估值估值函數(shù)函數(shù)搜索搜索算法算法狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換四TSS TSS是二值搜索，若求解成功，搜索算法會返回true或false。 二值搜索需要預(yù)設(shè)一個(gè)二元問題，搜索的目標(biāo)就是肯定該問題為真，或否定該問題： 例如：“黑方能贏么？” 對于TSS搜索，就是“MAX方（進(jìn)攻方）能通過連續(xù)的威脅著法獲勝么？”TSS原理黑DTSS勝的一個(gè)變化（輪黑走）STSS舉例由左圖可知：在上圖中黑可STSS勝黑可TSS勝的一個(gè)局面（輪黑走）TSS的形式化描述表2 TSS搜索的相關(guān)記號、函數(shù)及其涵義TSS的形式化描述表3 TSS搜索的結(jié)果及其涵義TSS的形式化描述1.

14、DTSS(pi, A A, A A) = true 2. MAi 3. ( ma MAi) (4. pi+1 = Succ(pi, A A, ma) 5. 2 Th(A A, pi+1) 6. Th(D D, pi+1) = 0 7. DTSS(pi+1, A A, D D) = true8. );9. DTSS(pi, A A, D D) = true 10. MDi 11. ( md MDi) (12. pi+1 = Succ(pi, D D, md) 13. (14. 0 Th(A A, pi+1) 15. DTSS(pi+1, A A, A A) = true16. )17. );(a

15、) DTSS(pi, x, y) = true的遞歸推導(dǎo)18. DTSS(pi, A A, A A) = false 19. MAi = 20. (21. MAi 22. ( ma MAi) (23. pi+1 = Succ(pi, A A, ma) 24. (25. Th(A, pi+1) 2 26. Th(D, pi+1) 0 27. DTSS(pi+1, A A, D D) = false28. ) 29. )30. );31. DTSS(pi, A A, D D) = false 32. MDi = 33. (34. MDi 35. ( md MDi) (36. pi+1 = Succ

16、(pi, D D, md) 37. (38. Th(A A, pi+1) = 0 39. DTSS(pi+1, A A, A A) = false40. )41. )42. );(b) DTSS(pi, x, y) = false的遞歸推導(dǎo)圖1 描述DTSS策略遞歸規(guī)則的偽代碼TSS的擴(kuò)展Anti-TSS表2 Anti-TSS搜索的相關(guān)記號、函數(shù)及其涵義TSS的擴(kuò)展Anti-TSS1. Anti-TSS(pi, A, A) = false2. MAi (ma MAi) (3. pi+1 = Succ(pi, A, ma) 4. MDi+1 (md MDi+1) (5. pi+2 = Succ(pi+1, D, md) 6. TSS(pi+2, A, D) = false7. )8. );描述Anti-TSS策略規(guī)則的偽碼TSS搜索 一般采用深度優(yōu)先搜索方式； 難點(diǎn)： 搜索的最大深度的設(shè)置； 時(shí)