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

apex

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年以后，计算机就能攻克最后的壁垒，终结人类职业棋手对围棋的统治。