爱华网学习目标
理解模式匹配的基本原理。
理解例子中的应用原理。
了解机器人学习的概念。
任务
实现模式匹配瞄准算法。
实现任务
可能你现在对模式匹配算法还非常陌生，不用担心，下面会先介绍什么是模式匹配，然后再应用到机器人瞄准策略中。
1. 问题分析
模式匹配的基本概念是记录并寻找相似的样本，在AI-CODE中，样本一般情况就是指对手的运动状态，也就是说寻找相似的运动状态。我这里举个例子，比如对手做圆周运动5周后又做200个距离的直线运动，然后又开始做圆周运动，在做完4周之后你会预测它紧接着会怎样运动？按照我们常规的经验来分析，我们会推测它会继续作圆周运动1周，然后做直线运动。为什么你我会做出这样的推断？首先，因为我们记住了它原来的运动，它原来是运动5个圆周然后200距离直线，我们对此记得清清楚楚，其次我们做了比较，找出了最匹配的地方，我们把这4个圆周运动，看做它原来做5个圆周运动的开始4个，所以我们推断它还会按照原来的规律继续下去，如果对手真是有这样的规律，那么我们将击中它。模式匹配算法也正是采用了这两个步骤实现了像你我一样的推断能力，而且利用计算机强记忆能力和快速计算能力，更能做出比你我更精确的推断。也许有人要说了，刚才那个例子，如果机器人不是按照那个规律运动的，第一次做圆周5次然后直线，第二次就做圆周4次然后就直线了呢，很有可能有这样的机器人啊，那么我们的分析就错啦。我这里回答你，是的，我们的分析就错了，但是随着我们记录的更多，我们会慢慢的正确起来，第一次5周，第二次4周的这种变化也是一种规律，只要我们记录的足够多，分析的足够多，下一次它如果再出现这样的情况，我们就知道了。也就是说，只要对手的运动有一定规律，我们就能分析出来，打中它。实际上通常的机器人运动都是有规律的，只是有的很明显，变化少，有的不很明显，变化多，很显然对于前者，模式匹配算法会打的很好，对于后者，可能效果略差。不管怎么样，这都是瞄准算法的一个大突破，现在我们一起来实现了这样一个机器人，你会看到它的强大。
2. 算法设计
根据刚才的分析，我们知道模式匹配算法主要是两个步骤，记录样本和比较样本（也就是寻找相似的样本，即匹配的意思，样本即模式的意思，模式匹配由此得名）。实际上算法大体可以说就是三步，如下图所示：
整体思路其实很简单，就那样三个步骤，我们在脑海里结合我们人类自己分析对手运动规律的方法很好理解这三个步骤。但是要在机器人程序中实现这样的功能，可能就要费一番功夫了。我们不要害怕，只要认真思考，总会有答案。不过这里我们的思考方法就很重要了，我们要倒着顺序思考，理由很简单，因为我们最终的目的是要很好的击中对手，而计算对手未来位置的部分是最后一个步骤。因此我们先从这个部分开始思考，根据历史中的一系列对手状态推断对手的未来位置，我们最好采用什么样的方法？回顾一下圆周瞄准那一章的把圆周运动精确为实际的多边形的图，那就是一个轨迹，我们根据对手的转动速度算出对手的方向再结合对手运动速度就能一个单位时间一个单位时间的推出（迭代）对手的未来位置（如果忘记那章的内容，请详细阅读那章后再继续读此章内容）。也就是说，我们需要对手一系列连续单位时间的方向和速度就能推断对手的未来位置。因此我们这里可以考虑，对手的样本就是对手的方向和速度，正好，方向和速度也能体现对手运动规律，因此这两个属性既能作为比较的样本——第二步骤，又能作为推算对手未来位置的属性——第三步骤，显然，第一步骤我们需要记录的对手的样本就是对手的方向和速度了。
3. 编写代码
根据以上分析，这里给出一个示例方案的相关代码：
/**
* 用模式匹配算法开火的机器人
* @author xiemin
*/
public class PatternFire extends SimpleRobot
{
//开火的火力
private static final double POWER = 0.5;
//保留历史纪录的最大长度
private static final int HISTORY_LENGHT = 2000;
//用于匹配段的长度
private static final int MATCH_LENGHT = 20;
//对手的速度记录
private double[] velocityRecord = new double[HISTORY_LENGHT];
//对手的方向记录
private double[] headingRecord = new double[HISTORY_LENGHT];
//数组的当前索引
private int currentIndex=0;
public void onRoundBegin(RoundBeginAction action)
{
currentIndex = 0;
}
public void onTick(TickAction action)
{
Bot opponent = getFirstOpponent();
if(opponent==null) return;
record(opponent);
int matchIndex = getMatchIndex();
Point2D firePoint = getFirePoint(matchIndex, POWER);
fire(firePoint, POWER);
}
//记录当前的机器人状态
private void record(Bot bot)
{
velocityRecord[currentIndex] = bot.getVelocity();
headingRecord[currentIndex] = bot.getHeading();
currentIndex++;
}
//计算最佳的匹配点
private int getMatchIndex()
{
double beatSimilarity=Double.POSITIVE_INFINITY;
int matchIndex=0;
//这里取i<currentFrame-100是为了避免比较样本和被比较样本重复
//和留取足够的节点给递推未来坐标用
for(int i=MATCH_LENGHT; i<currentIndex-MATCH_LENGHT; i++)
{
//取10个样本节点计算相似度
double similarity=0;
for(int j=1; j<=MATCH_LENGHT; j++)
{ similarity+=Math.abs(velocityRecord[i-j]-velocityRecord[currentIndex-j]);
similarity+=Math.abs(headingRecord[i-j]-headingRecord[currentIndex-j]);
//加了权值的匹配度计算
//similarity+=
//Math.abs(velocityRecord[i-j]-velocityRecord[currentIndex-j])/8; //similarity+=
//Math.abs(headingRecord[i-j]-headingRecord[currentIndex-j])/Math.PI; }
//记录最相似的相似度，以及对应的记录节点下标
if(similarity<beatSimilarity)
{
matchIndex=i;
beatSimilarity=similarity;
}
}
return matchIndex;
}
//得到开火的位置
private Point2D getFirePoint(int matchIndex, double power)
{
//预测位置
Point2D firePoint = getFirstOpponent().getLocation();
int time = 0;
while(matchIndex+time<currentIndex)
{
double distance = MathUtils.distance(getLocation(), firePoint);
if(distance/getBulletVelocity(power)<=time) break;
firePoint = MathUtils.nextPoint(firePoint, headingRecord[matchIndex+time], velocityRecord[matchIndex+time]);
time++;
}
return firePoint;
}
public static void main(String[] args)
{
startup(args, new PatternFire());
}
}
算法流程图中的第一步，主要实现代码是record函数中的代码，注意数组的用法，每次记录后currentIndex++增加一，这种数组的用法我们应该比较熟悉了。第二步的代码实现是函数getMatchedIndex，第三步的代码主要就是getFirePoint函数了，主要功能是求得射击方向，然后射击。
在getFirePoint函数中，求射击方向，原理和第十二章求圆周瞄准射击方向的原理类似，用了迭代的方法，可以参考对比这两部分，即能很好理解。这里用到了nextPoint函数，此函数作用是求开火点。
注意常量HISTORY_LENGHT，代表了机器人的记忆能力，我这里设为2000，也就是说这个机器人最多能保留历史纪录的最大为2000长度，这大概是几十轮的比赛了。一般比赛足够了，如果达到了这个量，就要从头开始。
如果不做这种方式控制matchIndex继续增长，数组容不下更多数据，会造成程序错误。常量HISTORY_LENGHT，是用于迭代推算对手未来位置、速度的，因为迭代推算的时候，时间是一步一步往后推，我们要保证推到最后的射击点要在我们记忆过的有效范围内，因此在寻找匹配样本的时候，我们的比较范围的最后边界要比当前样本下标提前一部分时间。见getMatchedIndex中的用法。
4. 调试算法
创建一个新的机器人，命名为Javabook.PatternFire采用上面的相关代码，建立成功后，新建战斗选择此机器人，再选择一个做圆周运动的机器人作为它的对手，你可以看到在对手饶几圈之后，我们就能打得很准了，说明他学习懂了对手的规律。换个绕墙走的对手看看，基本上对手绕墙一圈后，我们就能打得很准了，再换其他规律的对手，看看效果，可以看出，很多有规律的机器人，不管它的规律是什么样的，它几乎都能通过学习一段时间打的越来越好。可见我们的效果达到了，我们编写了一个能真正学习知识的机器人。
改进与扩展
虽然我们的机器人已经拥有了学习能力，但是这只是很简单的学习，因为在做样本比较的时候，我们只是比较了对于我们迭代推断敌人未来位置有用的敌人方向和敌人速度，如果我们再加入一些其他样本信息，可能会更好，注意比较的样本信息必须是跟敌人运动有关系的才有用，否则只会取得相反的效果。比如，如果加入敌人的转动速度作为比较样本，则比较有用，但是加入敌人的能量作为比较信息，则大部分情况都不会有用。还有，我们只是比较了一个单位时间的样本（当前样本和历史中的每一个样本比较），对于我们刚开始分析的时候举的例子，敌人圆周运动几圈是需要若干个单位时间的，因此，如果增加比较的样本数量（从当前到n个单位时间以前的一系列样本，和历史中相同长度的一系列样本的比较），则更会取得更好的效果。方方面面的改进还有很多。具体实现这里就不多述。提醒一点就是，比较的越多，程序用的时间越长，AI-CODE中每个机器人每个单位时间所能用的计算时间是有限的，因此在做改进的时候，不要一味的增加复杂度，以至于机器人运算超时而被系统强行终止。找出最有效的样本，最合适的样本比较长度，最合适的记忆长度，才能写出最强的模式匹配机器人。
总结
这一章我们讲述了模式匹配瞄准算法，并实现了一个采用此技术的机器人，可以说，从此我们的机器人拥有了学习能力。模式匹配的优点是能够观察出敌人运动轨迹的规律，并预测敌人未来出现的位置，因此一些很有运动规律的机器人将很难逃过模式匹配的法眼，但是正如它的优点的前提所说，它只对有运动规律的机器人很有效（有些运动规律并不是我们肉眼能看得出来，也许你看到某个机器人似乎很没规律，但是模式匹配机器人却能找出它的规律从而打得很准），而对于运动模式非常随机的机器人，可能就不是那么有效了。绕敌人运动那一章我们给绕敌人运动的机器人加入了反向的随机因素，这增加其实战中对于模式匹配机器人的扰乱效果。模式匹配是个很大很复杂的领域，它在人工智能中的作用也是非常大，几乎是每本人工智能书籍必讲的内容，我们这里讲的只是它的一个很小的应用。如果你深刻理解了它的原理，相信你定能用完全不同的实现方式写出更强的模式匹配机器人。
