徐心和 东北大学人工智能与机器人研究所 xuxinhe@gmail.com 中国象棋人机大战 与机器博弈原理 徐心和 东北大学人工智能与机器人研究所 xuxinhe@gmail.com 2006.10 东北大学人工智能与机器人研究所.

Presentation on theme: "徐心和 东北大学人工智能与机器人研究所 xuxinhe@gmail.com 中国象棋人机大战 与机器博弈原理 徐心和 东北大学人工智能与机器人研究所 xuxinhe@gmail.com 2006.10 东北大学人工智能与机器人研究所."— Presentation transcript:

1 徐心和 东北大学人工智能与机器人研究所 xuxinhe@gmail.com
中国象棋人机大战 与机器博弈原理 徐心和 东北大学人工智能与机器人研究所 东北大学人工智能与机器人研究所

2 主要内容 浪潮杯首届中国象棋人机大战 机器博弈的艰苦历程 中象机器博弈的关键技术分析 棋局表示 着法生成 评估函数 博弈搜索 系统开发
积极投入机器博弈的滚滚洪流 东北大学人工智能与机器人研究所

3 浪潮杯首届中国象棋人机大战 从AI创立50周年说起 1956年美国达特茅斯(Dartmouth )大学 以麦卡西为首的十位年轻学者
AI-Artificial Intelligence 从此开始了人工智能研究的新纪元 人工智能发展的道路并不平坦 如今，AI的研究已经硕果累累 什么是人工智能？ 东北大学人工智能与机器人研究所

4 人类智能的理解与机器实现 人类（生物）智能包括哪些？ 感知 思维（逻辑思维、形象思维、灵感思维） 动作（技巧） ……
人工智能举例：机器视觉、语音识别、文字识别、机器翻译、专家系统、神经网络、模糊逻辑、知识挖掘…… 机器人是人工智能的集中表现 东北大学人工智能与机器人研究所

5 北京-庆祝AI 50年 科技活动旬 中国科技会堂——国际学术(ICAI’06 )会议 中国科技馆——全国首届智能科技成果与产品博览会
浪潮杯首届全国计算机博弈锦标赛 2006全国机器博弈学术研讨会 浪潮杯首届中国象棋人机大战 人脑对电脑的巅峰对决 东北大学人工智能与机器人研究所

6 全国机器博弈锦标赛 以前仅在局部地区举行过中国象棋的计算机比赛——台湾每年都有；
ICGA COMPUTER OLYMPIAD 国际计算机（棋类）奥林匹克竞赛已经举办过11届，有中国象棋的比赛项目； 在大陆进行此类全国比赛今年是首届，浪潮集团冠名——浪潮杯； 今年仅有中国象棋的计算机比赛。 东北大学人工智能与机器人研究所

7 最高水平的参赛队 台湾：宝岛一号、兵芯 、深象 美国：梦入神机、神乎棋技 法国：谢谢大师
棋天大圣、象棋奇兵、象眼竞技、理治棋壮、棋乐无穷、棋之梦、将神传说、落花、青羽堂、天机、象棋ABC、象棋旋风 总计：18支代表队 缺席的高水平代表队：纵马奔流、棋海无涯 东北大学人工智能与机器人研究所

8 积分相等加赛2场 新老冠军的对决 东北大学人工智能与机器人研究所

9 决赛前5名 棋天大圣 象棋奇兵 象棋旋风 天 机 将神传说 东北大学人工智能与机器人研究所

10 记者招待会 引起各种媒体的广泛关注 东北大学人工智能与机器人研究所

11 浪潮天梭下战表 东北大学人工智能与机器人研究所

12 中国象棋人机大战 2006年8月9日 国家奥林匹克中心综合馆 东北大学人工智能与机器人研究所

13 浪潮天梭+全国锦标赛前5名 对阵5位象棋大师 左起：卜凤波、徐天红、柳大华、张强、汪洋 东北大学人工智能与机器人研究所

14 5位大师—全国最高水平 卜凤波 徐天红 张 强 柳大华 洋汪 东北大学人工智能与机器人研究所

15 现场掠影 东北大学人工智能与机器人研究所

16 国家奥体中心综合馆 棋天大圣挑战徐天红 东北大学人工智能与机器人研究所

17 东北大学人工智能与机器人研究所

18 对局结果 棋天大圣 ：徐天红 两和 象棋奇兵 ：卜风波 一胜，一和 象棋旋风 ：柳大华 两胜 天 机 ：张 强 一负，一和
棋天大圣 ：徐天红 两和 象棋奇兵 ：卜风波 一胜，一和 象棋旋风 ：柳大华 两胜 天 机 ：张 强 一负，一和 将神传说 ：汪 洋 一和，一负 电 脑 ：人脑 = 11 ：9 象棋特级大师、江苏象棋队高级教徐天红 国际特级大师、湖北象棋队高级教练柳大华 特级大师、辽宁队高级教练卜凤波 象棋大师、北京队教练张强 全国等级分排名第4的厦门象棋大师汪洋 东北大学人工智能与机器人研究所

19 柳大华“完败” 东北大学人工智能与机器人研究所

20 大师们谈感想 “虽然这次比赛规则上对人不利，在一定程度上影响了比赛结果。但是，我相信机器终将会战胜人，这是必然的趋势。”
东北大学人工智能与机器人研究所

21 东北大学人工智能与机器人研究所

22 紫禁城烽烟再起 素有“象棋第一人”之称全国排名第一的、31岁国际特级大师许银川 东北大学人工智能与机器人研究所

23 人机大战终极PK 东北大学人工智能与机器人研究所

24 2006年 8月 15日 北京香格里拉饭店 东北大学人工智能与机器人研究所

25 许银川赛后感 “能下成两和，是我意料之中的事情。一年之中有那么多比赛，这场对决，是我职业生涯中难忘的一幕。”
“棋天大圣”在本场比赛中表现的水平，可与大师相媲美。整场比赛很艰苦，但计算机的思维带给我非常大的开拓性启示。 “可以用暗潮汹涌，惊心动魄来概括。与计算机下棋真的很累，因为我在明处，它在暗处，不知道它想的是什么。” 东北大学人工智能与机器人研究所

26 机器博弈的艰苦历程 东北大学人工智能与机器人研究所

27 人机博弈 历史久远 1769年第一台“象棋机器”诞生 这不是我们 讨论的范畴 我们感兴趣 计算机博弈 属人工智能
1769年，一位凶牙利工程师向奥地利女王献上了一台名“特克”的下棋机：一个身着土耳其长袍的机器人特克，坐在放着棋盘的柜子后向人挑战；柜子可以打开让人观察，里面安装着齿轮、杠杆之类的机械。 令人不解的是，就这么个破玩意，竟然具有象棋大师般高超的棋艺，来自许多国家的宫庭棋师们在它面前纷纷落马。据说，就连俄国女王叶卡捷琳娜和法国皇帝拿破仑都曾是它的手下败将。这台机器后来巡游到了美国，仍然战无不胜，所向披靡，直到1827年，才被一位89岁的棋手卡洛尔击败。 疑惑不解的人们越来越把疑点集中到了与机器“特克”结伴同行的象棋冠军施莱伯格身上。1834年，终于有人发现秘密：“特克”下棋时，这位先生就躲在柜子里面。 In 1769 the Hungarian engineer Baron Wolfgang von Kempelen built a chess playing machine for the amusement of the Austrian Queen Maria Theresia. It was a purely mechanical device, shaped like a Turk. Naturally its outstanding playing strength was supplied by a chess master cleverly hidden inside the device. The machine was a fake. 我们感兴趣 计算机博弈 属人工智能 东北大学人工智能与机器人研究所

28 计算机博弈的艰苦历程 早在1958年，IBM推出的取名“思考”的IBM704就成为了第一台与人类进行国际象棋对抗的计算机，当时它一秒钟可以进行200步的运算，但是在人类棋手面前被打得丢盔卸甲。 而许多科学家却对此欢欣鼓舞，诺贝尔经济学奖和杰出科学贡献奖的获得者赫伯特·西蒙教授，早在1957年就预测说：“计算机在10年内将成为世界的国际象棋冠军！” 东北大学人工智能与机器人研究所

29 计算机博弈的艰苦历程 10年过去，不要说战胜世界冠军，就连与最“臭”的专业象棋选手对阵，电脑也都战战兢兢。
为了给电脑棋手打气，麻省理工学院的教授弗雷德金甚至不惜重金悬赏，设立10万美金的“弗雷德金奖”，声明这笔巨款将奖给第一个战胜世界国际象棋冠军的电脑程序设计者。 东北大学人工智能与机器人研究所

30 计算机博弈的艰苦历程 1980年，第一台真正意义上的象棋机器“Belle”在贝尔实验室诞生 由数百芯片组成 造价仅为２万美元
每秒可计算18万步 年间 为世界计算机象棋冠军 计算机学者 Ken Thompson 东北大学人工智能与机器人研究所

31 国际象棋计算机博弈简史 1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”，思考速度每秒200步。
60年代中期，科学家德里夫斯断言，计算机将无法击败一位年仅10岁的棋手。 　　 1973年，国际象棋软件4.0被开发出来，这是未来程序的基础。 1979年，国际象棋软件4.9达到专家级水平。 　　 1981年，CRAYBLITZ新的超级计算机拥有特殊的集成电路，预言将可在1995年击败世界棋王。 　　 1983年，BELLE AT＆T开发了国际象棋硬件，达到了大师水平。 东北大学人工智能与机器人研究所

32 国际象棋计算机博弈简史 80年代中期，皮兹堡的CARNEGIEMELLON大学开始研究世界级的国际象棋计算机程序。
1987年，“深思”首次以每秒钟75万步的思考速度露面，它的水平相当于拥有国际等级分为2450的棋手。 　　 1988年，“深思”击败丹麦特级大师拉尔森。 　　 1989年，“深思”已经有6台信息处理器，每秒思考速度达200万步，但在与世界棋王卡斯帕罗夫进行的“人机大战”中对阵以0比2败北。 　　 1990年，“深思”第二代产生，使用IBM的硬件，吸引了前世界棋王卡尔波夫与之对抗。 　　 1991年，“弗里茨”问世。 东北大学人工智能与机器人研究所

33 国际象棋计算机博弈简史 1993年，“深思”二代击败了丹麦国家队，在与世界优秀女棋手小波尔加的对抗中获胜。
1993年，“深思”二代击败了丹麦国家队，在与世界优秀女棋手小波尔加的对抗中获胜。 　　 1995年，“深蓝”更新程序，新的集成电路将其思考速度达到每秒300万步。 　　 1996年，“深蓝”在与卡斯帕罗夫的挑战赛中，以2比4不敌卡斯帕罗夫。 　　 1997年，“超级深蓝”开发出了更加高级的“大脑”，4名国际大师参与IBM的挑战小组为电脑与卡斯帕罗夫重战出谋划策，最后“超级深蓝”以3.5比2.5击败了卡斯帕罗夫。 卡斯帕罗夫要求重赛，但没有得到回应。 东北大学人工智能与机器人研究所

34 国际象棋计算机博弈简史 1999年，“弗里茨”升级为“更弗里茨”。
1999年，“弗里茨”升级为“更弗里茨”。 　　 2001年，“更弗里茨”更新了程序，击败了除了卡斯帕罗夫和阿南德，以及克拉姆尼克之外的所有排名世界前十位的棋手。 　 2002年10月，“更弗里茨”与克拉姆尼克在巴林进行“人机大战”，思考速度为每秒600万步。双方战成4比4平。　 2003年1～2月“更年少者”与卡斯帕罗夫举行人机对抗，双方3比3战平。 东北大学人工智能与机器人研究所

35 “深蓝之父”——许峰雄博士 出生于中国台湾省 现年47岁 1980年毕业于台湾大学电机系，获硕士学位
1989年获得美国卡内基梅隆大学计算机科学博士学位 东北大学人工智能与机器人研究所

36 “深蓝之父”——许峰雄博士 1985年，许峰雄博士开始了“人机博弈”的研究
1988年，研制出超级计算机 “深思”，首次战胜人类国际象棋特级大师本特·拉尔森。 1989年世界计算机象棋冠军 同年加入IBM研究院开始“深蓝”项目的研究 1991年，成为首位荣获美国计算机协会 Grace Murray Hopper奖的亚裔科学家 1991年 ACM国际计算机象棋大赛奖 1994年 ACM国际计算机象棋大赛奖 1996年 IBM优秀技术奖 东北大学人工智能与机器人研究所

37 “深蓝之父”——许峰雄博士 1997年5月11日，推出超级计算机 “深蓝”以3.5比2.5的总比分击败国际象棋特级大师卡斯帕罗夫；
为此，获得IBM奖，获得Fredkin（弗雷德金）奖； 1999年，Funnov Inc. 公司总裁； 2000年，康柏研究院 (惠普研究院) 技术负责； 2003年4月17日正式宣布加盟微软亚洲研究院，任高级研究员。 东北大学人工智能与机器人研究所

38 世界棋王——卡斯帕罗夫 出生于阿塞拜疆 现年45岁 自1984年以来一直稳居世界第一的位置
目前他仍被国际象棋协会排在克拉姆尼克之前，位居第一。 他被许多国际象棋专家认为是历史上最伟大的棋手。 在国际象棋界近乎成了神话般的人物。 东北大学人工智能与机器人研究所

39 世界棋王——卡斯帕罗夫 1989 vs Deep Thought 2.0 : 0 1995 vs Junior 1.5 : 0.5
1995 vs Fritz : 0.5 1996 vs Deep Blue : 2.0 1997 vs Deep Blue : 3.5　（更深的兰） 2003 vs Deep Junior : 3.0 2003 vs X3D-Fritz : 4.0 　须知：更弗里茨比当年“深蓝”运算能力快56倍 　　　　（奔4、2.8兆赫、4G内存） 东北大学人工智能与机器人研究所

40 世界棋王——卡斯帕罗夫 “这不仅仅是一场国际象棋比赛，更是一场赌博：人脑和电脑的较量。”
卡斯帕罗夫认为：“有些时候，电脑下得就像神一样完美，但有些时候，它还得向人类多多学习。” 东北大学人工智能与机器人研究所

41 中国首次国际象棋“人机大战” 2004年6月8日和12日的两场比赛
“紫光之星”采用了目前最快的7200转硬盘，最新ATIM 11,128M显存等业界顶级笔记本配置。(2600分左右 ) 中国极负盛名的国际象棋特级大师、 “美女棋后”诸宸(2493分 ) 紫光2:0获胜 关键: 运行了最先进的国象软件 东北大学人工智能与机器人研究所

42 中国象棋计算机博弈历史 中国象棋的计算机博弈却开展的不尽人意，成了“被爱情遗忘的角落”。
缺少学者的关注，寥寥无几的参与者，匮乏的参考文献，沉寂的计算机博弈氛围，使得中国象棋的计算机博弈在中国内陆难有作为，只是成为一些商家的游戏软件和教学载体。 这便是当前我们所面临的艰难局面。 应该说，在台湾还是开展得很不错。 东北大学人工智能与机器人研究所

43 中国象棋的挑战性 国际象棋棋盘8行8列总计64格，中国象棋10行9列总计90个交点，显然中国象棋的运子空间更大。
相比之下，中国象棋的着法更为特殊（如蹩马脚、压象眼等），棋局变化也更加复杂。 随着计算机博弈在Othello、Checker和国际象棋三种棋类上的成功，全世界的学者又把目光投到更为复杂的中国象棋(Chinese Chess)、日本将棋（Shogi）、围棋(Go)上面。 东北大学人工智能与机器人研究所

44 几种棋类的空间复杂度及树的复杂度对比 表中的数字为复杂度的自然对数值。 显然，这更是对中国学者提出的严峻挑战。 棋类 空间复杂度 树的复杂度
Chess 50 123 Chinese chess 52 150 Shogi 71 226 Go 160 400 表中的数字为复杂度的自然对数值。 显然，这更是对中国学者提出的严峻挑战。 东北大学人工智能与机器人研究所

45 中象机器博弈的关键技术分析 积极投入机器博弈的滚滚洪流 东北大学人工智能与机器人研究所

46 开展机器博弈活动的目的意义 人机大战是对计算机科学与系统的有力挑战 象棋博弈是人工智能学科的“果蝇” 人机大战可以动员广大科技青年的创新热情
象棋博弈有利于计算机知识的普及与提高 历史性的较量为IT公司提供了绝好的商机 有力促进国粹——中国象棋的发展与提高 东北大学人工智能与机器人研究所

47 东北大学棋天大圣的成长历程 2003年10月正式启动机器博弈课题 搜集资料、了解动态、学习相关文献 2004年初，开始组建队伍和初步开发工作
2004年5月提出目标——向中国象棋冠军挑战 正式成立“棋天大圣”代表队 聘请许峰雄博士为顾问 正式开始全面开发工作 2005年5月开发出比赛系统，校内亮相 2005年9月参加世界计算机（棋类）奥赛 东北大学人工智能与机器人研究所

48 启动 ——与深蓝握手（ ） 东北大学人工智能与机器人研究所

49 校内发动……发起挑战（ ） 东北大学人工智能与机器人研究所

50 聘请许峰雄博士报告、名誉教授、顾问 （ ） 东北大学人工智能与机器人研究所

51 第10届世界计算机（棋类）奥赛 2005年9月3-9日在台北举行
东北大学人工智能与机器人研究所

52 棋天大圣参加世界计算机（棋类）奥赛 东北大学人工智能与机器人研究所

53 棋天大圣勇夺世界第三 14支代表队双循环赛 棋天大圣战罢： 18 胜 6 平 2 负 积 21 分 冠军 象棋奇兵 亚军 棋海无涯
18 胜 6 平 2 负 积 21 分 冠军 象棋奇兵 亚军 棋海无涯 东北大学人工智能与机器人研究所

54 VS 中国象棋人机大战 时间：11月2日8:30-10:00 地点：听涛5号会议室 东北大学 计算机博弈代表队 棋天大圣 武汉理工大学
中国象棋大师 周熠 VS 时间：11月2日8:30-10:00 地点：听涛5号会议室 中国人工智能学会 机器博弈专业委员会 2005年10月30日 东北大学人工智能与机器人研究所

55 人机对弈（左机：王骄，右机：周熠） 东北大学人工智能与机器人研究所

56 比赛现场 东北大学人工智能与机器人研究所

57 接见双方选手 (左起: 棋天大圣对长王骄，徐心和，周熠）
接见双方选手 (左起: 棋天大圣对长王骄，徐心和，周熠） 东北大学人工智能与机器人研究所

58 挑战辽宁省女子冠军李晓春 （ ） 东北大学人工智能与机器人研究所

59 挑战辽宁省男子冠军丰鹤 （ ） 东北大学人工智能与机器人研究所

60 挑战特级象棋大师卜凤波 东北大学人工智能与机器人研究所

61 聘请卜大师为棋天大圣顾问 东北大学人工智能与机器人研究所

62 Computer Olympiad 11 夺冠 2006年 5月28日-6月3日 意大利都灵 东北大学人工智能与机器人研究所

63 Computer Olympiad 11 夺冠 东北大学人工智能与机器人研究所

64 中国机器博弈活动计划 2007年全国计算机博弈锦标赛将在重庆工学院举行 时间初步确定在2007年10月上旬，占用部分十一长假
比赛内容初步确定为：中国象棋；五子棋；六子棋； 9路围棋；围棋 选拔中国象棋计算机博弈锦标赛的前 x 名作为智能机器一方与中国象棋的 x 名大师级高手进行《中国象棋人机大战》 举行全国机器博弈学术研讨会 ，出版论文集 东北大学人工智能与机器人研究所

65 征文范围 机器博弈相关理论的研究进展； 中国象棋机器博弈关键技术研究； 中国象棋与国际象棋博弈技术对比； 中国象棋博弈程序的最新成果；
五子棋、六子棋、围棋等计算机博弈研究成果； 机器博弈研究对普通科学的影响； 社会科学中的机器博弈； 人类弈棋的认知过程研究； 基于网络的棋类博弈问题研究； 如何普及机器博弈相关理论与技术； 机器博弈应用案例分析； 其他与机器博弈相关的知识介绍与成果。 东北大学人工智能与机器人研究所

66 长远（2008年-） 1. 申办并积极落实2008年机器博弈大赛和大会在北京举办： The 13th Computer Olympiad
1. 申办并积极落实2008年机器博弈大赛和大会在北京举办： The 13th Computer Olympiad The 14th Advance in Computer Games 2. 坚持每年举行培训班、研讨班，做好普及与提高工作 3. 坚持每年举行全国大赛和学术研讨会 4. 坚持每年举行各种类型的人机大战 5. 积极开展其它棋类的计算机博弈活动——围棋尽快赶上国际先进水平 6. 在高校范围内积极开展机器博弈活动 东北大学人工智能与机器人研究所

67 E-mail: computergames@ise.neu.edu.cn
机器博弈将会给你带来 更多的机会 谢 谢　！ 东北大学人工智能与机器人研究所

68 遗传学与果蝇 果蝇比苍蝇小、形象较可爱。专门在水果上飞来飞去，生命力极强，而且繁殖很快。
把果蝇关在牛奶瓶里，再加些香蕉之类的水果，他们便“代代相传”。 果蝇20多天繁殖一代，容易在短期内出现突变性状，所以果蝇正符合遗传学研究的需要。 摩尔根和他的学生十年如一日。长期观察突变性状。终于硕果累累。 由于摩尔根选中了果蝇作为实验对象，1933年，摩尔根获得了诺贝尔生理学和医学奖。 东北大学人工智能与机器人研究所

69 遗传学与果蝇 比如，摩尔根确定了基因在染色体上。 1910年前后，摩尔根发现“伴性遗传”。
后来他和其助手又提出“连锁”基因概念、发现基因重组现象、作出果蝇的第一张染色体图… 摩尔根的工作使得经典遗传学进入顶峰时期。 在过去的将近一个世纪中，果蝇一直是遗传学家们应用最多的，用于探讨遗传学上怎样的改变可导致某种特定的生理特征产生。 遗传学通过研究果蝇取得了长足的进步 。 东北大学人工智能与机器人研究所

70 硬件进展神速 东北大学人工智能与机器人研究所