敵ロボットのパターンの繰り返しを見きわめる
Alisdair Owens (awo101@ecs.soton.ac.uk)
Student, University of Southampton
May 2002
パターン認識は現在のRobocodeのロボットで使われているターゲッティングで最も高等な方法です。もし敵ロボットが何らかのパターンの繰り返しを使っていれば、あなたはこのターゲッティングのシステムによってその敵ロボットに命中させられます。いくらか研究することで、パターン認識は乱戦(melee)の際も機能するようにできます。乱戦ではパターン認識は、単純なパターン解析よりも素晴らしい効果を発揮します。
このtipにはパターン認識の考え方の識見の基本が書かれています。パターン認識全体の話題はこのtipの範囲を超えています。しかしいくらか研究することによってあなたは、適切にパターン認識をするあなた自身のロボットの作り方を理解できるでしょう。パターン認識は、敵ロボットがあらかじめ規定しておいた様々なパターンのうちのどれかを使っているのか見つけだそうと試み、そして敵がそのパターンを使いつづけると想定してターゲッティングする、一連の作業です。このテクニックは、どんな類の繰り返しのパターンを使っているターゲットにも適合させられる、パターン解析とは異なります。パターン認識はそれより相当効率が良く、そのため乱戦状態でも機能するよう適合させられます。パターン解析は乱戦では、絶対に得られない膨大な処理時間とデータ量を要求する、というのに対して。
注意:
これは高度な話題です。議論についていくためには、あなたにはRobocodeの経験もしくはそれなりの数学の能力が必要です。
加速度の変化の認識
パターン認識の最もわかりやすい使用法は、"機銃掃射(strafe)"する・もしくは前後に繰り返して動くロボットに命中させられる能力を手に入れることです。このパターンは、"前進-停止、前進-停止(move forward-stop, move forward-stop)"パターンと同様に、敵ロボットの加速度が反転する間隔の時間を解析することによって認識できます。このパターンを調査してみると、Robocodeの取りうる加速度の値は1,0,-1,-2だけであることがわかりました。差しあたり単純さを優先して、加速度-2(滅多に使われません)は無視することにします。
最初の段階はデータを記録することです。リスト1はログを記録する基本的なクラスです。私たちは、私たちが集めているデータが役に立つかどうかを判別する能力を付け加えながら、このコードを改良していきます。(このtipのための一揃いのソースはリソースから入手できます。)
リスト1. パターン認識をするクラスのコード
public class AccelerationPatternRecogniser {
//average time between reverses of acceleration
public double avgreversetime;
//time of last reverse of acceleration
public long timelastreverse;
//the last time the bot accelerated, was it speeding up or down?
public boolean accelerating;
double lastacceleration, acceleration;
double lastvelocity;
//number of reverses
long readings;
public AccelerationPatternRecogniser() {
/**Set the initial values of the variables**/
lastacceleration = 0;
acceleration = 0;
timelastreverse = 0;
avgreversetime = -1;
}
public void add(double velocity, long time) {
/**work out the current acceleration**/
acceleration = velocity - lastvelocity;
if (acceleration > 1)
acceleration = 1;
if (acceleration < -1)
acceleration = -1;
/**set accelerating - if the bot is not accelerating at
the moment, do not alter.**/
if (acceleration == 1)
accelerating = true;
if (acceleration == -1)
accelerating = false;
/**Work out whether the acceleration has reversed**/
if ((acceleration != lastacceleration) && (acceleration != 0)) {
if (avgreversetime == -1) {
avgreversetime = time;
readings = 1;
} else {
avgreversetime = ((avgreversetime * readings) +
(time - timelastreverse))/(readings+1);
}
timelastreverse = time;
}
lastvelocity = velocity;
lastacceleration = acceleration;
}
}
|
このコードはターゲットの速度に関するデータのログの記録をします。これはシステムが使うために重要な変数を3つ提供します。加速度の反転の間隔の時間の平均・最後に加速度が反転した時間・最後に加速したときにターゲットが向いていた方向です。パターン認識をするこのクラスを使っているターゲッティングシステムと組み合わせて、あなたのロボットは、機銃掃射の動きか前進-停止パターンの動きのロボットに命中させられます。
そのパターンは使われているか?
このログ記録機能の問題点は、このパターンが実際に使われているかいないかどうかを見きわめる能力を持たないことです。これは速度の変化の間隔の時間のすべてを平均するだけです。変化の間隔の時間が合理的なほど一定かどうか看破するためには、私たちは変化の間隔の時間の標準偏差をとらなければなりません。これにより平均からそれぞれの結果の偏差がどれだけかがわかります。その偏差が大きいほど、パターンが存在する可能性は小さくなります。
標準偏差はこの式で求められます。
sd = sqrt(E[x^2] - E[x]^2)
ここでE[x^2]はすべての値の2乗の平均、E[x]^2はすべての値の平均の2乗です。この強化策は実装が驚くほど簡単で、すべての速度の追跡記録をし続けることなしに行えます。リスト2はできあがったログ記録クラスです。
リスト2. 変更されたコード
public class AccelerationPatternRecogniser {
//average time between reverses of acceleration
public double avgreversetime;
public double standdev;
//time of last reverse of acceleration
public long timelastreverse;
//the last time the bot accelerated, was it speeding up or down?
public boolean accelerating;
double lastacceleration, acceleration;
double lastvelocity;
double avgreversetimesquared;
long readings; //number of reverses
public AccelerationPatternRecogniser() {
/**Set the initial values of the variables**/
lastacceleration = 0;
acceleration = 0;
timelastreverse = 0;
avgreversetime = -1;
avgreversetimesquared = -1;
standdev = 0;
}
public void add(double velocity, long time) {
/**work out the current acceleration**/
acceleration = velocity - lastvelocity;
if (acceleration > 1)
acceleration = 1;
if (acceleration < -1)
acceleration = -1;
/**set accelerating - if the bot is not accelerating at
the moment, do not alter.**/
if (acceleration == 1)
accelerating = true;
if (acceleration == -1)
accelerating = false;
/**Work out whether the acceleration has reversed**/
if ((acceleration != lastacceleration) && (acceleration != 0)) {
if (avgreversetime == -1) {
avgreversetime = time;
avgreversetimesquared = Math.pow(time,2);
readings = 1;
} else {
avgreversetime = ((avgreversetime * readings) +
(time - timelastreverse))/(readings+1);
/**Work out the standard deviation**/
avgreversetimesquared =
((avgreversetimesquared * readings) +
(Math.pow(time - timelastreverse,2)))/(readings+1);
standdev = Math.sqrt(avgreversetimesquared -
Math.pow(avgreversetime, 2));
readings++;
}
timelastreverse = time;
}
lastvelocity = velocity;
lastacceleration = acceleration;
}
}
|
もし標準偏差が大きくなりすぎたら、ターゲットはこのパターンを使っていないことがわかり、かわりにあなたは、異なるパターンの解析をしたり、円形ターゲッティングか線型ターゲッティングに戻ったりできます。このログ記録クラスは、パターン認識の秘密めいた世界に足を踏み入れるにあたって必要な仕事の大部分を果たします。やり残されたのは、このログ記録クラスにより与えられたデータをあなた自身のターゲッティングシステムと結合させることだけです。おそらくあなたたちは異なるターゲッティングシステムを使っているでしょうから、これの実装はあなたにゆだねます。
システムの拡張
この基本的なシステムにできる拡張は幾つもあります。ここに上げるのはほんのわずかです。
-
パターンを増やす:
これは最もわかりやすい拡張です。もっと複雑な速度に基づいたパターンを追加してください。上述した2つのものよりもっと複雑でしょうが、あなたは、敵ロボットが一直線上に移動するとみなす、wallbotたちのための、パターン認識クラスをあなたは用意に付け加えられます。
-
ヘディングの変化の解析:
次の段階として、あなたは速度の認識と同時にヘディングの変化を解析できます。この解析は速度に基づいたパターン認識よりもっと複雑ですが、努力すれば非常に強力なターゲッティングシステムを作れます。
-
パターン解析:
これは、Wolverineや最近はJollyNinjaでみられますが、1対1でのターゲッティングにおける究極の姿です。これはバトルの実行中に新しいパターンを学習することができますが、恐ろしいほどCPU-intensiveです。これを実装すればあなたのロボットは侮れないものになるでしょう!
リソース
- このtipで論じられたパターン認識テクニックのためのソースコードをダウンロードしてください。
(以下略)
|