机器博弈

当Game遇到Computer徐长明东北大学秦皇岛分校电子信息系2010.04.11提纲•机器博弈概述•此次竞赛规则的补充•机器博弈的关键技术•博弈系统的设计与实现•相关资料机器博弈概述•当人类遇到了Game，人类骄傲地发现没有任何其它地球动物懂得此道•人类发明的工具不断发展肌肉和四肢的延伸。刀、釜、锹、蒸汽机…感知的延伸。电话、电视、无线电…大脑的延伸。计算机…•计算机在一定程度上解放了人脑，能说它具有智能么？•在1956年，人工智能学科诞生。•人工智能的先驱曾经考虑：计算机能下得一手好棋么，能在下棋方面超越人么？•Game遇到了计算机——ComputerGames•机器博弈（ComputerGames，CG）计算机下棋、计算机打牌，属于人工智能研究的范畴ComputerChessComputerChineseChessComputerGoComputerConnect6…•这里，Game有双重涵义游戏博弈•近几十年来，机器接二连三地打破了人类的智慧神话：1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”，思考速度每秒200步。1973年，国际象棋程序CHESS4.0诞生，成为未来程序的基础。1983年，KenThompson开发的国际象棋机器BELLE，成为第一个达到国际象棋大师水平的下棋机器。1988年，卡内基梅隆大学研究的国际象棋计算机——“深思”击败了丹麦特级大师拉尔森。1989年，“深思”每秒思考速度达200万步，但在与世界棋王卡斯帕罗夫进行的“人机大战”中，以0比2败北。1993年，“深思”二代击败了丹麦国家队，并在与世界优秀女棋手小波尔加的对抗中获胜。1996年，IBM“深蓝”在向卡斯帕罗夫的挑战赛中，以2比4败北。1997年，由1名国际特级大师，4名电脑专家组成的IBM“深蓝”小组研究开发出“更深的蓝”。它通过安装在RS／6000S大型计算机上的256个专用处理芯片，可以在每秒钟内计算2亿步，并且存储了百年来世界顶尖棋手的10亿套棋谱。最后，它以3.5比2.5击败卡斯帕罗夫。在2006年，以“浪潮天梭”服务器为载体的东北大学“棋天大圣”——NEUCHESS与中国象棋特级大师许银川之间展开了巅峰对决，最终以两战皆和告终。赛后，许银川说：“电脑一步可以算十几个变化，而我只能凭借经验和理解与它对抗”。还慨叹：“和计算机下棋压力很大，可以说暗潮汹涌、惊心动魄。”著名的科学家和专家当前机器博弈的发展水平•当前各种棋牌类游戏的机器博弈的水平在西洋跳棋、五子棋等棋类中，计算机已经与上帝（假设上帝除了不能修改棋类规则外，无所不能）的水平完全相同。•五子棋15*15棋盘；黑、白双方；黑先；已证明黑必然可胜。在国际象棋、中国象棋、奥赛罗、西洋双陆棋等棋类中，普遍认为机器全面超越了人类最顶尖的高手。在扑克、桥牌中，机器具备一定水平，但与人类顶尖高手尚有差距。在围棋方面，机器尚不及人类初段选手。•成绩与挑战并存机器博弈对科学的促进作用•TD学习方法诞生于Samuel的西洋跳棋程序中，该方法在天气预报、股市预测、机器人等方面应用广泛。–早在1959年，Samuel的西洋跳棋程序采用TD学习方法，打败了一名州冠军，引起了巨大轰动。•李开复的语音识别研究为了验证统计学习的效果，李开复以奥赛罗（Othello）为实验对象。他在奥赛罗程序中，采用了统计学习方法对估值函数的参数进行调整。李把该方法应用到语音识别中，识别准确率大幅提高。•1988年奥赛罗程序击败世界冠军第1盘:56:8第2盘:世界冠军弃权“没有办法走下去!!”•在2006年，法国国家实验室将Monte-Carlo方法和UCB1算法应用到围棋程序的博弈树搜索中——UCT算法。结果ComputerGo的水平被向前推进了一大截。•该方法改善了19路和9路围棋的水平，特别是9路围棋。人们预期在不久的将来，计算机将在9路围棋上战胜人类。•围棋机器博弈的研究在世界范围内已经成为热点，也许更优秀的新方法就要诞生…此次竞赛的目标•现实目标：–将兴趣和专业技能结合起来，将其作为一个有趣的实践平台。–实现一个机器博弈程序的编程规模适中（几百行~几万行不等），但充满挑战。有利于发现问题，并运用所学知识解决问题。–促进良好的学习氛围和研究氛围。•理想目标：–在国内竞赛中，获得良好成绩；–在国际竞赛中，获得良好成绩。此次竞赛规则的补充•竞赛的方式——人工操作两个对战程序分别运行于两台不同的机器上；两台机器间没有网络连接；竞赛的双方各出一名操作员，操作本方的程序，两个操作员肩负起程序间通讯（人工通讯）的作用；•要求：–显示器的摆放应有利于对方操作员看到；–如果没有可视化界面，仅有控制台程序，操作员有义务协助对方理解程序思考结果的涵义（着法的涵义）；–正在竞赛时，不得更换竞赛程序，也不得人为调整程序参数。机器博弈的关键技术•引擎程序的主要组成部分–数据结构–着法生成–博弈树搜索–局面估值–开局库和残局库此次竞赛涉及的博弈问题•二人博弈博弈的双方分别称为MAX和MIN•零和博弈博弈的最终结果之和为零•完全信息或非完全信息完全信息博弈：一字棋、点格棋、六子棋、亚马逊、九路围棋等不完全信息博弈：幻影围棋等•以中国象棋为例棋盘上的位置编码091929394959697989081828384858687888071727374757677787061626364656667686051525354555657585041424344454647484031323334353637383021222324252627282011121314151617181001020304050607080兵种编码兵种红帅红车红马红炮红士红相红兵无子编码１２３４５６７０兵种黑将黑车黑马黑炮黑士黑象黑兵编码－１－２－３－４－５－６－７棋子编码编码12345678910111213141516棋子黑将黑车黑马黑炮黑士黑象黑兵编码17181920212223242526272829303132棋子红帅红车红马红炮红士红相红兵棋盘状态的表示（1）行向路向0235616532000000000040000040707070707000000000000000000707070707040000040000000000235616532BS记录棋盘中各个位置上的兵种分布状况棋盘状态的表示（2）024108191153000000000060000070120130140150160000000000000000002802903003103202200000230000000000182026241725272119MS记录棋盘中各个位置上的棋子分布状况棋盘状态的表示（3）记录棋盘中各棋子所处的位置ChessmanIndex[33]={INVALID,49,9,89,19,79,17,77,49,59,29,69,6,26,46,66,86,40,0,80,10,70,12,72,30,50,20,60,3,23,43,63,83}；着法的表示•着法算子的运算功能：提-动-落-吃•提址——from即此着的出发位置；•动子——moved（chessmanmoved）即走动的棋子；•落址——to即着法的到达位置；•吃子——killed（chessmanCaptured）即吃掉的棋子。•对着法的要求：合法性、完整性、有序性killedtomovedfromq着法生成•着法生成就是根据当前局面，生成合法的着法，供搜索算法访问。•将着法生成不断地应用到各个儿子结点，便可得到博弈树局面（轮MAX走棋）局面（轮MIN走棋）着法（MAX方）MAXMINMAXMIN图例：着法（MIN方）博弈树的表示•据估算，从初始局面开始，国际象棋的完整博弈树约有10120个节点；•宇宙中粒子数目估计为1075左右。局面评估函数•在难以判断输赢的情况下识别棋局的好坏，可行的办法就是对局面进行量化。•通过为棋局“打分”，评判棋局的好坏。•由于评估需要大量的象棋知识，仁者见仁，智者见智；•评估函数的设计便成为机器博弈中最为人性化和模糊化的部分。•用函数F(v)表示局面v的估值。搜索算法•若总是把即将做出决策（必须选择一个策略）的一方称为MAX方，则任何博弈树搜索问题都可以归结为：寻找MAX方最优（近优）策略的过程。•在有限深度的条件下，处于最大深度的结点称为叶结点，在叶结点处要执行估值函数，从而得到叶结点优劣程度的量化。•极大极小搜索MAXMAXMIN5298761431244极大极小值搜索伪代码1intmin_max(POSpos,intdepth){2//处理递归出口3…45if(Maxnode)6current=-INFINITE;7else8current=+INFINITE;910MoveList=GenAllMove(pos);//着法生成1112while(m=GetNextMove(MoveList)){13MakeMove(m);14val=min_max(child(pos,m),depth-1);15UnmakeMove(m);1617if(Maxnode){18current=max(current,val);19}else{20current=min(current,val);21}22}//end_while23returncurrent;24}负极大值算法（NegaMaxSearch）•此时需要特别注意的则是，如果叶节点轮到MAX方走棋，评估函数返回MAXSideValue-MINSideValue；如果是MIN方走棋，则返回MINSideValue-MAXSideValue。•另外，由于负极大值计算等价于“Min搜索”，所以这里只进行β剪枝，非常有利于编程实现和提高搜索速度。12max,,nFvFFFvvvMAXMAXMIN45682434Alpha剪枝（1）由此产生最佳路径和最佳着法α=4Alpha剪枝发生在取极大的过程中MAXMAXMIN13682154Alpha-剪枝（2）7491224由此产生最佳路径和最佳着法α=4剪枝效果差别很大•不难发现，和最佳着法关系密切•什么是最佳着法？•怎样找到最佳着法？（1）（2）Beta剪枝（1）174298MAXMINMIN77由此产生最佳路径和最佳着法β=7Beta剪枝发生在取极小的过程中Beta剪枝（2）835791MAXMINMIN8426由此产生最佳路径和最佳着法448β=4Beta剪枝和Alpha剪枝具有同样规律剪枝效果与最佳着法的位置密切相关与博弈树展开的顺序密切相关（1）（2）需要指出的是•Alpha-Beta剪枝是根据极大-极小搜索规则的进行的，虽然它没有遍历某些子树的大量节点，但它仍是蛮力搜索。•Alpha-Beta剪枝技巧的发现，一下便为博弈树搜索效率的提高开创了崭新的局面。•Alpha-Beta搜索•是一种基于剪枝（cut-off）的深度优先搜索（depth-firstsearch）。•将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；•将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。负极大值Alpha-Beta搜索伪代码1intnega_alpha_beta(intalpha,intbeta,intdepth){2intval;34//处理递归出口5…67GenAllMove();//着法生成89while(m=GetNextMove()){10MakeMove(m);11val=-nega_alpha_beta(-beta,-alpha,depth-1);12Unma