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

东北大学人工智能与机器人研究所,中国象棋人机大战与机器博弈原理,徐心和东北大学人工智能与机器人研究所xuxinhe,2006.10,东北大学人工智能与机器人研究所,主要内容,浪潮杯首届中国象棋人机大战机器博弈的艰苦历程中象机器博弈的关键技术分析棋局表示着法生成评估函数博弈搜索系统开发积极投入机器博弈的滚滚洪流,东北大学人工智能与机器人研究所,浪潮杯首届中国象棋人机大战,从AI创立50周年说起1956年美国达特茅斯(Dartmouth)大学以麦卡西为首的十位年轻学者AI-ArtificialIntelligence从此开始了人工智能研究的新纪元人工智能发展的道路并不平坦如今，AI的研究已经硕果累累什么是人工智能？,东北大学人工智能与机器人研究所,人类智能的理解与机器实现人类（生物）智能包括哪些？感知思维（逻辑思维、形象思维、灵感思维）动作（技巧）人工智能举例：机器视觉、语音识别、文字识别、机器翻译、专家系统、神经网络、模糊逻辑、知识挖掘机器人是人工智能的集中表现,东北大学人工智能与机器人研究所,北京-庆祝AI50年,科技活动旬中国科技会堂国际学术(ICAI06)会议中国科技馆全国首届智能科技成果与产品博览会浪潮杯首届全国计算机博弈锦标赛2006全国机器博弈学术研讨会浪潮杯首届中国象棋人机大战人脑对电脑的巅峰对决,东北大学人工智能与机器人研究所,全国机器博弈锦标赛,以前仅在局部地区举行过中国象棋的计算机比赛台湾每年都有；ICGACOMPUTEROLYMPIAD国际计算机（棋类）奥林匹克竞赛已经举办过11届，有中国象棋的比赛项目；在大陆进行此类全国比赛今年是首届，浪潮集团冠名浪潮杯；今年仅有中国象棋的计算机比赛。,东北大学人工智能与机器人研究所,最高水平的参赛队,台湾：宝岛一号、兵芯、深象美国：梦入神机、神乎棋技法国：谢谢大师棋天大圣、象棋奇兵、象眼竞技、理治棋壮、棋乐无穷、棋之梦、将神传说、落花、青羽堂、天机、象棋ABC、象棋旋风总计：18支代表队缺席的高水平代表队：纵马奔流、棋海无涯,东北大学人工智能与机器人研究所,新老冠军的对决,积分相等加赛2场,东北大学人工智能与机器人研究所,决赛前5名,棋天大圣象棋奇兵象棋旋风天机将神传说,东北大学人工智能与机器人研究所,记者招待会,引起各种媒体的广泛关注,东北大学人工智能与机器人研究所,浪潮天梭下战表,东北大学人工智能与机器人研究所,中国象棋人机大战,2006年8月9日,国家奥林匹克中心综合馆,东北大学人工智能与机器人研究所,左起：卜凤波、徐天红、柳大华、张强、汪洋,浪潮天梭+全国锦标赛前5名对阵5位象棋大师,东北大学人工智能与机器人研究所,5位大师全国最高水平,卜凤波,柳大华,徐天红,洋汪,张强,东北大学人工智能与机器人研究所,现场掠影,东北大学人工智能与机器人研究所,国家奥体中心综合馆,棋天大圣挑战徐天红,东北大学人工智能与机器人研究所,东北大学人工智能与机器人研究所,对局结果,棋天大圣：徐天红两和象棋奇兵：卜风波一胜，一和象棋旋风：柳大华两胜天机：张强一负，一和将神传说：汪洋一和，一负电脑：人脑=11：9,东北大学人工智能与机器人研究所,柳大华“完败”,东北大学人工智能与机器人研究所,大师们谈感想,“虽然这次比赛规则上对人不利，在一定程度上影响了比赛结果。但是，我相信机器终将会战胜人，这是必然的趋势。”,东北大学人工智能与机器人研究所,东北大学人工智能与机器人研究所,紫禁城烽烟再起,素有“象棋第一人”之称全国排名第一的、31岁国际特级大师许银川,东北大学人工智能与机器人研究所,人机大战终极PK,东北大学人工智能与机器人研究所,2006年8月15日,北京香格里拉饭店,东北大学人工智能与机器人研究所,许银川赛后感,“可以用暗潮汹涌，惊心动魄来概括。与计算机下棋真的很累，因为我在明处，它在暗处，不知道它想的是什么。”,“能下成两和，是我意料之中的事情。一年之中有那么多比赛，这场对决，是我职业生涯中难忘的一幕。”,“棋天大圣”在本场比赛中表现的水平，可与大师相媲美。整场比赛很艰苦，但计算机的思维带给我非常大的开拓性启示。,东北大学人工智能与机器人研究所,机器博弈的艰苦历程,东北大学人工智能与机器人研究所,人机博弈历史久远,1769年第一台“象棋机器”诞生,这不是我们讨论的范畴,我们感兴趣计算机博弈属人工智能,东北大学人工智能与机器人研究所,早在1958年，IBM推出的取名“思考”的IBM704就成为了第一台与人类进行国际象棋对抗的计算机，当时它一秒钟可以进行200步的运算，但是在人类棋手面前被打得丢盔卸甲。而许多科学家却对此欢欣鼓舞，诺贝尔经济学奖和杰出科学贡献奖的获得者赫伯特西蒙教授，早在1957年就预测说：“计算机在10年内将成为世界的国际象棋冠军！”,计算机博弈的艰苦历程,东北大学人工智能与机器人研究所,计算机博弈的艰苦历程,10年过去，不要说战胜世界冠军，就连与最“臭”的专业象棋选手对阵，电脑也都战战兢兢。为了给电脑棋手打气，麻省理工学院的教授弗雷德金甚至不惜重金悬赏，设立10万美金的“弗雷德金奖”，声明这笔巨款将奖给第一个战胜世界国际象棋冠军的电脑程序设计者。,东北大学人工智能与机器人研究所,计算机博弈的艰苦历程,1980年，第一台真正意义上的象棋机器“Belle”在贝尔实验室诞生,计算机学者KenThompson,由数百芯片组成造价仅为万美元每秒可计算18万步1980-1983年间为世界计算机象棋冠军,东北大学人工智能与机器人研究所,国际象棋计算机博弈简史,1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”，思考速度每秒200步。60年代中期，科学家德里夫斯断言，计算机将无法击败一位年仅10岁的棋手。1973年，国际象棋软件4.0被开发出来，这是未来程序的基础。1979年，国际象棋软件4.9达到专家级水平。1981年，CRAYBLITZ新的超级计算机拥有特殊的集成电路，预言将可在1995年击败世界棋王。1983年，BELLEATT开发了国际象棋硬件，达到了大师水平。,东北大学人工智能与机器人研究所,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年12月“更年少者”与卡斯帕罗夫举行人机对抗，双方3比3战平。,国际象棋计算机博弈简史,东北大学人工智能与机器人研究所,出生于中国台湾省现年47岁1980年毕业于台湾大学电机系，获硕士学位1989年获得美国卡内基梅隆大学计算机科学博士学位,“深蓝之父”许峰雄博士,东北大学人工智能与机器人研究所,“深蓝之父”许峰雄博士,1985年，许峰雄博士开始了“人机博弈”的研究1988年，研制出超级计算机“深思”，首次战胜人类国际象棋特级大师本特拉尔森。1989年世界计算机象棋冠军同年加入IBM研究院开始“深蓝”项目的研究1991年，成为首位荣获美国计算机协会GraceMurrayHopper奖的亚裔科学家1991年ACM国际计算机象棋大赛奖1994年ACM国际计算机象棋大赛奖1996年IBM优秀技术奖,东北大学人工智能与机器人研究所,1997年5月11日，推出超级计算机“深蓝”以3.5比2.5的总比分击败国际象棋特级大师卡斯帕罗夫；为此，获得IBM奖，获得Fredkin（弗雷德金）奖；1999年，FunnovInc.公司总裁；2000年，康柏研究院(惠普研究院)技术负责；2003年4月17日正式宣布加盟微软亚洲研究院，任高级研究员。,“深蓝之父”许峰雄博士,东北大学人工智能与机器人研究所,出生于阿塞拜疆现年45岁自1984年以来一直稳居世界第一的位置目前他仍被国际象棋协会排在克拉姆尼克之前，位居第一。他被许多国际象棋专家认为是历史上最伟大的棋手。在国际象棋界近乎成了神话般的人物。,世界棋王卡斯帕罗夫,东北大学人工智能与机器人研究所,世界棋王卡斯帕罗夫,1989vsDeepThought2.0:01995vsJunior1.5:0.51995vsFritz41.5:0.51996vsDeepBlue4.0:2.01997vsDeepBlue2.5:3.5（更深的兰）2003vsDeepJunior3.0:3.02003vsX3D-Fritz4.0:4.0须知：更弗里茨比当年“深蓝”运算能力快56倍（奔4、2.8兆赫、4G内存）,东北大学人工智能与机器人研究所,世界棋王卡斯帕罗夫,卡斯帕罗夫认为：“有些时候，电脑下得就像神一样完美，但有些时候，它还得向人类多多学习。”,“这不仅仅是一场国际象棋比赛，更是一场赌博：人脑和电脑的较量。”,东北大学人工智能与机器人研究所,中国首次国际象棋“人机大战”,2004年6月8日和12日的两场比赛“紫光之星”采用了目前最快的7200转硬盘，最新ATIM11,128M显存等业界顶级笔记本配置。(2600分左右)中国极负盛名的国际象棋特级大师、“美女棋后”诸宸(2493分)紫光2:0获胜关键:运行了最先进的国象软件,东北大学人工智能与机器人研究所,中国象棋的计算机博弈却开展的不尽人意，成了“被爱情遗忘的角落”。缺少学者的关注，寥寥无几的参与者，匮乏的参考文献，沉寂的计算机博弈氛围，使得中国象棋的计算机博弈在中国内陆难有作为，只是成为一些商家的游戏软件和教学载体。这便是当前我们所面临的艰难局面。应该说，在台湾还是开展得很不错。,中国象棋计算机博弈历史,东北大学人工智能与机器人研究所,中国象棋的挑战性,国际象棋棋盘8行8列总计64格，中国象棋10行9列总计90个交点，显然中国象棋的运子空间更大。相比之下，中国象棋的着法更为特殊（如蹩马脚、压象眼等），棋局变化也更加复杂。随着计算机博弈在Othello、Checker和国际象棋三种棋类上的成功，全世界的学者又把目光投到更为复杂的中国象棋(ChineseChess)、日本将棋（Shogi）、围棋(Go)上面。,东北大学人工智能与机器人研究所,几种棋类的空间复杂度及树的复杂度对比,表中的数字为复杂度的自然对数值。显然，这更是对中国学者提出的严峻挑战。,东北大学人工智能与机器人研究所,中象机器博弈的关键技术分析,积极投入机器博弈的滚滚洪流,东北大学人工智能与机器人研究所,人机大战是对计算机科学与系统的有力挑战象棋博弈是人工智能学科的“果蝇”人机大战可以动员广大科技青年的创新热情象棋博弈有利于计算机知识的普及与提高历史性的较量为IT公司提供了绝好的商机有力促进国粹中国象棋的发展与提高,开展机器博弈活动的目的意义,东北大学人工智能与机器人研究所,东北大学棋天大圣的成长历程,2003年10月正式启动机器博弈课题搜集资料、了解动态、学习相关文献2004年初，开始组建队伍和初步开发工作2004年5月提出目标向中国象棋冠军挑战正式成立“棋天大圣”代表队聘请许峰雄博士为顾问正式开始全面开发工作2005年5月开发出比赛系统，校内亮相2005年9月参加世界计算机（棋类）奥赛,东北大学人工智能与机器人研究所,启动与深蓝握手（2003.10.7）,东北大学人工智能与机器人研究所,校内发动发起挑战（2004.5.8）,东北大学人工智能与机器人研究所,聘请许峰雄博士报告、名誉教授、顾问（2004.5.14）,东北大学人工智能与机器人研究所,第10届世界计算机（棋类）奥赛2005年9月3-9日在台北举行,东北大学人工智能与机器人研究所,棋天大圣参加世界计算机（棋类）奥赛,东北大学人工智能与机器人研究所,棋天大圣勇夺世界第三,14支代表队双循环赛棋天大圣战罢：18胜6平2负积21分冠军象棋奇兵亚军棋海无涯,东北大学人工智能与机器人研究所,中国象棋人机大战,东北大学计算机博弈代表队棋天大圣,武汉理工大学中国象棋大师周熠,VS,时间：11月2日8:30-10:00地点：听涛5号会议室,中国人工智能学会机器博弈专业委员会2005年10月30日,东北大学人工智能与机器人研究所,人机对弈（左机：王骄，右机：周熠）,东北大学人工智能与机器人研究所,比赛现场,东北大学人工智能与机器人研究所,接见双方选手(左起:棋天大圣对长王骄，徐心和，周熠）,东北大学人工智能与机器人研究所,挑战辽宁省女子冠军李晓春（2006.3.12）,东北大学人工智能与机器人研究所,挑战辽宁省男子冠军丰鹤（2006.3.12）,东北大学人工智能与机器人研究所,挑战特级象棋大师卜凤波,东北大学人工智能与机器人研究所,聘请卜大师为棋天大圣顾问,东北大学人工智能与机器人研究所,ComputerOlympiad11夺冠,2006年5月28日-6月3日,意大利都灵,东北大学人工智能与机器人研究所,ComputerOlympiad11夺冠,东北大学人工智能与机器人研究所,中国机器博弈活动计划,2007年全国计算机博弈锦标赛将在重庆工学院举行时间初步确定在2007年10月上旬，占用部分十一长假比赛内容初步确定为：中国象棋；五子棋；六子棋；9路围棋；围棋选拔中国象棋计算机博弈锦标赛的前x名作为智能机器一方与中国象棋的x名大师级高手进行中国象棋人机大战举行全国机器博弈学术研讨会，出版论文集,东北大学人工智能与机器人研究所,征文范围,机器博弈相关理论的研究进展；中国象棋机器博弈关键技术研究；中国象棋与国际象棋博弈技术对比；中国象棋博弈程序的最新成果；五子棋、六子棋、围棋等计算机博弈研究成果；机器博弈研究对普通科学的影响；社会科学中的机器博弈；人类弈棋的认知过程研究；基于网络的棋类博弈问题研究；如何普及机器博弈相关理论与技术；机器博弈应用案例分析；其他与机器博弈相关的知识介绍与成果。,东北大学人