博弈搜索.ppt

博弈搜索.ppt博弈搜索yinbaoyong@博弈(game)香农(Shannon)图灵(Turning)1957,Simon预言10年内出现打败国际象棋冠军的程序40年后深蓝打败卡斯帕罗夫博弈西洋跳棋1952,IBM,Samuel,1KHZ1990,Chinook,美国公开赛第二名。Tinsley博士,40多年的冠军,只输过3盘。第一次挑战,Tinsley博士输了两盘,但最终获胜1994,第二次挑战,Tinsley因健康原因退出比赛,Chinook成为世界冠军奥赛罗(Othello),也称翻转棋比国际象棋小的搜索空间1997,Logistello程序6比0击败人类冠军人类在翻转棋上无法与计算机较量博弈西洋双陆棋Tesauro开发的TD-GAMMON,稳定地排在世界前三桥牌1997,BridgeBaron,计算机桥牌赛冠军1998,GIB程序,人类标准桥牌世界冠军赛,第12名围棋分支因子≤361手谈和Go4++,10级,业余棋手的水平Gnugo和MoGo,在7X7的棋盘是完美的,在9X9的棋盘上相当于业余3段博弈国际象棋深蓝30个IBMRS/6000处理器:软件搜索480个定制的VLSI国际象棋处理器:行棋生成,树的最后几层的硬件搜索,,最高33亿每步棋最多生成300亿个棋局,常规搜索深度是14步评价函数使用的特征超过8000个使用了4000个棋局的开局手册,存有70万个大师级比赛棋谱使用大型数据库保存已解决的棋局,其中包括5个棋子的全部棋局和6个棋子的很多棋局2002,FRITZ程序挑战世界冠军Kramnik,战成平局中文网站:形式化状态:(局面,棋手)初始状态:(初始局面,棋手)例如:(象棋的初始布局,执红的棋手)动作算子:每一种合乎规则的移动目标测试:获胜的局面状态空间图博弈树博弈树:描述所有可能的对弈博弈树(双人、确定的、回合制)我的选择对手的选择选择结果效用值:用来度量收益的数值获胜为1,失败为-1,和为0获胜为+∞,失败为-∞,和为0结束时以你的收益为效用值v,例如“拱猪”博弈VS搜索最好的移动方式依赖于对手的移动不是寻找通往获胜局面的路径,而是寻找下一步的移动(希望能够达到获胜局面)特点:前提:零和博弈、信息完全、回合制无法预测对手行动试探对手每一种可能的行动时间有限必须近似解决方法搜索?深度优先?广度优先?A*算法?最优决策:极小极大搜索时间有限的对策:α-β剪枝、评估函数不完美的实时决策极小极大搜索确定性博弈的完美方法思路:移动到具有最大的“最小最大值”的局面 ==同最优秀的对手对弈时能够得到的最大收益双人博弈:3223