人工智能 Java 坦克机器人系列: 神经网络,下部

developerWorks
文档选项
将此页作为电子邮件发送

将此页作为电子邮件发送


最新推荐

Java 应用开发源动力 - 下载免费软件,快速启动开发


级别: 初级

Robo cool (robocool@gmail.com), 编程游戏爱好者,自由撰稿人

2006 年 8 月 24 日

Robocode 中团队作战是很复杂的应用,如何在多变的环境下找到自己想要的目标是团队作战的关键。本文将用贝叶斯网络来实现团队作战的目标的选择,贝叶斯网络是人工智能中机器学习的一种方法,它并不属于神经网络范围。由于本文不仅介绍了贝叶斯网络的应用,同样涉及到神经网络公共包的应用、Robocode 中使用神经网络的例子机器人分析,最后还介绍了 AI-CODE 这个类似于 Robocode 的编程工具的体系结构,以方便 C,C++,C# 用户在本文 Java 代码的基础上对神经网络知识的理解。

贝叶斯网络

贝叶斯网络亦称信念网络(Belief Network),于 1985 年由 Judea Pearl 首先提出。它是一种模拟人类推理过程中因果关系的不确定性处理模型,其网络拓朴结构是一个有向无环图(DAG)。它的节点用随机变量或命题来标识,认为有直接关系的命题或变量则用弧来连接。例如,假设结点 E 直接影响到结点 H,即 E→H,则建立结点 E 到结点 H 的有向弧(E,H),权值(即连接强度)用条件概率 P(H/E)来表示,如图所示:


有两个结点的贝叶斯网络示意图

有6个节点的贝叶斯网络

一般来说,有 n 个命题 x1,x2,,xn 之间相互关系的一般知识可用联合概率分布来描述。但是,这样处理使得问题过于复杂。Pearl 认为人类在推理过程中,知识并不是以联合概率分布形表现的,而是以变量之间的相关性和条件相关性表现的,即可以用条件概率表示。如



例如,对如图所示的 6 个节点的贝叶斯网络,有



一旦命题之间的相关性由有向弧表示,条件概率由弧的权值来表示,则命题之间静态结构关系的有关知识就表示出来了。当获取某个新的证据事实时,要对每个命题的可能取值加以综合考查,进而对每个结点定义一个信任度,记作 Bel(x)。可规定 Bel(x) = P(x=xi / D) 来表示当前所具有的所有事实和证据 D 条件下,命题 x 取值为 xi 的可信任程度,然后再基于 Bel 计算的证据和事实下各命题的可信任程度。





回页首


团队作战目标选择

在 Robocode 中,特别在团队作战中。战场上同时存在很多机器人,在你附近的机器人有可能是队友,也有可能是敌人。如何从这些复杂的信息中选择目标机器人,是团队作战的一大问题,当然我们可以人工做一些简单的判断,但是战场的信息是变化的,人工假定的条件并不是都能成立,所以让机器人能自我选择,自我推理出最优目标才是可行之首。而贝叶斯网络在处理概率问题上面有很大的优势。首先,贝叶斯网络在联合概率方面有一个紧凑的表示法,这样比较容易根据一些事例搜索到可能的目标。另一方面,目标选择很容易通过贝叶斯网络建立起模型,而这种模型能依据每个输入变量直接影响到目标选择。

贝叶斯网络是一个具有概率分布的有向弧段(DAG)。它是由节点和有向弧段组成的。节点代表事件或变量,弧段代表节点之间的因果关系或概率关系,而弧段是有向的,不构成回路。下图所示为一个简单的贝叶斯网络模型。它有 5 个节点 和 5 个弧段 组成。图中没有输入的 A1 节点称为根节点,一段弧的起始节点称为其末节点的母节点,而后者称为前者的子节点。


简单的贝叶斯网络模型
简单的贝叶斯网络模型

贝叶斯网络能够利用简明的图形方式定性地表示事件之间复杂的因果关系或概率关系,在给定某些先验信息后,还可以定量地表示这些关系。网络的拓扑结构通常是根据具体的研究对象和问题来确定的。目前贝叶斯网络的研究热点之一就是如何通过学习自动确定和优化网络的拓扑结构。

变量

由上面贝叶斯网络模型要想得到理想的目标机器人,我们就必须知道需要哪些输入变量。如果想得到最好的结果,就要求我们在 Robocode 中每一个可知的数据块都要模拟为变量。但是如果这样做,在贝叶斯网络结束计算时,我们会得到一个很庞大的完整概率表,而维护如此庞大的概率表将会花费我们很多的系统资源和计算时间。所以在开始之前我们必须要选择最重要的变量输入。这样从比赛中得到的关于敌人的一些有用信息有可能不会出现在贝叶斯网络之内,比如速度和方向。下面我们列出对选择系统最重要的 6 个变量数据,并用一个 6 维数组保存这些变量值。

1.自身机器人的能量:

机器人的能量是多少。它预计选择的目标敌人的能量和自己的能量相差数。


public double getScore (Enemy e)
  {
    int a1, a2, a3, a4 = 0, a5 = 0; //初始化每个变量
    Vektor mig = new TVektor (robot); //得到自身机器人类
    a1 = getEnergyIndex (robot.getEnergy ());  //初始化自身能量变量

mig为自身的机器人类,在上部的反向传播算法部分有说明,getEnergyIndex()为能量的状态值,在下面的状态部分有这个函数的详细说明。

2.敌人的能量:

当我们选择了两个目标时,如果此时我们的能量比较低,我们可以从已知的敌人中选择能量低的机器人作战,这样我们更有赢得胜利的机率。


a2 = getEnergyIndex (e.getEnergy ());

3.敌人的距离:

距离能让我们预防从远处向我们靠近的目标敌人。而且当我们穿过整个战场去攻击敌人,敌我距离也能让我们预防一些潜在的危险。在有效的范围内作出反应。


    a3 = getDistanceIndex (mig.substract (new TVektor (e)).getLength ());
  

4.敌人和它的队友的距离:

在团队战斗中,由于目标机器人过多,我们选择的敌人身边可能有离得很近的对方队友。如果此时我们只是针对选择的敌人作出反应而不考虑其队友将对我们十分不利。所以考虑到敌人与它的队友的距离就变得很重要了。


 Enemy[]en = worldmodel.getEnemies (); //得到地图中所有收集到的敌人
    mig = new TVektor (e);
    double aafstand = Double.MAX_VALUE;
   //分析容器类中每个敌人的距离
    for (int i = 0; i < en.length; i++)     {
		double aff = mig.substract (new TVektor (en[i])).getLength (); 
		if (aff < aafstand && aff > 2)
	  		a4 = getDistanceIndex (aff);
     }
     

5.有多少队友选择了给出的目标:

让队友去攻击同一敌人是一个不错的主意,这样可集中火力消灭敌人。但是,有可能有队友已经选择了目标机器人,如果这时让所有的机器人都去攻击同一个目标对已方是很不利的。所以只有知道有多少队友已经选择了敌人,才能让自己得到最大的利益。


  Teammate[]ttt = worldmodel.getTeammates (); //队友列表
    for (int i = 0; i < ttt.length; i++)
	//判断队友是否选择目标敌人
      if (e.getName ().equals (ttt[i].getEnemy ()))
	a5++;
    a5 = a5 > 2 ? 2 : a5;
 

6.胜利或失败:

当机器人战死,我们必须知道是否成功使用了当前的变量设置。此处胜利用 0 表示,失败用 1 表示.


贝叶斯网络设计
贝叶斯网络设计

由于队友(Friend)变量基本是类似的,所以我们用 Friends_targets 替代其实几个队友变量,即把 Friend{1-4} 移除,这样我们可以大大减少网络的开销。如下图 Fridends-target 代表了所有其他的队友:


减少贝叶斯网络大小
减少贝叶斯网络大小

我们用一个 6 维数组保存这些变量,最后把当前战斗情况下的变量加权保存到磁盘文件当中,在使用中通过读取操作从文件中读取。下面是读取变量加权的过程,保存过程与其类似:


  private void load ()   {
    int[] a;
	dataFile = robot.getDataFile ("-bayesian.dat");
    if (dataFile.exists ())    {
	while ((a = readLineIn ()) != null)  {
	    data[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]] = a[6];
	  }
      }
    else    {
	int a1, a2, a3, a4, a5, a6;
	for (a1 = 0; a1 < data.length; a1++) 
	  for (a2 = 0; a2 < data[a1].length; a2++)
	    for (a3 = 0; a3 < data[a1][a2].length; a3++)
	      for (a4 = 0; a4 < data[a1][a2][a3].length; a4++)
		for (a5 = 0; a5 < data[a1][a2][a3][a4].length; a5++)
		  for (a6 = 0; a6 < data[a1][a2][a3][a4][a5].length; a6++)
		    data[a1][a2][a3][a4][a5][a6]++;
      }
  }
  

状态

贝叶斯网络是它是由节点和有向弧段组成的,所以在贝叶斯网络中只有节点是不够的,我们还要知道每个节点的弧段,也即每个可能的输入都要有一个状态。但是在 Robocode 中给每个变量都设置状态是不可能的,比如我们要给距离这个 double 类型的变量构造相应的状态数。每个数字对应一个状态数,这将会生成一个庞大的状态数集数据表,如此巨大的数据表很有可能耗费系统资源。为了解决这个问题,我们把输入变量的范围分成区间,即把连续的问题分成线性问题求解。这样我们就可以基于每个变量区间来构造状态。这些区间变量可被看成是离散化的连续变量。

所以状态问题就转变为区间变量的划分问题,好的区间变量能为网络提供好的目标选择结果。根据上面变量的说明,我们主要是划分好能量、距离以及队友三个变量区间。

能量变量可能的区间范围如下:[0-20]、[21-50]、[51-120]、[121 无穷大]这个方法能区分"常规"机器人中三分之一的能量变量。如果在比赛开始,这个方法还能发现能量为 120 的敌人队长。


    private static int getEnergyIndex (double d)   {
    if (d < 20)  return 0;
    else if (d < 50) return 1;
    else if (d < 120)  return 2;
    else  return 3;
  }
  

此处我们分别用 0,1,2,3 分别表示不同能量区间下的状态。

对于距离变量可能的范围为:[0-100]、[101-300]、[301-700]、[701-1200]、[1201 无穷大]。这能让机器人区分其他机器人是很近,刚刚在雷达范围内还是在雷达之外。这个变量对雷达的扫描范围很重要,因为只有能扫描到的机器人才能更好的选择。


private static int getDistanceIndex (double d)  {
    if (d < 100)    return 0;
    else if (d < 300)    return 1;
    else if (d < 700)    return 2;
    else if (d < 1200)   return 3;
    else    return 4;
  }

现在我们看看 Friend 变量的状态如何指定?从直观上来看,队友包括如下的一些状态:没有目标(No target)、死亡(Dead)、同一目标(Same target)、另一目标(Another target)。但是在真正使用当中,我们并不需要知道队友是死亡还是有没有目标,我们只要知道队友是否同时选择的同一目标。这样,我们把"多少队友选择了给出的目标"变量状态设为 0,1,2 三种状态,0 表示没有队友选择目标,1 表示有一个队友选择了目标,2 表示有 2 个或 2 个以上的了队友选择了目标。

最后只剩下"胜利或失败"变量的状态了,由上面的变量说明我们知道"胜利或失败"变量只有两种状态,0 表示胜利,1 表示失败。

知道了所有变量的状态,相当于我们知道了这些变量的维数空间,这样我们在最初变量的初始化过程中,就可按变量的状态指定变量大小。


public class TargetSelection {
  //分别设定各变量的维数空间大小
  private int[][][][][][] data = new int[4][4][5][5][3][2];

为了更新贝叶斯网络我们要知道如何判断选择的目标是好的还是坏的。其实判断标准很简单:如果选择的目标在我们之前死去,这个选择就是好的;如果我们在目标这前死去,这个选择就是不好的。





回页首


贝叶斯公式与目标选择实现