劉邦鋒臺灣大學：資訊工程學研究所嚴礽麒Yan, Jeng-ChiJeng-ChiYan2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54039電腦對局的相關研究由來已久，自從電腦西洋棋程式Deep Blue在1997年擊敗人類世界冠軍之後，電腦圍棋就成為電腦對局下個階段的挑戰。 電腦圍棋的設計工作，是一件艱難而漫長的路，事前必須作整體與細部的規劃。然而許多細部地方又很難事前完全分析清楚，必須要倚靠對圍棋知識相當專業的人才能辦到。有鑑於此，我們將從專家棋士下棋的思路開始，從中取得設計電腦圍棋的正確方向，再透過專家的經驗法則，將其歸納分析為有效的演算法，然後設計並撰寫程式，所以這項研究工作充滿了專家系統及知識工程的概念。 九路圍棋程式GoKing是在2003年開始著手規劃設計，歷經三年的開發，在2006年4月時完成了GoKing 3.0之架構。本程式無論在軟體工程以及棋力表現上，都可算是當今最優秀的程式之一。在本篇論文中，將對GoKing的整體與局部之設計方式、以及我們設計上的獨到之處細加剖析，證明我們勝過他人之處。目前程式的棋力大約在5~8級之範圍，但若經過更為精緻的改良，未來突破段位水準是大有可能的。The studies of computer game have a long history. Since a computer chess program, Deep Blue, defeated human’s world champion in 1997, computer Go has become the next challenge of computer game. The designing of computer Go program is a long and strenuous road which requires comprehensive and detailed planning in advance. However, many details cannot be easily and completely analyzed in advance, without the assistance of experts in Go. Therefore, we started from the thinking of professional Go players to figure out a correct direction of computer Go designs. The expert experiences were analyzed and induced to derive effective algorithms before we started to design and compose the program. So this research is full of the concepts of expert systems and knowledge engineering. The 9 by 9 Go program, GoKing, was designed in 2003, and the structure of GoKing 3.0 was completed in April 2006. No matter in software engineering or performance, this program is one of the most outstanding programs in the present time. This research would focus on the integral and local designs of GoKing and analyze the specialties of the design to prove our edge. Now, the performance of GoKing is about 5-8 kyu. If it could be further modified and improved, it is very likely to break through the 1-dan grade in the future.第一章 緒論 1.1 引言 1 1.2 圍棋簡介 1 1.3 電腦圍棋的困難度 4 1.4 我們的目標 6 1.5 本篇論文之架構 6 第二章 電腦圍棋的發展過程 2.1 電腦圍棋的歷史 8 2.2 電腦圍棋比賽簡介 8 2.3 電腦圍棋程式簡介 11 2.4 電腦圍棋程式的等級評比 15 2.5 發展之瓶頸及未來展望 17 第三章 系統巨觀與架構 3.1 專業棋士下棋的思路 19 3.2 系統的設計概念 20 3.3 系統架構 21 3.4 精密的工具程式 25 第四章 資料結構 4.1 電腦圍棋中的物件階層概念 26 4.2 影響力評估值的作用 30 4.3 棋串設定的演算法 32 4.4 棋塊設定的演算法 33 第五章 棋形比對系統 5.1 棋形的擷取方法 37 5.2 棋形的表示方法 38 5.3 其他程式的棋形設計方式 40 5.4 棋形比對的應用與整合 42 第六章 重要工具程式的設計 6.1 落子後的氣數計算 45 6.2 著手是否自殺的判斷 47 6.3 避免不進子著手的選擇 47 6.4 真假眼形的判斷 49 6.5 有效自殺著手的判斷 51 第七章 棋串安危的認定 7.1 靜態的棋串安危分析系統 58 7.2 動態的棋串攻殺搜尋系統 60 7.3 棋串襲殺的著手選擇 62 7.4 棋串防禦的著手選擇 68 7.5 棋串攻擊與防禦的實例測試 72 第八章 棋塊眼位分析系統 8.1 棋塊眼位區的資訊 75 8.2 眼位點的成眼條件分析 77 8.3 棋塊眼位區的形狀 80 8.4 棋塊死活分析的實例測試 85 第九章 開局知識庫系統 9.1 開局知識庫之概念 88 9.2 開局知識庫之設計方法 89 9.3 相同盤面問題與解決方式 92 9.4 開局知識庫的應用方式 98 第十章 結論與未來展望 10.1 目前的成果 100 10.2 未來展望與目標 101 參考文獻 103 附錄 109en-US電腦對局電腦圍棋專家系統computer gamecomputer Goexpert systemthesis