论文部分内容阅读
摘要计算机博弈是人工智能的一个重要的研究领域,计算机围棋继国际象棋、中国象棋之后,已成为人工智能研究中一个新的挑战,本文介绍了计算机博弈的基本思想与发展现状。
中图分類号:TP3文献标识码:A
计算机博弈,历来是人工智能的一个重要的研究领域,早期人工智能的研究实践,正是从计算机下棋开始。因为人类开发下棋软件,目的是让计算机模仿人脑进行思维,如果能够掌握下棋的本质,也许就掌握了人类智能行为的核心,那些能够存在于下棋活动中的重大原则,或许就存在于其它任何需要人类智能的活动中。所以说,下棋软件某种意义上可以代表人工智能的发展程度。
从上世纪六十年代的“跳棋机”到1997年的“深蓝”,计算机下棋程序在人机对弈中取得了一个又一个胜利,但是这些程序虽然属于人工智能范畴,实际上它们并没有多少“智”的成分,主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索更快更有效。它们缺乏“智”的成分的根本原因,是我们自己并不清楚人类是以怎样的形式思考的。比如你写一个名字问一名教师,这人是不是他班上的学生。教师马上就可以回答是或不是。如果你问计算机,计算机也可以马上正确地回答是或不是。但计算机的方式是把这个名字与学生名单里所有名字一一比较以后得出的答案。计算机搜索很快,全走一遍几乎可以瞬间完成。但我们知道教师是不可能在短时间内把班上所有学生的名单过一遍的。类似的,我们看到一个人的照片,马上就知道我们以前见没见过这个人,我们不可能在短时间内把我们以前见过的人都检查一遍,那么我们是怎样得出结论的呢?现在我们对此还不是完全清楚。
下棋的时候棋盘上可走的地方很多,但下棋的人并不是每种走法都去考虑。那么哪些位置需要考虑,哪些位置不需要考虑,这就是“模式识别”问题。人脑有“模式识别”功能,可以很快得出一个大致的结论,计算机没有这种功能,只好所有的位置都考虑。在人机博弈中,计算机人工智能的基本思考方法是穷举法,即通过对所有可能的招法的演化结果进行比较,最后选择出一个最好的招法。例如在象棋的某个“局面”中,如果有38种合乎规则的棋子走法,无论选择其中哪一种,都会再生成一个新局面。将所有这些变化列起来,就会形成一棵“博弈树”,计算机要做的,就是比较最后一层结果,选择其中一个最好的,然后逆推,找到本局面下最好的一个走法,计算机的这种思考能力在中局搏杀阶段表现得尤为明显。另外,在人机对弈中,计算机面对每一步棋时,都将会模仿人的思考方法尽可能地简化搜索范围,然后对其进行横向比较并选择最优走法。但是,国际象棋的变化总数达到10的123次方,而中国象棋的变化数量比这还要多得多,可达10的144次方以上,围棋的变化就更多,达10的172次方以上,计算机不可能算出棋盘上的所有变化。因此,所谓的“利用穷举法选择最好的走法”,指的是棋局的局部,并且是在有限的步骤里,而不是通盘穷举,它更没法对整盘棋的形势做正确判断。这就是它中盘计算超强而大局观差的原因。半个世纪以前人们就开始研究国际象棋程序,但因计算机性能问题,在人机对弈中计算机始终表现不佳,因为大空间搜索不可行,就只能用人们设计的判别模式进行选择性地搜索(模仿人的思维)。选择不见得对,搜索又不彻底,结果当然不会好到哪里去。好在计算机的性能发展得很快,到了1997年,IBM的深蓝用“硬搜索”打败了人类国际象棋世界冠军卡斯帕罗夫。当然深蓝还请了一些国际象棋专家指点判别程序,但主要靠的还是硬搜索。
目前,在三大棋类项目中,国际象棋和中国象棋两项,计算机的水平都已经可以跟最顶级的职业棋手抗衡了,但在围棋项目中计算机的水平却始终上不去,目前围棋计算机大赛获得冠军的软件也只勉强达到业余初段水平,和顶级职业棋手相比,大概要被让七子。
为什么计算机围棋的水平和象棋比差这么多呢?除了资金等投入上有差距外,大致还有以下几个原因:
(1)国际象棋盘60格,中国象棋90个交叉点,而围棋则有361个交叉点。象棋一局棋一般三四十个回合七八十步棋,而围棋一盘棋一般要一百多手棋,最多的会超过三百手棋,这使围棋的计算量远远超过象棋,因此对计算机的性能提出了更高的要求,但按照传统的解决问题的思路,目前计算机还不能满足这种要求。
(2)中国象棋和国际象棋的目的比较明确,就是保存子力,保卫老将(王)。而围棋以占地多少决定胜负,厚势与薄味、要子和废子、模样和实地,这些都是判断上的问题,很难在程序中做出界定。
(3)在象棋中,计算占的比重很大,象棋中每个棋子的价值都是可以量化的,例如国际象棋中后相当于三个马或九个兵,在棋局的不同阶段或子力优势时再加上不同的权值,因此计算机可以用准确无误的计算来弥补它判断上的不足。但围棋的计算只是围棋的一部分,尤其是序盘阶段,对全局形势的分析与判断才是重点,由于在棋局进程中,随着周围的棋子布置不同,原有棋子的价值在不断地发生变化,如何判断取舍,这一方面正是计算机的弱点,也无法通过计算来弥补。
计算机围棋的难点之一,是缺乏好的估值函数,使计算机围棋不能如象棋一样,运用好的估值函数、搜寻树及-剪枝法,即可获得不错的棋力,计算机围棋大多依靠一些经验法则,以静态的评估为主,而动态的搜索则仅用于局部的、目标明确的棋串攻杀,全局的搜索较少。因此,人类的经验如何用于计算机围棋,就成了设计的重点。
围棋中一般认为达到业余初段水平才算入门,多年来计算机围棋的水平一直在门外徘徊,直到目前的最新技术,以蒙特卡罗方法为基础的UCT算法出现以后,计算机围棋终于达到了业余初段水平,而且从发展潜力来看还有很大提升空间。
蒙特卡罗是位于摩纳哥的赌城,蒙特卡罗方法(Monte Carlo,缩写为MC)的名称象征性地表明该方法的概率统计的特点,它是把所求解的问题同一定的概率模型相联系,用计算机实现统计模拟或抽样,以获得问题的近似解。MC怎样用于围棋呢?针对某局面下的某一手棋,由计算机模拟后续对局,得到这手棋的获胜概率,把所有可能下法的获胜概率都算出来后,选择获胜概率最大的下法。MC直接用在围棋上的缺点十分突出,首先是浪费了模拟次数,因为在有限的时间内只能模拟出一定的棋局数。其次,它没有考虑对方的下一手,如果我们把MC当作估值函数,那么对比传统的人机博弈程序,简单的MC相当于只搜索了一步。如果估值无比精准的话,那么这一步足矣。实际上围棋还不存在这么精确的估值,以MC的估值速度,往深算几步,耗费的时间无法接受。所以人们对算法进行了改进,首先是根据棋形和基本着法进行智能判定,只对合理的着法作模拟,对明显不合理的招法予以舍弃,其次,对难以判定优劣的多种可选方案,用AMAF算法进行随机选择。
以蒙特卡罗方法为基础的UCT算法,是目前计算机围棋在计算手筋和局部战斗上的最好的算法,在9€?的小棋盘上有过战胜职业棋手的记录,但它也有自己的局限,如果没有新的算法上的突破,很难跳出业余的段位,和职业棋手进行对抗。假如将来有一天,计算机围棋程序战胜了顶级职业棋手,是否说明计算机已经具有智能了呢?我们仍然不能得出这个结论。
参考文献
[1]蒋佑铭.电脑围棋对弈技术的发展趋势.围棋报,2009-10-3,第029版.
[2]Sylvain Gelly,Joanna Jongwane.蒙特卡罗方法在计算机围棋中的应用.程序员,2008(12):84-87.
中图分類号:TP3文献标识码:A
计算机博弈,历来是人工智能的一个重要的研究领域,早期人工智能的研究实践,正是从计算机下棋开始。因为人类开发下棋软件,目的是让计算机模仿人脑进行思维,如果能够掌握下棋的本质,也许就掌握了人类智能行为的核心,那些能够存在于下棋活动中的重大原则,或许就存在于其它任何需要人类智能的活动中。所以说,下棋软件某种意义上可以代表人工智能的发展程度。
从上世纪六十年代的“跳棋机”到1997年的“深蓝”,计算机下棋程序在人机对弈中取得了一个又一个胜利,但是这些程序虽然属于人工智能范畴,实际上它们并没有多少“智”的成分,主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索更快更有效。它们缺乏“智”的成分的根本原因,是我们自己并不清楚人类是以怎样的形式思考的。比如你写一个名字问一名教师,这人是不是他班上的学生。教师马上就可以回答是或不是。如果你问计算机,计算机也可以马上正确地回答是或不是。但计算机的方式是把这个名字与学生名单里所有名字一一比较以后得出的答案。计算机搜索很快,全走一遍几乎可以瞬间完成。但我们知道教师是不可能在短时间内把班上所有学生的名单过一遍的。类似的,我们看到一个人的照片,马上就知道我们以前见没见过这个人,我们不可能在短时间内把我们以前见过的人都检查一遍,那么我们是怎样得出结论的呢?现在我们对此还不是完全清楚。
下棋的时候棋盘上可走的地方很多,但下棋的人并不是每种走法都去考虑。那么哪些位置需要考虑,哪些位置不需要考虑,这就是“模式识别”问题。人脑有“模式识别”功能,可以很快得出一个大致的结论,计算机没有这种功能,只好所有的位置都考虑。在人机博弈中,计算机人工智能的基本思考方法是穷举法,即通过对所有可能的招法的演化结果进行比较,最后选择出一个最好的招法。例如在象棋的某个“局面”中,如果有38种合乎规则的棋子走法,无论选择其中哪一种,都会再生成一个新局面。将所有这些变化列起来,就会形成一棵“博弈树”,计算机要做的,就是比较最后一层结果,选择其中一个最好的,然后逆推,找到本局面下最好的一个走法,计算机的这种思考能力在中局搏杀阶段表现得尤为明显。另外,在人机对弈中,计算机面对每一步棋时,都将会模仿人的思考方法尽可能地简化搜索范围,然后对其进行横向比较并选择最优走法。但是,国际象棋的变化总数达到10的123次方,而中国象棋的变化数量比这还要多得多,可达10的144次方以上,围棋的变化就更多,达10的172次方以上,计算机不可能算出棋盘上的所有变化。因此,所谓的“利用穷举法选择最好的走法”,指的是棋局的局部,并且是在有限的步骤里,而不是通盘穷举,它更没法对整盘棋的形势做正确判断。这就是它中盘计算超强而大局观差的原因。半个世纪以前人们就开始研究国际象棋程序,但因计算机性能问题,在人机对弈中计算机始终表现不佳,因为大空间搜索不可行,就只能用人们设计的判别模式进行选择性地搜索(模仿人的思维)。选择不见得对,搜索又不彻底,结果当然不会好到哪里去。好在计算机的性能发展得很快,到了1997年,IBM的深蓝用“硬搜索”打败了人类国际象棋世界冠军卡斯帕罗夫。当然深蓝还请了一些国际象棋专家指点判别程序,但主要靠的还是硬搜索。
目前,在三大棋类项目中,国际象棋和中国象棋两项,计算机的水平都已经可以跟最顶级的职业棋手抗衡了,但在围棋项目中计算机的水平却始终上不去,目前围棋计算机大赛获得冠军的软件也只勉强达到业余初段水平,和顶级职业棋手相比,大概要被让七子。
为什么计算机围棋的水平和象棋比差这么多呢?除了资金等投入上有差距外,大致还有以下几个原因:
(1)国际象棋盘60格,中国象棋90个交叉点,而围棋则有361个交叉点。象棋一局棋一般三四十个回合七八十步棋,而围棋一盘棋一般要一百多手棋,最多的会超过三百手棋,这使围棋的计算量远远超过象棋,因此对计算机的性能提出了更高的要求,但按照传统的解决问题的思路,目前计算机还不能满足这种要求。
(2)中国象棋和国际象棋的目的比较明确,就是保存子力,保卫老将(王)。而围棋以占地多少决定胜负,厚势与薄味、要子和废子、模样和实地,这些都是判断上的问题,很难在程序中做出界定。
(3)在象棋中,计算占的比重很大,象棋中每个棋子的价值都是可以量化的,例如国际象棋中后相当于三个马或九个兵,在棋局的不同阶段或子力优势时再加上不同的权值,因此计算机可以用准确无误的计算来弥补它判断上的不足。但围棋的计算只是围棋的一部分,尤其是序盘阶段,对全局形势的分析与判断才是重点,由于在棋局进程中,随着周围的棋子布置不同,原有棋子的价值在不断地发生变化,如何判断取舍,这一方面正是计算机的弱点,也无法通过计算来弥补。
计算机围棋的难点之一,是缺乏好的估值函数,使计算机围棋不能如象棋一样,运用好的估值函数、搜寻树及-剪枝法,即可获得不错的棋力,计算机围棋大多依靠一些经验法则,以静态的评估为主,而动态的搜索则仅用于局部的、目标明确的棋串攻杀,全局的搜索较少。因此,人类的经验如何用于计算机围棋,就成了设计的重点。
围棋中一般认为达到业余初段水平才算入门,多年来计算机围棋的水平一直在门外徘徊,直到目前的最新技术,以蒙特卡罗方法为基础的UCT算法出现以后,计算机围棋终于达到了业余初段水平,而且从发展潜力来看还有很大提升空间。
蒙特卡罗是位于摩纳哥的赌城,蒙特卡罗方法(Monte Carlo,缩写为MC)的名称象征性地表明该方法的概率统计的特点,它是把所求解的问题同一定的概率模型相联系,用计算机实现统计模拟或抽样,以获得问题的近似解。MC怎样用于围棋呢?针对某局面下的某一手棋,由计算机模拟后续对局,得到这手棋的获胜概率,把所有可能下法的获胜概率都算出来后,选择获胜概率最大的下法。MC直接用在围棋上的缺点十分突出,首先是浪费了模拟次数,因为在有限的时间内只能模拟出一定的棋局数。其次,它没有考虑对方的下一手,如果我们把MC当作估值函数,那么对比传统的人机博弈程序,简单的MC相当于只搜索了一步。如果估值无比精准的话,那么这一步足矣。实际上围棋还不存在这么精确的估值,以MC的估值速度,往深算几步,耗费的时间无法接受。所以人们对算法进行了改进,首先是根据棋形和基本着法进行智能判定,只对合理的着法作模拟,对明显不合理的招法予以舍弃,其次,对难以判定优劣的多种可选方案,用AMAF算法进行随机选择。
以蒙特卡罗方法为基础的UCT算法,是目前计算机围棋在计算手筋和局部战斗上的最好的算法,在9€?的小棋盘上有过战胜职业棋手的记录,但它也有自己的局限,如果没有新的算法上的突破,很难跳出业余的段位,和职业棋手进行对抗。假如将来有一天,计算机围棋程序战胜了顶级职业棋手,是否说明计算机已经具有智能了呢?我们仍然不能得出这个结论。
参考文献
[1]蒋佑铭.电脑围棋对弈技术的发展趋势.围棋报,2009-10-3,第029版.
[2]Sylvain Gelly,Joanna Jongwane.蒙特卡罗方法在计算机围棋中的应用.程序员,2008(12):84-87.