決勝用AIの提出が完了しました。
提出完了後TLで感じたのですが、マラソンなどで経験を積んでいる人はやはり違うなあと感じました。
僕が試行錯誤で進んでいる所を当然のこととして一瞬で先に行っているのだろうなあと思います。
なのでここに書いてあることは相当筋が悪いです。
最終的にできたもの
- 幅100ビームサーチで3手探索。1手目のみ敵味方の忍術を考慮。
- 忍者2人を別々に考えたりはしない
- 序盤は再優先に取得するソウルを変えながら深い探索をし、最も良いものを採用。
- 落石や分身の危険・チャンスを察知し、相手の反応を伺う。
- 最初の落石・分身チャンスはとりあえず攻撃してみる。
- 「落石油断モード」「分身油断モード」
- 相手が分身を使ってソウルを強引に取っていると判断した場合、ソウルに敵分身する。
- 評価値の悪化を検出し、様々な評価関数を試す。
- それでも悪化が続いたら、「分身連打モード」
- 回転斬のために移動する「回転斬準備」
- 相手のソウルが尽きた時、詰み手順探索
- 二手詰みが見つかる程度
- 勝ちを確信したときにダンス💃
評価関数
n手先の盤面は、n個の移動経路の評価値の和と、最後の盤面の評価値を足して算出する。
- 盤面の評価
- 忍力(x100)
- 最も近いソウルまでの距離(x-1) (岩のあるマスは重みをつけて算出)
- 忍者同士が近すぎる時のペナルティ(距離3以下で-2)
- 経路の評価
- 獲得するソウル(x300)
- 回転斬で撃破する犬(x100)
- スキルを使われると即死する場合のペナルティ(状況により-10^5～-0.1)
以下、gitの履歴を見ながらひたすら振り返ります。
自分のモチベーション維持にAI名にバージョンを入れるのをやっていました。
v1～
とりあえず動かそうという段階。
- 犬が隣接していないマスに移動
- 岩は動かせないものとする
- ソウルまでの距離を計算し、最も近いソウルに移動
v2～
オンライン対戦での反省を活かしながら実装を進めた。
- 真面目なシミュレータを作る
- 1手探索。評価関数はソウルまでの距離と、端ペナルティなど。
- 詰んだら回転斬
- 詰んだら超高速
- 移動を落石によって妨害されて犬に捕まりそうな時、自雷撃
- 相手がスキル無しだと落石で詰む場合、敵落石
- 相手に2回回避されるまでやる。相手が防御系忍術を使えない場合は必ずやる。
- 詰んだら自分身
- 詰んだら自雷撃
v3.0～
作り直し。確かシルバーに居て、追い上げるぞという感じだった気がする。
気にするべき妨害は落石と分身。雷撃は即死にはならない。
分身は、自分身を使っていないときは即死にはならないので、考えないことにする。
評価関数は
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 壁付近のペナルティ
- 忍者同士が近すぎることのペナルティ
- 忍者周辺4マスに障害物や犬が多すぎることのペナルティ
- スキルを使われると即死する場合のペナルティ
を入れた。
1手探索で、高速移動、自雷撃、自分身、回転斬を試す。
自雷撃は忍者からの距離3まで。落石対策に関わる範囲がこれくらいなので。
自分身は四隅・犬の出現ポイント・忍者の居るマスを試す。
相手のスキルは、忍者の移動経路上の落石を常に考慮する。
自分身を使う場合は、忍者からの距離2までの敵分身と、分身上の落石を考慮する。
相手が妨害スキルを使ってこない場合にそのスキルへの警戒を緩める、「落石油断モード」や「分身油断モード」を実装した。
「分身油断モード」は実装が悪く、ほとんど機能しなかった。「落石油断モード」は妨害をしないAIにまあまあ刺さっていた。
v3.8～
ビームサーチを実装した。実行速度の関係で、2手目以降はスキル使用なし敵の妨害考慮なしにした。
最初は幅5深さ5とかを設定している(※まるで意味が無い)
評価関数は、盤面の評価と経路の評価を分ける必要性を感じたので、分けた。
盤面の評価は、
- 忍力
- 最も近いソウルまでの距離(岩は通過できないとする)
- 忍者同士が近すぎることのペナルティ
経路の評価は、
- 獲得するソウル
- 回転斬で撃破する犬
- スキルを使われると即死する場合のペナルティ
が該当する。
そして、複数手先の盤面の評価値は、経路の評価値の和+最後の盤面の評価値となる。
v4～/高速化
ビームサーチを実装したことで実行時間の問題が出てきたのでv3のAI部分を一旦消して、シミュレーション部分の高速化に取り組んだ。
ここで最後の方に実装したのも含めて高速化の話をしてしまいます。
AIはJavaで書いていたのでJavaの話です。
高速化をする上で役に立ったモノ・テクを列挙してみます。
オブジェクトプーリング
二次元配列のnewの時間がヤバイのでプールを作った。
ターン毎にほとんどの情報を捨てるので、ターン終了時にインデックスをリセットし、最初から順に取り出すということをしていた。
キャッシュ
犬の行動をシミュレーションするのに、忍者からの距離をBFSで求める部分がボトルネックになっていたので、岩と忍者の位置を入力、距離の配列を出力としてHashMapに突っ込み、必要に応じて取り出すようにした。
忍者が岩を動かさなければキャッシュにヒットしまくりなのでかなりの短縮になった。
バケツソート
犬を忍者からの距離順・id順にソートする部分に標準ライブラリを使っていたが遅いため専用のソート関数を自作した。
距離は0から100程度までしかない(本当?)ためバケツソートを使う。id順にソートする部分は挿入ソートを用いた。
配列を初期化する時間をケチるために、タイムスタンプを使って、バケツから出し入れするときに有効なデータか判定した。
並列化
移動を全パターン試すという処理がよく出てくるので、パターンをいくつかのブロックに分けて突っ込む。java.util.concurrentパッケージ大活躍。
色々高速化して結局一番遅いのはやっぱり犬の移動シミュレーションでした。
おおよそO(犬の数)になったと思うのですがう～ん
v5～
v4で高速化が済んだのでv5とした(バージョンの上げ方が適当過ぎる)
高速化が済んだ分探索できる量が増えたので、色々実験をしてどこに計算時間を割けばいいか色々検証する。
ビームサーチのパラメータ調整をした。
パラメータ調整に関する知見が全く無かったので、眺めてみたり自己対戦を重ねた。
色々試した結果、幅15深さ1か幅100深さ2くらいが適当だなあと思った。
深さや幅をこれ以上増やしてもあまり効果が得られなかった。
同一局面除去しないとビームサーチが貪欲と化すので気をつけましょう😇
— ぴろず (@p_shiki37) 2016年3月22日
評価関数が最も近いソウルまでの距離を利用しているからビーム内が似たり寄ったりになると思ったのですが、そもそもの原因はこっちだったかもしれない・・・
つまりビームサーチというよりは枝刈り全探索に近い？
探索が改良された分、評価関数のペナルティ項の多くを消した。
評価関数、特に何も考えずに忍力1につき100点、ソウル取ることは100点(つまりソウル獲得で合計+300点)
としていたが、忍術を使ってでもソウルを取る方が良い場面の方が多いので、ソウルを取ることの点数を300点にし、ソウル獲得は合計500点になった。
したがって、コスト5未満の忍術を使ってソウルを取れるなら積極的に忍術を使う。
結構動きが良くなるが、コスト高めの高速移動を使いすぎる傾向が出た。
普通のビームサーチの後、ビームに残ったものから追加の細いビームサーチをして、最も良い物を採用という処理を追加してみた。
これは出現するソウルなどを考慮していない分、微妙な動きをしてしまうのであとで消した。
ビームサーチが貪欲に近くなってしまうことの対策として、通常の評価関数で取れるソウルが無くなった時、複数の評価関数を試すという処理を取り入れた。
色々な評価関数を試してみたが、最も効果があったのは、特定の点との岩を無視した距離を使う評価関数だった。
点としては、マップ上の4隅と中央を使った。つまり、困ったときに追加で5つの評価関数を試す。
これにより、近くのソウルが取れない時に大胆な移動をして遠くのソウルを集めることが可能になった。
複数の評価関数を試しても3ターン連続で評価値が悪化する時、「分身連打モード」に移行する。
「分身連打モード」では、敵のスキルを無視し、いずれかの角に自分身を連打しながら最も近いソウルに向かうという動きに限定し、11手の深い探索を行う。
これにより、強引なソウル取得による粘りが可能になった。
なお敵分身には弱いが、敵分身を適切に使ってくるAIは予選のときにはほとんど居なかったので、結果として強くなった。
通常の探索でソウルが取れるまで近づければ、通常のモードに戻る。
v6
v5のAIのメイン部分がスパゲッティ化して頭が痛くなったので、一度リセットしてv6にした。
決勝の前日、最後のリセット。
v3の時にあった「落石油断モード」「分身油断モード」を復活。
これで「落石油断モード」「分身油断モード」「分身連打モード」「秒読みモード」の4つがあることになりif文地獄と化した。
上位陣で回転斬をうまく活用する流れがあったので、回転斬を積極的に使う動きを追加した。
具体的には特定の条件を満たすと、2ターン目に多くの犬を回転斬で倒せるような移動を探索する。
相手が忍術を使わないと落石や分身で詰むようなタイミングで、相手がどの忍術を使うか、あるいは使わないかを記録して、
攻撃をするかどうかの判断材料にする仕組みを復活。
pirozAI[6.5.1]、決勝進出！
決勝までの間もオンライン対戦をしたいが、油断モードや分身連打モードの対策をされるとマズイので、
実行時引数でこれらのモードを抑制できるようにした。
本戦に向けて並列化などのパフォーマンス改善をした後、基本的な動きの改善を試みた。
忍者同士が固まってしまう問題に対して、
- フィールドを4分割し、同じエリアに入っていると減点
- 忍者同士の距離が3以下だと減点
を試した所、後者が良かった。
また、序盤のソウル取得効率が勝敗に大きく影響することに気づいたため、
序盤は、再優先で取得するソウルを指定した評価関数というものを実装し、それぞれで細くて長めのビームサーチを実行。
最も評価がよかった評価関数を採用し、通常のビームサーチを行うという動きを実装した。
序盤のソウル取得効率が向上した。
ここまで忍者からソウルまでの距離計算では、岩は通れないものとしていて実際との剥離が大きかったため、
動かせる岩を重さ3,動かせない岩を重さ10として距離を計算するようにした。
動きはおおむね良くなったが、ソウルが岩で囲まれているような場合や、ソウルが岩でできた通路にある場合にはハマることが増えた。
これの対策にもなるが、2番目に近いソウルと3番目に近いソウルへ向かう評価関数を追加し、
複数の評価関数を試すフェーズに入れた。
複数の評価関数を試すフェーズに早めに突入するために、ビームの中身を見て、1手目から3手目で評価関数が下がるならば早めにこのモードに入るようにした。
複数手詰み探索を実装した。実際に動かしてみると、価値のある詰みを見つけられることはほとんど無かった。
唯一、敵が自分身を使えない時に2手詰みを発見できるので、この場合のみ探索するようにした。
これだけだと勿体無いので、勝ちを確信した時に意味のない動きをする「ダンスモード*1」を実装した。
ちなみにデバッグには役立った。
もうすぐ決勝
決勝出るぞニコファーレ行くぞ
ニコ生で放送されるぞ
live.nicovideo.jp
正直決勝進出者は皆強すぎなので勝てる気がしません。
あとは乱数の神に祈って、いい戦いを見せてくれることを期待します。
*1:またの名を煽りモード
