yukicoder score contest 6 writer記
少し時間が経ってしまいましたが、先日 yukicoder score contest 6 を開催させていただきました。今回はテスターは yunix さんにお願いしました。
優勝者は terry_u16 さんでした、おめでとうございます！
問題概要
縦スクロール型のシューティングゲームをプレイするプログラムを作成してください。
敵機は最上段に出現してグリッドを下に降りてくるので、最下段の自機を左右に動かしてうまく敵機を避けながら攻撃してね。
yukicoder.me
今回はリアクティブ形式の問題でした。毎ターン敵機がどの列に出現したか与えられるので、それに応じて自機をどう動かすかを決定します。
途中で敵機に衝突せずにゲームを終えられれば、シンプルな解法でもそこそこの点数が取れます。ただし衝突判定は結構バグらせやすく、短期コンテストだと厄介だったかもしれません。
想定解 (writer解/tester解)
序盤は基本的にプレイヤーの強化(=パワーの取得)を優先し、終盤で一気にスコアを稼ぐと良いというのは writer/tester 共通の見解でした。
この方針に則ったシンプルな貪欲法も結構強いのですが、ある程度シミュレーションで先読みして行動を決めた方がより強そうです。試しに使ってみたかったこともあってwriter解はモンテカルロ木探索(MCTS)のような何か*1、tester解はビームサーチでした。結論としてはこの問題はビームサーチの方が優秀だったように思います。
ビジュアライザ
前回に続き Siv3D というC++用のフレームワークを用いてアプリケーションを作成しました(Linux版を用意できなくて申し訳ないです)。アプリケーションが配布される形式は Topcoder のマラソンマッチ経験者なら慣れていそうですが、AHC はブラウザなのでそちらに慣れている方も多いかもしれません。Siv3D には web版も用意されているので、次回以降はそちらと併用することも検討しています。
グリッド上で敵機も自機もただの正方形で表示されているシンプルなグラフィックですが、それでも終盤に敵機をたった一撃で次々に破壊していく様子は見ていて爽快だったのではないでしょうか。
やはりこうしたアプリケーションを一番使い慣れている言語で実装できるのは助かりますね。この場を借りて Siv3D の制作関係者に御礼を申し上げます。
問題作成の経緯
ヒューリスティックの問題を作成する時はストーリーから作ることが多く、今回もそうでした。題材はいくつか考えていたのですが、シューティングゲームは問題を作りやすいかなと思って採用しました。最初から全ての敵機の情報がわかっている形式でも良いかなとも思っていましたが*2、より実際のゲームに近いリアクティブ形式にしてみました。敵機を倒し続けると自機がレベルアップして、ゲームが進むにつれて敵機も強くなっていく、というよくありそうなゲーム設定にしました。
ここまでは特に問題はなかったのですが、実際に問題を作るとなるとパラメータの設定がかなり難しいことに気付きました。敵機が弱すぎて簡単に殲滅できても困るし、逆に強すぎて全然倒せなかったらどうしようもありません。敵機の出現頻度や、自機と敵機の成長のバランスも悩ましかったです。とりあえず適当に設定して自分で解いていたのですが、後にビジュアライザが完成して結果を眺めてみるとかなりめちゃくちゃなパラメータ設定になっていました。やっぱりビジュアライザは偉大です。
色々とパラメータをいじってみたのですが、最終的には「序盤はパワーを重視して自機を強化、終盤で敵機を大量に破壊して一気にスコアを稼ぐ」といったゲームの性質の変化を実現できたかなと思います。
雑記
フィールドの左右がつながっていた？！
今回の問題はフィールドの左端と右端がつながっているという設定でした。最初はこの設定はなかったのですが、ずっと真ん中付近に陣取るのが強くなってしまいそうだなあと思って変更してみました。ここの説明文は特に強調していなかったこともあって、気付かなかった参加者が一定数いたようでした。ごめんなさい！
コンテストの形式について
yukicoder でスコアコンテストを開くのは3回目ですが、前回と同様にチームでの参加を可能としました。これはチームで参加できるヒューリスティックコンテストがかなり限られているので、そういった機会を提供したいという思いがありました*3。加えてコンテスト中でも問題への言及やビジュアライザの共有をほぼ制限しませんでした。普段の緊張感があるコンテストとは違いお祭り感覚で盛り上がってくれたら良いなと思っています。
優勝争い
順位表をずっと眺めていました。かなり早い時間帯から tomerun さんが高いスコアを出していてずっとリードしていたんですが、終盤にてりーさんが猛追してきて勝手に盛り上がっていました。ところが少し目を離した隙に nikaj さんという方がトップに躍り出ていて、なんか見たことないすごい人が現れたなーとか思っていました。よく考えると(よく考える前に気付くべきだった)、Topcoder のマラソンマッチに nika さんというレジェンドがいることに気付きます。いやまさかね、問題文は日本語しかないしさすがにこのコンテストの存在を知りようがないし、と思って恐る恐るコードを覗いてみたところ、どう見ても nika さんでした。もう yukicoder も国際化の時代です。
ここら辺で勝手に盛り上がりがピークに達していましたが、最後の提出で見事てりーさんが逆転優勝を決めました。世界トップレベルの戦い、とても見応えがありました。それにしてもてりーさん強すぎませんか？
最後に
今回も無事にコンテストを終えられてほっとしています。改めてテスターの yunix さん、コンテストに参加してくださった皆さん、参加できなかったけど問題を解いてくださった皆さん、ありがとうございました。そしてコンテストを開催する場を提供してくださっている yukicoder さん、いつもありがとうございます。これからもお世話になります。
今回はコンテスト終了後に twitter で振り返りスペースを開いてみました。そちらに参加してくださった皆さんもありがとうございました。
これからもコンテストを開いていきたいと思っていますので、次回以降もよろしくお願いします。
そういえば、スペースではマラソン作問が話題になりました。きっと次回の yukicoder score contest は yunix さんが開催してくださると信じて、今回は筆を置きたいと思います。
