东北大学人工智能大作业

机器博弈(MachineGamePlaying)注：维基百科和百度百科中对机器博弈的介绍较少，如有错误请多指教。01关于机器博弈机器博弈的含义：机器博弈就字面意思理解，即机器参与到博弈的过程当中，这不仅包括机器与机器之间的博弈，也包括机器与人类之间的博弈。机器博弈的特征：智力竞技一一机器博弈过程中机器与对手之间存在着智力上的比拼，并以此区分胜负。机器博弈的目标：击败对手一一机器博弈涉及多个主体，其最后的结果为分出胜负，博弈双方的目标均为击败对手，02博弈问题的描述(以棋类游戏为例)博弈问题的形式化定义：博弈被定义为一个四元组：(Q,Co,s⑼,s⑼滇中：Cg={c}：博弈空间(棋局或博弈状态的集合)Co={o}：算子空间(操作或规则的集合)c(o)ECG：当前棋局或博弈状态(最初即开局).二c(g)-QG：胜局或博弈目标集合应用Co中的算子(操作或规则)对c⑻进行操作，使其有利于转换为胜局c⑼w£c⑼的过程称为博弈。博弈问题的三要素：c⑹和c◎以及O(1)操彳(又称规则或算子):

o:Qg4g或:c(j)=o(c(i))(c(i),c(j)三C，G；o:Qg4g或:c⑻EQG（机器当前面对的棋局）⑶k-步博弈树：基于c⑨的k-步博弈规划图03机器博弈举例一字棋与极大极小算法Max-Min博弈：Stepl.生成k-步博弈树Max代表机器一方/Min代表敌方设Max面对的当前棋局为c⑼，以c⑼为根，生成k-步博弈树Step2.评估棋局（博弈状态）估价函数：为特定的博弈问题定义一个估价函数est（c）,用以评估k-步博弈树叶节点对应的棋局c^Qg,est（c）的值越大，意味着棋局c对Max越有利。Step3.回溯评估极大极小运算：由叶节点向根节点方向回溯评估，在Max处取最大评估值（或运算），在Min处取最小评估值（与运算）。注：Max按取最大评估值的方向行棋Step4.递归循环Max行棋后，等待Min行棋；Min行棋后，即产生对于Max而言新的当前棋局c（o）;返回Step1.,开始下一轮博弈

一字棋:设有3^3棋格，Max与Min轮流行棋，黑先白后，先将3颗棋子连成一线的一方获胜。一字棋博弈空间：共有9!种可能的博弈状态r»|_io甸@。。网口回把।。冏o阳;yc(g)=JTl®on®\wn®rn»rftI〔算意骅春郭泰祥J/一字棋算子空间：博弈规则集合0={&*#!@人###+&%$$$}一字棋博弈目标集合(对Max而言)：定义估价函数：est(c)(1)对于非终局的博弈状态c估价函数为：est(c)=(所有空格都放上黑色棋子之后，3颗黑色棋子连成的直线总数)-(所有空格都放上白色棋子之后，3颗白色棋子连成的直线总数)。例如：c=贝［Jest(c)=3-2=1箕_(2)若c是Max的胜局，则：est(c)=+0c例如：c=⑶若c是Min的胜局，则：est(c)=6例如：c=(2)牡林群林朴(-1)(0)(-1)(0)(-2)3.1.3Max-Min博弈过程：stepl.以c(o)(2)牡林群林朴(-1)(0)(-1)(0)(-2)3.1.3Max-Min博弈过程：stepl.以c(o)=为根，生成2-步博弈树:step2.评估博弈树叶节点对应的博弈状态Max酢##牡井件样step3.进行极大极小运算(Max-Min运算)Max按取最大评估值的方向行棋step4.等待Min行棋，产生新的c(o)返回stepl.五子棋机器博弈问题varmaxmin=function(board,deep){varbest=MIN;varpoints=gen(board,deep);//这个函数的作用是生成待选的列表，就是可以下子的Max_p'肿升甘壮洋小甘⑴(0)⑴(0)(-1)(0)(T)(0Max_p'肿升甘壮洋小甘⑴(0)⑴(0)(-1)(0)(T)(0空位for(vari=0;i<points.length;i++){varp=points[i];board[p[0]][p[1]]=R.com;〃尝试下一个子varv-min(board,deep-1);〃找最大值〃如果跟之前的一个好，则把当前位子加入待选位子Min书Z荐*71⑵।110H)if(v==best){bestPoints.push(p);)〃找到一个更好的分，就把以前存的位子全部清除if(v>best){best=v;bestPoints=[];bestPoints.push(p);)board[p[0]][p[1]]=R.empty;//记得把尝试下的子移除)varresult=bestPoints[Math.f100r(bestPoints.length*Math.random())];//在分数最高的几个位置中随机选择一个returnresult;)varmin=function(board,deep){varv=evaluate(board);//评价函数，这个函数返回的是对当前局势的估分。if(deep<=0||win(board)){returnv;)varbest=MAX;varpoints=gen(board,deep);for(vari=0;i<points.length;i++){varp=points[i];board[p[0]][p[1]]=R.hum;varv=max(board,deep-1);board[p[0]][p[1]]=R.empty;if(v<best){best=v;}}returnbest;}varmax=function(board,deep){varv=evaluate(board);if(deep<=0||win(board)){returnv;}varbest=MIN;varpoints=gen(board,deep);for(vari=0;i<points.length;i++){varp=points[i];board[p[0]][p[1]]=R.com;varv=min(board,deep-1);board[p[0]][p[1]]=R.empty;if(v>best){best=v;}}returnbest;}varmin=function(board,deep,alpha,beta){varv=evaluate(board);total++;if(deep<=0||win(board)){returnv;}varbest=MAX;varpoints=gen(board,deep);for(vari=0;i<points.length;i++){varp=points[i];board[p[0]][p[1]]=R.hum;varv=max(board,deep-1,best<alpha?best:alpha,beta);board[p[0]][p[1]]=R.empty;if(v<best){best=v;)if(v<beta){//AB剪枝ABcut++;break;))returnbest;)varmax=function(board,deep,alpha,beta){varv=evaluate(board);total++;if(deep<=0||win(board)){returnv;)varbest=MIN;varpoints=gen(board,deep);for(vari=0;i<points.length;i++){varp=points[i];b