中国象棋人机大战与机器博弈原理.ppt

中国象棋人机大战 与机器博弈原理 徐心和东北大学人工智能与机器人研究所 xuxinhe@2006.10主要内容•浪潮杯首届中国象棋人机大战 •机器博弈的艰苦历程 •中象机器博弈的关键技术分析 Ø棋局表示 Ø着法生成 Ø评估函数 Ø博弈搜索 Ø系统开发 •积极投入机器博弈的滚滚洪流 浪潮杯首届中国象棋人机大战•从AI创立50周年说起 •1956年美国达特茅斯(Dartmouth )大学 •以麦卡西为首的十位年轻学者 •AI-Artificial Intelligence •从此开始了人工智能研究的新纪元 •人工智能发展的道路并不平坦 •如今，AI的研究已经硕果累累 •什么是人工智能？人类智能的理解与机器实 现人类（生物）智能包括哪些？ 感知 思维（逻辑思维、形象思维、灵感思 维） 动作（技巧） …… 人工智能举例：机器视觉、语音识别、文字 识别、机器翻译、专家系统、神经网络、模 糊逻辑、知识挖掘……机器人是人工智能的集中表现北京-庆祝AI 50年•科技活动旬 •中国科技会堂——国际学术(ICAI’06 )会议 •中国科技馆——全国首届智能科技成果与 产品博览会 •浪潮杯首届全国计算机博弈锦标赛 •2006全国机器博弈学术研讨会 •浪潮杯首届中国象棋人机大战 •人脑对电脑的巅峰对决全国机器博弈锦标赛•以前仅在局部地区举行过中国象棋的计算 机比赛——台湾每年都有； •ICGA COMPUTER OLYMPIAD 国际计 算机（棋类）奥林匹克竞赛已经举办过11 届，有中国象棋的比赛项目； •在大陆进行此类全国比赛今年是首届，浪 潮集团冠名——浪潮杯； •今年仅有中国象棋的计算机比赛。

最高水平的参赛队•台湾：宝岛一号、兵芯 、深象 •美国：梦入神机、神乎棋技 •法国：谢谢大师 •棋天大圣、象棋奇兵、象眼竞技、理治棋 壮、棋乐无穷、棋之梦、将神传说、落花 、青羽堂、天机、象棋ABC、象棋旋风 •总计：18支代表队 •缺席的高水平代表队：纵马奔流、棋海无 涯新老冠军的对决积分相等加赛2场决赛前5名•棋天大圣 •象棋奇兵 •象棋旋风 •天 机 •将神传说记者招待会引起各种媒体的广泛关注浪潮天梭下战表中国象棋人机大战2006年8月9日国家奥林匹克中心 综合馆左起：卜凤波、徐天红、柳大华、张强、汪洋浪潮天梭+全国锦标赛前5名 对阵5位象棋大师5位大师—全国最高水平卜凤波柳大华徐天红洋 汪张 强现场掠影国家奥体中心综合馆棋天大圣挑战徐天红对局结果•棋天大圣 ：徐天红 两和 •象棋奇兵 ：卜风波 一胜，一和 •象棋旋风 ：柳大华 两胜 •天 机 ：张 强 一负，一和 •将神传说 ：汪 洋 一和，一负 • 电 脑 ：人脑 = 11 ：9柳大华“完败”大师们谈感想“虽然这次比赛规则上 对人不利，在一定程度 上影响了比赛结果。

但 是，我相信机器终将会 战胜人，这是必然的趋 势 紫禁城烽烟再起•素有“象棋 第一人”之 称全国排名 第一的、31 岁国际特级 大师许银川 人机大战终极PK2006年 8月 15日北京香格里拉饭店许银川赛后感“可以用暗潮汹涌，惊心动魄来概括 与计算机下棋真的很累，因为我在明处， 它在暗处，不知道它想的是什么能下成两和，是我意料之中的 事情一年之中有那么多比赛， 这场对决，是我职业生涯中难忘 的一幕棋天大圣”在本场比赛中表现的水平，可与大 师相媲美整场比赛很艰苦，但计算机的思维 带给我非常大的开拓性启示机器博弈的艰苦历程人机博弈 历史久远1769年第一 台“象棋机 器”诞生这不是我们 讨论的范畴我们感兴趣 计算机博弈 属人工智能• 早在1958年，IBM推出的取名“思考”的 IBM704就成为了第一台与人类进行国际象棋 对抗的计算机，当时它一秒钟可以进行200步 的运算，但是在人类棋手面前被打得丢盔卸 甲 • 而许多科学家却对此欢欣鼓舞，诺贝尔经济 学奖和杰出科学贡献奖的获得者赫伯特·西蒙 教授，早在1957年就预测说：“计算机在10年 内将成为世界的国际象棋冠军！” 计算机博弈的艰苦历程计算机博弈的艰苦历程• 10年过去，不要说战胜世界冠军，就连与最 “臭”的专业象棋选手对阵，电脑也都战战兢 兢。

• 为了给电脑棋手打气，麻省理工学院的教授 弗雷德金甚至不惜重金悬赏，设立10万美金 的“弗雷德金奖”，声明这笔巨款将奖给第一 个战胜世界国际象棋冠军的电脑程序设计者 计算机博弈的艰苦历程1980年，第一台真正意 义上的象棋机器“Belle” 在贝尔实验室诞生计算机学者 Ken Thompson由数百芯片组成 造价仅为２万美元 每秒可计算18万步 1980-1983年间 为世界计算机象棋冠军国际象棋计算机博弈简史 • 1958年，IBM704成为第一台能同人下棋的计算机， 名为“思考”，思考速度每秒200步 • 60年代中期，科学家德里夫斯断言，计算机将无法 击败一位年仅10岁的棋手 • 1973年，国际象棋软件4.0被开发出来，这是未来程 序的基础 • 1979年，国际象棋软件4.9达到专家级水平 • 1981年，CRAYBLITZ新的超级计算机拥有特殊的 集成电路，预言将可在1995年击败世界棋王 • 1983年，BELLE AT＆T开发了国际象棋硬件，达 到了大师水平•80年代中期，皮兹堡的CARNEGIEMELLON大学 开始研究世界级的国际象棋计算机程序。

•1987年，“深思”首次以每秒钟75万步的思考速度露 面，它的水平相当于拥有国际等级分为2450的棋手 •1988年，“深思”击败丹麦特级大师拉尔森 •1989年，“深思”已经有6台信息处理器，每秒思考速 度达200万步，但在与世界棋王卡斯帕罗夫进行的“人 机大战”中对阵以0比2败北 •1990年，“深思”第二代产生，使用IBM的硬件，吸 引了前世界棋王卡尔波夫与之对抗 •1991年，“弗里茨”问世国际象棋计算机博弈简史 •1993年，“深思”二代击败了丹麦国家队，在与世界 优秀女棋手小波尔加的对抗中获胜 •1995年，“深蓝”更新程序，新的集成电路将其思考 速度达到每秒300万步 •1996年，“深蓝”在与卡斯帕罗夫的挑战赛中，以2比 4不敌卡斯帕罗夫 •1997年，“超级深蓝”开发出了更加高级的“大脑”，4 名国际大师参与IBM的挑战小组为电脑与卡斯帕罗夫 重战出谋划策，最后“超级深蓝”以3.5比2.5击败了卡 斯帕罗夫 •卡斯帕罗夫要求重赛，但没有得到回应 国际象棋计算机博弈简史 • 1999年，“弗里茨”升级为“更弗里茨” • 2001年，“更弗里茨”更新了程序，击败了除 了卡斯帕罗夫和阿南德，以及克拉姆尼克之 外的所有排名世界前十位的棋手。

• 2002年10月，“更弗里茨”与克拉姆尼克在巴 林进行“人机大战”，思考速度为每秒600万步 双方战成4比4平 • 2003年1～2月“更年少者”与卡斯帕罗夫举行 人机对抗，双方3比3战平 国际象棋计算机博弈简史 出生于中国台湾省现年47岁 1980年毕业于台湾 大学电机系，获硕 士学位 1989年获得美国卡 内基梅隆大学计算 机科学博士学位“深蓝之父”——许峰雄博士“深蓝之父”——许峰雄博士•1985年，许峰雄博士开始了“人机博弈”的研究 •1988年，研制出超级计算机 “深思”，首次战胜人类 国际象棋特级大师本特·拉尔森 •1989年世界计算机象棋冠军 •同年加入IBM研究院开始“深蓝”项目的研究 •1991年，成为首位荣获美国计算机协会 Grace Murray Hopper奖的亚裔科学家 •1991年 ACM国际计算机象棋大赛奖 •1994年 ACM国际计算机象棋大赛奖 •1996年 IBM优秀技术奖 •1997年5月11日，推出超级计 算机 “深蓝”以3.5比2.5的总比 分击败国际象棋特级大师卡斯 帕罗夫； •为此，获得IBM奖，获得 Fredkin（弗雷德金）奖； • 1999年，Funnov Inc. 公司总 裁； • 2000年，康柏研究院 (惠普研 究院) 技术负责； • 2003年4月17日正式宣布加盟 微软亚洲研究院，任高级研究 员。

深蓝之父”——许峰雄博士•出生于阿塞拜疆 •现年45岁 •自1984年以来一直稳居世界 第一的位置 •目前他仍被国际象棋协会排 在克拉姆尼克之前，位居第一 •他被许多国际象棋专家认为 是历史上最伟大的棋手 •在国际象棋界近乎成了神话 般的人物 世界棋王——卡斯帕罗夫世界棋王——卡斯帕罗夫1989 vs Deep Thought 2.0 : 01995 vs Junior 1.5 : 0.51995 vs Fritz 4 1.5 : 0.51996 vs Deep Blue 4.0 : 2.01997 vs Deep Blue 2.5 : 3.5 （更深的兰）2003 vs Deep Junior 3.0 : 3.02003 vs X3D-Fritz 4.0 : 4.0须知：更弗里茨比当年“深蓝”运算能力快56倍（奔4、2.8兆赫、4G内存）世界棋王——卡斯帕罗夫卡斯帕罗夫认为：“有些时候，电脑下得就像神一 样完美，但有些时候，它还得向人类多多学习 “这不仅仅是一场国际象 棋比赛，更是一场赌博： 人脑和电脑的较量。

中国首次国际象棋“人机大战” •2004年6月8日和12日的两场 比赛 •“紫光之星”采用了目前最快 的7200转硬盘，最新ATIM 11,128M显存等业界顶级笔记 本配置2600分左右 ) •中国极负盛名的国际象棋特级大师、 “美女棋后”诸宸 (2493分 ) •紫光2:0获胜•关键: 运行了最先进的国象软 件•中国象棋的计算机博弈却开展的不尽人意， 成了“被爱情遗忘的角落”•缺少学者的关注，寥寥无几的参与者，匮乏 的参考文献，沉寂的计算机博弈氛围，使得 中国象棋的计算机博弈在中国内陆难有作为 ，只是成为一些商家的游戏软件和教学载体 •这便是当前我们所面临的艰难局面•应该说，在台湾还是开展得很不错 中国象棋计算机博弈历史 中国象棋的挑战性•国际象棋棋盘8行8列总计64格，中国象棋10 行9列总计90个交点，显然中国象棋的运子空 间更大 •相比之下，中国象棋的着法更为特殊（如蹩 马脚、压象眼等），棋局变化也更加复杂 •随着计算机博弈在Othello、Checker和国际 象棋三种棋类上的成功，全世界的学者又把 目光投到更为复杂的中国象棋(Chinese Chess) 、日本将棋（Shogi）、围棋(Go)上面。

几种棋类的空间复杂度及树的复杂度对比•表中的数字为复杂度的自然对数值 •显然，这更是对中国学者提出的严峻挑战 棋类空间复杂度树的复杂度Chess50123Chinese chess52 150Shogi71226Go160400中象机器博弈的关键技术分析积极投入机器博弈的滚滚洪流•人机大战是对计算机科学与系统的有力挑 战 •象棋博弈是人工智能学科的“果蝇” •人机大战可以动员广大科技青年的创新热 情 •象棋博弈有利于计算机知识的普及与提高 •历史性的较量为IT公司提供了绝好的商机 •有力促进国粹——中国象棋的发展与提高 开展机器博弈活动的目的意义东北大学棋天大圣的成长历程•2003年10月正式启动机器博弈课题 搜集资料、了解动态、学习相关文献 •2004年初，开始组建队伍和初步开发工作 •2004年5月提出目标——向中国象棋冠军挑 战 •正式成立“棋天大圣”代表队 •聘请许峰雄博士为顾问 •正式开始全面开发工作 •2005年5月开发出比赛系统，校内亮相 •2005年9月参加世界计算机（棋类）奥赛启。