人工智能与三盘棋.ppt

人工智能与三盘棋
人工智能概论
棋类游戏自古以来就是人类智慧的象征，受众面广泛，而且棋类游戏规则清晰，胜负容易评估，因此每一次人机对弈都会引起公众的极大关注，并推动人工智能技术的快速发展。
西洋跳棋
1956年2月24日，亚瑟·萨缪尔的下棋程序(在IBM 704上)战胜康涅狄格州的西洋跳棋冠军。IBM的股票一夜暴涨了15个点。
1962年6月12日，在IBM 7090晶体管计算机上（内存仅为32k）战胜了当时全美排名第四的棋手罗伯特·尼雷(R．W．Nealey)。
1994年，人工智能程序第一次战胜了人类西洋跳棋世界冠军马里恩·廷斯利(Marion Tinsley)。
2007年人工智能程序切努克(Chinook)诞生了，到目前为止人类在西洋跳棋项目上永远无法击败它，最多打成平手。
亚瑟·萨缪尔
马里恩·廷斯利
一项始于公元前3000年，比象棋还要古老的游戏——西洋跳棋(Checkers)
意义：
萨缪尔跳棋程序不仅在人工智能领域产生了重大影响，还影响到整个计算机科学的发展，早期计算机科学研究认为，计算机不可能完成事先没有显式编程好的任务，而萨缪尔跳棋程序否证了这个假设。
1956年，萨缪尔应约翰·麦卡锡（John McCarthy，“人工智能之父”，1971年图灵奖得主）之邀，在标志着人工智能学科诞生的达特茅斯会议上介绍这项工作，萨缪尔发明了“机器学习”（即不需要显式地编程，让机器具有学习的能力）这个词，将其定义为“不显式编程地赋予计算机能力的研究领域”。
塞缪尔被称为“机器学习之父”
萨缪尔的工作是早期AI的一个里程碑，其工作中强化学习与对抗学习的思想至今仍然是AI程序的核心算法。
“下西洋跳棋有什么了不起？哪天在国际象棋棋盘上赢了世界冠军，那才叫人工智能。”
随着PC的普及，每台个人电脑都可以运行一个水平相当高的西洋跳棋程序，会下棋的计算机逐渐褪去了光环。人们开始怀疑西洋跳棋程序的智能程度，认为它只不过是按事先编写的搜索策略一步步找到最佳走棋步骤而已。1996年2月10日，超级电脑深蓝首次挑战国际象棋世界冠军卡斯帕罗夫，但以2-4落败。
卡斯帕罗夫6岁开始下棋，13岁获得全苏青年赛冠军，15岁成为国际大师，16岁获世界青年赛第一名，17岁晋升国际特级大师，在22岁时成为世界上最年轻的国际象棋冠军。1985年至2006年间曾连续23次获得世界排名第一。曾11次获得国际象棋奥斯卡奖。他被认为是有史以来最强的棋手之一。在20多年的职业生涯中，卡斯帕罗夫保持世界头号棋手的地位长达20年之久。2005年3月11日在第九次夺得利纳雷斯国际象棋超级大赛冠军后，他宣布退役。
1997 年 5 月 11 日，加里·卡斯帕罗夫以 : （1胜2负3平）输给 IBM 的计算机程序 “深蓝”！
赛前，卡斯帕罗夫对自己另下了30万美元的赌注。
赛后，他希望IBM同意重赛，而且要提供更有利的环境。
意义：
人工智能发展史上的又一个里程碑。
深蓝在软件设计上采用了知识库结合搜索的方法。一方面，深蓝存储了100 年来几乎所有国际特级大师的开局和残局下法，利用知识库的思想帮助程序节省时间并得出合理的棋步。另一方面，深蓝采用的是α-β剪枝搜索算法，并采用规则的方法对棋局进行评价，大致思路是根据棋子的重要程度、棋子的位子、棋子之间的关系对棋局进行评价。
深蓝国际象棋AI程序汇聚了诸多人类国际象棋大师的知识与智慧，因此可以被认为是知识工程在计算机棋类博弈的经典应用。
但是，深蓝国际象棋AI的核心技术依然被认为是领域相关的，缺乏通用性。
尾声：
2001年，Deep Fritz 击败了卡斯帕罗夫、阿南德，并把除了克拉姆尼克之外的所有排名世界前十位的棋手横扫了一遍。
2002年，荷兰棋王范维利和 Rebel 进行了四局对抗赛。双方交错赢棋，最后打平。
同年，以色列名将斯米林对阵电脑国际象棋软件联队，八局中两胜六和，竟无一败绩，最后以 5：3 的比分取胜。
2002年10月，Deep Fritz 与世界冠军克拉姆尼克在巴林大战。最终比分 4：4。
2003年，卡斯帕罗夫两次接受了电脑的挑战：先是在年初于纽约与 Deep junior 下成 3 比 3 平，11月，还是纽约，对垒 Deep Fritz，双方以 2 比 2 握手言和。　　
同年，曾进