二、计算机围棋的基本原理
运用计算机来下围棋，似乎是一个很直接的想法，因为围棋的规则很简单，胜负定义也很明确，棋盘上每点的状态也只有黑子、白子和空点三种，这些都和计算机本身的特性相符合。另一方面也是由于它已被全世界研究了数千年，许许多多的战术观念及思考方法已被研究开发出来，这些几乎可以看做是真理的理论，都是可以在发展计算机围棋时去应用或参考的。
但是计算机围棋的发展过程，却没有想象中顺利，虽然围棋规则很简单，但是由于盘面广大（一般的对局棋盘是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]。
时间 地点 第一名 第二名 第三名
1985 台北 王若曦 曹国明 Allan Scarff
1986 台北 杜贵崇 刘东岳 Bruce Wilcox
1987 台北 王若曦 刘东岳 陈开佑
1988 台北 林和芳 刘东岳 Mark Boon
1989 台北 Mark Boon Bruce Wilcox 陈克训
1990 北京 Mark Boon 陈克训 Janusz Kraszek
1991 新加坡 Mark Boon 陈克训 刘东岳
1992 东京 陈克训 陈志行 Mark Boon
1993 成都 陈志行 Janusz Kraszek 陈克训
1994 台北 陈克训 David Fotland 陈志行
1995 汉城 陈志行 Michael Resis 陈克训
1996 广州 陈志行 陈克训 高国元
3.2 FOST杯世界计算机围棋比赛
FOST杯是由日本的Fusion of Science and Technology organization在1995年开始举办的，举办的时间地点大约是每年的九月在日本东京地区举行。1997年将在日本名古屋举行。FOST杯所提供的奖金如下：冠军是两百万日币、亚军是五十万日币、季军则是二十万日币。比赛是采用日本棋院的围棋规则，详细有关此比赛的细节可参考[Fotland 1996]。
目前为止举办过的比赛的时间地点及比赛成绩如表四。另主办单位为测试前几名的棋力，亦举办计算机对人脑的比赛，而两届的冠军陈志行教授的围棋程序HandTalk在经过测试后，在1995年给予日本棋院的五级棋力证书(约等于台湾九级棋力)，而在1996年则获得日本棋院的四级棋力证书(约等于台湾八级棋力)，由于HandTalk在近几年的各项比赛均拔得头筹，HandTalk可说是目前为止棋力最强的计算机围棋程序。
表四 FOST杯历年之比赛结果
时间 地点 第一名 第二名 第三名
1995 东京 陈志行 Michael Resis David Fotland
1996 东京 陈志行 Michael Resis David Fotland
程序名称 作者 单位
HandTalk 陈志行 广东省中山大学 中国
Go Intellect 陈克训 University of North Carolina 美国
Go4++ Michael Reiss Unistat Limited 英国
Many Faces David Fortland H.P. Inc. 美国
Stone 高国元 国立台湾大学 台湾
Jimmy 颜士净 国立台湾大学 台湾
Dragon 刘东岳 国立台湾大学 台湾
Archmage 严礽麒 国立台湾大学 台湾
Star of Poland Janusz Kraszek University of Slupsk 波兰
IGO Noriaki Sanechika AI Language Research Institute 日本
Goliath Mark Boon University of Amsterdam 荷兰
Nemesis Bruce Wilcox TOYOGO Inc. 美国
4.1.1许舜钦的学生们所制作的程序
由于计算机围棋比赛最早是在台湾所发起的，这也促成台湾在八十年代研究计算机围棋的风气。在其中一个较具代表性的研发小组为台湾大学资讯工程系许舜钦教授所领导的计算机围棋研发小组，在小组中曾代表参加计算机围棋比赛的包括王若曦、曹国明、高国元、刘东岳、严礽麒和颜士净，他们所制作的围棋程序都可说都是计算机围棋发展过程中重要的里程碑，这些程序中又以Dragon程序最为知名。
Dragon程序最著名的特色应该是它的棋串攻杀系统，此系统可说是充分发挥了计算机的特色，主要的做法是采用选择式搜寻法配合启发式的策略来计算棋串的攻杀。因为是具备相当完整的搜寻模块，所以在棋串攻杀时偶而会下出一些连有段棋士都意想不到的好棋出来。另外再配合根据丰富的比赛经验所制作的相当完备的棋型数据库，所以至今仍然可说是一个相当优秀的计算机围棋程序[Hsu and Liu, 1991] 。
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) 应用在计算机围棋的官子上，目前相关的一些结论是组合对局理论应用在收小官时，可以得到非常好的效果。
参考文献
[许 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 Engineering10, 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.
