顏士淨 國立台灣大學資訊工程研究所博士班研究生

許舜欽 國立台灣大學資訊工程系教授

1.1 起源

1. 2 基本規則及棋力計算方式

圍棋可以說是兩個人在棋盤上爭地的遊戲。兩人分持黑白，輪流將棋子下在棋盤的空點上。在棋盤上的每個棋子的鄰接點若為空點，則稱是這顆棋子的氣點，當棋子的氣點全被對方佔據時，則此棋子必須被對方提取。某些提子的時候，會產生同型反覆的情況，此時為避免同型反覆而無法解決，規定當剛提吃對方一顆棋子時，不可馬上提回，必須間隔一手之後才可提回。最後勝負的決定則是根據棋局終了時，計算雙方所佔有的地域的大小來決定。以上為基本的圍棋規則，詳細完整的圍棋規則可以參考應昌期圍棋教育基金會的”計點制圍棋規則”[圍棋基金會 1995]。

圖一 圍棋的棋力計算方式

但是電腦圍棋的發展過程，卻沒有想像中順利，雖然圍棋規則很簡單，但是由於盤面廣大（一般的對局棋盤是19×19），實際上對局時的變化卻比其它的棋戲複雜得多。例如西洋棋或象棋，已能藉由一些簡單的推理與深度的搜尋思考而達到相當高的棋力，但這種方法卻不太適合應用在圍棋這種高複雜度的棋戲中。A.Samuel估計checker的複雜度大約是10的40次方[Samuel, 1959]，而A.Newll估計西洋棋的複雜度大約是10的120次方[Newell et al., 1958]。這兩種棋戲的複雜度雖然已是天文數字，但比起圍棋的複雜度則要小得多了，Brown及Dowsey估計圍棋所有可能的變化大約是10的700次方[Brown and Dowsey 81]。

就棋塊或大龍攻防方面而言，程式必須要有辨認一塊棋的能力，且還要能”看”出周遭狀況而得悉安危與否。因此在程式中建有一”塊”棋的資料結構，用來獲得這塊棋的種種資訊，諸如它所包含的棋串、佔地數目、本身涵蓋的區域大小等。又為找出有利的攻防點，程式必須建立類似雷達網的系統，由一棋塊為根據向外層層擴散，以得知何處有敵子，何處有援軍，是否已被包圍等等。另外為了模擬人類棋手的視覺效果，也必須開發出一種影響力評估值的方法，藉由此方法，可加強電腦圍棋程式對於判斷模樣、棋塊安危和佔地數目的能力。

而當棋局中短兵相接，牽涉到死活糾纏的狀況時，就需要有一搜尋分析系統，藉著搜尋的細算功能，判斷棋子是否可以吃到(或逃出)，以及如何去吃(如何逃出)與吃(逃)該棋串之價值大小。此一攻殺細算模組為任何圍棋程式所必備[Hsu et al., 1994] [Hsu and Liu, 1991] [Hwang and Hsu, 1994]。

目前世界上較為人知的電腦圍棋比賽共有五個：應氏杯､FOST杯､奧林匹亞杯､北美杯及歐洲杯。而其中較大型的比賽為應氏杯和FOST杯，以下就這兩個比賽作一簡單的介紹。

3. 1 應氏杯世界電腦圍棋比賽

應氏杯主要是由應昌棋圍棋教育基金會所主辦的，為第一個全世界性的電腦圍棋比賽[許 1989]。應氏杯比賽主要包括兩個部份，電腦對電腦比賽和電腦對人腦比賽，其中人腦指的是青少年高段棋士。應昌棋圍棋教育基金會主要宗旨是推廣圍棋，其並為圍棋修訂了一套完整的圍棋規則，也就是俗稱的計點制，是公認較為完備的圍棋規則。

應氏杯的初賽於每年七月在台灣舉行，通過初賽者可獲得旅費補助。而決賽則因為為了推廣圍棋運動，自1990年起，於每年十一月分別在世界各不同大都市舉行。比賽的賽程安排是採瑞士制，而規則是用計點制圍棋規則，詳細的參加辦法可洽應昌棋圍棋教育基金會。

為了鼓勵人們從事電腦圍棋方面的研究，基金會給予在應氏杯中電腦對電腦的比賽的前三名獎金分別如下：冠軍是二十萬台幣、亞軍是四萬台幣、季軍則是二萬台幣。而電腦對人腦的比賽的獎勵則視局差而定，詳細的情形如表二所示。目前為止舉辦過的比賽的時間地點及比賽成績如表三所示[許 1989] [Fotland 1996] 。為方便閱讀起見，表三根據比賽成績只列出前三名及比賽的時間地點。

3.2 FOST杯世界電腦圍棋比賽

FOST杯是由日本的Fusion of Science and Technology organization在1995年開始舉辦的，舉辦的時間地點大約是每年的九月在日本東京地區舉行。1997年將在日本名古屋舉行。FOST杯所提供的獎金如下：冠軍是兩百萬日幣、亞軍是五十萬日幣、季軍則是二十萬日幣。比賽是採用日本棋院的圍棋規則，詳細有關此比賽的細節可參考[Fotland 1996]。

目前為止舉辦過的比賽的時間地點及比賽成績如表四。另主辦單位為測試前幾名的棋力，亦舉辦電腦對人腦的比賽，而兩屆的冠軍陳志行教授的圍棋程式HandTalk在經過測試後，在1995年給予日本棋院的五級棋力證書(約等於台灣九級棋力)，而在1996年則獲得日本棋院的四級棋力證書(約等於台灣八級棋力)，由於HandTalk在近幾年的各項比賽均拔得頭籌，HandTalk可說是目前為止棋力最強的電腦圍棋程式。

表四 FOST杯歷年之比賽結果

自1969年Zobrist完成第一個可與人對下的程式以來 [Zobrist, 1970]，世界各地研究電腦圍棋的人就越來越多，表五中為一些較為著名的程式。由於電腦圍棋尚在發展階段，各程式所使用的方法並不相同，特別是近年來在前述比賽中前幾名的程式，都是發展約十年的程式，故都有其特色和獨到之處。以下我們就分別介紹並討論他們所使用的方法。

4.1.1許舜欽的學生們所製作的程式

由於電腦圍棋比賽最早是在台灣所發起的，這也促成台灣在八十年代研究電腦圍棋的風氣。在其中一個較具代表性的研發小組為台灣大學資訊工程系許舜欽教授所領導的電腦圍棋研發小組，在小組中曾代表參加電腦圍棋比賽的包括王若曦、曹國明、高國元、劉東岳、嚴礽麒和顏士淨，他們所製作的圍棋程式都可說都是電腦圍棋發展過程中重要的里程碑，這些程式中又以Dragon程式最為知名。

Dragon程式最著名的特色應該是它的棋串攻殺系統，此系統可說是充分發揮了電腦的特色，主要的做法是採用選擇式搜尋法配合啟發式的策略來計算棋串的攻殺。因為是具備相當完整的搜尋模組，所以在棋串攻殺時偶而會下出一些連有段棋士都意想不到的好棋出來。另外再配合根據豐富的比賽經驗所製作的相當完備的棋型資料庫，所以至今仍然可說是一個相當優秀的電腦圍棋程式[Hsu and Liu, 1991] 。

4.1.2陳志行教授的Handtalk程式

目前公認最強的電腦圍棋程式應該是陳志行教授的電腦程式HandTalk，陳教授本來是廣東中山大學的教授，本身的圍棋棋力約有業餘五段，幾年前為了專心發展電腦圍棋程式，申請退休並成立研發小組，專心研究電腦圍棋[黃 1996]。

關於HandTalk程式的內容，由於相關的程式內容及研究方法發表的並不多，現今外界對此程式的了解僅限於在比賽時與陳教授討論所得。以下是我們在幾次比賽中與陳教授討論所得的心得。

HandTalk程式是由組合語言所撰寫，所以它的執行速度很快，而程式本身也不大。由於程式並不大，可以推測出其所運用到的棋型資料也並不多，而且很可能是採用rule-based的方法。HandTalk在大多數的情況下都不會失誤，陳教授本人曾提到他是用到一種類似人在下圍棋時常用到的方法“手割“，來幫助判斷的。另HandTalk的定石資料也很少，這是根據我們實際測試所得到的結果。

HandTalk與其他的程式明顯不同的地方是它的攻殺能力特別強，在大多數的比賽中，都可以吃掉對方幾塊棋而獲勝。這應該是由於程式的棋塊安危判斷能力，形勢判斷系統，眼位判斷能力和棋型比對系統都很強的關係。有關這些系統的好壞，跟設計者的棋力非常有關，陳教授本身近職業水準的棋力，顯然對HandTalk程式的撰寫很有幫助。

4.1.3 陳克訓教授的Go Intellect程式

Go Intellent也是近年來全世界數一數二的程式，有關Go Intellect的內容，陳克訓教授有相當多的著作發表[Chen, 1989][Chen, 1990]，Go Intellect由於經過多年的發展，在對局時很少出錯，可說是發展的相當良好的程式。最近Go Intellect改進較多的地方約有下列三點：

(a) 精良的資料庫及棋步產生系統。

(b) 更快的局部攻殺系統。

4.1.4 Michael Reiss的Go4++程式

Michael Reiss在1983年開始發展電腦圍棋程式，而在最近開始有很好的表現，一度被HandTalk視為最強勁的對手。Go4++ 程式的棋力與它的設計者Michael Reiss並沒有很大差距，這是較為特別的地方[Burmeister and Wiles]。

Michael Reiss的主要觀念是使用一些簡單的演算法去計算大量的資訊，而不像一般電腦圍棋程式大都是用一些複雜的演算法去計算少量的資訊。舉例來說，Go4++程式在產生一個棋步之前，會先用十五個基本的棋型比對出大約五十個候選棋步，再用會用全局搜尋的方式去考慮產生一個棋步，但所用的評估函數卻很簡單：主要是考慮地域問題。這種方式跟一般製作其他棋類的方式較為接近，此方法的好處是對於模樣的感覺很有幫助，而且不需要很複雜的評估函數。壞處則是需要很大的計算量，程式運作需要一台很快速的電腦。

Go4++ 目前的最大優點是它對有關地域的好點不容易失誤，這是因為它考慮的候選棋步較多，且有進行全局搜尋的關係。而它的弱點則是處理棋塊攻殺的方式較弱，常會發生因為判斷錯誤而放棄一重要的棋塊，此缺點使得Go4++ 在最近的棋賽吃虧不少[Burmeister and Wiles]。

4.1.5 David Fotland的The Many Faces of Go程式

The Many Faces of Go (MFG)是最早商業化的軟體之一，在國際網路圍棋(IGS)上亦可看到它的蹤影，發展至今也有十多年的歷史，程式本身是用Ｃ語言撰寫，程式大小約四萬行[Burmeister and Wiles]。

MFG的特色之一是它有一個很好的棋型發展系統，目前為止它的棋型資料庫約包括1200個8×8的棋型和6900個5×5的棋型，要妥善運用這麼多棋型，並不是一件容易的事。首先是棋型的來源，MFG有一個棋型編輯系統，可以用手動的方式來剪貼下所需的棋型。Fotland本來的構想是讓高段棋士與MFG對奕，再從對奕的棋譜中剪貼下所需的棋型，但後來Fotland卻發現最好的棋型擷取地方是IGS上的高段棋士對奕的棋譜。再來是當這麼多棋型要運用在程式中時，所需的計算量是很大的，例如要在一個19×19的棋盤比對1000個棋型，用普通的方式可能要三百萬個運算，MFG將棋型編譯成為用位元陣列表示，如此便可用平行位元比對的方式進行計算，可將計算量降到350,000[Fotland 1996]。

4.1.6 高國元的Stone程式

高國元本來也是台大資訊許舜欽教授的學生，後來到北卡大成為陳克訓教授的博士班研究生，所以他的程式可說是綜合兩者之所長。高國元目前所作的研究中部份是有關電腦圍棋的官子，這個研究的主要的方法是將組合對局理論 (combinatorial game theory) 應用在電腦圍棋的官子上，目前相關的一些結論是組合對局理論應用在收小官時，可以得到非常好的效果。

我們將電腦圍棋發展至今的一些代表性程式的棋力統計於圖六，這些程式為陳志行教授的HandTalk、陳克訓教授的Go Intellect、Mark Boon的Goliath和許舜欽教授的學生們所製作的程式（包括王若曦、曹國明、高國元、劉東岳、嚴礽麒和顏士淨）。從圖六我們可以看出在電腦圍棋發展初期的八十年代，圍棋程式以大約每年兩級的速度在進步，而到了九十年代電腦圍棋已發展到某一程度，但仍以大約每年一級的速度在穩定進步中，由此看來，電腦圍棋目前仍在穩定發展之中，另一方面，在前述文章中，由各圍棋程式各有特色看來，電腦圍棋還有相當大的發展空間。綜合上述兩點，再根據我們本身對電腦圍棋的了解，我們推測電腦圍棋的棋力大約在西元兩千年前後，可以到達日本棋院的初段棋力（約台灣的五級左右）。

圖六 電腦圍棋棋力進步情形（棋力/年份）

[許 1989] 許舜欽，電腦圍棋在台灣的回顧與前瞻，中國工程師學會，日本分會，1989年學術研討會論文集，1989。

[圍棋基金會 1995] 應昌期圍棋教育基金會，計點制圍棋規則，1995年版。

[黃 1996] 黃天源，比朝陽更絢爛的黃昏，羊城晚報，港澳海外版，1996/11/15。

[Allis et al., 1991] L.V. Allis, Van Den Herik, and H.J. Herschberg. Heuristic Programming in Artificial Intelligence 2, Ellis Horwood 1991.

[Berliner, 1974] H.J. Berliner. Chess as Problem Solving: the Development of a Tactics Analyzer. Ph.D. Dissertation, Carnegie-Mellon University, Pittsburgh, 1974.

[Burmeister and Wiles 96] Jay Burmeister and Janet Wiles. An Introduction to the Computer Go Field and Associated Internet Resources. World-Wide-Web page, http: //www.psy.uq.edu.au/~jay/, 1996.

[Brown and Dowsey 81] D.J. H. Brown and Dowsey, S. The challenge of Go. New Scientist, 1981, pages 303--305.

[Chen, 1989] Ken Chen. Group identification in Computer Go. Heuristic Programming in Artificial Intelligence, Levy & Beal ( Eds.), Ellis Horwood 1989, pages 195--210.

[Chen, 1990] Ken Chen. The move decision process of Go intellect. Computer Go, No.14, pages 9--17, 1990.

[Fotland 1996] David Fotland. World Computer Go Championships, World-Wide-Web page, http://www.mth.kcl.ac.uk/~mreiss/bill/comp/.

[Hsu et al., 1994] S.C. Hsu, J.C. Yan, and H. Chang. Design and implementation of a computer Go program Archimage 1.1. Journal of Information Science and Engineering 10, pages 239--258, 1994.

[Hsu and Liu, 1991] S.C. Hsu and D.Y. Liu. The design and construction of the computer Go program dragon 2. Computer Go, No. 16, pages 3--14, 1991.

[Hwang and Hsu, 1994] Y.J. Hwang and S.C. Hsu. Design and implementation of a position judgment system for computer Go programs. Bulletin of the College of Engineering, N.T.U., No. 62, pages 21--33, Oct. 1994.

[Kojima et.al., 1996] Takuya Kojima, Kazuhiro Ueda, and Saburo Nagano. A case study on acquisition of pattern knowledge in Go using ecological analogy. Game programming workshop in Japan, pages 133--139, 1996.

[Lorentz, 1995] Richard J. Lorentz. Pattern matching in a Go Playing Program. Game programming workshop in Japan, pages 167--174, 1995.

[Mü ller, 1995] Martin Mü ller. Computer Go as a Sum of Local Games: An Application of Combinatorial Game Theory. Ph.D. Dissertation, Swiss Federal Institute of Technology Zurich, 1995.

[Newell et al., 1958] A. Newell A., J.C. Shaw, and H.A. Simon. Chess playing programs and the problem of complexity. IBM Journal of Research and Development, Vol. 4, No. 2. Pages 320--335, 1958.

[Reitman and Wilcox, 1978] Walter Reitman and Bruce Wilcox. Pattern recognition and pattern-directed inference in a program for playing Go. Pattern-Directed Inference Systems, pages 503--523, 1978.

[Samuel, 1959] A.L. Samuel. Some studies of machine learning using the game of checkers. IBM Journal of Research and Development, Vol. 3, No. 3, pages 210--229, 1959.

[Zobrist, 1970] Zobrist, A. L. Feature Extraction and Representation for Pattern Recognition and the Game of Go, Ph.D. Dissertation, University of Wisconsin, 1970.