1593人阅读
&电脑围棋小洞天 &　　　　　　陈志行&　　定量的重要性 　　人下围棋时，无疑在绝大多数情况下只作定性考虑。在判断形势时则以定量为主、定性为辅。也就是说，判断形势要从量上计算双方实空的对比，但还要考虑薄味、弱块、发展实空的可能性等因素。到了收官阶段，棋手的思路会增加定量的考虑。　　电脑围棋则更需要定量。上一章提到的静态评价函数，本身就是数量来表达当前局面的优劣的。　　围棋文化评论家胡廷楣曾在一篇介绍电脑围棋的进步的文章中，提到多年前我国著名数学家吴文俊的看法：电脑围棋如果单凭经验，单单存储许多名家的棋谱，将不是真正解决问题的方法。围棋如果要实现电脑与人对弈，就应考虑建立数量关系，就是要定量。没有这一步，是很难的。　　也许因为吴文俊是数学家，特别重视数量关系吧。我远远不是数学家，数学懂得很少。我只是一名围棋爱好者，同时是在使用电脑作科技计算上有点经验的人。我的看法与吴文俊不谋而合，认为电脑围棋必须首先重视定量：对于电脑围棋，质和量这对矛盾中，量是矛盾的主要方面。围棋的胜负焦点在于量：围取相对于对方的足够地域。围棋程序中每一着的选点，原则上应该是能取得最大地域和最有效地防止对方取得地域的一手。为了选取这样的着点，无疑会遇到许多定性问题，如攻击与防守、做眼与破眼、连续与切断、好形与坏形等等。这都是必须认真对待的。但是归根结底，每着棋的目的主要还是取得最大的利益而防止对方取得利益，而最后目的又是取得相对于对方的足够地域&&仍然是个&量&字。　　人下围棋，定量用得最多的收官。人工智能的学术界对此也有过一些研究。最有成果的当推美国人伯勒坎普、沃尔夫两人合著的书《数学围棋收官》。书中除了提出有关的理论和算法外，还列出20多个问题图，大多数是9路棋盘的，也有13路和19路。他们还请人编了一个程序，按照他们提出的方法来解这些题。据说，即使是九段棋手也不一定能解得对，因而要输给那个程序。　　然而围棋对局程序不能只考虑收官。围棋中有待研究的学术问题浩如烟海。为了提高程序棋力而急待研究的问题也不少。我想，其中的定量问题也许应该是个重点或者突破口吧。　　人脑下围棋时较少考虑量，不等于量不重要。电脑下围棋时也许大量的时间花在定性问题上，却归根结底离不开定量。人脑的思考，定性比较容易，定量相对困难。电脑却相反，定量(数值计算)是它的本能，而定性却不那么容易。人，和初次见面的朋友谈上一会儿后，过几天再见面时就能认得，就算他换了穿戴也照样认得。电脑要认得一个人就不那么容易了。电脑认人靠的还是模式识别，但这种模式识别跟围棋棋形的模式识别相比，复杂得不可同日而语。这种辨认人的相貌之类的模式识别，尽管属于定性问题，电脑仍然要转化为数量关系来处理。这种数量，像鼻子有多高、嘴巴有多宽之类，用少数几个显然不行，必须选定一大堆记录起来。要识别一个人是否就是所记录的这个，就要把这些数据一一对照。这里还有一个困难：嘴巴有多宽，是会变的：他带着笑意欢迎你的时候，嘴巴要比严肃时宽一些。模式识别时就要连这种因素也考虑进去，也就是要允许数据有某种程度的变化。这就说明电脑处理定性问题远远不如人脑。可是电脑的数值计算能力，人脑就望尘莫及。&&&让它下盘围棋 作者:乔治.约翰逊
看看电脑会有多高明 让它下盘围棋 &　　　　　　乔治.约翰逊&　　电脑&深蓝&一举击败国际象棋大师卡斯帕罗夫震惊了西方世界，可这一消息在东方顶多让人打个哈欠而已。　　尽管在日本、中国、韩国和其它国家有很多人钟情于国际象棋，但在那里更流行的还是看上去再简单不过的围棋。这一古老的游戏精深美妙，其之于国际象棋好比东方拳术之于西方拳击。如今的围棋迷们自豪地发现，电脑要想正儿八经地玩一玩这一迄今为止最纯粹的&人类&游戏，还差得远呢。　　台湾的应昌期先生悬赏140万美元征求第一台击败围棋高手的电脑。重赏之下必有勇夫，过去十年来 ，电脑设计家们绞尽脑汁，的确使电脑围棋的本领日渐提高。目前在美国和日本举行的国际电脑围棋年赛，冠军奖金均约为二万五千美元。然而尽管这些冠军们才技鹤立鸡群，但在与学棋约一年的人比赛时仍然不堪一击。初学者便可以横扫当今所有的围棋电脑，用不着有个卡斯帕罗夫。　　&深蓝&能够击败国际象棋冠军，靠的是基本的行棋知识加上强大无比的检索演算能力。而这排山倒海般的能量在围棋的精妙面前完全无能为力。迄今最强的电脑围棋程序之一&多面围棋&的设计者、美国惠普电脑公司的工程师大卫&佛特兰德说：&强力检索对围棋全无作用，你得创造出一个像人一样精明的程序来。&　　要使电脑下出的围棋多少像点样子，必须使其具备辨认各种微妙复杂的图形的能力以及运用自身直觉经验的能力。这种能力正是人类智慧的一大特点。如果真有一天电脑能打败围棋高手，那将标志着人工智能开始成为实实在在的东西了，也将宣告又一个科技时代的到来。　　下围棋时，棋盘上的图形如美丽的花瓣一一展开，人的思维就沉浸于这些图形所构成的美妙世界中，一串串行云流水般的行棋次序犹如一首首如泣如诉的旋律。关键就在于如何使电脑能够谱写并体会这视觉的音乐。表面上看来，围棋似乎比国际象棋简单，而通常人们把象棋比作一场中世纪的战争，围棋则更像是一场烽火连天的世界大战，很多情况下很难说清哪一方领先。在世界专业水平的国际象棋比赛中，如果你丢掉一个兵，棋局的结果在绝大部分情况下便有定论。而在围棋中，也许你在某一局部的生死搏斗中丢盔卸甲，但比赛可能远没有结束，你还可以在别处卷土重来。　　对于电脑来说，国际象棋与围棋的种种区别是无法逾越的巨大鸿沟。由于棋子移动方式的制约，国际象棋棋手在思考下一步棋时，大约只有35种合法选择。&深蓝&等电脑会针对这些选择加以分析，考虑对手的回应以及下几个回合可能出现的情况。最好的国际象棋电脑程序可以分析到七八个回合。这种信息检索选择方式就好比一棵枝叶繁茂的大树：主干分出35个枝干，每个枝干再分成35个树杈，每个树杈再分出35个树枝，依此类推。愈是高级的电脑程序所派生的树杈树枝的层次就愈多，最终达到每一片树叶，即可供选择的结果。如要求电脑能思考到第7个回合，即14步棋，便需要有3514(十万亿以上)片&树叶&。每多一个回合，树叶的数量就有爆炸性的增长。电脑工程师们使电脑能够合理地&剪枝&，仅使一部分而非全部树叶与主干相连。尽管如此，能够思索7个回合的国际象棋电脑每步棋仍然大概有500亿或600亿种选择。　　这样的数字已足够惊人，而电脑下围棋则更不可思议。选择之树的庞大茂密使迄今最强大的电脑也无法承受。通过&剪枝&，还要剩下一亿亿种选择，那么一台与&深蓝&同等速度的围棋电脑(即每秒钟可分析两亿种可能性)每下一子需要想一年半的时间。　　还远不止于此，即使经过如此这般上天入地的检索，围棋电脑在与人对局时并占不了多大便宜。国际象棋电脑在经过大量的信息筛选之后试图找到使其处于最佳位置的那一步棋，所采用的办法是称作价值功能的相当简单的公式：每个兵的价值为1、马和象为3、车为5、后为9，这一数字再与显示棋盘上位置强弱的另一数字相乘，以得出某一棋子在当时的相对值。还有其它一些公式用来决定某些概念的价值量，如王的安全程度或某一棋子受到攻击的可能性等。这些规定虽不一贯正确，但能使电脑对棋局的进展有个大致的感觉并据此做出自己的决断。而围棋则不受这些简单分析的约束。围棋盘上并无像&王&一样的棋子。每颗子都是平等的。统计双方吃子的多寡也不能说明什么问题。有时某一着棋便可以沧海变桑田，将对方苦心经营的领土化为己有，将对方的大龙变为自己的佐餐。　　围棋棋手们是通过对形状的认识来评估棋局的进展，而对这些形状的认识是无法作出几何分析的棋手完全依赖自身的经验去感觉哪些形状是活的或死的、好的或坏的。这一对形状的感觉正是胜负的关键，也是棋手水平高低的关键。棋手不愿浪费自己的棋子去无谓地攻击对方活的形状或无谓地去试图挽救自己死的形状。有时千钧系于一发，高明的棋手也难以作出生死的判断。要赋予电脑这种对形状的感觉，电脑科学家们面临着人工智能领域的基本课题。佛特兰德先生给他的围棋程序&多面围棋&输入一些基本概念，如对领地的认识及对棋子连接的认识，并输入二百多个高层次的战术概念，如&攻击弱棋&、&向处女地进行扩张&、&落后时开始无理地侵入&等。&多面围棋&可辨认一千一百多个不同的形状，每一种形状都有一些可行的手数。像&深蓝&一样，&多面围棋&储存很常用的开局形式及一些惯用套路。依赖这些储存的知识，&多面围棋&每一步棋仅在5至10种可能性中作出选择，而非理想的二百多种。　　给电脑输入一些概念是一回事，而教给它灵活运用这些概念则是另外一回事。可接可不接的棋或可断可不断的棋什么时候应连接或切断?什么时候又无需连接或切断?比起人类对于模糊概念的处理能力，电脑今天还是个婴儿。　　能够击败人类的围棋冠军而赢得应昌期围棋基金会悬赏的140万美元奖金恐怕是个无法实现的梦。该项奖金将于2000年到期。围棋电脑的设计师们希望把截止日期推迟一两个世纪。&
陈克训及其棋子分块法
&&陈志行 &
&&& &棋慧&是美籍华人陈克训所设计的电脑围棋程序，在电脑围棋赛上屡获佳绩。其特点之一是战斗力较强。这种较强的战斗力在很大程度上应归功于陈克训对棋子分块的深入研究。这种研究成果已用于他早期的程序&探索者&。下面的介绍中提到的具体数字都是在&探索者&中用到的。&&& &块&大体是一组有关连的同色棋子，它构成了围棋对局中的战术单元。若把整个棋局看成一个战争，则块可看成一支部队，它可以独立地活动，在局部与邻块的攻防就构成一个战役。
&&& 围棋的人工智能的一个基本任务是分块。优良的分块法能使电脑对当前的局面有较好的了解。它可用于估计局部棋子的安危、确定战术搜索的范围、产生弱块的攻防着点，且在终局阶段在块边缘及其外侧选取收官着点。
&&& 陈克训的分块法以&影响&和&链&这两个基本概念为基础。
&&& 首先讨论&影响&。
&&& 围棋中有一个概念叫做&外势&，它表征着棋子对外的影响。例如，下图的黑子把白角包围起来。白角形成了近10目的实空，而黑棋则对外方有着强大的影响，也就是有强大的外势。在围棋程序中，影响这个概念是泛指，不仅包括外势。图中的白子虽因不能对中腹和两边发出影响而无外势，但这些白子仍有对角上空位的影响，其结果是把这些空位控制在白方而形成实空。
　&┏┳┳┳┳┳┳┳┳┳&┣╋╋╋○○╋╋╋╋&┣○○○●●●╋╋╋&图一&┣○●●╋╋╋╋╋╋&┣●╋╋╋╋╋╋╋╋&┣╋●╋╋╋╋╋╋╋&┣╋╋╋╋╋╋╋╋╋&& 棋盘上的每个棋子都要对盘面发出影响。这影响在棋子的紧邻（距离为1）为最大值ｍ，并随距离增加而按比例衰减，衰减因子为ｆ。&探索者&选用ｍ=64、ｆ=1/2。 衰减因子为1/2就是距离每增加１时影响值减半。于是，一个棋子对邻位的影响值为64，尖位和关位为32,小飞和大关位（拆二位）为16,等等。ｍ值取为2的幂，而ｆ取为1/2，就使各级影响值均为整数，避免了小数运算。围棋程序因要计算很多问题，宜尽量节省计算量，因此通常都避免小数运算而只用整数运算。
&&& 这里所说的距离，严格些说应该是有效距离。问题在于棋子前面若有别的棋子挡住，则不易影响到它的后面。陈克训的做法是定义两点间的有效距离为从其中一点到另一点通过空位的最短途径。例如，下列棋盘上从棋子１到ａ位距离为２、到ｂ位距离为３。棋子１到ｃ位的距离，若黑子不存在，则距离还是３。现在有了黑子挡路，要绕弯路才能到达Ｃ位，距离为５。这么一来，棋子１对ｂ、ｃ两处的影响就不一样：对ｂ的影响是１６，而对ｃ的影响则只有４。
&╋╋╋╋╋╋╋╋╋╋&╋╋①╋●ｃ╋╋╋╋&&图二&╋╋╋ａ╋╋╋╋╋╋&╋╋╋╋╋╋╋╋╋╋&╋╋ｂ╋②╋╋╋╋╋&╋╋╋╋╋╋╋╋╋╋&&& 若干个棋子对一个空位的这些影响可以取代数和。陈克训取黑子的影响为正、白子的为负。上图ａ位受上方黑白各一子的影响互相抵销，只剩白子２的影响，为-16；ｂ位受黑子影响为４、受白１影响为-16，受白２影响为-32，净影响为4-16-32 = -44。ｃ位受黑子影响为64，受白１影响为４，受白２影响为８，净影响为64-4-8 = 52。
&&& 由于边角更易接受棋子的影响，在一至三线的空位的影响值被乘以某因子使其变大。这称为边角调整。边角调整后更把净影响值按比例换算为-ｎ与ｎ间的数。&探索者&取ｎ=64。这就是说，把净影响值等于或大于198者换算为64，-198或更小者换算为-64，而中间的值则变换到（-64,64)之间。这种换算称为规格化。具规格化影响值ｎ(-ｎ)的空位意为该点受黑（白）全控制，大体就是该方的实空了。规格化影响值０是不属任何一方控制的点。容易理解，规格化影响值可以用来计算地域。把特别大的净影响值通过规格化变为ｎ(-ｎ)，是因为某点的净影响值不论多大也不过是某方的一目地域。
&&& 规格化影响值可用于分块并对棋子的安危进行估算。
&&& 相连的同色子，即属于同一串的棋子，当然属于同一块。
&&& 取定一个界限值ａ。规格化影响值不小于ａ的空位作为黑方所控制的空位，而对白方则为不大于-ａ者。经验表明 a=n/4 是合适的界限。这ｎ就是上述规格化影响中的最大值。
&&& 某方的若干棋子若与己方所控制的空位或敌死子相连，就可以认为这些棋子属于同一块。
&&& 这里的所谓相连，是指通过相邻位置不间断地相连，就像串的定义中的一样。
&&& 这种分块法符合块的意义，即块是可以独立地作战的同色棋子的一个集体。若同色子连同所控制的位置（空位和敌死子）连在一起，就可看成难以分割的整体，即成为一块。
&&& 然而只用影响值来确定块是不全面的。常有这样的情况，同色的两串实际上不可分割，却并非通过具足够大的影响值的空位相连。为了使分块方案更为完善，须补充以&链&的概念。
&&& 原则上，链是不可分割的同色串的整体。然而如何确定不可分割性却不简单。陈克训提出了实际上采用的直观推断准则。
&&& 若两串有两个以上的公气，或只有一个公气但该处能防止敌进子（例如该处是虎口），就把这两串看成属于同一链。
&┣╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋&┣○○╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋&图三&ａｂｂａ╋╋╋╋╋○╋╋╋╋○╋○╋╋╋&┣○○╋╋╋╋╋○╋╋╋╋╋●○╋╋╋╋&链的例子&┣╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋&& 双关&&&&&&&&& 尖&&&&&&&&&&& 虎&&& 对于前一情况，若敌在两公气之一走棋，则我方可走在另一公气处使两串合而为一。对于后一情况，若敌着子于公气处，我方可立即吃掉它。
&&& 双关和尖连均属前一情况。图中的两ａ位若均有黑子，则两ｂ位的影响值黑白相消而不为任何一方所控制。但不论黑走在两ｂ位中哪一点，白均可占另一点而将两串连起来，故不能分割。
&&& 显然这种只管判断不能识别复杂的不可断的连接。相反，这里有一个有意思的缺点。考虑如下图的三个白子：
&╋╋╋╋╋╋╋╋╋&╋╋╋ａ○╋╋╋╋& &图四&╋╋╋○ｂ●●╋╋&╋╋╋ｃ○╋╋╋╋&╋╋╋╋╋╋╋╋╋&&& 上、中两白子有两公气ａ和ｂ，故属同一链。同样中、下两白子有两公气ｂ和ｃ，亦属同一链。但三者不能属于同一链，因若黑走在ｂ处，白智能连接在ａ、ｃ两点之一而不能都走到。为了回避这一问题，当我们发现正好有两个公气且无一是能防敌进子的，我们把两者合并成链，并标出这两点使其不再用于将来的合并。
&&& 同一链中的棋子均应属于同一块。例如，下图中的白子若仅考虑影响值则成为两块，每块只有一个眼。有了链的概念，因两串通过尖连而成为一链，就构成有两眼的一块。
&┏┳┳●○┳○●┳┳&┣╋╋●○○○●╋╋&┣╋●●○●●●╋╋& 图五&●●●╋○●╋╋╋╋&●╋○○╋●╋╋╋╋&●○╋○●●╋╋╋╋&●○○○●╋╋╋╋╋&●●●●●╋╋╋╋╋&┣╋╋╋╋╋╋╋╋╋&&& 通过影响和链来作出分块，与人类棋手的直觉是颇为一致的。一旦分了块，其安全性即可用其影响值及其自由度来估计。块的自由度意为它周围的敞开程度，它和逃出及利用周围敞开处做眼的难易程度有关。块中的影响值及自由度足够大则安全。不够大的可检查它能否做两眼，从两眼及逃出的难易程度来对安全程度作估计，并加以定量化而用数字0至64来表示：64为安全，较少的则不尽安全。安全性为0的即完全无望，也就是死块，其中的棋子和邻近的空位均可判为对方的地域。
&&& 若我方某块不安全而非无望，即安全性小于64但大于某界限，就会有适当的防守着点使其加强。若某敌块不安全而非无望，就会有攻击点以图攻杀或欺凌该块而取利。这就是说，分块能用来产生攻防着点。 &
&想和电脑下盘棋 一、电脑、围棋和我
　　文革时，我在中国科技大学上学，当逍遥派时结识了围棋，从此与围棋结下了 不解之缘。读研究生后中断了八九年，近十年又下了起来，兴趣比年轻时更浓，围 棋竟成了我的第一业余爱好。与电脑结识则稍晚一点，在年我当大学 助教时，有些课题需上机计算，便开始学习编程。那时没有&电脑&这个词(也许 台湾或香港有)，我们只知道那玩艺儿叫&计算机&，是非常先进和贵重的设备，拥 有一台个人电脑这种事连做梦也想不到。当时，在发达国家计算机也只在大学、科 研机构和少量的大公司才有，当时处于封闭状态的中国，依靠科技人员的不懈努力 也制造了一些计算机。当时，一台计算机要占据整整一间实验室，性能远不如现在 奔腾机，软件更是少得可怜，基本上只能做科学计算，一台机器往往只有一两种编 程语言供用户使用，如Fortran、Algol，使用极不方便--先要自己仔仔细细地 把源程序写在普通纸上，然后在一种专门的穿孔机上把源程序&写&到一条长长的 黑纸带上。穿孔机像一种老式打字机，不同的是打字员每敲一个键，它就在那条黑 纸带上穿一排孔，不同的字符对应孔的不同排列方式，像电报码一样。为什么要这 样做呢?因为黑色穿孔带是计算机唯一接受的输入方式。上机前要先申请机时，机 房工作人员根据情况排出上机时间表，轮到者在指定日期和时间(如果到外单位上 机，常常会被安排在半夜)带着预先准备好的黑色空孔带和一颗不安的心进入酷似 外科手术室的机房，进行那期待已久的计算。如果在安排的时间内没有完成计算， 而下一个用户已经到达，计算机往往被无情地中断。　　至于改错、重新穿孔等一连串的麻烦都是现在的电脑爱好者无法想象的。现在 在个人电脑上十几分钟完成的事情那时要花费几天或更久。 　　即便如此，我仍对计算机的功能惊叹不已。　　80年代初，美国的家用电脑市场发生一件大事：实力雄厚的德州仪器公司决 定退出家用电脑市场，将它库存的全部TI99电脑以极低廉的价格同一天在全美出 售。当时正在美国留学的我也没有放过这次机会。这是我的第一台个人电脑，虽然 其功能不能与现在的PC机相比，但它具备了电脑的基本功能，可以用BASIC语言 编程。最使我兴奋的是它的键盘输入方式以及简单编辑的基本功能使我永远摆脱纸 带穿孔的烦恼。随着时间的推移，我的电脑不断更新换代，直至现在的多媒体PC 机。电脑对我来说是工具，是宠物。我用它储存数据、作文字处理、进行科学计算、 辅助教学等，当然，近年来收发电子邮件和上网浏览更是少不得它。　　1987年，我自学C语言时给自己出了一道习题：编写一个围棋打谱程序，完 成后输入了棋书和围棋杂志上一些棋谱，供自己和朋友欣赏。　　当时也曾萌发编制围棋对弈程序的想法，但觉得难度太大，一时难以着手。直 到最近几年，才开始对弈程序的研制，目的是能达到围棋初学者的水平，原以为这 个目的不难达到，事实证明这个想法是错的。难怪贝多芬曾对他的弟子说：&你们 只有长期刻苦地练习钢琴，才会知道自己弹不好钢琴。
　　二、电脑围棋为什么这么难
　　IBM公司的&深蓝&已经击败了国际象棋之王卡斯帕洛夫，电脑围棋何时能击 败九段?已故的台湾实业家应昌期先生曾重金悬赏，在2000年前击败台湾九段高手 的程序，现在看来是&可望而不可及&--我想，目前世界上从事电脑围棋研究的 人，是没有人在期待这笔奖金的。我国数学界泰斗吴文俊先生曾对记者谈论他对电 脑围棋的看法，他认为：围棋的计算量大得惊人，没有什么好办法。计算机界人士 对围棋的复杂度作了比较透彻的研究后认为：如果和国际象棋作比较的话，国际象 棋全局的计算量只能抵得上围棋中一个局部战斗的计算量。同为棋类，两者的特点 相殊甚远。国际象棋的目标是吃掉对方一个子(王)，而在围棋中吃掉一个子甚至一 串子常常算不了什么，国际象棋中不同的子有不同的价值，皇后的价值大大超过卒 的价值；而围棋中的子只分白子黑子，子的价值完全由它和周围乃至全局其它子的 关系而定。爱好围棋的朋友一定知道，围棋中有很多时刻并没有所谓&最佳手&， 好几个不同的选点都是好点，连专业高手也不能贸然判断孰优孰劣。　　当然，理论上讲，最佳手是存在的，但凭现在人类对围棋的认识，还不能准确 无误地算出来。围棋的这种模糊性给棋手提供了尽情发挥的舞台，有人认为下围棋 是艺术创作，此话毫不过分。我们知道，电脑的强项是计算，而创造性正是电脑的 弱点。　　我国有志电脑围棋的人士多数靠业余时间，在缺乏资金和社会舆论支持的情况 下搞。虽然中国是围棋的发源地，但是似乎欧美有更多的人对电脑围棋具有热情， 这一点从国际互联网上可见一斑。在我国最早投入这个领域的大概要数中山大学的 陈志行教授，他的电脑程序&手谈&已获得六次世界冠军，为中国人争得荣誉。和 &深蓝&相比，&手谈&对硬件要求很少，中国人能在外部条件不如别人的情况下 开发出最好的围棋对弈程序是很不简单的。　　专业棋手对电脑围棋怎么看?《电脑报》也曾报道过俞斌、常昊等围棋国手用 电脑搞棋谱程序的事。但从目前来看，我国没有一个职业棋手真正投入这个项目。 据说日本已经有九段棋手编制了对弈程序参加电脑围棋比赛。如果说大部分专业棋 手对电脑围棋嗤之以鼻，我也不会感到奇怪，因为现有的电脑围棋距离他们的标准 实在太远。电脑围棋现在处于童年甚至婴儿时代，但其发展前景相当广阔，总有一 天会引起多数专业棋手的认可甚至参与，卡斯帕洛夫几年前还深信电脑会击败 他。&深蓝&在开发过程中得到过若干职业国际象棋棋手的指导。
　　三、为什么研究电脑围棋
　　美国曾经发射一艘宇宙飞船向太空作永恒的飞行，目的是希望某一天它能被某 个星球的外星人截获而使外星人知道宇宙中曾经有过人类文明。显然，用地球上的 文字来传达信息是毫无意义的，于是美国人只在飞船上放置了各种有代表意义的实 物，其中有一件便是国际象棋。国际象棋能代表地球上最高级的棋类吗?恐怕未必。 我在网络上看见一个西方人介绍他对围棋的认识过程。他原是一位国际象棋迷，自 从学会围棋后，便觉得与围棋相比，国际象棋索然无味，下一盘国际象棋像是经历 一次战斗，而下一盘围棋像经历一场大规模战争。围棋在中国至少有2000多年的 历史，是中华文化遗产的一颗灿烂明珠，任何一个年代的中国人都没有理由将它舍 弃，更何况现在围棋已经走向世界，将电脑这个现代科技的产物应用于国宝围棋上， 是一件十分有意义的工作。　　围棋在我国既是高级娱乐又是一项竞技项目，相应地，电脑围棋的主要目的也 不外乎娱乐比赛，但对围棋对弈程序开发人员来说，其意义却不限于此，对他们来 说，写这个程序是接受一个严峻的挑战，是试图揭开围棋神秘的面纱。国外有人撰 文，标题为&你想知道电脑多聪明，就和它下一盘围棋吧&。　　人工智能学术界对电脑围棋相当重视，日本一年一度的FOST杯国际电脑围棋 赛就是日本人工智能年会的一个项目。正因为围棋计算量太大，不可能用简单的计 算来设计程序，而更多地采用模拟人脑的方式来做分析和判断，因而真正有水平的 程序是具有相当程度的人工智能的。已经有不少人在电脑围棋方面写了博士硕士论 文，例如&电脑围棋与模式识别&等，著名博弈论专家Berlcamp还写了一本专著， 从理论上探讨围棋收官。电脑围棋程序的算法是一种组合优化的技术，因此围棋程 序开发本身是一项科研，它与计算机科学和数学有着密切的关系。　　尽管国内对电脑围棋有些研究，也有一些论文，但是基础性的研究成果还很肤 浅，对于围棋还没有建立适当的数学模型，当然要建立模型是不容易的，在算法理 论上也没有突破，希望不久后在理论上能有进展，这样，电脑围棋的水平会有所进 步。
(撰稿人：湖南大学数学系杨劲根教授)
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：842870次
积分：11263
积分：11263
排名：第458名
原创：111篇
转载：524篇
译文：46篇
评论：115条
(1)(2)(1)(1)(1)(1)(1)(4)(4)(1)(1)(1)(1)(1)(1)(2)(3)(29)(22)(9)(11)(1)(8)(35)(26)(1)(3)(1)(1)(2)(4)(1)(1)(1)(1)(1)(9)(24)(89)(86)(85)(68)(76)(34)(22)(4)电脑为什么会下象棋？_百度知道
电脑为什么会下象棋？
是否是电脑自己和自己反复搏弈直到选出最佳步骤（就如兹威格《象棋的故事》）电脑为什么会下象棋？它如何判断局面的忧劣？最强的中国象棋软件能和大师对弈么？它的数学原理是什么
，而不是含含糊糊的编程..请懂得此类专家给解释一下、套路.我要知道的是数学原理
提问者采纳
0,16},9; case 1; while(j& case 3;100, 1;17,32;stdafx，我们实验课上经常做这些^_^#include &if(i&lt,i;=LastOfSide[, 2, 0},&#47,6.x)。 思路2,y)) ADD(n;=9 && j& break: 32棋子的坐标 tside, 1, 1; #include &quot,32;&#47.x==0) manIndex=27; #include &quot,j) else { if(NOBLACK(x;if(i&lt,j) i=x-2,i;k=32; scanUp =low+1, 2, 0, 0; 将 士 象 马 车 炮 兵 const int base[7]= {300;&#47,1,9,YBW=BWA*10;&#47.x==0) manIndex=5.dll timespan是思考的限定时间：如果别人走马;flag=FALSE,j) break,i,j) i=x-1;=9 && j&gt,y+1)) ADD(n;if(i& case 17: i=x+1,tmanposition[0];if(i&gt.y);&#47.x; count=0; static BOOLn++) { x=tmanposition[n].x) &#47,tmanposition[16],y) i=x-1,x: case 2,j) j=y+2,j)) if(NOMAN(x+1;if(i&lt,i,j)) ADD(n,x: i=x+1，你就走马。 本程序中的算法没有使用这一变量.x==0) manIndex=7;ShowInt(计算机 const int RED=0,13,32;[6] {32;&#47, 0}, 0, 3; if(low&i&lt,y)
case 5,j) } break.11/10; break,int& x1;&#47,32!=1) #define NOMAN(i, 0; scanDown = high,tx,j)) if(NOMAN(x-1: i=x+1。按照思路一的算法 往多了算 一盘棋有50回合.x-1; &#47,31}, 0; int scanUp;if(tmap[tx][ty]==FistOfSide[: i=x+1,y)) { if(; break,6;MantisChessDef, 0} }; static int BeAteCount[32];j=y+1,x: if (manpoint[5],6;进攻的重视程度 &#47, 0;0 && ManBaseValue[i]&gt,j)) { i=x+1，每步有50种变化 一共的变化数就是50的100次方就算少算一点 一盘棋有20回合;士 const int BLACK_X=9; POINT from[MAXMOVE], 0,否则返回FALSE ******************************************************************/=9 && j&&#47,0, 0;scanDown),j) i=x-2.,3;8; pivot_point=targetpoint[mid];=1 && j&lt，平均每方每步可有35种走法,1, { 0;32; if(NOMAN(i.x==0) manIndex=21,32, 0};=8 && NORED(i.,0, { 0!flag) { ADD(0;=1) { if(NOMAN(i;&#47, 0: if(tmanposition[0],i,6, 0,y) i=x-1;MantisChessThink,32, 0; if(NOMAN(i,resultman, 0;0 && ManBaseValue[i]&gt,y) break,32, 3;j=y+2,int& y1, 1,y)) ADD(16.x==0) manIndex=1;****************************************************************** 例!tside].,32;i&flag=FALSE,32; static int ManContact[32][32],y)) { if(,32}; &#47，之所以他能够拥有下棋的能力,32; for(i=FistOfSide[; int side=(int)map[0]-48, 2*base[3]*range[3]&#47,i.y), 0,i,5; point=targetpoint[high]; else { if(NORED(i; POINT to[MAXMOVE]: if(tmanposition[0]; x2=resultpoint, 0;if(i&[4] {32; BOOL EnumList(int tmap[11][12]; else if (manpoint[28], { 0;=1) { if (NOMAN(i,32;j++) { if(tmap[x][j]; &#47: QuickSort上下限 返回值., 4;=1 && NORED(i,32,y)) ADD(0; / chessman[scanDown]=pivot_ else manIndex=2, 0; } i=x-1, { 0,j)) ADD(n,32: i=x+2,32};if(i&gt,6,n;卒 // /i++) { for(j=0;MW-棋子宽度; switch(k) { case 6;/100; /i++) { if(BeAteCount[i]&lt,6;j++) { if(tmap[x][j],0,j) i=x-1,&#47: case 6, 20,i, 1，格式是if, { 0; case 5; ManBaseValue[i]=BV1[k]+ManBaseValue[i]*BV2[k],1;=6 && j&&#47,y)) ADD(n, 0; else manIndex=4,ManContact),返回小于n的随机整数 int rnd(const int& n);=1 && j&lt,j) (SideOfMan[tmap[i][j]].; targetpoint[low]=point,11,j) i=x+2, 0;BOOL Thinking(int tmap[11][12]; /=10 && NOBLACK(i, 0,int& y2);if(i&gt, 0: if (manpoint[3];=LastOfSide[tside],300。如车可以走到任意一点;i&lt,32，是因为我们预先教会了他;i&&#47.,所将军的棋子不能被吃掉 { j=0;/ i++) { manpoint[i];j&lt, 4; } BOOL test(char* x1) { return FALSE,y-1)) ADD(n, 0},0,j)
} } else { ManExtValue[i]+=ManBaseValue[j]*contactpercent2&#47, base[5]-base[5]*range[5]&#47.x=x,i, 0};&#47,int &if(i&lt, 0,32;************************************************************************* 把Think重新包装一下,i, 2,32.x==0) manIndex=13,j) i=x-1,high), 4*2*base[6]*range[6]&#47: &#47，我目前所知道的最牛的机子名叫【深蓝】;if(i&lt, 0} } };防守的重视程度 const int contactpercent2=25;车 const int RED_P=5，详细资料如下 case 9,j)) ADD(n;flag=FALSE.; SW-棋子间隔的一半 const int BWA=MW+SW*2; [0][1][2][3][4][5][6][7][8][9][10][11] {32, base[3]-base[2]*range[2]&#47, 3; case 16; while(i&/ const int BV2[7]=/=0)&#47!flag)flag=TRUE,32; static int ManExtValue[32]., base[4]-base[4]*range[4]/j=y+2,1;=8 && NORED(x,7;tmanposition[0],/=1 && NORED(i, },int& x2;i&lt,32，以毫秒为单位;=6 && j&gt, 0,1; } int length=(int)strlen(map),y)) { i=x-2;if(j&lt: 无 ******************************************************************&#47, 0};100&#47,32}&#47,32,32.h&quot，数字越大价值越高 const int ManBPlus[2][12][11]= { { { 0, 0;scanDown-1) Mantis_QuickSort(A;j=y-1; }
&#47,&#47,int contact[32][32]),j)) ADD(n;&#47, 0};j=y-2,2: ManBaseValue[i]+=BV3[ ManBPlus[SideOfMan[i]][tmanposition[i]; break, { 0; case 3;2;BWA-棋格宽度 const int XBW=BWA*9,i; const int FistOfSide[2]={0.then: 列出所有走法 参数;价值的变动范围 const int contactpercent1=20,=1 && j& } maxvalue -=j, 0,32,3.h const int MW=32: if (manpoint[25]: if (manpoint[7]; case 6; / &#47,32;/ /=1 && NOBLACK(i.给出棋子序号, 1;if(i&gt,4; } else { if(high-low==1) { if(A[high]&gt., 1,y)) ADD(n, 2.,POINT targetpoint[];/if(i&gt, 0; &#47.net,j)) ADD(n; chessman[low]=k, 3;&#47,0,2; &#47,13,32, 0, 0; } maxvalue +=j,j)) { i=x+1;/100.x==tmanposition[16]; i++) { for (int j = 0, 4,i,32;=1 && NOBLACK(i,32,j)) ADD(n, 0;红方 const int BLACK=1;=10 && NORED(i, 0,32; } void ShowInt(int i) { char buf[256]!flag) ADD(n;j=y-1,j)) ADD(n;tmanposition[0];n&=4 && NOBLACK(i;if(i&lt,j)
[0] {32, 0;=1 && NOBLACK(i; break, 2,j)) ADD(n,32: i=x+1,32;=9 && j&gt, { 0: if (manpoint[27],i, 0,32};return FALSE://www,i,j)) ADD(n;=1 && j&gt,j)) ADD(n,y)) ADD(n; break,32}, 0;=10 && NORED(i.y=0; const int BV3[5]=/=9 && j&gt,1;if(i&lt,32;=10 && NOBLACK(i, 0;象 const int BLACK_M=10: i=x+1,int &tside, 0}, base[6]-base[6]*range[6]&#47,&#47,&#47,32;-------------下面几项可以调试智能模块--------------------------- #define S_WIDTH 8 #define S_DEPTH 6 &#47, 0;j&j=y-1,0), 0;if(i&gt,3; switch(n) { case 0,5,i, 0}; else if (manpoint[29],i,low, 0},32;[1] {32,32;[7] {32, 2; A[mid]=A[low];=6 && NORED(i;&#47, 2*base[1]*range[1]/if(i&gt,2!tside])goto _NOKING;&#47,i, 0,6 ，也就是100步,y)) { i=x+2;j=y+1,int * y=tmanposition[n]: case 4,j)) ADD(n.x==0) manIndex=25;[10] };/stdio, 0,y) break, { 0;test&j=y-2, 0; &#47,1; /红帅 const int RED_S=1,0.h&quot, 0,j) i=x-2,&quot, 1，计算机本身是没有只能的, { 0.x==0) manIndex=28;=3 && NOBLACK(i, 0},32,SW=1.x==0) manIndex=14.x==0) manIndex=17;&#47,32, 3,i; / A[scanDown]=k; else manIndex=26;=LastOfSide[tside],32,int &=1 && NORED(i,x;己方 OwnSee[j]=TRUE;&#47,i; while(j&&#47, { 0,i;17,i;=scanDown && A[scanUp]&gt,32; tmap[x][y]=manIndex，实现了我们跟计算机之前的对话,x，战胜了国际象棋大师【卡斯帕罗夫】; else manIndex=31;[5] {32; point=targetpoint[mid];=9) { if(NOMAN(i;/ } j++;------------------------------------------- static void ContactV(int tmap[11][12],32; int index = 1,y)) ADD(n; } i=x-1; } j=y-1.x==0) manIndex=11,32: 局面的价值 ******************************************************************/Calculate, 1; else if (manpoint[30],j) i=x-1, 4;4,32;100, 1,j)) ADD(n;thinking的y从10到1 int color = (int)map[index + 2]-48, 0.;****************************************************************** Value,32, &#47, LPVOID lpReserved ) { return TRUE,32;i++) { if(ManContact[i][FistOfSide[; POINT manpoint[32], 0;黑方 const int RED_K=0;if(i&gt: 指向棋子所走到位置的指针; targetpoint[scanUp]=targetpoint[scanDown],sizeof(int)*32*32),i.,32;if(i&gt.h&quot，别人走了一步以后,j) break,POINT tmanposition[32],ty) {chessman[count]=if(i&lt.h&quot,变动范围±13%应设base[3]=200,j)) ADD(n, 2*base[5]*range[5]&#47.x==0) manIndex=12;=1 && NOBLACK(i;if(i&=1 && NORED(i，是通过程序语言来实现的,32; } } } } for(i=FistOfSide[tside]; &#47,y)) { i=x+2,int high) { int pivot, 0, 0; targetpoint[scanDown]=pivot_point,i,32,j)) ADD(n, 0,4; &#47,int& x2,32,scanDown-1); 12: 轮到哪一放走 返回值,32;/&#47,32, 1;=1) { if (NOMAN(i, 0;&#47.,i: if (manpoint[21],300},j)) ADD(n,32; 11,j)) ADD(n,y) else { if(NOBLACK(i; } } manpoint[manIndex], 0}; while(i&gt, 2;[9] {32,32, 1*2*base[6]*range[6]/i++) { if(tmanposition[i]; BOOL b=Think( tmap.y+1, 0; #define NORED(i, 0;=4 && j&lt,6: case 20; if(high-low&lt, 1;=LastOfSide[tside]: case 10, 3;
} i=x-1,j) &#47, 1;%d&if(i&=10 && NORED(i!flag) ADD(n,32,j)) if(NOMAN(x-1, 3, 0, 0;=10 && NOBLACK(i;&#47: if (manpoint[17].就跟上面的如果怎么样就怎么样是一样的了, off) #endif BOOL APIENTRY DllMain( HMODULE hModule, 0.;=1 && NOBLACK(x,y;j=y+2,32; if(NOMAN(i，与chessman一起组成走法列表 （存放结果）
} } if (，这样计算机就懂得在不同情况下如何处理了哦^_^希望姐姐的解释还比较清晰^_^【补充来了】^_^思路1, 0,3; / const int LastOfSide[2]={15;=6 && NOBLACK(i;100&#47,32;100.y,32;炮 const int RED_B=6,0; A[low]=k;&#47. } } else { switch (type) { case 0, 3。 **************************************************************************/ } i++; #include &quot, 3; else manIndex=8.,13; } else { j=0, 3, 0;j=y+1; &#47,1, { 0;j=y-2;i&将帅在同一列 { flag=FALSE;&#47,x; } } if(flag&&BeAteCount[k]&gt,j)) ADD(n, 1, 4,sizeof(int)*32);&#47，计算机会去计算,10,j) j=y-1, 0;&#47,6; break,32;if(i&lt,j)) ADD(0,j)) ADD(n,int &tside, 1: i=x+1, 4;high) Mantis_QuickSort(A; i &=1 && j&gt: manIndex=0; if(; ZeroMemory(ManExtValue.,j) break,y) break, 0, 0,j) i=x-1.x=tx,y)) ADD(n; } } } mid=(low +high)&#47!tside],10;兵 const int BLACK_K=7: 待排序的棋子列表 targetpoint, 0;if(i&lt, 0,j)) ADD(16,j) (SideOfMan[tmap[i][j]]; A[high]=A[low],4; struct MOVEHISTORY {
while(i&0-6 int manIndex=0;&#47: i=x+2; &#47, 0; &#47,32，棋盘上90个点!，就是1后面跟着40个0【也就是说;&#47,3; } } for(i=0;32,5;100 },&quot, 0;4;=1) { if (NOMAN(x; if (color==0) { switch (type) { case 0,i,6,32; case 23,1,13;=9 && j&仕 const int RED_X=2;人 const int COM=1,j) } i=x-1,6 ,32;/ chessman[low]=k; if(NOMAN(i;j=y-2, 0}.;&#47,32;/if(j&gt,&&#47, 0,32，也就是40步; int Value(int tmap[11][12]; case 5, 2!tside]]) { maxvalue=9700,i;j=y-1,y+1)) ADD(n,x： 关键值 兵在不同位置的价值附加 { 0*2*base[6]*range[6]&#47,1!flag) ADD(n,y+1)) ADD(n; targetpoint[mid]=targetpoint[low], { 0,32,32,32;100/ chessman[mid]=chessman[low],y) break, 10; } j--;=8 && NORED(i;count++,j) i=x+2,11;=1 && j&lt: 32棋子的坐标 =1 && j&gt,2,x，各点可走的点, 3;/StdA } i--,y) else { if(NORED(i; #include &quot,/ break,chessman.x==0) manIndex=30; } #ifdef _MANAGED #pragma managed(pop) #endif Calculate,j)) if(NOMAN(x+1;&#47,i, 0};=6 && j&if(i&gt, { 0.h&&#47, 1, 0, 0, 50};车 const int BLACK_P=12.h&quot,j)) ADD(n;=9 && j&lt,j)) ADD(n,进行坐标变换;100/ } i++,j) i=x+1,i,32。 &#47, }.x==0) manIndex=23,32;thinking的x从1到9 int y = 10 - ((int)map[index + 1]-48), 0, 0;&#47,j: case 24; length) { int x =1 + ((int)map[index + 0]-48); sprintf(buf, DWORD ul_reason_for_ &#47,/
POINT resultpoint={0,i,i, 0;4; if(NOMAN(x，你有多少种可能的走法,i, 0,j)) ADD(n;100,j)) ADD(n;[8] {32; for (int i = 0; else manIndex=10, 0; int betaken[MAXMOVE],j) i=x+1,x,j)) ADD(n; for(i=FistOfSide[, 0}, { 0,j) i=x+1,32, 0;/ int maxvalue=0; else manIndex=24;&#47,6,1;=1 && j& j++) { tmap[i][j] = 32;相 const int RED_M=3,32!OwnSee[j]) { ManExtValue[i]+=ManBaseValue[j]*contactpercent1&#47, { 0,y-1)) ADD(n,j)) { if(,6; static BOOL OwnSee[32],int chessman[]; &#47!=32) { flag=TRUE, 0; for(n=FistOfSide[tside]; flag=FALSE,sizeof(int)*32); } j=y+1;j=y-2: 指向棋子列表的指针（存放结果） move,j)) if(NOMAN(x+1, 2,1,32.y.htm其实, 0; case 3; 32,j) 【我是学c++的】呵呵, { 0;=9 && j&if(i&lt,j)) ADD(n, 1: 估值函数 参数,i; while(pivot&gt,y)) ADD(n：把马设为平均价值200,j) } j=y-1;随即函数,32; void ShowString(char * t);=pivot) scanUp++,i; case 1,x; } j++, 0,side,j) else { if(NORED(x, 4; } static BOOL } &#47, 0;j=y+1,32; } return b, 0;test&quot,int activity[32];=1 && j& while(j&lt,32};/=10) { if(NOMAN(x; const int MAXMOVE = 1000;if(i&兵卒在不同位置的价值;; A[scanUp]=A[scanDown]; BOOL Calculate(char* &#47,x, 4, { 0,32,4: “照相”返回TRUE, 0,0,k, 0; /if(i&gt, 3,y)) ADD(n,int &tside) {
while(i&以下是全局函数定义; case 7; } }while(scanUp& static int ManBaseValue[32]; } } j=y+1,8!; &#47, 0, 0, 0; while(j& k=chessman[scanUp];j=y+2; while(j&j) j=ManBaseValue[i],/MantisChessThink,5,y)) { i=x-2,x, 0, 2*base[4]*range[4]/ ZeroMemory(BeAteCount, 0我是学计算机的，加了注释，呵呵,32
提问者评价
果然高人，十分专业。
其他类似问题
62人觉得有用
按默认排序
其他9条回答
，推算下一步（下下一步.计算的步数越多越耗时间。。）的走法带来的局面的总的值的和，出现哪种局面就用哪种走法，电脑的水平也越高另一个是给电脑输入棋谱,电脑行走时一般象棋程序是两种算法一个是根据每个子的价值给每个子赋值。.写程序的时候两种算法结合使用是比较好的一种选择，下下下一步
就是把实战中 人下过的谱都记录下来 按谱下啊象棋不比围棋
围棋有2X10的30次方的可能象棋可行的有几千万就不错了几千万的运算量对现在的电脑来说不算什么了吧
把一写套路输入进去了 电脑就按套路下棋所以电脑很容易 只要赢一次 电脑的路线就很明了
这是因为程序里面保存有棋谱棋谱里面记录有象棋的走法,举个例子,只要你走车,可能它就会走马,有多个棋谱,交替使用的
楼主问得太笼统了，其实说电脑会下象棋是一个很庞大的数学问题。计算机专业里面有一门专门的科学叫人工智能，就是为了解决这方面的问题。现有的大多棋类游戏，有点人工智能的大多采用的是危机值来确定的。说得很细点就是，在每一步时，他利用堆栈会对这步分析对方下步走对自己不利的概率。所以，为什么现在的计算机还要提升速度，就是为了算得更远。不过遗憾，中国的人工智能在世界上还是比较落后的。
我感觉就是编程的自己搞的凭电脑超强的记忆集百家之长所以对付他们最好的办法就是出其不意
电脑下棋其实很简单，就是不断的计算路数，从这些路数中选择对自己最有利的路数。总之，电脑只会做人们已经能解决的问题。它的强项就是能重复做事情而不会感到烦。
把一些下棋 方法写进去了
您可能关注的推广回答者：
下象棋的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁