Download presentation
Presentation is loading. Please wait.
1
電腦圍棋程式設計的 演進與發展 僑光技術學院 資訊科技系 嚴礽麒
2
電腦對局(Computer Game) 是人工智慧(Artificial Intelligent)的領域之一
讓電腦程式具有思考分析能力，能夠與人進行黑白棋、五子棋、西洋棋、象棋、圍棋等等的對奕。 例：由IBM超級電腦上所研發的西洋棋程式『深藍』(DeepBlue)，在1997年擊敗了當代的世界冠軍卡斯帕洛夫(Kasparov)。
3
常見棋類遊戲介紹 黑白棋(Othello) 五子棋(Go-moku) 西洋棋(Chess) 象棋(Chinese Chess)
六子棋(Connect 6) 圍棋(Go)
4
一般常見的誤解 誤解1：電腦對局程式可以將所有的棋譜輸入電腦，因而戰勝人腦。
誤解2：電腦計算速度太快，人一定算不贏電腦，所以所有的棋類遊戲都一定是電腦必勝。 誤解3：一個下棋很遜的程式設計者，無法設計出一個比他厲害的下棋程式。
5
象棋的複雜度概算 通常一盤棋大約經過40回合(共80步)可得到最後結果。 每回合可走的所有棋步平均約有45種。
複雜度粗略估計： 45*45*45*…*45 = 4580 最後再考慮去除一些對稱重複情形後，將之微調大約是10150。
6
棋類遊戲難易度分析 黑白棋 五子棋 西洋棋 象棋 圍棋 複雜度 1050 1080 10123 10150 10700 比人類最強者強？
絕對是 大約是 不是 遠不如人類
7
電腦 vs. 人腦 電腦優勢： 運算速度極快 能記憶大量資料 不會有情緒影響 人腦優勢： 具有敏銳的直覺 能將經驗累積成知識
8
電腦對局理論基礎 遊戲樹(Game Tree) 最大最小值搜尋(Minimax Search) α-β pruning
Iterative deepening search
9
遊戲樹(Game Tree) 電腦程式先將所有可能的走法整理出來，然後嘗試走走看；接著再將對方所有可能走法也整理出來，接著也去走走看。如此循環反覆，一直進行到某種條件符合才停止，然後經過審局函數評估，再從其中選出最佳著手。 用到遞迴呼叫觀念。 執行時間通常相當久。 除錯工作不容易。
10
遊戲樹概念圖 我方著手 敵方著手 我方著手 Win 50 80 Lose -5 Win 20 40 90
11
審局函數(Evaluation) 在遊戲樹中用來評估局面的優劣程度(假定正值表示我方佔優，負值表示敵方佔優，其絕對值大小代表優勢程度高低)。
審局函數在計算上愈快愈好。 審局函數愈精準，則對於著手的建議愈正確。
13
象棋的審局函數(1) 10000 200 1000 420 450 100 通常會將不同兵種給予一個固定分數
審局時只要將雙方棋盤上的子力分數加總對比，就可以得到一個近似正確的估計值。 10000 200 1000 420 450 100
14
象棋的審局函數(2) 除了子力之外，尚可將棋子位置也納入評估優劣的考量。
絕對位置：例如馬臥槽是絕佳位置，馬塞在將正前方是極惡位置。 相對位置：馬被擋馬腳、象被塞象眼都是不好位置；而包佔據空頭是絕佳位置。 但增加此項考量，亦有計算較費時的缺點，是否採用仍是trade-off的問題。
15
象棋局勢分析範例
16
最大最小值搜尋 概念：由於輪到我方著手時，會盡量使我方局勢有利(評估值愈大愈好)；輪到敵方著手時，會盡量使我方局勢不利(評估值愈小愈好)。
作法：在搜尋過程上，由底層終端節點經由審局函數取得評估值後，視該層由何方著手來選出最大值或最小值予以傳回。
17
最大最小值搜尋概念圖 80 -5 40 Win 90 我方Max 敵方Min 我方Max Win 50 80 Lose -5 Win 20
90
18
α-β pruning 概念：是用來改良最大最小值搜尋的效能。亦即當某種條件成立時，一些搜尋的分支路徑完全可以省略。
19
α-β pruning概念圖 80 -5 40 Win 90 我方Max 敵方Min 我方Max Win 50 80 Lose -5
20 40 90
20
圍棋基本規則―氣與提子
21
圍棋基本規則―打劫(1)
22
圍棋基本規則―打劫(2)
23
圍棋基本規則―打劫(3)
24
圍棋基本規則―打劫(4)
25
圍棋的死活
26
圍棋基本規則―勝負計算 黑棋29目，白棋25目
27
圍棋棋力鑑定標準 低 高 初 (業餘) 級 段 初 2 3…9 段 (職業)
28
象棋與圍棋的相異處 可選擇棋步總數不同 兵種與性質不同 全局性與局部性 設計困難處不同 審局函數 著手選擇
29
圍棋的困難
30
電腦圍棋的歷史 起始：Zobrist，1969年。 早期時代：1970~1985年。
過渡時代：約自1986年開始，局部重點加強，例如棋形資料庫與棋串吃逃搜尋。 成熟時代：約始於1989年，具備了多目標式的搜尋系統，而且也有了簡單的局勢分析，甚至是靜態的死活判斷。
31
電腦圍棋程式比賽 應氏盃(1985~2000) Computer Olympiad Tournament(1990~)
FOST盃(1995~2000)
32
應氏盃早中期程式水平
33
1990年後程式水平 具有棋塊概念 地域認知能力 多目標搜尋系統 靜態死活分析能力 眼位分析能力 死活知識庫建立
34
目前最強圍棋程式 HandTalk：廣東中山大學陳志行教授研發
MoGo：為法國程式工程師Sylvain Gelly與 Yizao Wang所研發 Crazy Stone：為法國程式工程師Remi Coulon所研發 Go Intellect：北卡大學陳克訓教授研發 Aya：日本學者研發 GnuGo：是個開放程式讓大家研發的程式
35
電腦圍棋的物件階層 棋子(stone) 棋串(block) 棋鏈(chain) 棋塊(group)
36
勢力影響值 作法：利用每個棋子對於周圍具有或多或少影響力的概念，去計算盤面的勢力值。 4 目的： 辨識雙方勢力強弱 用於設定棋塊範圍
預估雙方可能地域 協助判斷棋塊安危 4
37
勢力影響值應用實例(1) -5 -6 3 14 17 6 -3 -6 0 -7 -1 8 28 32 11 -8 -6 -5
38
勢力影響值應用實例(2)
39
棋串設定方法 使用圖形連通的DFS演算法 對每個棋串記錄其子數、棋子位置、氣數、氣點位置、相鄰敵方棋串等資訊
40
棋鏈的種類 尖(黑▲) 扳(白) 跳(黑◎) 飛(白□)
41
棋塊『連通』的條件 同色棋子 同色棋鏈空點 強勢點 敵方死子
42
棋塊的範圍與地域辨識
43
棋塊的地域認定 邊界點：棋塊最外層的棋子或空點， 潛力點：由邊界空點向內推一層，代表可能成為地域的點，
地域點：棋塊內部空點或敵方死子，可視為確定地
44
棋塊安危認定原則 初步認定： 詳細認定： 棋塊的地域點是否足夠 棋塊是否被包圍 棋塊的潛力點個數多寡 靜態死活分析
周圍有無敵方的危險或死亡棋塊
45
專家棋士下棋的思路 敏銳的棋塊安危感覺 熟練的棋形要點反應 精簡深入的細算思考 直接進攻、聲東擊西、纏繞攻擊、製造雙擊
設法安定、拓寬出路、以攻代守 熟練的棋形要點反應 精簡深入的細算思考
46
靜態死活分析 目的：採取完全不用search的方式，直接從棋塊之地域點作眼位分析，來判斷棋塊死活。
所需資訊：棋塊的地域點個數、位置、各點真假眼形態、有無敵方死子、有無中心位置等。 所需技術：專業的圍棋知識、細膩精確的分析歸納能力、不斷的反覆測試
47
著手選擇系統 著手選擇模組： 棋塊死活 棋塊攻防 連結分斷 棋串吃逃 地域搶佔 以預估目數出入作為著手分數 目前分支度：8
48
審局函數判斷因素 棋塊確定地域目數 周圍可能成地之潛力 棋塊安危程度及範圍大小 危險棋串之有無 棋塊中的缺陷棋形
49
全局搜尋基本架構 Game Tree structure Minimax search & α-β pruning Depth：6
Width：8 other skills
50
棋形的觀念 棋形樣式(Pattern) 應用實例
51
棋形樣式的方向轉換
52
棋形樣式的擷取
53
棋形的分類 依棋形術語分類(製作時) 依棋形用途分類(應用時) 根據棋子配置的相對位置關係來區分 例如尖、跳、飛、長、扳、虎
根據著點的作用與含意來區分 例如連結、分斷、擴大、壓迫、整形
54
棋形的等級 緊急：大多屬於連接、分斷類棋形 重要：大多是包圍、突破，以及重要的擴 張、壓迫類棋形
重要：大多是包圍、突破，以及重要的擴 張、壓迫類棋形 一般：屬於一般常見的下法，不特別重要 但也相當實用 特殊：屬於特殊情況才使用的手法，多半 有奇兵之意味
55
棋形樣式(pattern)的表示 _ _ _ _ _ _ X O _ _ _ . . X _ _ . @ @ _ 33 33 6
56
棋形樣式中之特殊狀況 _ _ _ _ _ _ _ X O _ Matching and Good _ X . X _ _ _ O _ _
Matching and Good Matching but Bad
57
棋形系統的選點實例
58
系統之工具程式 目的：有助於開發圍棋程式系統 特色： 全部採用專家經驗法則去歸納分析 重視正確性與效率 不用到任何search或遞迴
59
避免不進子問題
60
系統解出的「撲」手範例
61
棋串安危的認定 棋串安危認定 => 棋塊安危認定 方式： 效能比較： 靜態安危分析系統 動態攻殺搜尋系統
準確度：動態(9成) > 靜態(7~8成) 速度：靜態 >> 動態
62
靜態棋串安危分析 棋串安危等級： LIBERTY_SAFE：氣數夠多而視為安全。 CAREFUL：大致上安全，但有微小的不安。
DANGEROUS：氣數為2~3氣，並且伴隨了一些危險因子(氣點太靠近盤端、…)。 VERY_DANGEROUS：危險等級非常高，伴隨的危險因子更多。 EXPIRED：只剩1氣且非「反提」的棋串。
63
棋串安危分析判斷因素 棋串氣數 氣點位置 氣點周圍有無敵子 氣點周圍有無敵方棋鏈 有無友方支援棋鏈 勢力影響值高低
64
棋串安危靜態分析實例
65
棋串攻殺搜尋系統 尋找敵我雙方的目標棋串 攻擊方(Killer)負責襲殺目標棋串 防守方(Defender)負責救援目標棋串
攻防雙方 recursive call 形成 game tree 由 AND-OR方式產生決策 以布林值 True代表棋串安全 以布林值 False代表棋串被吃
66
F T 代表安全 F 代表被吃 Killer (AND) Defender(OR) 1 2 3 T T F T F F F F
T T F T F F F F F T F T
67
提高搜尋效率的方法 設定著手選擇之 priority 將較佳之著手優先進行搜尋 降低 branch (棋步選擇量)
68
Killer Moves之分類 直接緊氣 「撲」 避免不進子 包圍 攻擊連結鏈棋串 逃出我方(包圍者)之棋串 攻殺手筋 系統測試實例
69
緊氣原則 目標棋串愈能長氣之點愈優先 包圍之棋串能順便長氣之點較優先
70
撲 是將棋子送入對方虎口中，迫使對方提吃，以求能迅速縮減對方氣數之手法。
71
包圍 利用「包圍鏈」來封鎖目標棋串 只要目標棋串尚未被封鎖，且氣數低於安全氣數，則包圍的 priority就比較高。
72
攻擊連結鏈棋串 分斷連結鏈之聯繫 側襲連結鏈之棋串
73
救援我方包圍棋串之範例 救援的方法選擇 救援的重要性
74
不進子的處理 連接會被提吃之位置 (B點) 對接觸之敵方已死棋串緊氣 (C點)
75
手筋範例 點入 第一線立下
76
系統測試範例
77
靜態死活分析系統 概念：在棋塊區域辨識後，能夠根據棋塊中的相關資訊，以『無搜尋』的方式分析研判該棋塊的眼位。
目的：為了提升搜尋效能，增快審局函數判斷局勢的速度。
78
名詞定義 眼位區(Eye Region)：是指棋塊中某一個獨立且連通的地域範圍所形成的集合。
眼位點(Eye Point)：是指該眼位區中包含的所有空點或敵方死子之位置。 眼位個數(Eye number)：是指眼位區R中包含的眼位數(Re)。 棋塊眼位數＝ΣRe
79
棋塊眼位數計算範例 眼位區1(A) ： 0.5 眼位區2(B、C)： 0 眼位區3(D、E)： 1
棋塊眼位數 ＝ = 1.5 危險
80
眼位點分析因素 位置：地域點、潛力點、邊界點 眼形種類：真眼、半眼、假眼 狀態：空點、敵方死子
81
靜態死活分析範例
82
開局時搜尋情況(1) 搜尋廣度問題 α-β pruning 之效能
83
開局時搜尋情況(2) 搜尋深度問題 複雜局勢不易明確分析
84
開局知識庫系統 目的：為彌補開局階段搜尋深廣度不足。
作法：使用hash function將九路棋盤盤面以及相關資訊儲存到一個極大的檔案中，藉由不斷的輸入實戰棋譜資料，使其具備學習功能。 技巧：由於棋譜檔案很大，且未來資料量會隨之增多，必須處理對稱盤面造成的重複，以及盤面資訊如何正確解讀問題。
85
開局知識庫實作概念 Hash function 棋譜檔案
86
開局知識庫著點選擇 依勝負局數資訊分析 以亂數決定 著點 A B C D E 勝局 32 8 2 1 負局 34 24 勝率 48 25
負局 34 24 勝率 48 25 50 33
87
開局知識庫界面
88
發展電腦圍棋的條件 最好是該種棋類高手 圓熟的程式設計功力 具資料結構理論基礎 優異的邏輯分析能力 鍥而不捨的研究精神
89
設計電腦圍棋之甘苦談 生不逢時 獨孤求勝 速成 v.s. 大成？ 大破大立 廢寢忘食之毅力 嘔心瀝血的除錯
90
The End
Similar presentations
