电脑围棋程式设计的演进与发展.ppt

电脑围棋程式设计的演进与发展￿￿￿￿Still￿waters￿run￿deep.流静水深流静水深,人静心深人静心深￿￿￿￿Where￿there￿is￿life,￿there￿is￿hope有生命必有希望有生命必有希望電腦對局(Computer Game)n n是人工智慧(Artificial Intelligent)的領域之一n n讓電腦程式具有思考分析能力，能夠與人進行黑白棋、五子棋、西洋棋、象棋、圍棋等等的對奕n n例：由IBM超級電腦上所研發的西洋棋程式『深藍』(DeepBlue)，在1997年擊敗了當代的世界冠軍卡斯帕洛夫(Kasparov)常見棋類遊戲介紹n n黑白棋(Othello)n n五子棋(Go-moku)n n西洋棋(Chess)n n象棋(Chinese Chess)n n六子棋(Connect 6)n n圍棋(Go)一般常見的誤解n n誤解1：電腦對局程式可以將所有的棋譜輸入電腦，因而戰勝人腦n n誤解2：電腦計算速度太快，人一定算不贏電腦，所以所有的棋類遊戲都一定是電腦必勝n n誤解3：一個下棋很遜的程式設計者，無法設計出一個比他厲害的下棋程式象棋的複雜度概算n n通常一盤棋大約經過40回合(共80步)可得到最後結果。

n n每回合可走的所有棋步平均約有45種n n複雜度粗略估計：45*45*45*…*45 = 4580n n最後再考慮去除一些對稱重複情形後，將之微調大約是10150棋類遊戲難易度分析黑白棋黑白棋五子棋五子棋西洋棋西洋棋象棋象棋圍棋圍棋複雜度複雜度1010505010108080101012312310101501501010700700比人類比人類最強者最強者強？強？絕對是絕對是絕對是絕對是大約是大約是不是不是遠不如遠不如人類人類電腦 vs. 人腦n n電腦優勢：n n運算速度極快運算速度極快n n能記憶大量資料能記憶大量資料n n不會有情緒影響不會有情緒影響n n人腦優勢：n n具有敏銳的直覺具有敏銳的直覺n n能將經驗累積成知識能將經驗累積成知識電腦對局理論基礎n n遊戲樹(Game Tree)n n最大最小值搜尋(Minimax Search)n nα-β pruningn nIterative deepening search遊戲樹(Game Tree)n n電腦程式先將所有可能的走法整理出來，然後嘗試走走看；接著再將對方所有可能走法也整理出來，接著也去走走看如此循環反覆，一直進行到某種條件符合才停止，然後經過審局函數評估，再從其中選出最佳著手。

n n用到遞迴呼叫觀念n n執行時間通常相當久n n除錯工作不容易遊戲樹概念圖我方著手敵方著手我方著手WinWinLose5080-52040090審局函數(Evaluation)n n在遊戲樹中用來評估局面的優劣程度(假定正值表示我方佔優，負值表示敵方佔優，其絕對值大小代表優勢程度高低)n n審局函數在計算上愈快愈好n n審局函數愈精準，則對於著手的建議愈正確象棋的審局函數(1)n n通常會將不同兵種給通常會將不同兵種給予一個固定分數予一個固定分數n n審局時只要將雙方棋審局時只要將雙方棋盤上的子力分數加總盤上的子力分數加總對比，就可以得到一對比，就可以得到一個近似正確的估計值個近似正確的估計值100002002001000420450100象棋的審局函數(2)n n除了子力之外，尚可將棋子位置也納入評估優劣的考量n n絕對位置：例如馬臥槽是絕佳位置，馬塞在將絕對位置：例如馬臥槽是絕佳位置，馬塞在將正前方是極惡位置正前方是極惡位置n n相對位置：馬被擋馬腳、象被塞象眼都是不好相對位置：馬被擋馬腳、象被塞象眼都是不好位置；而包佔據空頭是絕佳位置位置；而包佔據空頭是絕佳位置n n但增加此項考量，亦有計算較費時的缺點，是否採用仍是trade-off的問題。

象棋局勢分析範例最大最小值搜尋n n概念：由於輪到我方著手時，會盡量使我方局勢有利(評估值愈大愈好)；輪到敵方著手時，會盡量使我方局勢不利(評估值愈小愈好)n n作法：在搜尋過程上，由底層終端節點經由審局函數取得評估值後，視該層由何方著手來選出最大值或最小值予以傳回最大最小值搜尋概念圖8080-540Win80-5Win4090我方Max敵方Min我方MaxWinWinLose5080-52040090α-β pruningn n概念：是用來改良最大最小值搜尋的效能亦即當某種條件成立時，一些搜尋的分支路徑完全可以省略n n技巧：如果能將著手選擇優劣事先作排序，則α-β pruning 的效果會更好α-β pruning概念圖8080-540Win80-5Win4090我方Max敵方Min我方MaxWinWinLose5080-52040090圍棋基本規則―氣與提子圍棋基本規則―打劫(1)圍棋基本規則―打劫(2)圍棋基本規則―打劫(3)圍棋基本規則―打劫(4)圍棋的死活圍棋基本規則―勝負計算黑棋29目，白棋25目圍棋棋力鑑定標準低低 高高9 8 7 6 5 4 3 2 1 初 2 3 4 5 6 7(業餘)級 段 初 2 3…9 段 (職業)象棋與圍棋的相異處n n可選擇棋步總數不同n n兵種與性質不同n n全局性與局部性n n設計困難處不同n n審局函數審局函數n n著手選擇著手選擇圍棋的困難電腦圍棋的歷史n n起始：Zobrist，1969年。

n n早期時代：1970~1985年n n過渡時代：約自1986年開始，局部重點加強，例如棋形資料庫與棋串吃逃搜尋n n成熟時代：約始於1989年，具備了多目標式的搜尋系統，而且也有了簡單的局勢分析，甚至是靜態的死活判斷電腦圍棋程式比賽n n應氏盃(1985~2000)n nComputer Olympiad Tournament(1990~)n nFOST盃(1995~2000)應氏盃早中期程式水平1990年後程式水平n n具有棋塊概念具有棋塊概念n n地域認知能力地域認知能力n n多目標搜尋系統多目標搜尋系統n n靜態死活分析能力靜態死活分析能力n n眼位分析能力眼位分析能力n n死活知識庫建立死活知識庫建立目前最強圍棋程式n nHandTalk：廣東中山大學陳志行教授研發n nMoGo：為法國程式工程師Sylvain Gelly與 Yizao Wang所研發n nCrazy Stone：為法國程式工程師Remi Coulon所研發n nGo Intellect：北卡大學陳克訓教授研發n nAya：日本學者研發n nGnuGo：是個開放程式讓大家研發的程式電腦圍棋的物件階層n n棋子棋子(stone)(stone)n n棋串棋串(block)(block)n n棋鏈棋鏈(chain)(chain)n n棋塊棋塊(group)(group)勢力影響值n n作法：利用每個棋子作法：利用每個棋子對於周圍具有或多或對於周圍具有或多或少影響力的概念，去少影響力的概念，去計算盤面的勢力值。

計算盤面的勢力值n n目的：目的：n n辨識雙方勢力強弱辨識雙方勢力強弱n n用於設定棋塊範圍用於設定棋塊範圍n n預估雙方可能地域預估雙方可能地域n n協助判斷棋塊安危協助判斷棋塊安危 4 4 6 8 6 6 8 6 5 12 16 12 5 5 12 16 12 5 6 12 24 32 24 12 6 6 12 24 32 24 12 6 4 8 16 32 4 8 16 32 3232 32 16 8 4 32 16 8 4 6 12 24 32 24 12 6 6 12 24 32 24 12 6 5 12 16 12 5 5 12 16 12 5 6 8 6 6 8 6 4 4勢力影響值應用實例(1) -5 -6 3 14 17 6 -3 -6 0 -5 -6 3 14 17 6 -3 -6 0 -7 -1 8 -7 -1 8 28 3228 32 11 -8 -6 -5 11 -8 -6 -5 6 12 6 12 44 50 4044 50 40 8 -22 -22 -8 8 -22 -22 -8 12 12 36 48 62 4136 48 62 41 -10 -10 -30 -34-30 -34 -21 -21 18 18 36 61 5136 61 51 16 16 -34 -65 -53-34 -65 -53 -24 -24 17 17 35 42 3235 42 32 -8 -8 -59 -72 -56-59 -72 -56 -27 -27 16 16 34 3434 34 24 -18 24 -18 -54 -68 -46-54 -68 -46 -20 -20 12 24 12 24 3030 16 -17 16 -17 -38 -44-38 -44 -24 -11 -24 -11 5 12 16 7 -7 -22 -20 -11 0 5 12 16 7 -7 -22 -20 -11 0勢力影響值應用實例(2) 0 6 8 6 0 0 0 0 0 0 6 8 6 0 0 0 0 0 5 16 16 8 5 0 -4 0 0 5 16 16 8 5 0 -4 0 0 18 36 28 12 10 0 -8 -6 0 18 36 28 12 10 0 -8 -6 0 34 45 34 45 28 28 17 1 -3 -16 -12 -5 17 1 -3 -16 -12 -5 37 49 35 37 49 35 1 1 -13 -29 -41 -30 -12 -13 -29 -41 -30 -12 40 40 4747 20 20 -4-4 -21-21 -45 -45 -50-50 -42 -21 -42 -21 48 48 5454 48 1448 14 -14-14 -30 -60 -44 -20 -30 -60 -44 -20 42 61 42 61 44 2544 25 17 -19 17 -19 -30-30 -34 -21 -34 -21 31 43 45 31 17 -5 -29 -30 -12 31 43 45 31 17 -5 -29 -30 -12棋串設定方法n n使用圖形連通的使用圖形連通的DFSDFS演算法演算法n n對每個棋串記錄其子數、棋子位置、氣數、氣點對每個棋串記錄其子數、棋子位置、氣數、氣點位置、相鄰敵方棋串等資訊位置、相鄰敵方棋串等資訊棋鏈的種類n n尖尖( (黑黑▲▲) )n n扳扳( (白白) )n n跳跳( (黑黑◎◎) )n n飛飛( (白白□)□)棋塊『連通』的條件n n同色棋子n n同色棋鏈空點n n強勢點n n敵方死子棋塊的範圍與地域辨識棋塊的地域認定n n邊界點：棋塊最外層邊界點：棋塊最外層的棋子或空點，的棋子或空點，n n潛力點：由邊界空點潛力點：由邊界空點向內推一層，代表可向內推一層，代表可能成為地域的點，能成為地域的點，n n地域點：棋塊內部空地域點：棋塊內部空點或敵方死子，可視點或敵方死子，可視為確定地為確定地棋塊安危認定原則n n初步認定：n n棋塊的地域點是否足夠棋塊的地域點是否足夠n n棋塊是否被包圍棋塊是否被包圍n n棋塊的潛力點個數多寡棋塊的潛力點個數多寡n n詳細認定：n n靜態死活分析靜態死活分析n n周圍有無敵方的危險或死亡棋塊周圍有無敵方的危險或死亡棋塊專家棋士下棋的思路n n敏銳的棋塊安危感覺n n直接進攻、聲東擊西、纏繞攻擊、製造雙擊直接進攻、聲東擊西、纏繞攻擊、製造雙擊n n設法安定、拓寬出路、以攻代守設法安定、拓寬出路、以攻代守n n熟練的棋形要點反應n n精簡深入的細算思考靜態死活分析n n目的：採取完全不用search的方式，直接從棋塊之地域點作眼位分析，來判斷棋塊死活。

n n所需資訊：棋塊的地域點個數、位置、各點真假眼形態、有無敵方死子、有無中心位置等n n所需技術：專業的圍棋知識、細膩精確的分析歸納能力、不斷的反覆測試著手選擇系統n n著手選擇模組：n n棋塊死活棋塊死活n n棋塊攻防棋塊攻防n n連結分斷連結分斷n n棋串吃逃棋串吃逃n n地域搶佔地域搶佔n n以預估目數出入作為著手分數n n目前分支度：8審局函數判斷因素n n棋塊確定地域目數n n周圍可能成地之潛力n n棋塊安危程度及範圍大小n n危險棋串之有無n n棋塊中的缺陷棋形全局搜尋基本架構n nGame Tree structuren nMinimax search & α-β pruningn nDepth：6n nWidth：8n nother skills棋形的觀念棋形樣式(Pattern)應用實例棋形樣式的方向轉換棋形樣式的擷取棋形的分類n n依棋形術語分類(製作時)n n根據棋子配置的相對位置關係來區分根據棋子配置的相對位置關係來區分n n例如尖、跳、飛、長、扳、虎例如尖、跳、飛、長、扳、虎n n依棋形用途分類(應用時)n n根據著點的作用與含意來區分根據著點的作用與含意來區分n n例如連結、分斷、擴大、壓迫、整形例如連結、分斷、擴大、壓迫、整形棋形的等級n n緊急：大多屬於連接、分斷類棋形n n重要：大多是包圍、突破，以及重要的擴 張、壓迫類棋形n n一般：屬於一般常見的下法，不特別重要 但也相當實用n n特殊：屬於特殊情況才使用的手法，多半 有奇兵之意味棋形樣式(pattern)的表示_ _ _ _ __ X O _ __ . . X __ . @ @ __ _ _ _ _ 33 33 6 4 8 00棋形樣式中之特殊狀況_ _ _ _ __ _ X O __ X . X __ _ O _ __ _ _ _ _33 33 11 4 8 00Matching and GoodMatching but Bad棋形系統的選點實例系統之工具程式n n目的：有助於開發圍棋程式系統n n特色：n n全部採用專家經驗法則去歸納分析全部採用專家經驗法則去歸納分析n n重視正確性與效率重視正確性與效率n n不用到任何不用到任何searchsearch或遞迴或遞迴避免不進子問題系統解出的「撲」手範例棋串安危的認定n n棋串安危認定 => 棋塊安危認定n n方式：n n靜態安危分析系統靜態安危分析系統n n動態攻殺搜尋系統動態攻殺搜尋系統n n效能比較：n n準確度：動態準確度：動態(9(9成成) > ) > 靜態靜態(7~8(7~8成成) )n n速度：靜態速度：靜態 >> >> 動態動態靜態棋串安危分析n n棋串安危等級：n nLIBERTY_SAFELIBERTY_SAFE：氣數夠多而視為安全。

氣數夠多而視為安全n nCAREFULCAREFUL：大致上安全，但有微小的不安大致上安全，但有微小的不安n nDANGEROUSDANGEROUS：氣數為：氣數為2~32~3氣，並且伴隨了一些氣，並且伴隨了一些危險因子危險因子( (氣點太靠近盤端、氣點太靠近盤端、…)…)n nVERY_DANGEROUSVERY_DANGEROUS：危險等級非常高，伴隨：危險等級非常高，伴隨的危險因子更多的危險因子更多n nEXPIREDEXPIRED：只剩：只剩1 1氣且非「反提」的棋串氣且非「反提」的棋串棋串安危分析判斷因素n n棋串氣數n n氣點位置n n氣點周圍有無敵子n n氣點周圍有無敵方棋鏈n n有無友方支援棋鏈n n勢力影響值高低棋串安危靜態分析實例棋串攻殺搜尋系統n n尋找敵我雙方的目標棋串n n攻擊方(Killer)負責襲殺目標棋串n n防守方(Defender)負責救援目標棋串n n攻防雙方 recursive call 形成 game treen n由 AND-OR方式產生決策n n以布林值以布林值 True True代表棋串安全代表棋串安全n n以布林值以布林值 False False代表棋串被吃代表棋串被吃      Killer   (AND)Defender(OR)Killer   (AND)Defender(OR) F T F TT        F       F      F      F T         T          F 1 2 3FT 代表安全代表安全F 代表被吃代表被吃提高搜尋效率的方法n n設定著手選擇之 priorityn n將較佳之著手優先進行搜尋n n降低 branch (棋步選擇量)Killer Moves之分類n n直接緊氣n n「撲」n n避免不進子n n包圍n n攻擊連結鏈棋串n n逃出我方(包圍者)之棋串n n攻殺手筋n n系統測試實例緊氣原則n n目標棋串愈能長氣之目標棋串愈能長氣之點愈優先點愈優先n n包圍之棋串能順便長包圍之棋串能順便長氣之點較優先氣之點較優先撲n n是將棋子送入對方虎口中，迫使對方提吃，以求是將棋子送入對方虎口中，迫使對方提吃，以求能迅速縮減對方氣數之手法。

能迅速縮減對方氣數之手法包圍n n利用「包圍鏈」來封鎖目標棋串利用「包圍鏈」來封鎖目標棋串n n只要目標棋串尚未被封鎖，且氣數低於安全氣數，只要目標棋串尚未被封鎖，且氣數低於安全氣數，則包圍的則包圍的 priority priority就比較高就比較高攻擊連結鏈棋串n n分斷連結鏈之聯繫分斷連結鏈之聯繫n n側襲連結鏈之棋串側襲連結鏈之棋串救援我方包圍棋串之範例n n救援的方法選擇救援的方法選擇n n救援的重要性救援的重要性不進子的處理n n連接會被提吃之位置連接會被提吃之位置 (B (B點點) )n n對接觸之敵方已死棋串緊氣對接觸之敵方已死棋串緊氣 (C (C點點) )手筋範例n n點入點入n n第一線立下第一線立下系統測試範例靜態死活分析系統n n概念：在棋塊區域辨識後，能夠根據棋塊中的相關資訊，以『無搜尋』的方式分析研判該棋塊的眼位n n目的：為了提升搜尋效能，增快審局函數判斷局勢的速度名詞定義n n眼位區(Eye Region)：是指棋塊中某一個獨立且連通的地域範圍所形成的集合n n眼位點(Eye Point)：是指該眼位區中包含的所有空點或敵方死子之位置n n眼位個數(Eye number)：是指眼位區R中包含的眼位數(Re)。

n n棋塊眼位數＝ΣRe棋塊眼位數計算範例眼位區1(A) ： 0.5 眼位區2(B、C)： 0 眼位區3(D、E)： 1棋塊眼位數 ＝ 0.5 + 0 + 1 = 1.5  危險危險 眼位點分析因素n n位置：地域點、潛力點、邊界點位置：地域點、潛力點、邊界點n n眼形種類：真眼、半眼、假眼眼形種類：真眼、半眼、假眼n n狀態：空點、敵方死子狀態：空點、敵方死子靜態死活分析範例開局時搜尋情況(1)n n搜尋廣度問題搜尋廣度問題n nα-β pruning α-β pruning 之效能之效能開局時搜尋情況(2)n n搜尋深度問題搜尋深度問題n n複雜局勢不易明確分析複雜局勢不易明確分析開局知識庫系統n n目的：為彌補開局階段搜尋深廣度不足n n作法：使用hash function將九路棋盤盤面以及相關資訊儲存到一個極大的檔案中，藉由不斷的輸入實戰棋譜資料，使其具備學習功能n n技巧：由於棋譜檔案很大，且未來資料量會隨之增多，必須處理對稱盤面造成的重複，以及盤面資訊如何正確解讀問題開局知識庫實作概念棋譜檔案Hash function開局知識庫著點選擇n n依勝負局數資訊分析依勝負局數資訊分析n n以亂數決定以亂數決定著點著點A AB BC CD DE E勝局勝局32328 82 21 10 0負局負局343424242 22 21 1勝率勝率48482525505033330 0開局知識庫界面發展電腦圍棋的條件n n最好是該種棋類高手n n圓熟的程式設計功力n n具資料結構理論基礎n n優異的邏輯分析能力n n鍥而不捨的研究精神設計電腦圍棋之甘苦談n n生不逢時n n獨孤求勝n n速成 v.s. 大成？n n大破大立n n廢寢忘食之毅力n n嘔心瀝血的除錯The End。