《环球科学》:打造围棋“深蓝”
来自：MACD论坛(bbs.macd.cn)
作者：lyaaa
浏览：5524
回复：3
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
撰文/卡伦·A·弗兰克尔（Karlen A Frankel）
12年前，IBM公司研制的超级计算机“深蓝”（Deep Blue）在6局比赛中击败了国际象棋世界冠军加里·卡斯帕罗夫（Garry Kasparov）。这个里程碑式的事件终结了人类在又一个智力策略游戏上的统治地位。只有亚洲的围棋仿佛是计算机科学的“阿喀琉斯之踵”：人类总是能够轻松击败计算机。但最近出现的一种新的围棋算法，却能战胜高水平的棋手。
围棋的复杂度高，且极具欺骗性，对计算机程序提出了巨大的挑战。围棋的棋盘由两组数量相同、互相正交的平行线构成，分为9线小棋盘与19线大棋盘两种。对弈双方分执黑白两色棋子。通过在棋盘的交叉点上落子，棋手要尽可能扩张自己的领地并包围对方棋子。在大棋盘的对弈中，每一步可采取的策略数量都非常巨大。对局中期，平均每一步能采取200种不同的策略，相比而言，国际象棋中每一步数十种的可选策略就显得微不足道了。此外，还要考虑数量众多的后续策略。由于棋盘上每个位置都对应着三种状态：黑子占据、白子占据和空位，N个位置便可构成3N种不同的状态。如果考虑规则约束，小棋盘大约有1038种不同的状态，大棋盘的状态数量则达到了惊人的10170种。其他一些因素也会影响比赛胜负：棋盘上棋子的数量优势并不能确保胜利，棋手必须在考虑局部形式的同时，兼顾全局。
为了处理如此众多的可能情况，人工智能专家已经设计出一些算法，来限制搜索的范围，但它们都无法在大棋盘的比赛中战胜实力稍强的人类棋手。去年秋季，两位匈牙利研究人员报告了一种新算法，它的胜率比现有最佳算法提高了5%，能够在小棋盘的比赛中与人类职业棋手抗衡。这种被称为UCT(Upper Confidence bounds applied to Trees)的算法，是匈牙利国家科学院计算机与自动化研究所（位于布达佩斯）的列文特·科奇什（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年以后，计算机就能攻克最后的壁垒，终结人类职业棋手对围棋的统治。
（译/陈家乾 校/虞骏）
附录:
蒙特卡罗算法
以概率和统计理论方法为基础的一种计算方法。将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解。为象征性地表明这一方法的概率统计特征，故借用赌城蒙特卡罗命名。又称统计模拟法、随机抽样技术。由S.M.乌拉姆和J.冯·诺伊曼在20世纪40年代为研制核武器而首先提出 。它的基本思想是，为了求解数学、物理、工程技术以及管理等方面的问题 ，首先建立一个概率模型或随机过程，使它们的参数，如概率分布或数学期望等问题的解；然后通过对模型或过程的观察或抽样试验来计算所求参数的统计特征，并用算术平均值作为所求解的近似值。对于随机性问题，有时还可以根据实际物理背景的概率法则，用电子计算机直接进行抽样试验，从而求得问题的解答。
蒙特卡罗方法有很强的适应性，问题的几何形状的复杂性对它的影响不大。该方法的收敛性是指概率意义下的收敛，因此问题维数的增加不会影响它的收敛速度，而且存贮单元也很省，这些是用该方法处理大型复杂问题时的优势。因此，随着电子计算机的发展和科学技术问题的日趋复杂，蒙特卡罗方法的应用也越来越广泛。它不仅较好地解决了多重积分计算、微分方程求解、积分方程求解、特征值计算和非线性方程组求解等高难度和复杂的数学计算问题，而且在统计物理、核物理、真空技术、系统科学 、信息科学 、公用事业、地质、医学，可靠性及计算机科学等广泛的领域都得到成功的应用。
| 
发表于 2008-3-26 19:42
|
陕ICP19026207号—2 陕ICP备20004035号
