打造围棋“深蓝”--2007-08-13 《环球科学》2007年第8期

扎西

打造围棋“深蓝”
2007-08-13    《环球科学》2007年第8期      

撰文/卡伦·A·弗兰克尔（Karlen A Frankel）

    12年前，IBM公司研制的超级计算机“深蓝”（Deep Blue）在6局比赛中击败了国际象棋世界冠军加里·卡斯帕罗夫（Garry Kasparov）。这个里程碑式的事件终结了人类在又一个智力策略游戏上的统治地位。只有亚洲的围棋仿佛是计算机科学的“阿喀琉斯之踵”：人类总是能够轻松击败计算机。但最近出现的一种新的围棋算法，却能战胜高水平的棋手。

   

     围棋的复杂度高，且极具欺骗性，对计算机程序提出了巨大的挑战。围棋的棋盘由两组数量相同、互相正交的平行线构成，分为9线小棋盘与19线大棋盘两种。对弈双方分执黑白两色棋子。通过在棋盘的交叉点上落子，棋手要尽可能扩张自己的领地并包围对方棋子。在大棋盘的对弈中，每一步可采取的策略数量都非常巨大。对局中期，平均每一步能采取200种不同的策略，相比而言，国际象棋中每一步数十种的可选策略就显得微不足道了。此外，还要考虑数量众多的后续策略。由于棋盘上每个位置都对应着三种状态：黑子占据、白子占据和空位，N个位置便可构成3N种不同的状态。如果考虑规则约束，小棋盘大约有1038种不同的状态，大棋盘的状态数量则达到了惊人的10170种。其他一些因素也会影响比赛胜负：棋盘上棋子的数量优势并不能确保胜利，棋手必须在考虑局部形式的同时，兼顾全局。

     为了处理如此众多的可能情况，人工智能专家已经设计出一些算法，来限制搜索的范围，但它们都无法在大棋盘的比赛中战胜实力稍强的人类棋手。去年秋季，两位匈牙利研究人员报告了一种新算法，它的胜率比现有最佳算法提高了5%，能够在小棋盘的比赛中与人类职业棋手抗衡。这种被称为UCT的算法，是匈牙利国家科学院计算机与自动化研究所（位于布达佩斯）的列文特·科奇什（Levente Kocsis）与加拿大阿尔伯塔大学（University of Alberta，位于埃德蒙顿）的乔鲍·塞派什瓦里（Csaba Szepesvári）合作提出的，是著名的蒙特卡罗方法（Monte Carlo method）的扩展应用。

      20世纪70年代，蒙特卡罗方法首次运用于围棋程序，这种方法的作用类似于选举投票：用统计采样的方式，预测大规模群体的表现与特质。围棋程序会随机出招，模拟大量的比赛，对候选走法加以评估并排序。然而，每一步都采用评估值最高的走法，并不能保证获得比赛的胜利。相反，这种方法仅仅是限制了搜索的范围。

      UCT扩展了蒙特卡罗方法，集中关注那些最有希望赢得比赛的走法。科奇什说：“UCT的主要思想是对走法进行选择性采样。”他解释说，这种算法必须达到一种平衡，既要尝试当前的最佳走法，发现其中可能隐藏的昏招，还要搜索“当前并非最佳的走法，以确保不会因为先前的估计错误而错失妙招”。

      UCT为每一种走法计算一个索引值，然后按照索引值最高的走法出招。索引值由采用该走法后最终取胜的概率（即胜率）决定，该走法被计算却未被采用的次数也对索引值有一定的影响。UCT会在内存中维护一棵“决策树”，用来记录每一种走法的统计数据。如果遇到一种先前从未计算过的走法，算法就会将它纳入决策树，并随机出招完成余下的比赛。

      判定随机比赛的胜负后，UCT就会更新比赛中采用过的所有走法的统计数据。如果该走法的索引值等于它的胜率，算法就能快速选定这招最有希望获胜的策略。但开局时走出妙招，仍然无法确保比赛的最终胜利。所以在选择走法时，UCT会增大计算次数少的候选走法的权值，以使胜率的总体分布趋向平坦。

     法国南巴黎大学的数学家西尔万·热利（Sylvain Gelly）与巴黎技术学校的王毅早（Yizao Wang，音译）将UCT集成到一个他们称之为MoGo的程序中。该程序的胜率竟然比先前最先进的蒙特卡罗扩展算法几乎高出了一倍。今年春季，MoGo在小棋盘的比赛中击败了实力强劲的业余棋手，在大棋盘比赛中也击败了实力稍弱的职业棋手，充分展示了能力。热利认为UCT易于实现，并有进一步完善的空间。科奇什预言，10年以后，计算机就能攻克最后的壁垒，终结人类职业棋手对围棋的统治。


（译/陈家乾  校/虞骏）

胡喨涵

从去年《环球科学》中文版发布以来，我每月都抽空看，可是不懂的太多了

Lightalt

0DAY上可以弄到《自然》《科学》等杂志的英文版....
看的更不懂了。。。

laodiao8014

哈哈,幸亏我下围棋,几个围棋乱程序不堪一击,还是上网找网友下好哇!
围棋有361个点,不计打劫来回提子,下法是361!种,这个阶乘太大啦!够电脑折腾一阵子了,我在游艺机上下象棋输过,围棋嘛!别下9*9盘的,81!小了点,估计电脑算得了的.

[ 本帖最后由 laodiao8014 于 2008-5-7 22:08 编辑 ]

refla

围棋中“势”的概念，是很难用数学描述的，故围棋算法一直无突破性进展。我不知道他所说的“职业选手”是否指东北亚的职业选手，是几段选手。如果对东北亚的三段选手能有超过50%的胜率，才有希望10年内终结人类的垄断地位！

fwjmath

穆勒: 计算机围棋的革命性进展
2007.08.28  来自：TOM围棋论坛　     共有评论(0)条 发表评论   [收藏到我的网摘]
老式的围棋程序如Goliath和手谈,编程时注重在围棋知识,而新的方法"monte carlo"和UCT,注重于海量的搜索和随机的下法搜索,而不是确定性的算法

"过去12个月是计算机围棋史上最令人振奋的时刻"计算机科学家马丁.穆勒星期天晚上在满座的欧洲围棋会议的演讲厅里面说.数以百计的围棋手们在EGC周末赛事五轮令人精疲力尽的比赛后留了下来,聆听Alberta大学来的穆勒教授讲述计算机围棋的革命性进展.

快速的回顾了过去50年的计算机围棋研究,穆勒指出,老式的围棋程序如Goliath和手谈,编程时注重在围棋知识,而新的方法"monte carlo"和UCT,注重于海量的搜索和随机的下法搜索,而不是确定性的算法.Gnugo和MoGo是使用这种新方法的主要程序."他们在7X7的棋盘是完美的,在9X9的棋盘上相当于业余3段",穆勒说.恐怕没有一个棋手输棋会像穆勒在06年12月被Gnuno击败时这样高兴.

去年,郭娟职业五段和crazystone程序在7X7的棋盘上进行了一系列的比赛,程序总是取得胜利或者执白的时候和棋.今年,MoGo在9X9的棋盘上对郭娟取得了9胜5负的好成绩."Monte Carlo"总是下出一些奇怪的下法,穆勒对此不无担忧."但是这种算法善于取胜" 这种程序每秒钟进行100,000次仿真或者说1百万步."为什么这种算法如此有效"穆勒问. "还没有理论上的解释,尽管经验性的结果是如此之好" 换句话说,"我们还不知道".

尽管穆勒说,很多研究者现在认为,职业水平的围棋程序出现只是一个时间问题.他觉得可能还有些遥远."我自己的看法是我们还需要一到两个的好点子,但我还不知道这些点子从哪里得到.

Source: http://news.csdn.net/n/20070828/108033.html

fwjmath

这个我觉得主要是搜索算法的改进~~~当然好像“势”这种概念的表达也会使计算机围棋更进一步~~~
做个类比：深蓝能够战胜卡斯帕罗夫，除了搜索方面的好算法（单步延伸等等），还有象棋知识（兵结构、评价函数）。两者都是很重要的~~~