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

電腦圍棋程式設計的演進與發展,電腦對局(Computer Game),是人工智慧(Artificial Intelligent)的領域之一讓電腦程式具有思考分析能力，能夠與人進行黑白棋、五子棋、西洋棋、象棋、圍棋等等的對奕。例：由IBM超級電腦上所研發的西洋棋程式深藍(DeepBlue)，在1997年擊敗了當代的世界冠軍卡斯帕洛夫(Kasparov)。,常見棋類遊戲介紹,黑白棋(Othello)五子棋(Go-moku)西洋棋(Chess)象棋(Chinese Chess)六子棋(Connect 6)圍棋(Go),一般常見的誤解,誤解1：電腦對局程式可以將所有的棋譜輸入電腦，因而戰勝人腦。誤解2：電腦計算速度太快，人一定算不贏電腦，所以所有的棋類遊戲都一定是電腦必勝。誤解3：一個下棋很遜的程式設計者，無法設計出一個比他厲害的下棋程式。,象棋的複雜度概算,通常一盤棋大約經過40回合(共80步)可得到最後結果。每回合可走的所有棋步平均約有45種。複雜度粗略估計：45*45*45*45=4580最後再考慮去除一些對稱重複情形後，將之微調大約是10150。,棋類遊戲難易度分析,電腦 vs.人腦,電腦優勢：運算速度極快能記憶大量資料不會有情緒影響人腦優勢：具有敏銳的直覺能將經驗累積成知識,電腦對局理論基礎,遊戲樹(Game Tree)最大最小值搜尋(Minimax Search)-pruningIterative deepening search,遊戲樹(Game Tree),電腦程式先將所有可能的走法整理出來，然後嘗試走走看；接著再將對方所有可能走法也整理出來，接著也去走走看。如此循環反覆，一直進行到某種條件符合才停止，然後經過審局函數評估，再從其中選出最佳著手。用到遞迴呼叫觀念。執行時間通常相當久。除錯工作不容易。,遊戲樹概念圖,我方著手,敵方著手,我方著手,Win,Win,Lose,50,80,-5,20,40,0,90,審局函數(Evaluation),在遊戲樹中用來評估局面的優劣程度(假定正值表示我方佔優，負值表示敵方佔優，其絕對值大小代表優勢程度高低)。審局函數在計算上愈快愈好。審局函數愈精準，則對於著手的建議愈正確。,象棋的審局函數(1),通常會將不同兵種給予一個固定分數審局時只要將雙方棋盤上的子力分數加總對比，就可以得到一個近似正確的估計值。,100002002001000420450100,象棋的審局函數(2),除了子力之外，尚可將棋子位置也納入評估優劣的考量。絕對位置：例如馬臥槽是絕佳位置，馬塞在將正前方是極惡位置。相對位置：馬被擋馬腳、象被塞象眼都是不好位置；而包佔據空頭是絕佳位置。但增加此項考量，亦有計算較費時的缺點，是否採用仍是trade-off的問題。,象棋局勢分析範例,最大最小值搜尋,概念：由於輪到我方著手時，會盡量使我方局勢有利(評估值愈大愈好)；輪到敵方著手時，會盡量使我方局勢不利(評估值愈小愈好)。作法：在搜尋過程上，由底層終端節點經由審局函數取得評估值後，視該層由何方著手來選出最大值或最小值予以傳回。,最大最小值搜尋概念圖,我方Max,敵方Min,我方Max,Win,Win,Lose,50,80,-5,20,40,0,90,-pruning,概念：是用來改良最大最小值搜尋的效能。亦即當某種條件成立時，一些搜尋的分支路徑完全可以省略。技巧：如果能將著手選擇優劣事先作排序，則-pruning 的效果會更好。,-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，1969年。早期時代：19701985年。過渡時代：約自1986年開始，局部重點加強，例如棋形資料庫與棋串吃逃搜尋。成熟時代：約始於1989年，具備了多目標式的搜尋系統，而且也有了簡單的局勢分析，甚至是靜態的死活判斷。,電腦圍棋程式比賽,應氏盃(19852000)Computer Olympiad Tournament(1990)FOST盃(19952000),應氏盃早中期程式水平,1990年後程式水平,具有棋塊概念地域認知能力多目標搜尋系統靜態死活分析能力眼位分析能力死活知識庫建立,目前最強圍棋程式,HandTalk：廣東中山大學陳志行教授研發MoGo：為法國程式工程師Sylvain 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 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-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,棋串設定方法,使用圖形連通的DFS演算法對每個棋串記錄其子數、棋子位置、氣數、氣點位置、相鄰敵方棋串等資訊,棋鏈的種類,尖(黑)扳(白)跳(黑)飛(白),棋塊連通的條件,同色棋子同色棋鏈空點強勢點敵方死子,棋塊的範圍與地域辨識,棋塊的地域認定,邊界點：棋塊最外層的棋子或空點，潛力點：由邊界空點向內推一層，代表可能成為地域的點，地域點：棋塊內部空點或敵方死子，可視為確定地,棋塊安危認定原則,初步認定：棋塊的地域點是否足夠棋塊是否被包圍棋塊的潛力點個數多寡詳細認定：靜態死活分析周圍有無敵方的危險或死亡棋塊,專家棋士下棋的思路,敏銳的棋塊安危感覺直接進攻、聲東擊西、纏繞攻擊、製造雙擊設法安定、拓寬出路、以攻代守熟練的棋形要點反應精簡深入的細算思考,靜態死活分析,目的：採取完全不用search的方式，直接從棋塊之地域點作眼位分析，來判斷棋塊死活。所需資訊：棋塊的地域點個數、位置、各點真假眼形態、有無敵方死子、有無中心位置等。所需技術：專業的圍棋知識、細膩精確的分析歸納能力、不斷的反覆測試,著手選擇系統,著手選擇模組：棋塊死活棋塊攻防連結分斷棋串吃逃地域搶佔以預估目數出入作為著手分數目前分支度：8,審局函數判斷因素,棋塊確定地域目數周圍可能成地之潛力棋塊安危程度及範圍大小危險棋串之有無棋塊中的缺陷棋形,全局搜尋基本架構,Game Tree structureMinimax search&-pruningDepth：6Width：8other skills,棋形的觀念,棋形樣式(Pattern),應用實例,棋形樣式的方向轉換,棋形樣式的擷取,棋形的分類,依棋形術語分類(製作時)根據棋子配置的相對位置關係來區分例如尖、跳、飛、長、扳、虎依棋形用途分類(應用時)根據著點的作用與含意來區分例如連結、分斷、擴大、壓迫、整形,棋形的等級,緊急：大多屬於連接、分斷類棋形重要：大多是包圍、突破，以及重要的擴 張、壓迫類棋形一般：屬於一般常見的下法，不特別重要 但也相當實用特殊：屬於特殊情況才使用的手法，多半 有奇兵之意味,棋形樣式(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或遞迴,避免不進子問題,系統解出的撲手範例,棋串安危的認定,棋串安危認定=棋塊安危認定方式：靜態安危分析系統動態攻殺搜尋系統效能比較：準確度：動態(9成)靜態(78成)速度：靜態 動態,靜態棋串安危分析,棋串安危等級：LIBERTY_SAFE：氣數夠多而視為安全。CAREFUL：大致上安全，但有微小的不安。DANGEROUS：氣數為23氣，並且伴隨了一些危險因子(氣點太靠近盤端、)。VERY_DANGEROUS：危險等級非常高，伴隨的危險因子更多。EXPIRED：只剩1氣且非反提的棋串。,棋串安危分析判斷因素,棋串氣數氣點位置氣點周圍有無敵子氣點周圍有無敵方棋鏈有無友方支援棋鏈勢力影響值高低,棋串安危靜態分析實例,棋串攻殺搜尋系統,尋找敵我雙方的目標棋串攻擊方(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 Moves之分類,直接緊氣撲避免不進子包圍攻擊連結鏈棋串逃出我方(包圍者)之棋串攻殺手筋系統測試實例,緊氣原則,目標棋串愈能長氣之點愈優先,包圍之棋串能順便長氣之點較優先,撲,是將棋子送入對方虎口中，迫使對方提吃，以求能迅速縮減對方氣數之手法。,包圍,利用包圍鏈來封鎖目標棋串只要目標棋串尚未被封鎖，且氣數低於安全氣數，則包圍的 priority就比較高。,攻擊連結鏈棋串,分斷連結鏈之聯繫,側襲連結鏈之棋串,救援我方包圍棋串之範例,救援的方法選擇,救援的重要性,不進子的處理,連接會被提吃之位置(B點)對接觸之敵方已死棋串緊氣(C點),手筋範例,點入,第一線立下,系統測試範例,靜態死活分析系統,概念：在棋塊區域辨識後，能夠根據棋塊中的相關資訊，以無搜尋的方式分析研判該棋塊的眼位。目的：為了提升搜尋效能，增快審局函數判斷局勢的速度。,名詞定義,眼位區(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 function將九路棋盤盤面以及相關資訊儲存到一個極大的檔案中，藉由不斷的輸入實戰棋譜資料，使其具備學習功能。技巧：由於棋譜檔案很大，且未來資料量會隨之增多，必須處理對稱盤面造成的重複，以及盤面資訊如何正確解讀問題。,開局知識庫實作概念,棋譜檔案,Hash function,開局知識庫著點選擇,依勝負局數資訊分析以亂數決定,開局知識庫界面,發展電腦圍棋的條件,最好是該種棋類高手圓熟的程式設計功力具資料結構理論基礎優異的邏輯分析能力鍥而不捨的研究精神,設計電腦圍棋之甘苦談,生不逢時獨孤求勝速成 v.s.大成？大破大立廢寢忘食之毅力嘔心瀝血的除錯,The End,