問題

www.topcoder.com

戦略

主に以下の 2つになります。

各エルフについてルールベースによる行動の選択
- 経路についてはダイクストラ法を使用しての探索
どの AI が使用されているかの検出 & メタ戦略

今回の問題では各AIの弱点を上手く攻める必要があったので、序盤の箱の配置でどの AI が使用されているかを検知し各AIに対して特化した戦略を使用しました。個人的な攻略難易度としては「AI3 > AI2 > AI1 > AI4 > AI5」の順となっています。

AI のタイプ推定

自分は C++ を使っていたので Java で書かれた AI のコードを C++ で書き直して、各 AI がどの位置に箱を置くのかをシミュレーションしてその一致率が高いものを採用しました。正直 AI のタイプについては入力で渡しても良かったと思います。（特に AI2 と AI3 の判別が難しかったので）

AI5 対策

今回のAIの中で一番攻略が容易となっています。AI5 の特徴としては以下の 2つになります。

ターン毎に指定された座標に箱を置く
プレゼントを守る行動は一切行わない

そのため「プレゼントに向かって移動、プレゼントを回収したら戻る」というコードを書くだけでもプレゼントの回収率 100% を達成することがほぼ可能です。（無理なパターンとしては プレゼントの数 > エルフの数 の時ぐらいです）

あとは全ての AI 攻略に共通する対策ですが、プレゼントの回収は画面外から遠いもの（中央付近）を優先するようにしています。これは終盤に出現したエルフが何も回収出来ずにゲームが終了してしまう可能性をなるべく排除するのと、後半になればなるほど中央の守りが堅くなり到達が困難になるため序盤のうちに回収したいからです。

余計なお金を使わせる

AI5 はプレゼントが全て回収されたあとも箱を設置してくれるので、最後の 1個のプレゼントに関しては回収したあとに画面外から出ず待機させ、他のエルフに箱を回収させるようにしています。そうすることでマネーを消費させてスコアアップを狙うことが出来ます。

この「あえてゲームを終了させずに箱を設置させることでマネーを消費する」という戦略も全ての AI 共通の戦略となっています。

AI4 対策

特徴としては「プレゼントが危なくなったらブロックを行う」プレゼント防衛型の AI となっています。そのため、単純に接近するだけでは箱でブロックされてプレゼントの回収が行なえません。そのためいくつか工夫が必要になります。

AI4 の弱点として以下の 3つがあります。

プレゼントの周辺マス以外については特に警戒されない
箱かプレゼントを保持しているエルフは警戒されない
プレゼントを回収しているエルフに対するブロックは行われない

そのため自分の戦略としては「箱 or プレゼントを持っているエルフを利用して警戒されずにプレゼントに近づく」というものを採用しました。

具体的には下記の画像のような プレゼントの周辺 4マスのいずれかを箱 or プレゼント持ちのエルフに待機させる 状態を維持するようにします。

この状態を維持することで安定してプレゼントの回収を行うことが出来ます。

具体的には プレゼントに近づいても箱でブロックされる ということが無くなります。

近づくと箱でブロックされる。

箱でブロックするのをプレゼント持ちのエルフで回避して、位置を入れ替えることでプレゼントの回収を行う。

AI1 対策

特徴としては「プレゼントの集合を効率よく囲んでブロックする」エリア防衛型の AI となっています。各プレゼント毎にブロックを行うのではなくエリアに対してブロックを行うので箱を効率よく利用できマネーの消費を抑えることが出来ます。

MM131 においては一番優秀だった AI1 ですが 1つ弱点が存在しております。

プレゼントを囲む経路上に箱が置けない場合は箱を置かない。

また、この経路を作成する際には木以外のマスについては同じコストで計算されているので画像のような箱で囲まれている状態と

経路の一部にエルフが入り込んでいる状態は経路のコストとしては同じになります。（エルフがいる位置に箱を置きたいが、エルフがいるので箱を置くことが出来ない。また、コストが一緒なので箱持ちエルフを回避した経路を作ることもない）

攻略としては以下の段階を踏みます

囲まれている部分の箱を回収する
箱を回収したエルフは「ゲート役」として他のエルフが囲いの中に入る手助けを行う

ゲート役について

ゲート役のエルフは他のエルフがエリア内に入る手助けを行います。具体的には近くにエルフが来たらマスを開けて通り過ぎたら元の位置に戻るという行動を行います。

この行動は相手の AI が箱を置きたい場所を常にエルフがいる状態にして箱を置くのを防ぎつつエリア内の出入りを自由に出来るというメリットがあります。

AI2, 3 対策

この 2つの AI が今回の攻略で一番難しかったタイプになります。

AI2, 3 は基本的な方針は一緒で「箱が置ける場所に置いてみて、一番プレゼントが回収しにくくなる場所に箱を置く」というものです、評価値の算出方法の点が異なります。

少ししか改善されない場合でもマネーがある限りどんどん箱を設置していくので、MM131 的にはあまり良くない解法でも今回の問題に関してはかなり攻略が難しい AI となりました。（箱の物量作戦で押し切られるのが一番つらい）

基本的な攻略は AI1 の時と一緒でゲート役のエルフを上手く使いながらエリア内に侵入しプレゼントを回収していきます。

閉じ込められるのを回避する

箱を回収する際に場所によっては閉じ込められて再度箱の回収が必要になってしまうので、それをなるべく避けるために相手の箱の設置場所を先読みしてなるべく閉じ込められないように行動するようにしています。

次のターンで再度閉じ込められてしまう。

相手の行動を先読みで閉じ込められないように行動。

これで大体 1% の改善です（AI は 5つあるので 0.2% の改善）

正直この 2つのタイプについては特に特化した戦略を思いつかなかったのであまりスコアは良くありませんでした。（複数のエルフを使って攻略する案はあるのですが、実装が複雑になりそうなので止めました）

まとめ

いつもの問題だとジャッジ内部の AI のコードを読んでそれに対応するコードを実装するみたいな感じだと思うので、AI のタイプが複数あってそれぞれに対応する必要があったのは斬新だなと思いました。ただ高いスコアを得るためにはジャッジコード + AIのコードを読む必要があり、AI のコードが Java で書かれていたため C++ で再実装する必要があったのでいつもよりコード量が多くなってしまったのは少し面倒だなと感じました。（AI のタイプを推定するためにも移植は必要）

ルールベースのコードを書くと毎回最後の方で条件が複雑になってしまって、最後の方はデバッグに時間が取られてしまったのは戦い方としてはあまり良くなかったなと思った。まだ実装したい案はいくつかあったけどバグの埋め込みの可能性のほうが高いので結局手が出せなかったのは残念。