正在进行安全检测...
发布时间:2023-11-05 07:05:23 来源:文档文库
小
中
大
字号:
龙源期刊网http://www.qikan.com.cn浅谈围棋机器博弈作者:高梦萱来源:《中国科技纵横》2018年第19期摘要:本文首先阐述了计算机博弈的概念与历史,讨论了难度最高的围棋机器博弈并比较了不同项目间复杂度;随后从历史发展的角度介绍了围棋机器博弈在各个阶段的发展情况以及取得的成就;之后分析了围棋机器博弈当前面临的问题并给出建议,最后论述了围棋机器博弈未来可能的发展方向。关键词:机器博弈;围棋;发展中图分类号:TP18文献标识码:A文章编号:1671-2064(2018)19-0247-02相信很多人都还记得十年前那场人机对战—IBM公司研发的计算机“深蓝”对战国际象棋特级大师卡斯帕罗夫,最终,卡斯帕罗夫以2.5:3.5(1胜2负3平)输给了“深蓝”,震惊了世界,同时也让人们对机器博弈有了更深的认识。从上世纪五十年代开始,许多著名计算机科学家如阿兰·图灵(AlanTuring),信息论创始人科劳德·香农(ClaudeE.Shannon),人工智能(ArtificialIntelligence,AI)的创始人麦卡锡(JohnMcCarthy)以及冯·诺依曼等都在进行机器博弈相关的研究。计算机博弈也称机器博弈(ComputerGames),最早是由从事计算机棋牌竞技研究的科学家们给出了定义,他们认为ComputerGames就是让计算机能够像人一样会思考和决策,能够下棋[1]。ComputerGames直译为计算机游戏,为了便于和计算机游戏区分,ComputerGames中文译为机器博弈,或者计算机博弈。机器博弈属于人工智能领域的一个重要分支,机器博弈的水平在一定程度上也代表了人工智能的发展水平。在机器博弈中,围棋被公认为难度最大,但随着计算机技术的快速发展,人工智能在围棋机器博弈领域也取得了骄人的成绩。2016年3月,由谷歌DeepMind团队研发的AlphaGo与韩国围棋世界冠军、职业九段棋手李世石进行了比拼,被称为围棋人机大战,最终AlphaGo以4比1的总比分获胜;2017年5月,在中国乌镇围棋峰会上,它与排名世界第一的世界围棋冠军柯洁对战,以3比0的总比分获胜[2]。AlphaGo围棋的胜利打破了人们长久以来认为只有人类擅长下围棋的看法,此前,研究人员普遍认为具备思考能力的人工智能还需要数十年才会出现。本文将对围棋机器博弈的基本概念、发展历史、现状等内容进行详细论述,以期让人们对围棋机器博弈有一个全面、深入的认识。1围棋机器博弈概述围棋机器博弈是机器博弈中的重要组成部分。它之所以被认为是棋类机器博弈中最为复杂的项目,根本原因就在于所研究对象围棋的搜索空间远大于国际象棋等其它棋种。博弈问题中衡量问题的复杂性主要根据状态空间复杂度和博弈树复杂度两项指标,博弈过程的局面称为状
龙源期刊网http://www.qikan.com.cn态,而博弈问题的状态复杂度是指从初始局面出发,产生的所有合法局面的总和。对于完备信息的博弈系统如围棋、国际象棋等,其搜索还通常基于博弈树搜索算法。博弈树复杂度是指从初始局面开始,其得到理论解所需展开的最小搜索树的所有叶子节点的总和。表1给出了部分棋类博弈问题的复杂度,可以看出,对于局面复杂、形式变幻多样的围棋来说,无论是状态复杂度还是博弈树复杂度都远高于其它棋种,因此,精确计算围棋博弈的状态复杂度几乎是不可能的。围棋博弈的难度主要体现在两方面:一是搜索空间巨大—合法的围棋的变化(10172)大于宇宙中原子数(1080);二是局面判断难—从此前各种研究成果中看来,对于围棋不可能有一个很好的静态局面评估函数[1,3]。围棋机器博弈是一个高复杂度的完备信息博弈问题,求出围棋的均衡策略基本是不可能的,另一方面,正是围棋机器博弈研究的高难度与复杂性吸引着众多人工智能研究的许多科研机构和科学家。2围棋机器博弈的发展历程2.1第一代圍棋人工智能历史上第一个完整下完一盘围棋的程序是1968年在美国完成的,由此开启了近20年人们对于围棋AI的探索。一直到1990年,中山大学化学系教授陈志行编写出了名为“手谈”的程序,在问世以后实力快速提升,不断用实力获取回报,甚至于1995至1998年赢得计算机围棋世锦赛七连冠,一度成为九十年代的神话。“手谈”的成功,与其中前所未有的“势力函数”的应用有着密切的关系。“势力”在围棋中代表一个棋子对周围空间的影响,将这种影响量化便得到了作为标准的“势力函数”。同时,这种函数还能够初步解决棋的走向问题,也就是得出了围棋中最高深玄妙的“下法”。这在当时无疑是一次突破,也为后来围棋人工智能的持续发展打下了坚实的基础。同时期的围棋AI还有陈克训的GoIntellect,在1992及1994年两度夺得应氏杯,雷秀瑜的Wulu,DavidFotland的MFG也曾问鼎应氏杯,由此,围棋AI进入到繁荣阶段[4,5]。2.2第二代围棋人工智能在此之后,围棋人工智能不断发展,衍生出各种更加完备的算法,例如用评分判定下法对于自己利弊的极小化极大搜索算法以及以概率统计理论为指导用于判断棋局结果的蒙特卡洛算法。这两种算法相较于先前的程序,更加充分地利用了电脑的计算能力,并且能够很好地支持并行计算,提升了工作效率,但同时也存在缺少前后逻辑关联等问题。在诞生于这个时代的围棋人工智能里,最成功的叫做Zen,也被称作天顶围棋。ZEN是由日本的加藤英树教授及其团队开发的,是集成各种算法应用的一次突破。在2011