Computer Go 计算机围棋.ppt

1、電腦圍棋程式設計的演進與發展,僑光技術學院 資訊科技系嚴礽麒,電腦對局(Computer Game),是人工智慧(Artificial Intelligent)的領域之一 讓電腦程式具有思考分析能力，能夠與人進行黑白棋、五子棋、西洋棋、象棋、圍棋等等的對奕。 例：由IBM超級電腦上所研發的西洋棋程式深藍(DeepBlue)，在1997年擊敗了當代的世界冠軍卡斯帕洛夫(Kasparov)。,常見棋類遊戲介紹,黑白棋(Othello) 五子棋(Go-moku) 西洋棋(Chess) 象棋(Chinese Chess) 六子棋(Connect 6) 圍棋(Go),一般常見的誤解,誤解1：電腦對局程式

2、可以將所有的棋譜輸入電腦，因而戰勝人腦。 誤解2：電腦計算速度太快，人一定算不贏電腦，所以所有的棋類遊戲都一定是電腦必勝。 誤解3：一個下棋很遜的程式設計者，無法設計出一個比他厲害的下棋程式。,象棋的複雜度概算,通常一盤棋大約經過40回合(共80步)可得到最後結果。 每回合可走的所有棋步平均約有45種。 複雜度粗略估計：45*45*45*45 = 4580 最後再考慮去除一些對稱重複情形後，將之微調大約是10150。,棋類遊戲難易度分析,電腦 vs. 人腦,電腦優勢： 運算速度極快 能記憶大量資料 不會有情緒影響 人腦優勢： 具有敏銳的直覺 能將經驗累積成知識,電腦對局理論基礎,遊戲樹(Gam

3、e Tree) 最大最小值搜尋(Minimax Search) - pruning Iterative deepening search,遊戲樹(Game Tree),電腦程式先將所有可能的走法整理出來，然後嘗試走走看；接著再將對方所有可能走法也整理出來，接著也去走走看。如此循環反覆，一直進行到某種條件符合才停止，然後經過審局函數評估，再從其中選出最佳著手。 用到遞迴呼叫觀念。 執行時間通常相當久。 除錯工作不容易。,遊戲樹概念圖,我方著手,敵方著手,我方著手,Win,Win,Lose,50,80,-5,20,40,0,90,審局函數(Evaluation),在遊戲樹中用來評估局面的優劣程度(

4、假定正值表示我方佔優，負值表示敵方佔優，其絕對值大小代表優勢程度高低)。 審局函數在計算上愈快愈好。 審局函數愈精準，則對於著手的建議愈正確。,象棋的審局函數(1),通常會將不同兵種給予一個固定分數 審局時只要將雙方棋盤上的子力分數加總對比，就可以得到一個近似正確的估計值。,10000 200 200 1000 420 450 100,象棋的審局函數(2),除了子力之外，尚可將棋子位置也納入評估優劣的考量。 絕對位置：例如馬臥槽是絕佳位置，馬塞在將正前方是極惡位置。 相對位置：馬被擋馬腳、象被塞象眼都是不好位置；而包佔據空頭是絕佳位置。 但增加此項考量，亦有計算較費時的缺點，是否採用仍是tra

5、de-off的問題。,象棋局勢分析範例,最大最小值搜尋,概念：由於輪到我方著手時，會盡量使我方局勢有利(評估值愈大愈好)；輪到敵方著手時，會盡量使我方局勢不利(評估值愈小愈好)。 作法：在搜尋過程上，由底層終端節點經由審局函數取得評估值後，視該層由何方著手來選出最大值或最小值予以傳回。,最大最小值搜尋概念圖,我方Max,敵方Min,我方Max,Win,Win,Lose,50,80,-5,20,40,0,90,- pruning,概念：是用來改良最大最小值搜尋的效能。亦即當某種條件成立時，一些搜尋的分支路徑完全可以省略。 技巧：如果能將著手選擇優劣事先作排序，則- pruning 的效果會更好。

6、,- pruning概念圖,我方Max,敵方Min,我方Max,Win,Win,Lose,50,80,-5,20,40,0,90,圍棋基本規則氣與提子,圍棋基本規則打劫(1),圍棋基本規則打劫(2),圍棋基本規則打劫(3),圍棋基本規則打劫(4),圍棋的死活,圍棋基本規則勝負計算,黑棋29目，白棋25目,圍棋棋力鑑定標準,低 高 9 8 7 6 5 4 3 2 1 初 2 3 4 5 6 7(業餘) 級 段 初 2 39 段 (職業),象棋與圍棋的相異處,可選擇棋步總數不同 兵種與性質不同 全局性與局部性 設計困難處不同 審局函數 著手選擇,圍棋的困難,電腦圍棋的歷史,起始：Zobrist，1

7、969年。 早期時代：19701985年。 過渡時代：約自1986年開始，局部重點加強，例如棋形資料庫與棋串吃逃搜尋。 成熟時代：約始於1989年，具備了多目標式的搜尋系統，而且也有了簡單的局勢分析，甚至是靜態的死活判斷。,電腦圍棋程式比賽,應氏盃(19852000) Computer Olympiad Tournament(1990) FOST盃(19952000),應氏盃早中期程式水平,1990年後程式水平,具有棋塊概念 地域認知能力 多目標搜尋系統 靜態死活分析能力 眼位分析能力 死活知識庫建立,目前最強圍棋程式,HandTalk：廣東中山大學陳志行教授研發 MoGo：為法國程式工程師S

8、ylvain Gelly與 Yizao Wang所研發 Crazy Stone：為法國程式工程師Remi Coulon所研發 Go Intellect：北卡大學陳克訓教授研發 Aya：日本學者研發 GnuGo：是個開放程式讓大家研發的程式,電腦圍棋的物件階層,棋子(stone) 棋串(block) 棋鏈(chain) 棋塊(group),勢力影響值,作法：利用每個棋子對於周圍具有或多或少影響力的概念，去計算盤面的勢力值。 目的： 辨識雙方勢力強弱 用於設定棋塊範圍 預估雙方可能地域 協助判斷棋塊安危,4 6 8 6 5 12 16 12 5 6 12 24 32 24 12 6 4 8 16

9、32 32 32 16 8 4 6 12 24 32 24 12 6 5 12 16 12 5 6 8 6 4,勢力影響值應用實例(1),-5 -6 3 14 17 6 -3 -6 0 -7 -1 8 28 32 11 -8 -6 -5 6 12 44 50 40 8 -22 -22 -8 12 36 48 62 41 -10 -30 -34 -21 18 36 61 51 16 -34 -65 -53 -24 17 35 42 32 -8 -59 -72 -56 -27 16 34 34 24 -18 -54 -68 -46 -20 12 24 30 16 -17 -38 -44 -24 -

10、11 5 12 16 7 -7 -22 -20 -11 0,勢力影響值應用實例(2),0 6 8 6 0 0 0 0 0 5 16 16 8 5 0 -4 0 0 18 36 28 12 10 0 -8 -6 0 34 45 28 17 1 -3 -16 -12 -5 37 49 35 1 -13 -29 -41 -30 -12 40 47 20 -4 -21 -45 -50 -42 -21 48 54 48 14 -14 -30 -60 -44 -20 42 61 44 25 17 -19 -30 -34 -21 31 43 45 31 17 -5 -29 -30 -12,棋串設定方法,使用

11、圖形連通的DFS演算法 對每個棋串記錄其子數、棋子位置、氣數、氣點位置、相鄰敵方棋串等資訊,棋鏈的種類,尖(黑) 扳(白) 跳(黑) 飛(白),棋塊連通的條件,同色棋子 同色棋鏈空點 強勢點 敵方死子,棋塊的範圍與地域辨識,棋塊的地域認定,邊界點：棋塊最外層的棋子或空點， 潛力點：由邊界空點向內推一層，代表可能成為地域的點， 地域點：棋塊內部空點或敵方死子，可視為確定地,棋塊安危認定原則,初步認定： 棋塊的地域點是否足夠 棋塊是否被包圍 棋塊的潛力點個數多寡 詳細認定： 靜態死活分析 周圍有無敵方的危險或死亡棋塊,專家棋士下棋的思路,敏銳的棋塊安危感覺 直接進攻、聲東擊西、纏繞攻擊、製造雙擊

12、設法安定、拓寬出路、以攻代守 熟練的棋形要點反應 精簡深入的細算思考,靜態死活分析,目的：採取完全不用search的方式，直接從棋塊之地域點作眼位分析，來判斷棋塊死活。 所需資訊：棋塊的地域點個數、位置、各點真假眼形態、有無敵方死子、有無中心位置等。 所需技術：專業的圍棋知識、細膩精確的分析歸納能力、不斷的反覆測試,著手選擇系統,著手選擇模組： 棋塊死活 棋塊攻防 連結分斷 棋串吃逃 地域搶佔 以預估目數出入作為著手分數 目前分支度：8,審局函數判斷因素,棋塊確定地域目數 周圍可能成地之潛力 棋塊安危程度及範圍大小 危險棋串之有無 棋塊中的缺陷棋形,全局搜尋基本架構,Game Tree str

13、ucture Minimax search & - pruning Depth：6 Width：8 other skills,棋形的觀念,棋形樣式(Pattern),應用實例,棋形樣式的方向轉換,棋形樣式的擷取,棋形的分類,依棋形術語分類(製作時) 根據棋子配置的相對位置關係來區分 例如尖、跳、飛、長、扳、虎 依棋形用途分類(應用時) 根據著點的作用與含意來區分 例如連結、分斷、擴大、壓迫、整形,棋形的等級,緊急：大多屬於連接、分斷類棋形 重要：大多是包圍、突破，以及重要的擴 張、壓迫類棋形 一般：屬於一般常見的下法，不特別重要 但也相當實用 特殊：屬於特殊情況才使用的手法，多半 有奇兵之意味

14、,棋形樣式(pattern)的表示,_ _ _ _ _ _ X O _ _ _ . . X _ _ . _ _ _ _ _ _ 33 33 6 4 8 00,棋形樣式中之特殊狀況,_ _ _ _ _ _ _ X O _ _ X . X _ _ _ O _ _ _ _ _ _ _ 33 33 11 4 8 00,Matching and Good,Matching but Bad,棋形系統的選點實例,系統之工具程式,目的：有助於開發圍棋程式系統 特色： 全部採用專家經驗法則去歸納分析 重視正確性與效率 不用到任何search或遞迴,避免不進子問題,系統解出的撲手範例,棋串安危的認定,棋串安危認定

15、 = 棋塊安危認定 方式： 靜態安危分析系統 動態攻殺搜尋系統 效能比較： 準確度：動態(9成) 靜態(78成) 速度：靜態 動態,靜態棋串安危分析,棋串安危等級： LIBERTY_SAFE：氣數夠多而視為安全。 CAREFUL：大致上安全，但有微小的不安。 DANGEROUS：氣數為23氣，並且伴隨了一些危險因子(氣點太靠近盤端、)。 VERY_DANGEROUS：危險等級非常高，伴隨的危險因子更多。 EXPIRED：只剩1氣且非反提的棋串。,棋串安危分析判斷因素,棋串氣數 氣點位置 氣點周圍有無敵子 氣點周圍有無敵方棋鏈 有無友方支援棋鏈 勢力影響值高低,棋串安危靜態分析實例,棋串攻殺搜尋

16、系統,尋找敵我雙方的目標棋串 攻擊方(Killer)負責襲殺目標棋串 防守方(Defender)負責救援目標棋串 攻防雙方 recursive call 形成 game tree 由 AND-OR方式產生決策 以布林值 True代表棋串安全 以布林值 False代表棋串被吃,Killer (AND) Defender(OR) Killer (AND) Defender(OR),F T F T,T F F F F,T T F,1 2 3,F,T 代表安全 F 代表被吃,提高搜尋效率的方法,設定著手選擇之 priority 將較佳之著手優先進行搜尋 降低 branch (棋步選擇量),Killer

17、 Moves之分類,直接緊氣 撲 避免不進子 包圍 攻擊連結鏈棋串 逃出我方(包圍者)之棋串 攻殺手筋 系統測試實例,緊氣原則,目標棋串愈能長氣之點愈優先,包圍之棋串能順便長氣之點較優先,撲,是將棋子送入對方虎口中，迫使對方提吃，以求能迅速縮減對方氣數之手法。,包圍,利用包圍鏈來封鎖目標棋串 只要目標棋串尚未被封鎖，且氣數低於安全氣數，則包圍的 priority就比較高。,攻擊連結鏈棋串,分斷連結鏈之聯繫,側襲連結鏈之棋串,救援我方包圍棋串之範例,救援的方法選擇,救援的重要性,不進子的處理,連接會被提吃之位置 (B點) 對接觸之敵方已死棋串緊氣 (C點),手筋範例,點入,第一線立下,系統測試範

18、例,靜態死活分析系統,概念：在棋塊區域辨識後，能夠根據棋塊中的相關資訊，以無搜尋的方式分析研判該棋塊的眼位。 目的：為了提升搜尋效能，增快審局函數判斷局勢的速度。,名詞定義,眼位區(Eye Region)：是指棋塊中某一個獨立且連通的地域範圍所形成的集合。 眼位點(Eye Point)：是指該眼位區中包含的所有空點或敵方死子之位置。 眼位個數(Eye number)：是指眼位區R中包含的眼位數(Re)。 棋塊眼位數Re,棋塊眼位數計算範例,眼位區1(A) ： 0.5 眼位區2(B、C)： 0 眼位區3(D、E)： 1 棋塊眼位數 0.5 + 0 + 1 = 1.5 危險,眼位點分析因素,位置：地域點、潛力點、邊界點 眼形種類：真眼、半眼、假眼 狀態：空點、敵方死子,靜態死活分析範例,開局時搜尋情況(1),搜尋廣度問題 - pruning 之效能,開局時搜尋情況(2),搜尋深度問題 複雜局勢不易明確分析,開局知識庫系統,目的：為彌補開局階段搜尋深廣度不足。 作法：使用hash func