路边野花不採白不採

偶在国内的博客:http://blog.sina.com.cn/deannn
个人资料
  • 博客访问:
正文

看看你的电脑能有多高明,让它下盘围棋吧

(2009-06-02 12:55:18) 下一个


十来年前电脑“深蓝”一举击败国际象棋大师卡斯帕罗夫,震惊了西方世界。然而这一新闻在东方顶多让人打个哈欠而已。

围棋,洋人眼里黑石头与白石头的游戏,与古老的东方历史一样深不可测,渗透着人类最高层次的思维与智慧。在如今科技日异千里的时代,围棋迷们发现,电脑要想正儿巴经地玩一把这一迄今为止最纯粹的“人类”游戏,还差得远呢。

台湾的应昌期先生生前对推广围棋文化乐此不疲,曾悬赏一百四十万美元征求第一台击败围棋高手的电脑。重赏之下必有勇夫,电脑专家们绞尽脑汁,的确使电脑下围棋的本领有所提高。在美国和日本举行的国际电脑围棋年赛,冠军奖金约为两万五千美元。然而这些矮子里拔出来的电脑冠将军与学棋一年左右的人比赛时仍然不堪一击。初学者便可以横扫当今所有的围棋电脑,用不着请一位卡斯帕罗夫。

如今电脑的运行速度越来越快,容积越来越大,但近年来下围棋的本领仍在没有多大长进,应老先生的赏金只好留待后人来拿了。

“深蓝”能够击败国际象棋冠军,靠得是基本的行棋知识再加上强大的检索和运算能力。而这排山倒海般的能量在精妙的围棋面前完全无能为力。迄今最强的电脑围棋程序之一“多面围棋”的设计者美国惠普电脑公司的工程师大卫•佛特兰德说:“强力检索对围棋全无作用。你得写出一个像人一样精明的程序来。”

要使电脑下出的围棋多少像点样子,必须使其具备辨认各种微妙复杂的图形的能力以及运用自身直觉经验的能力。这种能力正是人类智慧的一大特点。如果真有一天电脑能打败围棋高手,那将标志着人工智能开始成为实实在在的东西了,也将宣告又一个科技新时代的来临。

下围棋时,棋盘上的图形如缤纷的花瓣逐渐展开蔓延。人的思维就沉浸于这些图形构成的美妙世界中,一串串行云流水般的行棋次序犹如一首首时而悠缓时而激昂的旋律。问题就在于如何使电脑能够谱写并体会这一视觉音乐。

表面上看来,围棋似乎比国际象棋简单:64个方格上的国际象棋每一方各有16个棋子,等级从兵到王。每个棋子只能根据规则以自己特有的方式移动,譬如象只准走斜线;马只能L型进退;兵第一步时可向前走一格或两格,以后只能走一格,不准后退,吃子时须向前斜一格吃;此外还有王车易位、兵落底升后等各种规则。而围棋则没有那么多复杂的规定。所有棋子都是一个模样,对局者将黑白棋子分别放置在19路见方的棋盘的未被占据的交叉点上,直到双方均认定无处可继续落子,然后再根据双方所占据的地盘的大小来决定胜负。国际象棋在开局时,全部棋子都在棋盘上,以后逐渐减少,直到一方的王被对方吃掉为止。而围棋则是从零开始,361个交叉点,处处是战场,有的地方硝烟弥漫,有的地方则风平浪静,有时几处同时燃起战火。国际象棋好比是一场兵来将挡的中世纪战争,围棋则更像是一场烽火连天的世界大战,很多情况下很难说清哪一方领先。在世界专业水平的国际象棋比赛中,如果你丢掉一个兵,棋局的结果在绝大部分情况下便有定论。而在围棋中,也许你在某一局部的战斗中丢盔弃甲、死伤累累,但比赛往往远没有结束,你还可以在别处卷土重来。

对于电脑来说,国际象棋与围棋的种种区别是无法逾越的巨大鸿沟。由于每只棋子移动方式的制约,国际象棋棋手在思考下一步棋时,大约只有35种选择。“深蓝”等电脑会针对这些选择加以分析,考虑对手的回应以及下几个回合可能出现的情况。最好的国际象棋电脑程序可以分析到七、八个回合。这种信息检索方式就好比一棵枝叶繁茂的大树:主干分出35个支干,每个支干再分成35个树杈,每个树杈再分成35个树枝,如此类推。愈是高级的电脑程序所派生的树枝树杈的层次就愈多,最终达到每一片树叶,即可供选择的结果。如果要求电脑能思考到第七回合,即14步棋,便需要有35的14次方(十亿万亿以上)片“树叶”。每多一个回合,树叶的数量就有爆炸性的增长。电脑工程师们使电脑能够合理地“剪枝”,仅使一部分而非全部树叶与主干相连。尽管如此,能够思索七个回合的国际象棋电脑每步棋仍然需要有五百亿到六百亿种选择。

这样的数字已足够惊人,而电脑下围棋则更不可思议。选择之数的庞大繁密使迄今最强大的电脑也无法承受。下第一步棋,361个点的任何一点都是合法的,而第二步棋有360个选择。随着棋局的发展,选择逐渐减少。但一般说来,每落一子平均约有200个选择,而国际象棋仅有35个。也就是说,要国际象棋想两个回合四步棋子,全部棋子在棋盘上的位置变化大约为150万种(35x35x35x35=1,500,625),而围棋则需要16亿(200x200x200x200=1,600,000,000)。在布局阶段数字还要大得多。再多一个回合,数字还会爆增:国际象棋为18亿,围棋为640亿。如果要像“深蓝”一样思考7个回合14步棋,围棋电脑的“树叶”并非国际象棋的35的14次方,而是200的14次方之多。通过“剪枝”,还要剩下一亿亿种选择。那么,一台与“深蓝”同等速度的围棋电脑(即每秒种可分析二亿种可能性)每下一子需要昼夜不停地想上一年半!而这一着冥思苦想一年又半载的棋没准又是一着臭棋。



还远不止如此。即使经过如此这般上天入地的检索,围棋电脑在与人对局时并占不了多大便宜。国际象棋电脑程序在经过大量的信息筛选之后试图找到使其处于最佳位置的那一步棋,所采用的办法是所谓价值评估的相当简单但实用的公式:每个兵的价值为1、马和象为3、车为5、后为9,然后将这一数字再与衡量棋盘上每个位置的强弱的另一数值相乘,从而得出某一棋子在当时的相对值。此外,还要其它一些公式用来决定某些概念的价值量,如王的安全程度百分比以及某一棋子暴露于攻击的百分比等。这些并非一贯正确的教条已经足以使电脑具备相当水平了,使它对棋局的进展有个大致的掌握,再加上电脑里输入了很多一流棋手过去的棋局,下到某一步常可不时问问大师以往都是怎么下的。而围棋则不受那些简单分析的约束。围棋盘上并未像“王”一样的棋子,每颗都是相等的。统计双方吃子的多寡也不能说明什么问题。有时某一着棋便可以沧海桑田,将对方苦心经营的领地化为己有,将对方的大龙变为自己的佐餐;有时又明明看到自己的棋行将被吃,而放下不走,另辟战场。另外,棋谱数据库也无多大作用,由于围棋千变万化,三四十步开外基本就是“you are on your own”的状态了。

围棋棋手们是通过对形状的认识来评估棋局的进展,而对这些形状的认识是无法做出几何分析的。棋手完全依赖自身的经验去感觉哪些形状是好的或坏的。这一对棋形的感觉正是胜负的关键,也是棋手水平高低的关键。棋手不愿意浪费自己的子力去无谓地攻击对方活的形状或试图挽救自己死的形状。有时面临复杂的战斗,棋手很难完全算清;有时又面临多种选择,举棋不定。此时棋手就用棋形整理思路,往往好看的棋形就是更具效率的、不易受到攻击的。下出滞重、丧失变化的棋被称为“俗手”,棋手会觉得下不出手,就完全不予考虑。这样有时就出现有趣的“专业棋手的盲点”:有时一手“愚形”或“凝形”的棋却是此时的最佳选择,业余棋手看得到,专业棋手却想不到。

日本著名棋手大竹英雄号称“美学大师”,对恶形恶状的棋形深恶痛绝,宁可输棋也要把棋下的漂亮,因而比其它日本棋手更为鄙视韩国围棋,说曹熏玄的棋是“农民的棋”。其实棋形的漂亮与否虽然有大致的概念,但也会有不同的观点。有的棋手喜欢轻灵的形状,有的则爱好厚重的形状,也就是所谓棋风的不同。与吴清源共同创造“新布局”的木谷实早期偏爱滴水不漏的坚实。一次在走角部的三三定式时,明明按常规应该“飞”,他却笨笨地“爬”了一手,一边把棋子打在棋盘上,一边嘴里还嘟囔着:“虽然先生看见要骂,还是要这样下!”从此这一定式又有了新的变化,后人称之为“木谷流”。

由此可见,与其说要教给电脑下棋的感觉,不如说要教给它人的感觉,这便是世界科技发展史上人工智能领域最根本的难题。



惠普的佛特兰德先生给他的围棋程序“多面围棋”输入一些围棋的基本概念,如对领地的保护意识及棋子互连的意识,并输入二百多个高层次的战术概念,如“攻击弱棋”、“向处女地进行扩张”、“落后时开始无理侵入”等。“多面围棋”可辨认一千一百多个不同的形状,每一种形状都有一些可行的手数。像“深蓝”一样,“多面围棋”储存了很多常用的开局定式及一些惯用套路。依赖这些储存的知识,“多面围棋”每一步棋仅在五至十种可能性中做出选择,而非理想的二百多种。

给电脑输入一些概念是一回事,而教给它灵活运用这些概念又是另一回事。可接可不接的棋或可断可不断的棋什么时候连接或切断?什么时候又无需连接或切断?什么是可弃之不用的废子?什么又是绝不可放弃的“棋筋”?比起人类对模糊概念的处理以及对经验的灵活运用,电脑今天还是个婴儿。

但围棋电脑的设计师们仍然坚信,让围棋成为世界冠军理论上是成立的。因为既然每一步棋的选择是根据棋盘上的每一个位置的价值来决定的,也就是说围棋从纯粹意义上来讲其实是数学的游戏(我们也常听棋手说这手棋很大、那个见小),所以只要把每一个位置的数学价值准确计算出来,电脑就能成为围棋高手。目前至少在收官阶段(即收尾终局阶段)可以做得到。

能够击败人类的围棋冠军而赢得应昌期围棋基金会悬赏的一百四十万美元的奖金,是个在悠悠岁月中难圆的梦。该悬赏的奖金已于2000年过期了。当年应老先生推广围棋的精神可嘉,但把事情想得太简单了。电脑专家们真希望把悬赏的截止日期推迟一两个世纪。



(本文部分资料取材于纽约时报)
[ 打印 ]
阅读 ()评论 (5)
评论
路边野花不採白不採 回复 悄悄话 回复cohomology的评论:
多谢老兄高见
cohomology 回复 悄悄话 1. 顶你这篇文章
2. 就围棋的迷人程度及复杂性来讲,就像你说的,应该远远高于国际象棋。围棋没有在西方普及,我觉得深处还是他们的文明优越论在作怪。不过这个太有争议了,社科上的问题很难讲清楚,我觉得也讲不清楚。搁下不讲 ^_^.

我觉得概率在布局阶段是有用的。这儿有必要稍微严格的定义一下:例如第一手走那?一般来讲星,小目,为什么只有这几个地方?从数学上讲应该解释成这样: 走在那一步输棋的数学期望最小?现代围棋理论的发展表明应该有这样的关系(当然没有严格证明):走星输棋的数学期望和走星输棋的数学期望非常接近,而这两个数学期望值又明显的小于比如走天元,目外等等的输棋的数学期望值。

在棋盘上图没有形成之前,概率应该是 有用的。这时“只此一手”应该解释为这一手输棋的数学期望最小。 这就是为什么布局阶段很多时候说二间高夹可以,二间低夹也可,取舍看对局者的风格。从数学角度来讲,就是这两种选择输棋的数学期望差不多。

一旦图形成,我觉得,Graph 理论管理局部问题,这时局部的“只此一手”及手筋应该可以从Graph理论当中得出,而概率则管全局问题:如它应该回答这样的问题:应该在哪一个局部下子? 盯在一个局部连续下子是否可以得到全局利益最大化?何时在一个Graph上脱先?
总之Graph管局部,概率管全局。


在人工智能方面,我觉得Godel不完全性定理及P是否等于NP的解决对这一领域的发展具有决定性的影响。当然前提是我们用图灵机来实现人工智能。我觉得这两个结果决定了人工智能的局限性。当然这个局限是从数学基础论的角度来说。现实是人工智能一日千里。但不知你注意到没有,人工智能还主要在所有排列组合中如何高效选择最佳或接近最佳的一种这样的工作。从数学角度来看,还是在可数集范围内(即此集合和自然数集合有一个1-1对应映射). 它能不能在不可数集中选最佳方案,如在和实数集合相等价(即和实数集有一个1-1对应映射的)集合中选?我觉得不行。

一家之言,有错误的地方,付之一笑罢了。
路边野花不採白不採 回复 悄悄话 回复cohomology的评论:

再者,人的智慧是无穷的。谁也想象不到将来甚至五年之后的科技发展,人发明的电脑总会有战胜人自己的那一天。围棋电脑的落后的原因之一还是因为人投入的精力不够。国际象棋在西方更为普及,使有关的电脑程序更先进。而当今西方仍然是围棋沙漠,仅靠中日韩的努力还不够。围棋电脑的推广还有赖于围棋本身在全球的推广。
路边野花不採白不採 回复 悄悄话 回复cohomology的评论:

谢谢这位网友的高见。的确,要电脑围棋有所突破,需要有创新方式。就像人工智能领域的突破点不能拘泥于使机器人更有本领一样。不过我觉得概率对下围棋没什么作用。在布局阶段之后,多数情况下是所谓“只此一手”的绝对选择。
cohomology 回复 悄悄话 要在电脑下围棋方面有所突破,我觉得要在围棋的数学理论方面要有所建树。我觉得现在的Algebraic Graph theory很有意思。也许是一个突破口。另外概率论的采用似乎也是必不可少的,比如用Random Matrices 理论。因为围棋中数目巨大的可能性为概率的应用提供了很好的前提。甚至解析理论的应用也应该是有可能的。因为对一个图,可以assiciate 一个 L-函数 ...... . 专业的东西说的太多了。 总之我觉得并不能局限在排列组合及消减排列组合的数目方面。

登录后才可评论.