刚做完课设,发个热乎的。(小编感谢大傻叉提供这样的好文章)
语言不是我们要讨论的重点,当你真的需要研究使用何种语言的时候,语言不过是一种选择(机器码和汇编除外)

在本程序中使用到了博弈树,在看此文前最好先百度下博弈树,以免被此文误导。
博弈树被广泛应用到博弈类游戏的AI上。本人(BigIdiot)也不例外,毕竟用博弈树和不是用博弈树所产生的AI区别还是很大的。

博弈树使用时必须有个前提,双方都想赢。

由于双方都想赢所以他们都会走对自己最有利的棋(两面性,对自己最有利与对对方最不利)

A,B对弈

 

关于节点价值:

非叶子节点的价值由其子节点的价值总结得到。

叶子节点的价值由棋面估价方法产生。
A的角度上讨论

 

如果对棋面进行估价为Value(GetValue()实现)。对A越有利则Value越大,对B越有利则越小。

最后我们设定三个特殊值

MaxValue 此棋面表示A获胜。你可以给A获胜的棋面不同的值以表示赢的程度。但A获胜的棋面值必须大于A没有获胜的棋面

0         双方均势。最典型的是当产生平局时给的值

MinValue 此棋面表示B获胜。你也可以给B获胜的棋面不同的值以表示赢的程度。但B获胜的棋面值必须小于B没有获胜的棋面

显然当A走棋,A会走最终获得Value最大的棋

B走棋,B会走最终获得Value最小的棋

 

博弈树//以五子棋为例,解释可能不是很完善

以起始搜索棋面为根节点。

每个节点都是一个棋面。

每条从根节点到叶子节点的路径都是一种走法。

若一个节点的深度为n

n%2==0时表示归A走棋。则该节点的Value取其所有子节点Value的最大值。

n%2==1时表示归B走棋。则该节点的Value取其所有子节点Value的最小值。

 

博弈树的扩展

在五子棋的博弈中,每次可以走棋的情况是很多的。当棋面上有n个子时共有255-n种走法。这也导致也若要将所有的走法都扩展的话,可能4步就已经是极限了。所以在进行扩展是应该选择最好几个点进行扩展。这就需要另一个估价方法。能够返回一个点的Value(GetSeatValue()实现)

 

深度搜索

在博弈树的搜索中,通常使用深度优先搜索。

这样就可以一边扩展一边搜索。减小了内存空间的消耗。

而且使用深度搜索才能使用阿尔法-贝塔剪枝贝塔剪枝来减小时间的消耗。

 

阿尔法-贝塔剪枝

剪掉不会影响结果的子树,加快效率。

原理

如节点N轮到A走棋。N取子节点N1,N2,N3,N4Value的最大值

N1的值已经算出为N1Value

N2以扩展出节点N21,N22,N23,N24,N25

N21的值已经算出为N21Value

N21Value<N1ValueN22,N23,N24,N25的值不会影响N的值

证明:

min(N21,N22,N23,N24,N25)<=N21  --->   N2<=N21

N21<N1

--->N2<N1 --->max(N1,N2,N3,N4)==max(N1,N3,N4) -->N=max(N1,N3,N4)

也就是说,此时已经证明N2的值不会影响N的值,所以N2可以被剪枝

 

 

当了解了这些的时候我们就可以实现博弈树了

  1. int DepthCable(int depth)//深度收索,depth为当前搜索到的深度   
  2. {   
  3.     int seatValueList[][] = new int[WIDTH+1][3];//存储价值较高的点   
  4.     int x,y,camp,value,i;//x,y记录坐标,camp记录当前层由camp下棋后扩展得到的。value记录节点价值,i用于循环        并标记是否没有点可以扩展   
  5.     if(depth%2==1)//该层为this.camp下棋后的扩展层   
  6. {   
  7. //depthValue[]为全局变量,用于存储不同博弈深度的Value   
  8. //给博弈深度价值表的当前深度赋初值   
  9. //this.camp下棋后扩展的节点取最大值,赋值MINVALUE-1才能保证不遗漏结果   
  10.     depthValue[depth]=MINVALUE-1;   
  11.     camp=this.camp;//camp等于AI的阵营方   
  12.     }else  
  13.     {   
  14. //非this.camp下棋后扩展的节点取最小值,赋值MAXVALUE+1才能保证不遗漏结果   
  15.         depthValue[depth]=MAXVALUE+1;   
  16.          camp=-this.camp;//this.camp为AI的阵营   
  17.     }   
  18.     if(depth==this.depth)//深度限制,保证AI计算耗时的有限性   
  19.     {   
  20. //GetValue(camp);方法将返回当camp下棋时相对AI阵营的局面价值   
  21.         return GetValue(camp);   
  22.     }   
  23.         //  GetSeatValueList(camp)获取较有价值的几个点的坐标和value   
  24.         seatValueList = GetSeatValueList(camp);   
  25.     //扩展seatValueList中的节点,WIDTH为宽度限制   
  26.         for(i = 0 ; i < WIDTH && seatValueList[i][2] != 0 ; i++)   
  27.         {   
  28. //扩展节点seatValueList[i]   
  29. //获取扩展节点的坐标   
  30.         x=seatValueList[i][0];   
  31.         y=seatValueList[i][1];   
  32.          if(seatValueList[i][2] == MAXVALUE)//表示这步棋会导致游戏结束   
  33.         {   
  34. //当归AI下棋时AI胜利,反之对方胜利   
  35.             if(depth%2==1)   
  36.             {   
  37. //若AI下一步棋就能赢,则必下此点   
  38.     if(depth==1)   
  39.                 {   
  40. //seat[3]存储最后决定的坐标和价值   
  41.                     seat = new GetSeat(x,y,MAXVALUE);   
  42.                 }   
  43.                 return MAXVALUE;   
  44.             }   
  45.             return MINVALUE;   
  46.         }   
  47.         this.map[x][y]=camp;//改变棋面   
  48.         value=DepthCable(depth+1);//扩展节点并获取节点Value   
  49.         this.map[x][y]=0;//恢复棋面   
  50.     //与或运算和α-β剪枝   
  51.         if(depth%2==1)//与或计算的同时,使用了阿尔法-贝塔剪枝   
  52.         {   
  53.             if(value >= depthValue[depth-1])   
  54.             {   
  55.                 return value;   
  56.             }   
  57. //或节点取最大值   
  58.             if(value > depthValue[depth])   
  59.             {   
  60.                 depthValue[depth]=value;   
  61.             }   
  62.         }else  
  63.         {   
  64.             if(value <= depthValue[depth-1])   
  65.             {   
  66.                 return value;   
  67.             }   
  68. //与节点取最小值   
  69.             if(value < depthValue[depth])   
  70.             {   
  71.                 depthValue[depth]=value;   
  72.             }   
  73.         }   
  74.         /*当depth为1时,表示返回到第一层扩展的节点,取value最大的节点为最终结   果*/  
  75.         if(depth==1)   
  76.         {   
  77.             if(depthValue[1] > seat[2])   
  78.             {   
  79. //将节点价值为depthValue[1]坐标为(x,y)的节点存到最终节点中   
  80.                 seat = new GetSeat(x,y,depthValue[1]);   
  81.             }   
  82.         }   
  83.     }   
  84. //没有节点可以扩展表示游戏结束且为平局   
  85.     if(i==0)   
  86.     {   
  87.         return 0;   
  88.     }   
  89.     //返回与或运算后的depth-1层节点的价值   
  90.     return depthValue[depth];   
  91. }   

 

博弈树的应用确实会增加AI。但是AI的强弱(强指深度高,宽度恰当,耗时少)关键在于估价方法。估价方法可以说是AI的精髓。而且一个人的估价方法的高明度不仅仅取决于编程能力,还取决于对游戏本身的理解。同样编程能力的人,对游戏的理解越深,所编写的AI越高。
你也可以尝试去编写游戏AI。本人建议先尝试写黑白棋(我也是这么过来的)。因为黑白棋几乎不用编写点位估价方法,棋面估价方法也很简单。但是它在挑选可扩展点和向下扩展时对棋面的修改有一点点的难度。当然这个难度只是在要求较高的效率下才有的。去试试吧!

小林子打字好辛苦,麻烦转载注明: 转载自林枫紫涵

本文链接地址: http://www.lfzh.org/wuziqijava.html

作者: BigIdiot, BigIdiot