围棋程序设计基础
0 概述
本章说明编撰本文的目的，以及本文编撰过程中的组织形式和工作程序。
0.1 项目概述
本文及其编撰过程，旨在发起并完成一项以围棋程序为研究对象的，基于互联网合作创作的志愿项目。
0.2 组织
本项目愿意、并鼓励任何有志于在计算机围棋（Computer Go）领域作出贡献的个人和团体随时加入。参与本项目的个人和团体称为组织成员。组织成员有义务为项目提供作品和思想。组织成员共同享有本项目最终形成的任何作品的署名权。
本组织形式为基于互联网的松散型组织。组织成员采用注册方式加入组织。对于为本项目提供作品的作者，如需声明保留其作品的部分或全部版权，须实名注册。
本组织常设编委会负责作品编辑和事务协调。组织内部事务处理采用民主协商，在民主协商不能解决的情况下的采用表决作为最终解决方式。
组织成员可随时退出。
0.3 工作程序
本项目由发起人拟定编撰提纲，在互联网上发布，并接受组织成员投稿或推荐组织外的作品。投稿将立即在互联网上预发布，同时由编委会评估其技术价值并确定是否接受。投稿可根据组织和作者的共同意愿被全部或部分接受，投稿在被接受之前可能会在编委会的建议下经过若干轮的修订和补充。投稿一经接受，即成为本项目下作品的一部分发布。除有特别声明，其作者将与组织共同享有版权。未被接受的投稿可由作者收回版权，或委托组织代理版权或发布到公共域。
加入本项目的作品，可以是著述、算法、软件、代码或代码片断。
加入本项目的作品，如果引用或编译了他人作品，可由作者本人或编委会与原著作者沟通确认版权问题。
组织成员可随时针对已发布的作品进行技术商榷，并可引用、修订或另行发表新的作品，新作品须经编委会和原作者共同评估并确定是否接受，编委会具有最后决定权，如被接受的新作品不能得到原作者的认可，应在该新作品的正文中显式地说明。
编委会对被接受并进入本文的作品具有修订权，在行使修订权时，应与相关作品的作者进行充分的沟通。如修订不能得到原作者的认可，应在修订的正文中显式地说明。
组织成员可随时就本项目和已发布的作品提出自己的观点。观点不是实质作品，但可被组织接受并引用到现有或以后的作品之中。观点的第一提出人与组织共同享有该观点的署名权。
0.4 版权
除非特别声明，作品一经为组织接受，其署名权和物质权利由组织和作者共享，其修订权为组织所有。
0.5 表决
组织对于不能民主协商解决的事务采取表决方式。一般事务可由编委会表决通过，重大事件须由全体成员表决通过。表决结果简单多数为通过。
0.6 物质利益
本项目为志愿性项目，其组织为非盈利性组织。组织在项目运作期间通过赞助、成果转让等行为中所获得的物质利益，为组织所有，并授权编委会用于项目的支出。
本项目形成的作品，如在发布中取得物质利益，为组织和作者共同享有，并授权编委会合理分配。
组织解散、改组或转制时，应由编委会主持清算，将剩余物资在所有组织成员中合理分配。其分配方案应通过全体成员的认可，或通过全体表决。
0.7 工作语言
本项目工作语言为简体中文。特定术语有歧义可能时，可同时标注英语和日语。
0.8 组织宗旨
信心、奉献、卓越
1 围棋
本章简要阐述围棋的起源、发展历史和当前状况。
1.0 大事年表
公元前24世纪前后：尧发明围棋。 （一说为舜发明围棋，这样的话要晚50年左右）不列颠百科称围棋发明于公元前2306，并未注明出处。
春秋、公元前7世纪：孔子《论语》‘饱食终日,无所用心,难矣哉!不有博弈者乎?’ 是提及围棋的最早文献。（《左传》‘有今宁子视君不知弈棋，其何以免乎？弈者举棋不定，不胜其耦，而况置君而弗定乎？’疑为后世传作）
东汉、公元1世纪： 班固（32-92，《汉书》作者）《弈旨》为现存最早围棋理论专著。
三国、公元196年：《孙策诏吕弈棋局》为现存最早棋谱。
宋、11世纪：棋待诏李逸民编修《忘忧清乐集》，为现存最早的棋谱集，其中收录了《棋经十三篇》等名局、《孙策诏吕弈棋局》、《烂柯图》等古谱，一些古定式和34个死活题，这是现存最早的死活问题。
元、1349年：严德甫、晏天章编修《玄玄棋经》。为古代最著名的围棋专著。
明：1368-1644年出现了近代数子法，取代了古代的数空法。 过百龄编官子谱、三子谱、四子谱。
清、1644-1911：道光二十八年，邓元i《弈潜斋丛谱》 (1881)；黄龙士《弈括》；范西屏《当湖十局》施定庵《弈理指归》
1.1日系围棋大事表
公元618年：围棋何时传入日本目前尚无法考证，但《隋书》中曾记录日本博弈盛行，以至于天皇担心子民玩物丧志而下旨“弈棋与赌博同禁”。这表明围棋在这之前已经在日本时兴了。
武周、701-703年：日本僧人辨正入唐，时遇李隆基（唐玄宗）龙潜之日，以善围棋，屡见赏遇。（[日]木宫泰彦《中日交通史・上》引《怀风藻》）
1603年：本因坊一世算砂（公元1467-1568年）日海上人，受最高法印获许开殿后建立了近代围棋规则，并为名人棋所。
1612年：围棋四大家本因坊、井上、安井、林地位确立，此时算砂以后，其弟子井上家的中村道硕已获封名人。
1626年："御城棋"开始。1628年成为固定赛事。道硕之后其弟子算知同本因坊二世算悦互先六局均是黑棋胜，名人棋所因此空位。
1668年：算悦去世，算知终于获封名人，但随即本因坊三世道悦提出争棋。预定六十盘的争棋道悦以受定先的棋份开始，到第16局时以6局领先晋升棋份为先相先，至当年20盘结束时，后5局仍多3胜，至此名人已经失去棋位，后40盘也不再继续。算知引退。
1690年：段位制度开始，本因坊四世道策 (1645年-1702年)获四世名人棋所。
1703年：井上家四世道节因硕获五世名人棋所。
本因坊五世道知获六世名人，之后四大家并没有高手出现。本因坊九世察元与井上因硕争棋六局5胜1负成为7世名人。
1835年："天保呕心沥血之棋"井上家赤星因彻对本因坊12世丈和。后者封8世名人。14世后的秀策(1829年-1862年)棋力高超，早逝而谥封本因坊。
1863年："御城棋"历史结束。本因坊17世后袭19世，也是林家13世的秀荣成为名人棋所。
本因坊21世秀哉为最后一个名人。围棋进入现代历史。
2 围棋程序的原理
本章论述围棋程序设计的基础原理，以程序设计员的角度考量围棋，并研究围棋的表示方法。
2.0 一些启示
一个困扰围棋程序的问题是问题本身。程序的目标是什么？基于局面的程序设计思想就是依赖于局面的静态评估，更进一步地将静态评估函数用于搜索，得到新的评估结果。这是目前程序共同采用的解决方案。无论怎样设计的静态评估函数，都有一个主观判断的问题，就是要依赖人类棋手的经验。而当今的围棋职业棋手，在某些局面的评估上仍然存在着分歧，这有人类棋手所说的棋风因素，也有棋手本人的技术专长因素。计算水平强的棋手总是喜欢将局面导向战斗，而官子水平强的棋手更喜欢选择轻巧的应对回避没有把握的对杀。
程序怎么做？有些程序在设计前期就考虑并实现了棋风属性，希望使其更像人类棋手的行为，它们中间有一些已经取得了相当的成功（针对于目前很多程序着手生成的机械呆板而言）。但这样的实现随着棋力的增强变得越来越困难，特别是调整的困难度。
要在棋力方面有所突破，除了目前这条普遍采用的技术路线，还有一个考虑是充分利用计算机日益强大的计算能力。此时，给围棋程序一个目标，将是我们必须面对的问题。
研究古围棋我们可以看到围棋的一些发自自然的特性，为适应竞技的需要，这些特性在现代围棋已经弃用。
2.0.1 围棋胜负的本质
古围棋的一个很有意思的概念是“棋头”，流传至今的一些棋谱中就可以看到棋头对布局和官子都有很大的影响。现代围棋是以比目或数子计算胜负，这样看来棋头就变得难以理解。
我们想象围棋是古人从现实生活（那时人民生活环境是足够糟糕和单调的）中抽象出来的一种演算工具的话，问题就迎刃而解了。“地”是古时君王最为关心的物质，有了地就有了粮食，有了粮食就能养活很多的人口，更多的人口意味着更多的军队，更多的军队自然就意味着王权的强大和稳固。
这在围棋的表层上得到了充分的反映。围棋确实要比实地的大小。“地”在现实意义上不是同质化的，有肥有瘠，拥有肥沃土壤的领主发展起来当然更容易一些。围棋在这方面区别于象棋的就在于它发现了用位置表现这样的特性，而不是如象棋那样用有限的棋子等级来表现。位置和棋子可以组合出大量的变化，其中的复杂性远不能用一句“金角银边草肚皮”来概括。
进一步地推演，在双方实地定型之后，接着要发生的事情。当然两边还要发生战事，首先是边界上，大家你占一点我占一点，这就是围棋单官了。再后来呢，打到对方空中的棋子自然有去无还，为积聚实力进攻，各方都在自己的领地休养生息，那就要消耗地的资源。现实意义上就是人口膨胀，围棋棋盘上就是一步步填满自己的空。因为每块棋只剩下两只眼的时候再填对方就要提掉它了，所以最后肯定有一方填不下去了，那他就失败了，接下去走的情况显然是他的子一个不剩了。
这也是古代一统思想的真实反映，回到棋盘上，这样比较胜负的结果，除了目数差外，因为每块棋额外需要两目维持活棋，所以哪方多出一块棋就等于少了两目。
2.0.2 比目法的由来
很多人以为古围棋是数子法计算胜负（现在中国规则是数子），其实这是一个误区。除了棋头的概念外，古围棋计算胜负的方法更接近于比目法。
在上节所述的基本原理下，为节省时间，（也许也是为了避免一方将对方的棋子从棋盘上都提走的尴尬），古棋手发现填空的时候没有必要一手一替的全填满，而是各自用棋子填满各自的空就可以。然后就比较双方剩下的棋子数目，这样的胜负计算介于数子和比目之间，但更接近于比目法，其实区别只在于比目法要保留提子，提子算作目数，而古围棋还要数棋头，棋头是没有办法用棋子来直接表现的，所以直接的方法就是干脆回填了再比较。当然略有知识的棋手就可以不需要回填数清楚胜负。
那么说来，如果按以下三条规则定义，可以使围棋的目标确定为胜者通吃：
1，双方轮流着手
2，无气提吃
3，单热子禁提（这里借用了应氏的热子概念）
胜者通吃这一目标使得围棋问题本身演变成了一个全局的死活问题，假如围棋问题有唯一解或有限解的话，这样的命题方式将有助于实质性的解决。
如果考虑让子和回填，则第一条规则可略加改动：
1，除第一手和最后一手可以连着外，双方论流着手
2.0.3 从小棋盘看着手
尽管使用归纳法也许并不是一个恰当的方法，但可以给我们带来一些启示。
因为有对称的关系，我们考虑单数路数的棋盘。
略有棋力的棋手可以很快发现3路、5路、7路棋盘的正解（1路不用说了吧）。令人颇感兴趣的是正解都在中心位上。我们用计算机程序计算了5路棋盘，程序算法相当原始，只是一层层搜索下去，所以还没有办法在现有的计算资源上解决7路问题。不过从象棋问题的解决来看，解决7路问题是可以可行的。象棋棋盘是8路，正好介于7路和9路之间，当然象棋的变化与围棋的特点完全不同。
9路棋盘还是一个问题。据了解国内尚没有9路棋盘的专业比赛，如果有的话，也许可以通过结果统计进行研究。
如果采用归纳法的话，显然正解还是中心位。但是值得注意的是，7路棋盘的中心位刚好是4-4星位。这在古围棋中也是一个神秘的位置。
我们现在的推断是：围棋的正解当在天元位或4-4星位。
2.0.4 关于座子
提到了星位，不得不说到座子，这又是古围棋的一大特性。
现代围棋毋庸置疑是一种游戏，一种竞技项目。而放上座子之后，其变化就受到了极大的限制，日本近代发现的所有星位以外的定式就都没有了用武之地。所以，加上了座子古围棋似乎更像是一种推演工具（拿现代词汇说就是虚拟现实）。
然而一般而言，拓扑相关问题的正解往往是在对称的中心位上，如果围棋问题有唯一解或有限解的话，我们更容易相信它是在对角线上的某一点。
但座子并非只是一个魔咒。座子在围棋中的另一个作用不知为什么会被人们忽视，就是避免模拟棋。为了让棋手充分发挥想象力，甚至现行所有棋规都没有禁止模拟棋。模拟棋对于高水平的职业棋手来说未必是一个很头疼的事情，但对于一般的棋手显然是一个问题。
2.0.5 三劫循环
一个可能性是在围棋搜索过程中出现三劫循环。这是我们所设定的胜者通吃所没有包含的。如果坚信围棋问题有唯一解或有限解，可以立即抛弃这样的局面，就像近代日本围棋认为三劫是不祥之兆一样；也许还可以简单地保留作为最终目标，即和棋，感谢历史上已经给我们提供了太多三劫例子，特别是诸葛亮老先生六出祁山九进中原闹的确实是三劫循环。
2.0 精确和模糊的辩证法
博弈程序是要讲究精确的，这就是问题最终复杂化的根本原因。但是这里是没有捷径可循的，只有一步一步深入下去。很多围棋大师讲求棋势，追求围棋美学，其实这是棋力已经达到一个相当的层次之后的事情，对于职业棋手来说，很多局面的死活问题实际上他们一眼看过去就是跟打叫一样，所以才会有寻求围棋艺术的可能。
程序是不是可以在顶级高手的支持下，一步上青天呢，这显然要求把棋手的思想数字化，于是我们会说精确就是数字化。
有趣的是现在围棋能够量化要素恰好不是精确的，像影响了，摸样了，都早就被采用不同算法给量化了，可是结果并不精确；相反地，死活题没法给量化，主要是靠模式匹配，而这里又更多的使用了模糊算法。呵呵，真的弄不明白什么是精确，什么是模糊了。
3 围棋程序的方法
本章探讨围棋程序设计中使用的各种方法。
4 辅助工具
本章介绍围棋程序设计中经常使用的一些工具。
5 围棋程序的现状
本章介绍围棋程序的发展现状，对各种围棋程序的分析。
6 其他相关的成果和资源
7 作者和版权声明
8 名词和术语
8.1 项目内部名词定义
8.1.1 项目：本文中独立使用的项目一词，除非在其上下文中另有明确的限制或定义，均指为编撰本文而发起并实施的项目。
8.1.2 组织：为实施本项目而聚集的个人或团体。
8.1.3 成员：参与本项目组织的个人或团体。
8.1.4 作品：为本项目接受，并以正文、附件方式编入本文的著述、算法、软件或软件代码。
8.1.5 观点：为本项目接受的主张（idea）、提示（tips）、建议(suggestion）
8.1.6 贡献：组织成员为本项目提供作品、思想以及其他的工作（如收集资料、测试等）
[ Last edited by iie on 2005-12-28 at 09:43 ]
[ 本帖最后由 iie 于 2006-12-24 18:27 编辑 ]
搜索更多相关主题的帖子:
围棋 程序设计 基础
