はじめに

こんにちは。株式会社Spakona 代表の河崎太郎（@taro_kawa6）です。「第4回空戦AIチャレンジ」に参加し、最終一位入賞を果たすことができました。なお、今回のチームは河崎（@taro_kawa6）、鈴木、和地（@akifumi_wachi）、青木（@thun_c）の4名で構成されています。

本記事では、コンペの序盤に試しに作成してみた 「ルールベースの手法」 について解説します。

我々のチーム Spakona_Inc が最終的に採用した解法の詳細については、以下の記事にて解説しておりますので合わせてご覧ください。

背景

第4回空戦AIチャレンジでは、エージェント同士の対戦結果だけでなく、機械学習をどう利用したか、再利用性があるかといった定性評価が大きな加点となります。これは、これまで3回開催された空戦AIチャレンジの全てで優勝者がルールベースの手法を組み込んでおり、主催者である防衛装備庁の研究目的に反した結果だからだと思われます。よって、定性評価を確実に上げる上で、最終提出するエージェントには再利用性と相性の悪い設計は排除するべきです。一方で、コンペティションのルールとして禁止しているわけではないため、定性評価を重視しない参加者が機械学習を伴わないエージェント（以下、非学習エージェント）を開発する可能性はあります。つまり、リーダーボード上の対戦環境を想定する上では、非学習エージェントを対戦相手として意識する必要があります。
我々のチームでは、最終提出用に開発する強化学習エージェントとは別に、以下の用途で非学習エージェントの開発も並行して進めました。

学習済みのエージェントの対戦相手とし、強さを測る目的
学習中のエージェントの対戦相手とし、学習を促進する目的

探索アルゴリズムの検討

今回の問題を流し目で読んだ時、以下の特徴を確認しました。

2チームが複数の操作対象を操る多対多の対戦型のゲーム
物理シミュレーションを伴う
明確な目的がある

この特徴を全て満たすゲームとして、CodinGameのFANTASTIC BITSがあります。このゲームは2対2でフィールド上に散りばめられた複数のボールを相手のゴールに入れた数を競うものでした。
FANTASTIC BITSでは敵チームの動きをルールベースで決めつけた状態で遺伝的アルゴリズムによるローリングホライズンで自チームの動きを決定する方針をとった参加者が優勝していました。

第4回空戦AIチャレンジの序盤では、この方針が可能か検討していました。しかし、敵の位置がレーダーに映らないとわからない点、敵の弾を知覚できるのが着弾直前である点、物理シミュレーションの複雑さなどの要因から、FANTASTIC BITSで有効なアルゴリズムは空戦AIと相性が悪いと判断しました。
背景でも触れた通り、非学習エージェントの目的は学習エージェントの壁打ちでしかないです。そのため、探索アルゴリズムの使用には固執せず、ルールベースでそれらしい動きをするエージェントの開発にシフトすることにしました。

8月6日時点

まずは運営が用意したルールベースエージェントであるBenchMarkに勝つ方法を考えました。リーダーボードに載る際に最初にBenchMarkと対戦して初期レートがつくルールだった点と、下位のチームがBenchMarkをそのまま提出する可能性があるため、BenchMarkに勝てることには「弱いエージェントに勝てる」以上の価値があります。リーダーボード上位のエージェントは「BenchMarkに勝てるエージェント」のはずなので、「BenchMarkに勝てるエージェントに勝てるエージェント」開発のための壁打ち相手として「BenchMarkに勝てるエージェント」が有効だと考えたためです。
BenchMarkはY(横)方向に直進して敵を見つけたら攻撃しながら引き返すエージェントです。雑に直進して交戦すると撃墜される恐れがあります。そこで、初期位置時点でX(縦)方向の並びが外側の2機と内側の2機で役割を分ける方針を考えました。

外側2機: 敵機に見つからないぐらい大きく外側から周りこみ、敵に見つからないまま護衛機を探す
内側2機: 直進して敵と交戦する

内側2機は数の利で負ける可能性がありますが、敵が避ける動作をしてくれると敵が護衛機に到達するまでの時間が遅れ、その間に自軍の外側2機が護衛機を撃墜する作戦です。

8月9日時点

以下の変更により、自チームの強化学習エージェントにも勝てるようになりました。

外側2機: 敵を恐れて遠くに行き過ぎると護衛機への到達が遅くなるため、軌道を少し内側に調整
内側2機: ほぼ同じ位置を通ると敵をはさみうちしにくい点から、少し離れて行動するように変更

8月10日時点

外側2機: 護衛機を見つけたら予定していた軌道に関係なく護衛機を追うように修正
内側2機: 敵に見つかりやすい位置で逃げるように変更。敵の弾切れを誘う効果と、外側2機を隠す目的

8月11日時点

ここまで開発したエージェントは、ビジュアライザ上では敵を見つけているように見えるのになぜか追わない現象が発生していました。直線的な動きだとレーダーの範囲が固定されてしまうため、わざと小刻みに首を振りながら進むように調整したところ、正しく敵を追う動きが増えました。
さらに、各機の動きを以下のように調整しました。

外側2機: 護衛機到達が早まるよう、さらにルートを護衛機寄りにした
内側2機: 敵機を攪乱しやすいよう、弾切れを恐れず頻繁に攻撃するようにした

この時点で詳細な勝率を測定し、30戦ずつランダムシードで対戦したところ、以下のようにかなり強いことがわかりました。

vs 自チームの強化学習エージェント: 勝率85%
vs BenchMark: 勝率86.7%

シミュレータの更新が数回発生し、常に同じ条件ではありませんでしたが、このエージェントは9月6日頃までリーダーボード上でも1位争いができる程度の強さでした。

9月8日時点

これまで、攪乱用の内側2機は敵を見つけたら敵と逆側に逃げるようにしていました。敵機が正面にいる場合、180度方向に戻ることになります。しかし、戦闘機の仕組み上、真後ろに移動するには旋回が必要で、旋回中に撃墜されることがありました。また、これまでのエージェントでは高さは常に一定に保っており、XY平面上の動きしか取り入れていませんでした。そこで、高度方向へ90度旋回し、スピードを落とさずに敵機から逃げる方針を取り入れました。画像の縦側が高さ方向です。

9月9日時点

9月8日の考察から、敵を見つけてから180度旋回するのでは遅いと考え、敵を見つける前に方向転換しておくことを考えました。護衛機を撃墜するゲームである以上、敵は自軍の護衛機側に近い方向を向いているはずです。お互いに最速で直進した場合、どのぐらいの位置で交戦状態になるかはあらかじめ見積もれます。敵を見つける前から事前にちょうどいい位置で方向転換しておくことで、避ける際の旋回方向を抑えることを考えました。

また、実験過程で偶然見つけた現象として、その場で旋回し続けると敵の弾を避けやすいことがわかりました。誘導弾が追う動きと旋回の動きがちょうどかみあって追いつけないまま機能停止しているようでした。そこで、わずかな時間、XY平面上では同じ場所を旋回し、高さ方向には大きく上下する動きで速度を落とさず弾を避けるようにしました。

敵を避けやすくなったことで、自機を外側、内側に分ける必要がなくなり、護衛機への到達もより早くなりました。自チーム内の強いエージェント同士の対戦では、護衛機への到達スピードで勝負が決まることも多かったため、これも大きな利点となりました。

この時点で自チームの強化学習エージェント相手の勝率は60%となり、壁打ち相手としてはちょうどいい強さとなりました。

非学習エージェントの開発停止

ここまで、自チーム内最強エージェントは非学習エージェントでした。背景に記載の通り、このエージェントは最終提出用途ではなく、学習エージェントの壁打ち相手として機能することが重要です。勝率60%は都合がいいと考えていましたが、その後の実験結果では、自作の非学習エージェントを対戦相手に加えて学習したエージェントよりも、BenchMarkやその他の学習エージェントのみを対戦相手にした学習エージェントのほうが、リーダーボード上のスコアが高いことが判明しました。
原因としては以下が考えられます。

リーダーボード上に我々の非学習エージェントに似たエージェントが存在しない
非学習エージェントに勝つために必要な戦略が、その他のエージェント相手に相性が悪い

よって、学習エージェントの強さを測る目的でも、学習を促進する目的でも、逆効果だと言えます。
非学習エージェントをさらに強くすることは可能だと考えていましたが、そもそも強くすることに意味がなくなってしまったため、この時点で開発を停止しました。