花枕杯に参加してきました。
これは花AI塚というツールを使い、東方花映塚上で動作するAIを実装し戦わせ最強を決めるコンテストです。
自分の総合順位は5位、ただし参加者総数は5人、つまり最下位でした。
まぁ結果は散々でしたが、参加はしたのでその感想とか、参加したAIの解説とか、そういうことを書いておこうと思います。
参加したAIはこちら。
名前：縦移動禁止花AI@メディスン
http://wordpress.click3.org/garakuta/tate_kinshi_hana_ai.zip
AI解説
ひとまず.zipの中に入れた解説を丸ごとペタリ。
縦移動を封印し、横移動だけに特化してそこそこ戦えるようにしたAI。
別になめプではなく、余裕こきすぎて24時間しか作業時間が取れなかったため、
実装内容を絞って時間対効率の最大化を図ったためこうなった。アルゴリズムも最初考えていたものが処理速度上不可能と発覚したので即興。
その割には結構いい線いってると思うが現実は如何に。@メディスンとあるが、別に専用カスタマイズされているわけではなく、誰でも動く。
単に作者がメディスン好きなだけである。
メディスンかわいいよメディスン。一応LunaAI相手でもラウンド取れることもあるぐらいにはちゃんと戦える。
※ただし咲夜さんと映姫様除く。仕組み：
自身のy座標一列分の配列(以下危険度マップ)を作り
弾や敵などに対し、そのy座標に到達するまでにかかる時間と、到達したときのx座標を算出。
その周囲を到達までの時間で埋めるを繰り返す。すると、弾が到達するまでにかかる時間が長いx座標ほど安全という理屈により、
どの辺のx座標を目指せばいいかがなんとなくわかるので、
あとはそれを念頭に置いて移動したり色々するだけのAI。一応軽いキャラ対策などは入れたが、後述の弱点のように問題点は多い。
それ以外にも、粒弾相手でも被弾してしまうようなコーナーケースのつぶしは足りないし、
長期的展望による回避行動もとらないし、C2の運用やコンボなど改善の余地はたくさんある。弱点：
当然ながら縦には移動しない(というか後ろの弾がまったく見えていないので出来ない)ので、
咲夜さんのC2/C3は撃たれたら真横弾で落ちるのは確定。
映姫様の自機狙いレーザーの対策をとっていないので、されるとあっという間に死ぬ。
文さんのExは判定強いくせに早いので、ちょっと周囲の弾配置が悪いとすぐ詰む。
ルナサを相手にすると後ろから弾が飛んでくるため運ゲー化する。
チルノはパーフェクトフリーズで背後の弾がこっち向かってくると避ける手段がない。
ミスティアは未対策なので、チャージアタックの弾源に重なり落ちる光景がよく見られる。
てゐさんは中央からちょっと外れるとExの軌道に巻き込まれ、そのまま壁と挟まれて死ぬ。
中でも書いてある通り本体の実装に取れた時間がエントリー最終日である1月31日の24時間しかなかったため、突貫作業で実装されたAI。
時間がなくなった理由はこれとかこれのせい。
それ以外にも仕事で休日出勤が4日ほどあった。
まぁ期日が決まってるものがあり、不測の事態もありうるのに、他にかまけていた自分が悪いという話でした。
さてAIですが、最初は縦移動封印などする気はなく、まったく別のアルゴリズムで作るつもりでした。
画面全域を表す二次元配列を作り、そこの弾の予想軌道上に「到達までにかかる時間によって減算される危険度」を設定し、そこから判明する付近の安全領域に向かって移動する、という感じ。
単純にこれだと計算量がとんでもないことになると予想は出来ていたので、対象の弾を自分の周囲に限定したり、弾や自機のxyを割る5した値を使うなど軽量化案はいくつか考えていました。
だが現実は予想以上に厳しかったのです。
なんと300*450(ゲーム内の移動可能範囲+α)の配列をローカル変数として定義しただけで、体感してわかるほどの強烈なラグが。
調査の結果、テーブルのリサイズがありえないほど重いようで、事前に値をつめておいて更新するだけならそれほどでもないことが分かったのですが、自分はこの事件で心が折れてしまいました。
なので、処理速度が問題にならないぐらい軽いアルゴリズムを検討するところから始めることになります、ちなみにこの時1月31日の午前5時5分(エントリー締め切りは1月31日24時00分)。
そこで考えたのが、自分は普段どうやって弾幕を避けているのか。
最初のアルゴリズムの軽量案である”xy割る5″も、自分がプレイするときは1ピクセル単位で見ているわけではなく、もっと荒い単位でとらえているはずだという点からきているからです。
そこで気づいたのが、避けるだけなら最下段に張り付いて、基本的に左右移動だけでなんとかしている、という事実。
実装に割ける時間も少なかったので元から攻撃に関することは諦めようとは思っていました、なので縦の移動を封印し横移動だけに特化すれば、簡単かつ高速に動作するAIが作れるのではないか、と。
考えている時間はありません、なので自分はこの閃きに賭けることにしました。
さて、横移動にだけ限ると言ってもアルゴリズムはいくらでも考え付きます、だがそんなのをまともに検討している時間はありません。
なので初案のアルゴリズムをそのまま横一列に限って使うことにしました。
これは単純に危険度マップのサイズを減らすだけに留まらず、考慮するべきフレーム数問題をも解決しています。
なぜならば、弾がそのy座標を通過する1フレームだけ考慮すれば基本的に十分だからです。
後に、実際には弾の大きさを考慮して前後数フレームは検討しなければならないことに気づきますが、それでも初案に比べれば劇的な高速化でした。
(画面全域、全弾対象、xyを整数に切り上げただけの値を使用、10フレーム先まで計算、と比較すると単純計算で実に1/4500の計算量)
ちなみにこの時午前5時22分。
この後は特に面白い話はなくて。
ひとまずベースの実装を終え(7時15分)
Easyにすら負けるレベルでバグバグだったのでひたすらCPUと対戦してバグをつぶし(10時16分)
朝ご飯を食べ(11時23分)
拡張にかかるコストが大きくなりすぎたのでリファクタをいれ(13時05分)
※この時点で自分では勝てない強さに到達してます、とはいえ自分は花はとても弱い(花Exが安定せず、クリアできたことが過去二回しかない)のであまり参考になりませんが。
LunaCPU相手にひたすら勝負を挑み被弾したら原因を調べて潰すを繰り返し(16時11分)
キャラごとの個別対策をひたすら入れ(21時52分)
全キャラ相手に一戦してそれだけで勝負が終わるほどの致命的バグがないことを確認し提出した(23時26分)
その後は
エントリー人数や使用キャラなどが公開され(02月01日 01時02分)
就寝(01時21分)
花枕杯開始(14時00分)
花枕杯終了(16時00分)
起床して最下位だということを知る(18時54分)
となっています。
さて、AIの解説に戻りましょう。
本AIで縦移動禁止や作成にかかった時間を除く大きな特徴として、マイクロスレッド上に実装されいるというものがあります。
マイクロスレッドというのはコルーチンやファイバーの親戚で、実態はシングルスレッドですがまるでマルチスレッドのように使え、なおかつスレッドの切り替えタイミングを自身で決められる仕組み、です。
これにより、1フレームに一回だけ実行する処理を簡潔に書けたり、フレームをまたいでもローカル変数を維持しておけたり、といった恩恵を受けられます。
と言ってもこれはあれば便利程度の物で、AI作成では大して重要でありません。
ですが、私はマイクロスレッドをとても愛好しているので導入しました(私制作のAIツール3種すべてでマイクロスレッドが提供されているのもそのため)。
マイクロスレッドはmy_lib.lua上に実装されていて、create_([head|tail]_)?threadで作成、yield関数を呼び出すと次のマイクロスレッドに実行が移り、すべてのマイクロスレッドが一度ずつ実行されると次のフレームへ進む。
headやtailはマイクロスレッドの中での実行順序を指定するための物で、headで作られたものはそうでない物すべてよりそのフレーム内で先に呼ばれる、tailは逆に後に呼ばれる。
たとえばtailはキー操作に使われており、他のスレッドでキー操作をしたくなったらグローバルの配列上にポンポン投げ入れ、tailのマイクロスレッドでその結果を一つにまとめてsendKeys関数に渡している。
感想とか色々
花枕杯は非常に楽しかった。
一時期TopCoderをやっていた時も思いましたが、参加者たちがさまざまな方法論でプログラムを作成し、それらを競わせるというものは知的遊戯として非常に面白い物です。
結果は残念なことに最下位で、それ自体は非常に悔しいのですが、そういう感情すらただプログラムを書いているだけでは味わえないもので、醍醐味の一つだと思います。
本選をリアルタイムで見れなかったのは地味に凹みました。
いや前日に30時間以上連続で起きていたのだから当然ではあるのですが、なぜ14時までに起きられなかったのか……。
自分が独自アルゴリズムで参加したのは、作業時間的に劣る自分が勝てるとしたらアルゴリズムで優るしかないという思いからだったのですが、結果だけ見るとそんなことしない方が結果は良かったかもしれません、反省。
だけど、自分のAIの弱さがまるでアルゴリズムが劣るせいととられていそうなのが心残り。
なので、次回があればこのAIの正当進化系で参加しようと思っています。
もしかしたら次回を待たずに余暇で改良して公開するかもしれないですが、その時は適当に遊んでこいつ相変わらず弱いなーなどと楽しんでください。
それと作者さんが参加者の一人だったせいか、期間中に花AI塚にバグが次々と見つかり日々修正されていくというのもなかなかに面白い事態でした。
花AI塚のソースコードが公開されていたりすると、原因行数まで特定してのユーザーによるデバッグも行われてさらに楽しそうですが、ツールの性質上花映塚の対人チートに利用できるため無理なんですよね、残念。
実はAI提出時点では自分はエキシビジョンの存在をすっかり忘れていました。
提出時に主催であるろくしーさんさんに聞かれて思い出したものの、そこから実装を変更するには時間が足りず、そのまま提出することになりました。
結果はエキシビジョンも同点最下位、まぁ当然ですね。
一応最下位のもう一方は被弾時以外C1しか使わない妖夢AIさんであったため、もし最下位決定戦が成立していたら勝てたのかもしれませんが、お互いにエキシビジョン専用処理なしなので所詮どんぐりの背比べですかね。
最後に、主宰のろくしーさん、ツール開発の@ide_anさん、自分以外の参加者さん、とても楽しかったです、ありがとうございました。