愛華網(wǎng)學(xué)習(xí)目標(biāo)
理解模式匹配的基本原理。
理解例子中的應(yīng)用原理。
了解機(jī)器人學(xué)習(xí)的概念。
任務(wù)
實現(xiàn)模式匹配瞄準(zhǔn)算法。
實現(xiàn)任務(wù)
可能你現(xiàn)在對模式匹配算法還非常陌生，不用擔(dān)心，下面會先介紹什么是模式匹配，然后再應(yīng)用到機(jī)器人瞄準(zhǔn)策略中。
1. 問題分析
模式匹配的基本概念是記錄并尋找相似的樣本，在AI-CODE中，樣本一般情況就是指對手的運動狀態(tài)，也就是說尋找相似的運動狀態(tài)。我這里舉個例子，比如對手做圓周運動5周后又做200個距離的直線運動，然后又開始做圓周運動，在做完4周之后你會預(yù)測它緊接著會怎樣運動？按照我們常規(guī)的經(jīng)驗來分析，我們會推測它會繼續(xù)作圓周運動1周，然后做直線運動。為什么你我會做出這樣的推斷？首先，因為我們記住了它原來的運動，它原來是運動5個圓周然后200距離直線，我們對此記得清清楚楚，其次我們做了比較，找出了最匹配的地方，我們把這4個圓周運動，看做它原來做5個圓周運動的開始4個，所以我們推斷它還會按照原來的規(guī)律繼續(xù)下去，如果對手真是有這樣的規(guī)律，那么我們將擊中它。模式匹配算法也正是采用了這兩個步驟實現(xiàn)了像你我一樣的推斷能力，而且利用計算機(jī)強記憶能力和快速計算能力，更能做出比你我更精確的推斷。也許有人要說了，剛才那個例子，如果機(jī)器人不是按照那個規(guī)律運動的，第一次做圓周5次然后直線，第二次就做圓周4次然后就直線了呢，很有可能有這樣的機(jī)器人啊，那么我們的分析就錯啦。我這里回答你，是的，我們的分析就錯了，但是隨著我們記錄的更多，我們會慢慢的正確起來，第一次5周，第二次4周的這種變化也是一種規(guī)律，只要我們記錄的足夠多，分析的足夠多，下一次它如果再出現(xiàn)這樣的情況，我們就知道了。也就是說，只要對手的運動有一定規(guī)律，我們就能分析出來，打中它。實際上通常的機(jī)器人運動都是有規(guī)律的，只是有的很明顯，變化少，有的不很明顯，變化多，很顯然對于前者，模式匹配算法會打的很好，對于后者，可能效果略差。不管怎么樣，這都是瞄準(zhǔn)算法的一個大突破，現(xiàn)在我們一起來實現(xiàn)了這樣一個機(jī)器人，你會看到它的強大。
2. 算法設(shè)計
根據(jù)剛才的分析，我們知道模式匹配算法主要是兩個步驟，記錄樣本和比較樣本（也就是尋找相似的樣本，即匹配的意思，樣本即模式的意思，模式匹配由此得名）。實際上算法大體可以說就是三步，如下圖所示：
整體思路其實很簡單，就那樣三個步驟，我們在腦海里結(jié)合我們?nèi)祟愖约悍治鰧κ诌\動規(guī)律的方法很好理解這三個步驟。但是要在機(jī)器人程序中實現(xiàn)這樣的功能，可能就要費一番功夫了。我們不要害怕，只要認(rèn)真思考，總會有答案。不過這里我們的思考方法就很重要了，我們要倒著順序思考，理由很簡單，因為我們最終的目的是要很好的擊中對手，而計算對手未來位置的部分是最后一個步驟。因此我們先從這個部分開始思考，根據(jù)歷史中的一系列對手狀態(tài)推斷對手的未來位置，我們最好采用什么樣的方法？回顧一下圓周瞄準(zhǔn)那一章的把圓周運動精確為實際的多邊形的圖，那就是一個軌跡，我們根據(jù)對手的轉(zhuǎn)動速度算出對手的方向再結(jié)合對手運動速度就能一個單位時間一個單位時間的推出（迭代）對手的未來位置（如果忘記那章的內(nèi)容，請詳細(xì)閱讀那章后再繼續(xù)讀此章內(nèi)容）。也就是說，我們需要對手一系列連續(xù)單位時間的方向和速度就能推斷對手的未來位置。因此我們這里可以考慮，對手的樣本就是對手的方向和速度，正好，方向和速度也能體現(xiàn)對手運動規(guī)律，因此這兩個屬性既能作為比較的樣本——第二步驟，又能作為推算對手未來位置的屬性——第三步驟，顯然，第一步驟我們需要記錄的對手的樣本就是對手的方向和速度了。
3. 編寫代碼
根據(jù)以上分析，這里給出一個示例方案的相關(guān)代碼：
/**
* 用模式匹配算法開火的機(jī)器人
* @author xiemin
*/
public class PatternFire extends SimpleRobot
{
//開火的火力
private static final double POWER = 0.5;
//保留歷史紀(jì)錄的最大長度
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];
//數(shù)組的當(dāng)前索引
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);
}
//記錄當(dāng)前的機(jī)器人狀態(tài)
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是為了避免比較樣本和被比較樣本重復(fù)
//和留取足夠的節(jié)點給遞推未來坐標(biāo)用
for(int i=MATCH_LENGHT; i<currentIndex-MATCH_LENGHT; i++)
{
//取10個樣本節(jié)點計算相似度
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]);
//加了權(quán)值的匹配度計算
//similarity+=
//Math.abs(velocityRecord[i-j]-velocityRecord[currentIndex-j])/8; //similarity+=
//Math.abs(headingRecord[i-j]-headingRecord[currentIndex-j])/Math.PI; }
//記錄最相似的相似度，以及對應(yīng)的記錄節(jié)點下標(biāo)
if(similarity<beatSimilarity)
{
matchIndex=i;
beatSimilarity=similarity;
}
}
return matchIndex;
}
//得到開火的位置
private Point2D getFirePoint(int matchIndex, double power)
{
//預(yù)測位置
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());
}
}
算法流程圖中的第一步，主要實現(xiàn)代碼是record函數(shù)中的代碼，注意數(shù)組的用法，每次記錄后currentIndex++增加一，這種數(shù)組的用法我們應(yīng)該比較熟悉了。第二步的代碼實現(xiàn)是函數(shù)getMatchedIndex，第三步的代碼主要就是getFirePoint函數(shù)了，主要功能是求得射擊方向，然后射擊。
在getFirePoint函數(shù)中，求射擊方向，原理和第十二章求圓周瞄準(zhǔn)射擊方向的原理類似，用了迭代的方法，可以參考對比這兩部分，即能很好理解。這里用到了nextPoint函數(shù)，此函數(shù)作用是求開火點。
注意常量HISTORY_LENGHT，代表了機(jī)器人的記憶能力，我這里設(shè)為2000，也就是說這個機(jī)器人最多能保留歷史紀(jì)錄的最大為2000長度，這大概是幾十輪的比賽了。一般比賽足夠了，如果達(dá)到了這個量，就要從頭開始。
如果不做這種方式控制matchIndex繼續(xù)增長，數(shù)組容不下更多數(shù)據(jù)，會造成程序錯誤。常量HISTORY_LENGHT，是用于迭代推算對手未來位置、速度的，因為迭代推算的時候，時間是一步一步往后推，我們要保證推到最后的射擊點要在我們記憶過的有效范圍內(nèi)，因此在尋找匹配樣本的時候，我們的比較范圍的最后邊界要比當(dāng)前樣本下標(biāo)提前一部分時間。見getMatchedIndex中的用法。
4. 調(diào)試算法
創(chuàng)建一個新的機(jī)器人，命名為Javabook.PatternFire采用上面的相關(guān)代碼，建立成功后，新建戰(zhàn)斗選擇此機(jī)器人，再選擇一個做圓周運動的機(jī)器人作為它的對手，你可以看到在對手饒幾圈之后，我們就能打得很準(zhǔn)了，說明他學(xué)習(xí)懂了對手的規(guī)律。換個繞墻走的對手看看，基本上對手繞墻一圈后，我們就能打得很準(zhǔn)了，再換其他規(guī)律的對手，看看效果，可以看出，很多有規(guī)律的機(jī)器人，不管它的規(guī)律是什么樣的，它幾乎都能通過學(xué)習(xí)一段時間打的越來越好。可見我們的效果達(dá)到了，我們編寫了一個能真正學(xué)習(xí)知識的機(jī)器人。
改進(jìn)與擴(kuò)展
雖然我們的機(jī)器人已經(jīng)擁有了學(xué)習(xí)能力，但是這只是很簡單的學(xué)習(xí)，因為在做樣本比較的時候，我們只是比較了對于我們迭代推斷敵人未來位置有用的敵人方向和敵人速度，如果我們再加入一些其他樣本信息，可能會更好，注意比較的樣本信息必須是跟敵人運動有關(guān)系的才有用，否則只會取得相反的效果。比如，如果加入敵人的轉(zhuǎn)動速度作為比較樣本，則比較有用，但是加入敵人的能量作為比較信息，則大部分情況都不會有用。還有，我們只是比較了一個單位時間的樣本（當(dāng)前樣本和歷史中的每一個樣本比較），對于我們剛開始分析的時候舉的例子，敵人圓周運動幾圈是需要若干個單位時間的，因此，如果增加比較的樣本數(shù)量（從當(dāng)前到n個單位時間以前的一系列樣本，和歷史中相同長度的一系列樣本的比較），則更會取得更好的效果。方方面面的改進(jìn)還有很多。具體實現(xiàn)這里就不多述。提醒一點就是，比較的越多，程序用的時間越長，AI-CODE中每個機(jī)器人每個單位時間所能用的計算時間是有限的，因此在做改進(jìn)的時候，不要一味的增加復(fù)雜度，以至于機(jī)器人運算超時而被系統(tǒng)強行終止。找出最有效的樣本，最合適的樣本比較長度，最合適的記憶長度，才能寫出最強的模式匹配機(jī)器人。
總結(jié)
這一章我們講述了模式匹配瞄準(zhǔn)算法，并實現(xiàn)了一個采用此技術(shù)的機(jī)器人，可以說，從此我們的機(jī)器人擁有了學(xué)習(xí)能力。模式匹配的優(yōu)點是能夠觀察出敵人運動軌跡的規(guī)律，并預(yù)測敵人未來出現(xiàn)的位置，因此一些很有運動規(guī)律的機(jī)器人將很難逃過模式匹配的法眼，但是正如它的優(yōu)點的前提所說，它只對有運動規(guī)律的機(jī)器人很有效（有些運動規(guī)律并不是我們?nèi)庋勰芸吹贸鰜?，也許你看到某個機(jī)器人似乎很沒規(guī)律，但是模式匹配機(jī)器人卻能找出它的規(guī)律從而打得很準(zhǔn)），而對于運動模式非常隨機(jī)的機(jī)器人，可能就不是那么有效了。繞敵人運動那一章我們給繞敵人運動的機(jī)器人加入了反向的隨機(jī)因素，這增加其實戰(zhàn)中對于模式匹配機(jī)器人的擾亂效果。模式匹配是個很大很復(fù)雜的領(lǐng)域，它在人工智能中的作用也是非常大，幾乎是每本人工智能書籍必講的內(nèi)容，我們這里講的只是它的一個很小的應(yīng)用。如果你深刻理解了它的原理，相信你定能用完全不同的實現(xiàn)方式寫出更強的模式匹配機(jī)器人。
