第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 机器博弈研究面临的各种挑战 徐心和,邓志立,王骄,徐长明,刘纪红,马宗民 (东北大学信息学院,辽宁沈阳110004) 摘要:让计算机学会下棋打牌,尤其和人类的精英对决,这是机器博弈领域长期的奋斗目标,也是人工智能学科极 富挑战性的研究课题.为能在这一新兴的研究领域取得更快更多突破性进展,有力发挥机器博弈的“果蝇作用,有 必要很好地明确机器博奔研究当前面临哪些挑战性问题.从学术观念、实战博弈、理论发展、军事应用、国际接轨、普 及提高及学生创新性培养等多角度阐述当前在机器博弈领域急需解决的主要问题,以期有更多的青年学者能够投 身到这一极富挑战性的研究领域. 关键词:机器博弈;人工智能;博弈论;事件对策;兵棋推演;果蝇 中图分类号:1P18文献标识码:A文章编号:16734785(2008)04-0288-06 Challengng issues facng com puter game research XU Xin-he,DENG Zhi-li,WANG Jiao,XU Changm ing,LIU Ji-hong,MA Zongm in (Istitute of Infomation Science and Engineering.Northeastem University,Shenyang 110004,China) Abstract:A long-tem goal of computer game programmers is to make computers able to play board and card games well enough to challenge Super Master p layers In order to speed up the development of new domains of research that could yield breakthrough results,it is necessary to understand what is holding back computer game research This paper describes key problems in the areas of academ ic concepts,actual games,theoretical developments,mil- itary applications,intemational competitions,cultivation of the creativity of students and so on,all ofwhich must to be quickly solved in order to get more results in this challenging and mportant field Keywords:computer game;artificial intelligence;game theory,event game theory,war gam ing drosophila Computer game(CG)的中文内容十分丰富.计理I,信息论的创始人香浓(C E Shannon))教授,又 算机游戏,这是最为直白的翻译,也是当今最为流行 给出了极大极小算法),著名的计算机学家阿兰·图 和普及的软件成果,同时也是发展前景远大的软件 灵(A.Turing)也曾做过机器博奔的研究).伴随着计 产业.计算机游戏可以称为CG的广义翻译.在计 算机硬件的飞速发展,āB剪枝算法的提出、极小 算机出现之初,人们提出“computer game就是让计 树的证明)、负极大值算法的给出1与迭代深化思想 算机下棋,如国际跳棋、国际象棋,设法学习人的思 的实现6],都使得机器博弈有了长足进展.以BM深 维模式,努力让计算机具备人一样的博弈能力,对于 蓝为代表的划时代成果,表明计算机的弈棋能力己 这种狭义的理解,在中文中便翻译为机器博弈. 经可以和人类精英较量.如今,机器博弈已经成为一 本文便是从狭义的角度探讨问题. 个独立而重要,颇有发展前途的学术研究领域,但是 机器博弈是人工智能学科和计算机学科的研究 它在中国的发展还很落后 方向之一.自从计算机诞生以来,许多著名学者都曾 可喜的是,机器博弈在中国已经起步,并初具规 经涉足这一领域的研究工作.计算机之父冯·诺依曼 模.象棋、围棋与六子棋等棋类开发队伍在不断壮 (Von Meunann)就提出了用于博弈的极大极小定 大,国内外的比赛也引起了社会的关注.但是人们经 常关注的问题还是参加哪个比赛项目,能不能拿到 收稿日期:2008-01-08 基金项目:因家自然科学基金资助项目(60774097). 奖牌,计算机又能挑战哪一级的棋手,人们看到的也 通信作者:徐心和.Emai让uxinhe@gmail com. 常常是失败和胜利,却不太注意机器博弈自身还有 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 机器博弈研究面临的各种挑战 徐心和 ,邓志立 ,王 骄 ,徐长明 ,刘纪红 ,马宗民 (东北大学 信息学院 ,辽宁 沈阳 110004) 摘 要 :让计算机学会下棋打牌 ,尤其和人类的精英对决 ,这是机器博弈领域长期的奋斗目标 ,也是人工智能学科极 富挑战性的研究课题. 为能在这一新兴的研究领域取得更快更多突破性进展 ,有力发挥机器博弈的“果蝇 ”作用 ,有 必要很好地明确机器博弈研究当前面临哪些挑战性问题. 从学术观念、实战博弈、理论发展、军事应用、国际接轨、普 及提高及学生创新性培养等多角度阐述当前在机器博弈领域急需解决的主要问题 ,以期有更多的青年学者能够投 身到这一极富挑战性的研究领域. 关键词 :机器博弈 ;人工智能 ;博弈论 ;事件对策 ;兵棋推演 ;果蝇 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0420288206 Challenging issues fac ing computer game research XU Xin2he, DENG Zhi2li, WANG Jiao, XU Chang2m ing, L IU Ji2hong, MA Zong2m in ( Institute of Information Science and Engineering,Northeastern University, Shenyang 110004, China) Abstract: A long2term goal of computer game p rogrammers is to make computers able to p lay board and card games well enough to challenge SuperMaster p layers. In order to speed up the development of new domains of research that could yield breakthrough results, it is necessary to understand what is holding back computer game research. This paper describes key p roblem s in the areas of academ ic concep ts, actual games, theoretical developments, m il2 itary app lications, international competitions, cultivation of the creativity of students and so on, all ofwhich must to be quickly solved in order to get more results in this challenging and important field. Keywords: computer game; artificial intelligence; game theory; event game theory; war gam ing; drosophila 收稿日期 : 2008201208. 基金项目 :国家自然科学基金资助项目 (60774097). 通信作者 :徐心和. E2mail: xuxinhe@gmail. com. Computer game (CG)的中文内容十分丰富. 计 算机游戏 ,这是最为直白的翻译 ,也是当今最为流行 和普及的软件成果 ,同时也是发展前景远大的软件 产业. 计算机游戏可以称为 CG的“广义 ”翻译. 在计 算机出现之初 ,人们提出“computer game”就是让计 算机下棋 ,如国际跳棋、国际象棋 ,设法学习人的思 维模式 ,努力让计算机具备人一样的博弈能力. 对于 这种“狭义 ”的理解 ,在中文中便翻译为机器博弈. 本文便是从“狭义 ”的角度探讨问题. 机器博弈是人工智能学科和计算机学科的研究 方向之一. 自从计算机诞生以来 ,许多著名学者都曾 经涉足这一领域的研究工作. 计算机之父冯 ·诺依曼 (Von Meunann)就提出了用于博弈的极大极小定 理 [ 1 ] ,信息论的创始人香浓 (C. E. Shannon)教授 ,又 给出了极大极小算法 [ 2 ] ,著名的计算机学家阿兰 ·图 灵 (A. Turing)也曾做过机器博弈的研究 [ 3 ] . 伴随着计 算机硬件的飞速发展 , α2β剪枝算法的提出 [ 4 ]、极小 树的证明 [ 5 ]、负极大值算法的给出 [ 5 ]与迭代深化思想 的实现 [ 6 ] ,都使得机器博弈有了长足进展. 以 IBM“深 蓝 ”为代表的划时代成果 ,表明计算机的弈棋能力已 经可以和人类精英较量. 如今 ,机器博弈已经成为一 个独立而重要 ,颇有发展前途的学术研究领域 ,但是 它在中国的发展还很落后. 可喜的是 ,机器博弈在中国已经起步 ,并初具规 模. 象棋、围棋与六子棋等棋类开发队伍在不断壮 大 ,国内外的比赛也引起了社会的关注. 但是人们经 常关注的问题还是参加哪个比赛项目 ,能不能拿到 奖牌 ,计算机又能挑战哪一级的棋手 ,人们看到的也 常常是失败和胜利 ,却不太注意机器博弈自身还有 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第4期 徐心和,等:机器博弈研究面临的各种挑战 ·289· 许多更深的内涵,还面临多方面的严峻挑战 2计算机棋类博弈分析 于是机器博弈通常只被看作是一种科技活动, 而常常被学术界所忽视,也正是由于缺少学术研究 尽管目前有的棋类的计算机水平己经高出了人 的有力支持,才使得这一方向的发展比较缓慢,尤其 类大师,如国际象棋,但是计算机间的较量仍然持续 是在中国内陆.机器博弈作为计算机学科的一个分 不断,各种人机大战也接二连三.因为计算机的智能 支,在吸收其他学科的成果方面明显不足,如对策 也需要不断地提高.而那些水平还不高的计算机博 论、系统论与控制论等方面.作为人工智能学科的 弈项目,如中国象棋、日本将棋和围棋,更是倍受人 “果蝇”,机器博弈由于缺少计算机学科的有力支 们的青睐。 持,其研究成果也只能作为初级的游戏产品.本文则 计算机棋类博弈基本属于完全信息的动态博 是要剖析机器博弈中的学科问题和科学技术问题, 弈,也就是对弈双方不仅清楚当前的局面,了解对手 从学术观念的分歧、棋类和牌类的实战博弈机器博 以往的着数,而且了解对手接下来可能采取的着数. 弈和博弈论的关系、机器博弈的军事应用、如何发挥 尽管双方可能采取的着法数以十计、百计,但毕竞还 机器博弈的“果蝇功能、如何与国际接轨以及如何 是有限的.计算机可以通过展开一颗根在上、叶在下 普及提高及培养学生创新性等角度阐述当前在机 的庞大的博弈树描述这一对弈过程,再利用自身在 器博弈领域急需解决的问题,以期引起有识之士的 时间和空间上的强大能力,进行巧妙的搜索,从而找 关注,动员更多的青年学者能够投身到这一研究领 到可行解及近优解,即给出当前的着法 域,让机器博弈在人工智能学科显现巨大的威力. 显然,计算机的搜索能力是计算机智力水平的 重要体现.其实,人类在求解各种问题的时候,解析 1学术观念的分歧 求解还是次要的.人们大量采用的方法和人类智能 机器博弈在中国大陆没有受到应有关注的原因 的体现,主要也是在头脑里搜索.脑袋转的快、主意 比较复杂.其中重要的一点便是它属于游戏“的范 多,智商就高 畴,好像只能是软件开发商经营的业务,而不是高等 机器博弈软件的设计,首先遇到的难题便是数 院校与研究院所涉足的领地.人们一般认为,没有多 据结构的选择,其中包括棋盘、棋子、棋局和着法的 大的学问,导致在人工智能这一重要的研究方向上 编码与存储.良好的数据结构可以节省大量的存储 与国外拉开了很大的距离 空间,可以提高存取的效率.为了适应博弈树的展开 对比之下,让机器人踢足球,名为游戏,实为小 与搜索,常常还要同时给出棋局的多种数据格式,如 型高科技对抗平台.如果能让双足机器人跳起来,就 棋局状态、棋子位置、比特棋局、比特向量、哈希变换 是很大的成就了.其实许多基础性的研究工作就是 和哈希表等 应该从这些简单的问题和典型的范例入手,这样 棋局的静态评估是机器博弈的另一个难点,它 不仅需要棋类对弈的基本知识,而且用到直接量化、 的成果才能有很强的泛化能力 机器博弈丰富的学术内涵与理论价值在后面还 模式量化、随机评估与模糊评估等一系列手段.对于 象棋可以给每个棋子和棋位打分,而对于围棋则要 要阐述,而机器博弈的实现难度却是毋庸置疑的.下 进行定式的抽取和模式的匹配.棋类博弈的高手主 棋是硬碰硬的较量,行就是行,不行就是不行,非常 要在这方面提供更多的专业知识, 实际,来不得什么假设和宽容,因此,机器博弈是对 搜索算法是机器“思维"”的核心,包括着法生 学术、技术和能力的综合考验 成、博弈树展开、各种剪枝搜索和各种启发式搜索 应该看到在国际上非常重视这一领域的研究成 现有的成果非常丰富,也是今后研究工作的重点 果.在《科学》杂志评出的2007年的十大科学突破 编程语言、程序设计方法、软件工程与并行计算 中,第10项便是编制出挑战人类智力的电脑游戏程 等都是算法实现的重要技术,需要和博弈原理有机 序,充分肯定了加拿大科学家经过18年的不懈努 结合,才能编写出高水平的博弈软件1 力,终于完成了一个精心编写的人工智能程序,使西 洋跳棋成为至今为止使计算机彻底掌握了制胜诀窍 3计算机牌类博弈分析 的电脑程序1 众所周知,棋类游戏和牌类游戏有很大不同.棋 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
许多更深的内涵 ,还面临多方面的严峻挑战. 于是机器博弈通常只被看作是一种科技活动 , 而常常被学术界所忽视 ,也正是由于缺少学术研究 的有力支持 ,才使得这一方向的发展比较缓慢 ,尤其 是在中国内陆. 机器博弈作为计算机学科的一个分 支 ,在吸收其他学科的成果方面明显不足 ,如对策 论、系统论与控制论等方面. 作为人工智能学科的 “果蝇 ”,机器博弈由于缺少计算机学科的有力支 持 ,其研究成果也只能作为初级的游戏产品. 本文则 是要剖析机器博弈中的学科问题和科学技术问题 , 从学术观念的分歧、棋类和牌类的实战博弈、机器博 弈和博弈论的关系、机器博弈的军事应用、如何发挥 机器博弈的“果蝇 ”功能、如何与国际接轨以及如何 普及、提高及培养学生创新性等角度阐述当前在机 器博弈领域急需解决的问题 ,以期引起有识之士的 关注 ,动员更多的青年学者能够投身到这一研究领 域 ,让机器博弈在人工智能学科显现巨大的威力. 1 学术观念的分歧 机器博弈在中国大陆没有受到应有关注的原因 比较复杂. 其中重要的一点便是它属于“游戏“的范 畴 ,好像只能是软件开发商经营的业务 ,而不是高等 院校与研究院所涉足的领地. 人们一般认为 ,没有多 大的学问 ,导致在人工智能这一重要的研究方向上 与国外拉开了很大的距离. 对比之下 ,让机器人踢足球 ,名为游戏 ,实为小 型高科技对抗平台. 如果能让双足机器人跳起来 ,就 是很大的成就了. 其实许多基础性的研究工作就是 应该从这些“简单 ”的问题和典型的范例入手 ,这样 的成果才能有很强的泛化能力. 机器博弈丰富的学术内涵与理论价值在后面还 要阐述 ,而机器博弈的实现难度却是毋庸置疑的. 下 棋是硬碰硬的较量 ,行就是行 ,不行就是不行 ,非常 实际 ,来不得什么假设和宽容 ,因此 ,机器博弈是对 学术、技术和能力的综合考验. 应该看到在国际上非常重视这一领域的研究成 果. 在《科学 》杂志评出的 2007年的十大科学突破 中 ,第 10项便是编制出挑战人类智力的电脑游戏程 序 ,充分肯定了加拿大科学家经过 18年的不懈努 力 ,终于完成了一个精心编写的人工智能程序 ,使西 洋跳棋成为至今为止使计算机彻底掌握了制胜诀窍 的电脑程序 [ 7 ] . 2 计算机棋类博弈分析 尽管目前有的棋类的计算机水平已经高出了人 类大师 ,如国际象棋 ,但是计算机间的较量仍然持续 不断 ,各种人机大战也接二连三. 因为计算机的智能 也需要不断地提高. 而那些水平还不高的计算机博 弈项目 ,如中国象棋、日本将棋和围棋 ,更是倍受人 们的青睐. 计算机棋类博弈基本属于完全信息的动态博 弈 ,也就是对弈双方不仅清楚当前的局面 ,了解对手 以往的着数 ,而且了解对手接下来可能采取的着数. 尽管双方可能采取的着法数以十计、百计 ,但毕竟还 是有限的. 计算机可以通过展开一颗根在上、叶在下 的庞大的博弈树描述这一对弈过程 ,再利用自身在 时间和空间上的强大能力 ,进行巧妙的搜索 ,从而找 到可行解及近优解 ,即给出当前的着法. 显然 ,计算机的搜索能力是计算机智力水平的 重要体现. 其实 ,人类在求解各种问题的时候 ,解析 求解还是次要的. 人们大量采用的方法和人类智能 的体现 ,主要也是在头脑里搜索. 脑袋转的快、主意 多 ,智商就高. 机器博弈软件的设计 ,首先遇到的难题便是数 据结构的选择 ,其中包括棋盘、棋子、棋局和着法的 编码与存储. 良好的数据结构可以节省大量的存储 空间 ,可以提高存取的效率. 为了适应博弈树的展开 与搜索 ,常常还要同时给出棋局的多种数据格式 ,如 棋局状态、棋子位置、比特棋局、比特向量、哈希变换 和哈希表等. 棋局的静态评估是机器博弈的另一个难点 ,它 不仅需要棋类对弈的基本知识 ,而且用到直接量化、 模式量化、随机评估与模糊评估等一系列手段. 对于 象棋可以给每个棋子和棋位打分 ,而对于围棋则要 进行定式的抽取和模式的匹配. 棋类博弈的高手主 要在这方面提供更多的专业知识. 搜索算法是机器“思维 ”的核心 ,包括着法生 成、博弈树展开、各种剪枝搜索和各种启发式搜索. 现有的成果非常丰富 ,也是今后研究工作的重点. 编程语言、程序设计方法、软件工程与并行计算 等都是算法实现的重要技术 ,需要和博弈原理有机 结合 ,才能编写出高水平的博弈软件 [ 8 ] . 3 计算机牌类博弈分析 众所周知 ,棋类游戏和牌类游戏有很大不同. 棋 第 4期 徐心和 ,等 :机器博弈研究面临的各种挑战 · 982 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·290· 智能系统学报 第3卷 类游戏属于完备信息博弈,游戏双方清楚知道当前 畴,是运筹学的一个分支.相关理论都是通过解析的 对弈的所有情况,包括自己有多少子力,对手有多少 办法对问题进行求解.根据特定问题的类型,如囚徒 子力,可能有哪些着法,通过构造博弈树,利用计算 困境、智猪博弈、海边摊位与性别战等建立相应的数 机非凡的计算能力和巧妙的搜索算法,就容易看到 学模型,一般以双值矩阵给出收益函数.由于博弈双 若干步以后的局面,从而选出近乎高手的着法;但是 方都是“理性的”,都能够解算出对于自己最为有利的 对于牌类博弈来说,存在太多的不完备信息和不确 解策略、行动),双方能够取得“一致预测”,于是便 定性因素.牌类游戏的多数重要信息都是隐藏的,每 存在了双方都不愿意破坏的纳什均衡”理性共 个玩家只能看到其中的一部分,他们必须通过观察 识一均衡便成为博奔论处理问题的基本模式【] 其他玩家的行为,把各种信息拼在一起,才能获得更 对于一大批经济学中的完全信息的静态博弈问 多信息.因为比赛的这种不确定性,必将导致近于无 题,纳什均衡被证明是有效的.对于不完全信息的静 穷种态势的可能,另外牌类比赛在很多情况下并没 态博弈问题和完全不完全)信息的动态博弈问题 有所谓的“最佳着法”,因此牌类博弈树型的建模方 也都存在贝叶斯均衡或子博弈精炼纳什(贝叶斯) 法对于牌类机器博弈并不适用 均衡.应用上述理论,一系列经济学问题得到了很好 以扑克为例,顶级的扑克选手会在比赛中察言观 的解决.于是博弈论已经成为现代经济学的重要组 色,并根据对手的反应调整自己的策略.但是计算机 成部分 不可能做到这一点,它们只会按照一定的程序出牌」 棋类游戏都属于动态博弈问题.由于一场对弈的 虽然计算机无法像人那样去观察对手的一举一动从 回合都要数以十计,每个回合各方的策略选择也都数 而做出判断,但它却能记录下对手的比赛套路和方 以十计,在如此庞大的博弈树中,即使只考虑有限的 法,通过统计其出牌和不出牌的次数为比赛积累经 几个回合,理性的博弈者也难建立起“一致预测并取 验.显然,尽早绘制出对手比赛套路是取胜的关键 得共识,更何况事实存在的理性和信息的不对称性 因此,牌类博弈的关键技术在于统计建模、模式 于是,有理由对纳什均衡的普遍性提出怀疑 识别和机器学习.既要以大量高手的出牌规律作为 显然,博奔论的解析方法无法求解棋牌游戏问 基础知识,又要及时绘制当前对手比赛的套路. 题,而机器博弈的成果又在棋类游戏中取得令人瞩 显然这不是一般简单智能所能处理的事务 目的成就.就使人联想起数学分析和数值分析的相 值得提及的是,在机器博弈方面世界领先的加 互关系.以复杂函数的积分问题为例.用数学分析的 拿大艾伯塔大学(University of A lberta)设计的扑克 方法大多数函数是给不出积分的解析解的,但是应 程序在与知名扑克玩家菲尔·拉克的对弈中虽然未 用数值分析的方法,就很少找到不能求出积分值的 能取胜,但对手也不得不承认,和电脑的比赛比他职 函数来.因此可以说,博弈论像数学分析一样是用解 业生涯中此前任何一场都要绞尽脑汁,“电脑现在 析方法求解问题,而机器博弈却像数值分析一样是 就如此先进,未来将越来越难战胜州] 以计算机为手段的、用数值方法求解问题.两者相辅 相成,必然在博弈问题的分析与求解上开拓出广阔 4机器博弈的理论提升对于博 的天地 弈论的挑战 事件对策论便是根据博弈论的框架,从离散事 件动态系统的角度为机器博弈建立起的形式化描 通过以上的分析,不难看出机器博弈是一类实 述],而事件对策问题的求解则必然依靠机器博弈 践性很强的计算机应用技术的综合.如果在理论上 的方式1,因此建立机器博弈学,开展事件对策论、 加以提升,机器博弈应该具有什么样的理论体系呢? 机器博弈原理与方法学的研究都是很有意义的研究 机器博弈既然属于博弈的范畴,必然应该和博 方向 弈论具有一些内在的联系.博弈论(game theory)又 现实生活中的动态博弈问题都是非常复杂的 称对策论、游戏论,其概念的引出曾提及象棋的博 既有时间驱动的连续对策问题,又包含由事件驱动 弈,然而纵观博弈论的理论成果,却没有方法能够真 的离散对策问题.这种混杂对策问题的求解必然呼 正用到象棋博弈之中 唤能够将微分对策论与事件对策论有机结合起来的 以纳什均衡为代表的博奔论应该属于数学的范 混杂对策理论的创立4 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.hup://www.cnki.net
类游戏属于完备信息博弈 ,游戏双方清楚知道当前 对弈的所有情况 ,包括自己有多少子力 ,对手有多少 子力 ,可能有哪些着法 ,通过构造博弈树 ,利用计算 机非凡的计算能力和巧妙的搜索算法 ,就容易看到 若干步以后的局面 ,从而选出近乎高手的着法 ;但是 对于牌类博弈来说 ,存在太多的不完备信息和不确 定性因素. 牌类游戏的多数重要信息都是隐藏的 ,每 个玩家只能看到其中的一部分 ,他们必须通过观察 其他玩家的行为 ,把各种信息拼在一起 ,才能获得更 多信息. 因为比赛的这种不确定性 ,必将导致近于无 穷种态势的可能 ,另外牌类比赛在很多情况下并没 有所谓的“最佳着法 ”,因此牌类博弈树型的建模方 法对于牌类机器博弈并不适用. 以扑克为例 ,顶级的扑克选手会在比赛中察言观 色 ,并根据对手的反应调整自己的策略. 但是计算机 不可能做到这一点 ,它们只会按照一定的程序出牌. 虽然计算机无法像人那样去观察对手的一举一动从 而做出判断 ,但它却能记录下对手的比赛套路和方 法 ,通过统计其出牌和不出牌的次数为比赛积累经 验.显然 ,尽早绘制出对手比赛套路是取胜的关键. 因此 ,牌类博弈的关键技术在于统计建模、模式 识别和机器学习. 既要以大量高手的出牌规律作为 基础知识 ,又要及时“绘制 ”当前对手比赛的套路. 显然这不是一般简单智能所能处理的事务. 值得提及的是 ,在机器博弈方面世界领先的加 拿大艾伯塔大学 (University of A lberta)设计的扑克 程序在与知名扑克玩家菲尔 ·拉克的对弈中虽然未 能取胜 ,但对手也不得不承认 ,和电脑的比赛比他职 业生涯中此前任何一场都要绞尽脑汁 ,“电脑现在 就如此先进 ,未来将越来越难战胜 ” [ 9 ] . 4 机器博弈的理论提升 ———对于博 弈论的挑战 通过以上的分析 ,不难看出机器博弈是一类实 践性很强的计算机应用技术的综合. 如果在理论上 加以提升 ,机器博弈应该具有什么样的理论体系呢 ? 机器博弈既然属于博弈的范畴 ,必然应该和博 弈论具有一些内在的联系. 博弈论 ( game theory)又 称对策论、游戏论 ,其概念的引出曾提及象棋的博 弈. 然而纵观博弈论的理论成果 ,却没有方法能够真 正用到象棋博弈之中. 以纳什均衡为代表的博弈论应该属于数学的范 畴 ,是运筹学的一个分支. 相关理论都是通过解析的 办法对问题进行求解. 根据特定问题的类型 ,如囚徒 困境、智猪博弈、海边摊位与性别战等建立相应的数 学模型 ,一般以双值矩阵给出收益函数. 由于博弈双 方都是“理性的 ”,都能够解算出对于自己最为有利的 解 (策略、行动 ) ,双方能够取得“一致预测 ”,于是便 存在了双方都不愿意破坏的“纳什均衡 ”.“理性 —共 识 —均衡 ”便成为博弈论处理问题的基本模式 [ 10 ] . 对于一大批经济学中的完全信息的静态博弈问 题 ,纳什均衡被证明是有效的. 对于不完全信息的静 态博弈问题和完全 (不完全 )信息的动态博弈问题 也都存在贝叶斯均衡或子博弈精炼纳什 (贝叶斯 ) 均衡. 应用上述理论 ,一系列经济学问题得到了很好 的解决. 于是博弈论已经成为现代经济学的重要组 成部分 [ 11 ] . 棋类游戏都属于动态博弈问题. 由于一场对弈的 回合都要数以十计 ,每个回合各方的策略选择也都数 以十计 ,在如此庞大的博弈树中 ,即使只考虑有限的 几个回合 ,理性的博弈者也难建立起“一致预测 ”并取 得共识 ,更何况事实存在的理性和信息的不对称性. 于是 ,有理由对纳什均衡的普遍性提出怀疑. 显然 ,博弈论的解析方法无法求解棋牌游戏问 题 ,而机器博弈的成果又在棋类游戏中取得令人瞩 目的成就. 就使人联想起数学分析和数值分析的相 互关系. 以复杂函数的积分问题为例. 用数学分析的 方法大多数函数是给不出积分的解析解的 ,但是应 用数值分析的方法 ,就很少找到不能求出积分值的 函数来. 因此可以说 ,博弈论像数学分析一样是用解 析方法求解问题 ,而机器博弈却像数值分析一样是 以计算机为手段的、用数值方法求解问题. 两者相辅 相成 ,必然在博弈问题的分析与求解上开拓出广阔 的天地. 事件对策论便是根据博弈论的框架 ,从离散事 件动态系统的角度为机器博弈建立起的形式化描 述 [ 12 ] ,而事件对策问题的求解则必然依靠机器博弈 的方式 [ 13 ] ,因此建立机器博弈学 ,开展事件对策论、 机器博弈原理与方法学的研究都是很有意义的研究 方向. 现实生活中的动态博弈问题都是非常复杂的. 既有时间驱动的连续对策问题 ,又包含由事件驱动 的离散对策问题. 这种混杂对策问题的求解必然呼 唤能够将微分对策论与事件对策论有机结合起来的 混杂对策理论的创立 [ 14 ] . · 092 · 智 能 系 统 学 报 第 3卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第4期 徐心和,等:机器博弈研究面临的各种挑战 ·291· 一个小时就可以下一盘棋,就可以对电脑的智能” 5机器博弈的军事应用 兵棋推演 进行测试,而且可以悔棋、重试、复盘,可以一步步地 机器博弈最直接的应用应该是在作战模拟领 发现电脑与人脑功能的差距,从而不断地提高电脑 域因为象棋、围棋都是从两军对阵中抽象出来的智 的智力水平.基于机器博弈,可以直接开展如下的人 力游戏,都可以在两军对垒和作战形式上找到相互 工智能领域的研究工作: 对应的模式与范例,如兵种的设计与配合、消灭有生 1)如何将丰富的残局棋谱,经过抽象与提炼放 力量、围而攻之夺取地盘等,尽管战争的问题比棋类 到博弈程序当中,这是知识工程的典型课题; 游戏远远复杂,但在战略战术思想上还是具有很多 2)如何通过某个象棋大师的大量棋谱,自动归 的雷同.既然机器博弈系统已经可以和人类的精英 纳这位大师的下棋风格与特点,长项与弱项.这是知 进行较量,是不是一样能将计算机快速而缜密的逻 识挖据的典型课题: 辑思维能力应用到作战模拟当中 3)如何剖析一盘棋的胜败过程与原因,进而自 部队的指挥机关在谋划一场战役之前总是要详 动修改博弈程序,这是机器学习的典型例题: 细分析双方的兵力部署、战场的自然环境对方的可 4)如何将围棋的各种定式进行表示和分辨,这 能调动以及大量难以预见的事件、战斗与结果.早期 是模式识别的典型问题; 的战事谋划是在物理模型上进行的,称之为沙盘推 5)在模型修改过程中,有数不清的优化计算和 演.近代的战事谋划,包括日军袭击珍珠港、联合国 进化过程,这又是各种智能算法的用武之地, 军诺曼底登陆、美军的海湾战争等都是事先进行过 6)如何辅导一个初学者一步步地提高棋艺,切 周密的“兵棋推演”(war gam ing,war smulation),以 中要害地发现问题,这是智能教育的最好课题 便做到“不打无准备之仗”二战退役的老兵还专门 著名数学家、博弈论创始人冯·诺伊曼认为,如 开发了一种游戏,称之为“兵棋州) 果人们想找一种可以解释日常生活的理论,就必须 现代的兵棋推演己经不是在沙盘和地图上进 从解释扑克游戏的理论开始,即博弈论.在扑克游戏 行,己经实现了数字化,参谋人员可以在计算机上输 中,人工智能研究人员目前面临的挑战与冯·诺伊 入各种兵力的部署与调动,适时做出战斗的决策,并 曼在80年前所遇到的挑战一样,即如何理解那些骗 由计算机裁决战斗的结果和给出形象的显示 人的诡计.这一点得到了强大的计算机程序SpaBot 在兵棋推演数字化的情况下,兵棋推演的智能 的证实它击败了大多数登陆加拿大艾伯塔网站 化便是必然的发展趋势.如何实现兵棋推演的智能 想要一试身手的人【8) 化?如何研制无人作战飞机的联合作战策略?如何 “提到人工智能的研究载体,人们首先想到的 在未来的无人作战部队中实现自动指挥与配合?机 就是机器人.然而构造一个机器人,让机器人完成 器博弈的成果必然能够成为诸多关键技术的核心, 次试验,是相当复杂和消耗巨大的事情.就像在自动 因为它是人工智能的高级体现6个 控制系统中,只有构成了计算机的闭环控制,才能谈 6机器博弈一人工智能学科的“果蝇” 得上各种先进控制,如最优控制、自适应控制、鲁棒 控制与变结构控制等.在机器智能领域,也只有建立 果蝇一约3mm长的红眼小“苍蝇”,由于它能 了良好的计算机博弈系统,才能作为研究和实现高 在2周左右的时间繁衍一代,被遗传学家视为最理 级智能的平台,才能成为人工智能研究的果蝇 想的遗传学研究的载体.将果蝇关在牛奶瓶子里,给 7机器博弈的国际接轨 些香蕉之类的水果,他们便能代代相传”诺贝尔 生理学和医学奖获得者摩尔根和他的学生们先 棋牌类游戏深受群众欢迎,但又有很大的地域 后发现伴性遗传、基因重组等现象确定了基因在染 局限性.不同的民族、地域有着不同的棋牌游戏,同 色体上,做出果蝇的第1张染色体图,使得经典遗传 一种棋牌游戏也会因地而异.就像中国象棋和韩国 学进入顶峰时期 象棋,棋盘和棋子一样,但是下法不同,胜负规则都 那么什么是人工智能学科的果蝇理想的研究 有很大的区别 载体)?应该看到,机器博弈是既简单方便、经济实 在中国,象棋、麻将十分普及,可谓玩家最多的 用,又内涵丰富、变化无穷的逻辑思维的研究载体 棋牌游戏,但在国际上并不普及.目前真正全球化的 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
5 机器博弈的军事应用 ———兵棋推演 机器博弈最直接的应用应该是在作战模拟领 域. 因为象棋、围棋都是从两军对阵中抽象出来的智 力游戏 ,都可以在两军对垒和作战形式上找到相互 对应的模式与范例 ,如兵种的设计与配合、消灭有生 力量、围而攻之夺取地盘等. 尽管战争的问题比棋类 游戏远远复杂 ,但在战略战术思想上还是具有很多 的雷同. 既然机器博弈系统已经可以和人类的精英 进行较量 ,是不是一样能将计算机快速而缜密的逻 辑思维能力应用到作战模拟当中. 部队的指挥机关在谋划一场战役之前总是要详 细分析双方的兵力部署、战场的自然环境、对方的可 能调动以及大量难以预见的事件、战斗与结果. 早期 的战事谋划是在物理模型上进行的 ,称之为沙盘推 演. 近代的战事谋划 ,包括日军袭击珍珠港、联合国 军诺曼底登陆、美军的海湾战争等都是事先进行过 周密的“兵棋推演 ”(war gam ing, war simulation) ,以 便做到“不打无准备之仗 ”. 二战退役的老兵还专门 开发了一种游戏 ,称之为“兵棋 ” [ 15 ] . 现代的兵棋推演已经不是在沙盘和地图上进 行 ,已经实现了数字化 ,参谋人员可以在计算机上输 入各种兵力的部署与调动 ,适时做出战斗的决策 ,并 由计算机裁决战斗的结果和给出形象的显示. 在兵棋推演数字化的情况下 ,兵棋推演的智能 化便是必然的发展趋势. 如何实现兵棋推演的智能 化 ? 如何研制无人作战飞机的联合作战策略 ? 如何 在未来的无人作战部队中实现自动指挥与配合 ? 机 器博弈的成果必然能够成为诸多关键技术的核心 , 因为它是人工智能的高级体现 [ 16 ] . 6 机器博弈 ———人工智能学科的“果蝇 ” 果蝇 ———约 3 mm长的红眼小“苍蝇 ”,由于它能 在 2周左右的时间繁衍一代 ,被遗传学家视为最理 想的遗传学研究的载体. 将果蝇关在牛奶瓶子里 ,给 些香蕉之类的水果 ,他们便能“代代相传 ”. 诺贝尔 生理学和医学奖 [ 17 ]获得者摩尔根和他的学生们先 后发现伴性遗传、基因重组等现象 ,确定了基因在染 色体上 ,做出果蝇的第 1张染色体图 ,使得经典遗传 学进入顶峰时期. 那么什么是人工智能学科的果蝇 (理想的研究 载体 ) ? 应该看到 ,机器博弈是既简单方便、经济实 用 ,又内涵丰富、变化无穷的逻辑思维的研究载体. 一个小时就可以下一盘棋 ,就可以对电脑的“智能 ” 进行测试 ,而且可以悔棋、重试、复盘 ,可以一步步地 发现电脑与人脑功能的差距 ,从而不断地提高电脑 的智力水平. 基于机器博弈 ,可以直接开展如下的人 工智能领域的研究工作 : 1)如何将丰富的残局棋谱 ,经过抽象与提炼放 到博弈程序当中 ,这是知识工程的典型课题 ; 2)如何通过某个象棋大师的大量棋谱 ,自动归 纳这位大师的下棋风格与特点 ,长项与弱项. 这是知 识挖掘的典型课题 ; 3)如何剖析一盘棋的胜败过程与原因 ,进而自 动修改博弈程序 ,这是机器学习的典型例题 ; 4)如何将围棋的各种定式进行表示和分辨 ,这 是模式识别的典型问题 ; 5)在模型修改过程中 ,有数不清的优化计算和 进化过程 ,这又是各种智能算法的用武之地 ; 6)如何辅导一个初学者一步步地提高棋艺 ,切 中要害地发现问题 ,这是智能教育的最好课题. 著名数学家、博弈论创始人冯 ·诺伊曼认为 ,如 果人们想找一种可以解释日常生活的理论 ,就必须 从解释扑克游戏的理论开始 ,即博弈论. 在扑克游戏 中 ,人工智能研究人员目前面临的挑战与冯 ·诺伊 曼在 80年前所遇到的挑战一样 ,即如何理解那些骗 人的诡计. 这一点得到了强大的计算机程序 SparBot 的证实 ———它击败了大多数登陆加拿大艾伯塔网站 想要一试身手的人 [ 18 ] . 一提到人工智能的研究载体 ,人们首先想到的 就是机器人. 然而构造一个机器人 ,让机器人完成一 次试验 ,是相当复杂和消耗巨大的事情. 就像在自动 控制系统中 ,只有构成了计算机的闭环控制 ,才能谈 得上各种先进控制 ,如最优控制、自适应控制、鲁棒 控制与变结构控制等. 在机器智能领域 ,也只有建立 了良好的计算机博弈系统 ,才能作为研究和实现高 级智能的平台 ,才能成为人工智能研究的果蝇. 7 机器博弈的国际接轨 棋牌类游戏深受群众欢迎 ,但又有很大的地域 局限性. 不同的民族、地域有着不同的棋牌游戏 ,同 一种棋牌游戏也会因地而异. 就像中国象棋和韩国 象棋 ,棋盘和棋子一样 ,但是下法不同 ,胜负规则都 有很大的区别. 在中国 ,象棋、麻将十分普及 ,可谓玩家最多的 棋牌游戏 ,但在国际上并不普及. 目前真正全球化的 第 4期 徐心和 ,等 :机器博弈研究面临的各种挑战 · 192 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·292· 智能系统学报 第3卷 棋牌游戏种类有限,如国际象棋(chess)、围棋、五子 的积极性和运用知识的能力.机器博弈是一项很好 棋(obang,renju)和桥牌(bridge).尽管在国际机器 的学生科技活动,应该在全国高校中开展民间棋类 博弈协会(Intemational Computer Game A ssociation, 的电脑博弈竞赛,就像电子大赛、数模大赛那样持久 CGA)I9组织的计算机(棋类)奥林匹克大赛(com- 地开展下去 puter olymp iad,CO)包括有中国象棋,但参与者还都 然而面向机器博弈的普及与提高,目前还缺少 是华人,棋子上的汉字本身便将外国人拒之门外 合适的培训教材和自学教材,还缺少有针对性的讲 世界计算机国际象棋冠军赛(World Computer- 座和课程,这都是亟待解决的问题」 Chess Champ ionship)历史长久,每年都在高水平地 9结束语 进行,己经难有进入的可能.五子棋因为己经“宣 布被电脑“求解出来了,先手必胜,近年已经不再 如何在中国大地上将机器博弈的研究与活动开 组织电脑的比赛.这样与国际接轨的最好途径便是 展起来,是值得共同关注的问题.正确的方针应该 围棋和桥牌.后者由于属于非完整信息的动态博弈, 是:以比赛引起公众的注意,调动青年的创新热情 难度更大.于是,当前的前沿阵地便是围棋和9路围 以科学研究推动学科的发展,以丰富的研究成果带 棋(99的围棋). 动理论和应用的突破.机器博弈可以有力地推动人 针对五子棋的退出,台湾交通大学吴毅成教授 工智能学科的发展,应该给与足够的重视,投入足够 发明了六子棋(connect6),目前被认为是最为公平 的人力物力和财力,积极开展各式各样的机器博弈 的棋类2】,正从台湾向大陆和全球推开,这也确实 培训和竞赛活动,迎接CGA即将在中国北京举办 为我们的国际竞争提供了新的领地 的2008世界计算机国际象棋锦标赛、2008国际计 其实,在CGA组织的QO大赛的二三十种棋类 算机(棋类)奥林匹克大赛和2008第6届国际计算 比赛中,多数还是属于一些民间棋类,规则并不复 机博弈学术会议 杂,参赛队也不多,进入不太困难,争雄也有希望.比 参考文献: 如今年在阿姆斯特丹举行的13hC0大赛上,就有 一些小棋种只有两三个队参赛:Amazons(2队)、 [1]Von NEUMANN J,MORGENSTERN O.Theory of games Backgammon(3队)、Phantom Go(2队)和Surakarta and econom ic behavior[M ]Princeton:Princeton Universi- (2队)2 ty Press,1944 [2 ]SHANNON C E Programm ing a computer for playing chess 在国际赛场上和国际强手较量的另一种方式 [J].Philosophical Magazine,1950,41:256-275. 就是将优秀的中国民间棋类经过提升后推向世界, [3]TUR NGA Digital computers applied to games[C]//Fas- 作为一种新的更富挑战性的项目进行比赛,就像吴 ter than Thought London,1953:286-295. 毅成教授提出的六子棋一样 [4]FULLER SH,GASCHNGJ G,GLLOGLYJ J An analy- 8机器博弈的普及与提高 sis of the alpha-beta pruning algorithm[D].Pittsburg Car negie Melbn University,1973. 各种竞赛活动最能激发人们的创新精神,因为 [5]KNUTH D E,MOORE R N.An analysis of alha-beta prun- 胜利总是和创新结伴而行的.尽管目前在国际和国 ing[J ]A rtific ial Intelligence,1975(6):293-326 内都有了相应的锦标赛,但是参加计算机棋类大赛, [6]KORF R Iterative deepening an optmal admissible tree 不用说是象棋和围棋,就是编写五子棋和六子棋的 search[J ]Artificial Intelligence,1985,27(1):97-109. 博弈软件也是一项艰巨的软件工程 [7]EL IZABETH P.B reakthrough of the year human genetic va- 为了搞好机器博奔相关知识与技术的普及,可 viation[J]Science,2007,318(5858):1842-1849 [8除心和,王骄.中国象棋计算机博奔关键技术分析 以针对一些简单的民间棋类在青年学生中开展培训 [J]小型微型计算机系统,2006,27(6):961-969 和竞赛活动.比如开展的牛角棋的编程培训,开展的 XU Xinhe,WANG Jiaa Key technolgies analysis of Chi- 一字棋、二虎棋、三通棋、四季棋等竞赛活动,确实都 nese chess computer game[J].MiniM ico Computer Sys- 受到了学生的热烈欢迎2) tms,2006,27(6):961-969 实践结果表明,学生们给出了各种各样的算法, [9潘丽娟.打扑克人脑险胜电脑[BOL1[2007-07-27] 激发了青年学生的创新热情,提高了学生学习知识 http:/sports sohu com. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved htp://www.cnki.net
棋牌游戏种类有限 ,如国际象棋 ( chess)、围棋、五子 棋 ( gobang, renju)和桥牌 ( bridge). 尽管在国际机器 博弈协会 ( International Computer Game A ssociation, ICGA) [ 19 ]组织的计算机 (棋类 )奥林匹克大赛 ( com2 puter olymp iad, CO)包括有中国象棋 ,但参与者还都 是华人 ,棋子上的汉字本身便将外国人拒之门外. 世界计算机国际象棋冠军赛 (World Computer2 Chess Champ ionship)历史长久 ,每年都在高水平地 进行 ,已经难有进入的可能. 五子棋因为已经“宣 布 ”被电脑“求解 ”出来了 ,先手必胜 ,近年已经不再 组织电脑的比赛. 这样与国际接轨的最好途径便是 围棋和桥牌. 后者由于属于非完整信息的动态博弈 , 难度更大. 于是 ,当前的前沿阵地便是围棋和 9路围 棋 (9 ×9的围棋 ). 针对五子棋的退出 ,台湾交通大学吴毅成教授 发明了六子棋 ( connect 6) ,目前被认为是最为公平 的棋类 [ 20 ] ,正从台湾向大陆和全球推开 ,这也确实 为我们的国际竞争提供了新的领地. 其实 ,在 ICGA组织的 CO大赛的二三十种棋类 比赛中 ,多数还是属于一些民间棋类 ,规则并不复 杂 ,参赛队也不多 ,进入不太困难 ,争雄也有希望. 比 如今年在阿姆斯特丹举行的 13 th2CO大赛上 ,就有 一些小棋种只有两三个队参赛 : Amazons ( 2 队 )、 Backgammon (3队 )、Phantom Go ( 2队 )和 Surakarta (2队 ) [ 21 ] . 在国际赛场上和国际强手较量的另一种方式 , 就是将优秀的中国民间棋类经过提升后推向世界 , 作为一种新的更富挑战性的项目进行比赛 ,就像吴 毅成教授提出的六子棋一样. 8 机器博弈的普及与提高 各种竞赛活动最能激发人们的创新精神 ,因为 胜利总是和创新结伴而行的. 尽管目前在国际和国 内都有了相应的锦标赛 ,但是参加计算机棋类大赛 , 不用说是象棋和围棋 ,就是编写五子棋和六子棋的 博弈软件也是一项艰巨的软件工程. 为了搞好机器博弈相关知识与技术的普及 ,可 以针对一些简单的民间棋类在青年学生中开展培训 和竞赛活动. 比如开展的牛角棋的编程培训 ,开展的 一字棋、二虎棋、三通棋、四季棋等竞赛活动 ,确实都 受到了学生的热烈欢迎 [ 22 ] . 实践结果表明 ,学生们给出了各种各样的算法 , 激发了青年学生的创新热情 ,提高了学生学习知识 的积极性和运用知识的能力. 机器博弈是一项很好 的学生科技活动 ,应该在全国高校中开展民间棋类 的电脑博弈竞赛 ,就像电子大赛、数模大赛那样持久 地开展下去. 然而面向机器博弈的普及与提高 ,目前还缺少 合适的培训教材和自学教材 ,还缺少有针对性的讲 座和课程 ,这都是亟待解决的问题. 9 结束语 如何在中国大地上将机器博弈的研究与活动开 展起来 ,是值得共同关注的问题. 正确的方针应该 是 :以比赛引起公众的注意 ,调动青年的创新热情 , 以科学研究推动学科的发展 ,以丰富的研究成果带 动理论和应用的突破. 机器博弈可以有力地推动人 工智能学科的发展 ,应该给与足够的重视 ,投入足够 的人力物力和财力 ,积极开展各式各样的机器博弈 培训和竞赛活动 ,迎接 ICGA即将在中国北京举办 的 2008世界计算机国际象棋锦标赛、2008国际计 算机 (棋类 )奥林匹克大赛和 2008第 6届国际计算 机博弈学术会议. 参考文献 : [ 1 ]Von NEUMANN J, MORGENSTERN O. Theory of games and econom ic behavior[M ]. Princeton: Princeton Universi2 ty Press, 1944. [ 2 ] SHANNON C E. Programming a computer for p laying chess [J ]. PhilosophicalMagazine, 1950, 41: 2562275. [ 3 ] TUR ING A. D igital computers app lied to games[ C ] / /Fas2 ter than Thought. London, 1953: 2862295. [ 4 ] FULLER S H, GASCH ING J G , GILLOGLY J J. An analy2 sis of the alpha2beta p runing algorithm [D ]. Pittsburg: Car2 negie2Mellon University, 1973. [ 5 ] KNUTH D E,MOORE R N. An analysis of alpha2beta p run2 ing[J ]. A rtificial Intelligence, 1975 (6) : 2932326. [ 6 ] KORF R. Iterative deepening: an op timal adm issible tree search[J ]. A rtificial Intelligence, 1985, 27 (1) : 972109. [ 7 ] EL IZABETH P. Breakthrough of the year: human genetic va2 viation[J ]. Science, 2007, 318 (5858) : 184221849. [ 8 ]徐心和 ,王 骄. 中国象棋计算机博弈关键技术分析 [J ]. 小型微型计算机系统 , 2006, 27 (6) : 9612969. XU Xinhe, WANG Jiao. Key technologies analysis of Chi2 nese chess computer game [ J ]. M ini2M icro Computer Sys2 tem s, 2006, 27 (6) : 9612969. [ 9 ]潘丽娟. 打扑克人脑险胜电脑 [ EB /OL ]. [ 2007207227 ]. http: / /sports. sohu. com . · 292 · 智 能 系 统 学 报 第 3卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第4期 徐心和,等:机器博弈研究面临的各种挑战 ·293· [10范如国,韩民春.博弈论M武汉:武汉大学出版社, nec6[D].China,Taiwan:National Chiao Tung University, 2006:1-20 2006 [11李光久.博弈论基础教程[M北京:化学工业出版 [21]CGA赛:电脑棋类程序竞赛[B/OL]htp:/w 社,2005:25-58 grappa univ-lille3.fr/icga/?lang=4 [12除心和,郑新颖.棋牌游戏与事件对策[J]控制与决 [22除心和,徐长明,邓志立.积极开展民间棋类的计算机 策,2007,22(7):787-790 博弈活动「C]/12007中国自动化教育年会论文集.西 XU Xinhe,ZHENG Xinying Card and board games and e- 安:机械工业出版社,2007:216-219 vent game [J ]Control and Decision,2007,22 (7):787- XU Xinhe,XU Changm ing,DENG Zhili Develop the ac- 790 tivities of folk board computer games[C]//Proceedings of [13除心和,王浩,孔凡禹.事件对策理论及在棋类游戏 Chinese Automaton Education Conference Xi'an:Me- 中的应用[J]中南大学学报(自然科学版),2007,38 chanical Industrial Press,2007:216-219 增刊):718-721 作者简介: XU Xinhe,WANG Hao,KONG Fanyu Event game theory 徐心和,男,1940年生,教授,博士生 and an application o chess board game [J ]Joumal of 导师,中国系统仿真学会常务理事,中国 Central South University of Technobog Natural Science, 自动化学会机器人竞赛工作委员会副主 200738(SuppD):718-721. 任,中国人工智能学会机器博弈专业委 [14除心和,施鸿雁.一个空战实例中的混合对策问题 员会主任,主要研究方向为控制理论与 [C]1/2007中国控制与决策学术年会论文集.无锡,中 应用、系统仿真与智能控制、智能机器人 国,2007:913916 与模式识别,2003年以来重点研究机器博弈和博弈论.并在中 XU Xinhe,SHIHongyan An air combat case and hybrid 国象棋和六子棋的机器博弈方面取得国内领先的成绩 game problem C]//Proceedings of 2007 Chinese Control 邓志立,女,1981年生,硕士,主要 and Decision Conference W uxi,China,2007:913-916 研究方向为机器博弈,主攻六子棋的计 [15杨南征.虚拟演兵—兵棋、作战模拟与仿真M1北 算机博弈软件开发」 京:解放军出版社,2007 [16除心和,邓志立.基于机器博弈的作战模拟系统探讨 [C]/中国系统建模与仿真技术高层论坛论文集.北 京,2006:113-117 XU Xinhe,DENG Zhili Study on the war game smulation 王骄,男,1978年生,讲师,中国 system based on computer games[C]//Poceedings of High 人工智能学会机器博弈专业委员会委 Level Fonm on Chinese System Modeling and Smulation 员,主要研究方向为中国象棋计算机博 Beijing,2006:113-117. 弈,开发的“棋天大圣软件系统先后获 [17]摩尔根与果蝇[B/OL1[20080106]hp:/basic 得中国象棋机器博弈锦标赛全国冠军 shsmu edu cn/pke/Marx phibsophy/yxyzx/12 ppt (2006)和世界冠军(2006、2007 comput- [18]向黎.扑克牌里的博弈之道[B/OL】[200801-061 er olymp iad),在挑战中国象棋特级大师 http://bbs m so com.cn/viewthread php?tid =645174. 和全国冠军的人机大战中取得了优异成绩,并在集群系统的 [19]CGA home page EB /OL [2007-1125 htp://www. 并行计算方面有深入研究和成果」 cs unmaas nl/icga [20 WU IC,CHANG H C.Threat-based proof search for Con- 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[ 10 ]范如国 ,韩民春. 博弈论 [M ]. 武汉 :武汉大学出版社 , 2006: 1220. [ 11 ]李光久. 博弈论基础教程 [M ]. 北京 :化学工业出版 社 , 2005: 25258. [ 12 ]徐心和 ,郑新颖. 棋牌游戏与事件对策 [J ]. 控制与决 策 , 2007, 22 (7) : 7872790. XU Xinhe, ZHENG Xinying. Card and board games and e2 vent game [ J ]. Control and Decision, 2007, 22 ( 7) : 7872 790. [ 13 ]徐心和 ,王 浩 ,孔凡禹. 事件对策理论及在棋类游戏 中的应用 [J ]. 中南大学学报 (自然科学版 ) , 2007, 38 (增刊 ) : 7182721. XU Xinhe, WANG Hao, KONG Fanyu. Event game theory and an app lication to chess board game [ J ]. Journal of Central South University of Technolog: Natural Science, 2007 38 ( Supp l) : 7182721. [ 14 ]徐心和 ,施鸿雁. 一个空战实例中的混合对策问题 [C ] / /2007中国控制与决策学术年会论文集. 无锡 , 中 国 , 2007: 9132916. XU Xinhe, SH I Hongyan. An air combat case and hybrid game p roblem [ C ] / /Proceedings of 2007 Chinese Control and Decision Conference. W uxi, China, 2007: 9132916. [ 15 ]杨南征. 虚拟演兵 ———兵棋、作战模拟与仿真 [M ]. 北 京 :解放军出版社 , 2007. [ 16 ]徐心和 ,邓志立. 基于机器博弈的作战模拟系统探讨 [C ] / /中国系统建模与仿真技术高层论坛论文集. 北 京 , 2006: 1132117. XU Xinhe, DENG Zhili. Study on the war game simulation system based on computer games[C ] / /Proceedings of High Level Forum on Chinese System Modeling and Simulation. Beijing, 2006: 1132117. [ 17 ]摩尔根与果蝇 [ EB /OL ]. [ 2008201206 ]. http: / /basic. shsmu. edu. cn / jpkc /Marx_philosophy/yxyzx/12. pp t. [ 18 ]何 黎. 扑克牌里的博弈之道 [ EB /OL ]. [ 2008201206 ]. http: / /bbs. m so. com. cn /viewthread. php? tid = 645174. [ 19 ] ICGA home page [ EB /OL ]. [ 2007211225 ]. http: / /www. cs. unimaas. nl/ icga. [ 20 ]WU I C, CHANG H C. Threat2based p roof search for Con2 nect6 [D ]. China, Taiwan: National Chiao Tung University, 2006. [ 21 ] ICGA 赛 : 电脑棋类程序竞赛 [ EB /OL ]. http: / /www. grappa. univ2lille3. fr/ icga / ? lang = 4. [ 22 ]徐心和 ,徐长明 ,邓志立. 积极开展民间棋类的计算机 博弈活动 [ C ] / /2007中国自动化教育年会论文集. 西 安 :机械工业出版社 , 2007: 2162219. XU Xinhe, XU Changm ing, DENG Zhili. Develop the ac2 tivities of folk board computer games[ C ] / /Proceedings of Chinese Automation Education Conference. Xi’an: Me2 chanical Industrial Press, 2007: 2162219. 作者简介 : 徐心和 ,男 , 1940年生 ,教授 ,博士生 导师 ,中国系统仿真学会常务理事 ,中国 自动化学会机器人竞赛工作委员会副主 任 ,中国人工智能学会机器博弈专业委 员会主任 ,主要研究方向为控制理论与 应用、系统仿真与智能控制、智能机器人 与模式识别 , 2003年以来重点研究机器博弈和博弈论 ,并在中 国象棋和六子棋的机器博弈方面取得国内领先的成绩. 邓志立 ,女 , 1981年生 ,硕士 ,主要 研究方向为机器博弈 ,主攻六子棋的计 算机博弈软件开发. 王 骄 ,男 , 1978年生 ,讲师 ,中国 人工智能学会机器博弈专业委员会委 员. 主要研究方向为中国象棋计算机博 弈 ,开发的“棋天大圣 ”软件系统先后获 得中国象棋机器博弈锦标赛全国冠军 (2006)和世界冠军 (2006、2007 comput2 er olymp iad) ,在挑战中国象棋特级大师 和全国冠军的人机大战中取得了优异成绩 ,并在集群系统的 并行计算方面有深入研究和成果. 第 4期 徐心和 ,等 :机器博弈研究面临的各种挑战 · 392 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net