CodeVS参加記

せっかく参加できたので、色々と書いておく。

まず決勝に参加してみてやっぱり緊張したけど、最終的には楽しく過ごせた。
参加した動機の半分は就活目的だったけど、そういった意味でも結構、評価していただいたと思う。
自分の結果については、反則負けして勿体なくはあったけど、トップの方々に比べてタワー設置のアルゴリズムが大きく劣ってたし勝てはしなかったことを考えると、そんなに悔しくはない。問題に対するアプローチの仕方は今回、結構学んだことが多かった。

本当の決勝について
本当に良い試合ですごく良かった。敵が100ちかくでるマップでライフが1残るとか、ほぼあり得ないことだけど、それが決勝で起こるのだから面白いもんだなーと思う。
プログラムに関しては、個人名を出すのも難だけどyuukiさんのプログラムが凄かった。
周りの方々はyuukiさんが慎重すぎたように感じられるかもしれない。
けど、決勝用のデモとして配られたマップの中に極めてクリア困難なマップがあった。
そのことから決勝進出者の中では、お金はあるけどライフがなくなるようなゲームになるかもしれない、と考えている人は多かったと思う。
その高難易度のマップに対応するために、新しく戦略を考えたり実装したりするのは単純に大変なので、明確にそれをクリアできるようにプログラムを組まれたyuukiさんは凄いな、と感じる。
その結果、処理時間やお金が多少ではあるけど犠牲になってしまって、そこが敗因になってしまったのは仕方なかったのかどうかは難しいところだと思う。
今回はマップが進むにつれ、敵の性能は高くなるようだけど、それより直接的に難易度に直結しやすいマップの大きさや敵の出現位置の数なんかは前後半に依存しないようだったのも大きかった。
とにかく、本当に良い試合を決勝で行われた二人に拍手を送りたいと思う。


あとは予選や自分がとった戦略について書きたいと思う。

まず予選では可能だった埋め込みについて。
自分は一切、埋め込みはつかってない。というか、つかえなかった・・・。予選後、colunさんのツイートみて、すごく参考になった。
最終的に予選の自分の記録は残金40000だったが、決勝に参加してみて埋め込みを使わない上限は残金80000くらいではないかと思う。そういった意味では、決勝に行くために埋め込みを使う必要はなかったと思う。(多少、有利になる部分はあると思うけど)
他の決勝進出者の方々は多少なりとも埋め込みっぽいことをされているようだったけど、みなさんプログラミングの能力が高く予選で埋め込みができない仕様だったとしても順位はほぼ変わらなかったのではないかと思う。
この問題に関しては微妙だと感じる。
マラソン系のコンテストで入力の性質をつかんで、有利に働くようアプローチをかけることも重要な能力なことはたしかだけど、本質的なところから少しづれるのも確かだから。
ルールにない入力に制約されるのは微妙っていえば微妙・・・。
個人的には、もう少し埋め込みできないような仕様のほうが良かったとは思う。

信じられないかもしれないけど、CodeVSの決勝に行くだけなら高いプログラミング能力とかいらない。優勝を狙うなら、できないと難しいけど・・・。
理由は自分でコードを書く前に、ゲームに対して戦略を考えないといけない。この戦略を考えるのにあまりプログラミングの能力とかいらない。自分はCodeVSに関して200時間ちかくかけたと思うけど、最初から最終的にとった戦略があれば50時間もかからなかったと思う。つまり、対して実装してなくてずっと考えてたともいえるかもしれない。
データの可視化というか、判断材料を増やすためにプログラム書くことはあるけど、難しいアルゴリズムとか知っている必要ない。というか自分は知らない。

あとは自分がとった戦略について、つらつらと・・・
トップの方々に比べて劣っていることはあらかじめ明記しておく。
決勝ギリギリで進出できるラインの戦略と考えてもらえれば幸いです。
ソースコードを読むよりは分かりやすい文章になるはず・・・。

CodeVSは基本的に2つの問題に分かれる。
タワーを置く位置を決める問題と、どのタワーを先に強化していくかという問題。
重要なのは圧倒的にタワーを置く位置を決める問題で、理由はアルゴリズム的に難しく、タワーの強化とかは人間的な考え方でほぼベストな解が得られて簡単に実装できるし差がつかない。

この2つの問題の前に、シミュレーションについては完璧に実装しておく必要がある。(できてない自分がいうのも難だけど)
自分に都合の良い実装をすると(タワーの性能を過大評価するとか)あっという間にライフが無くなって死ぬし、自分に都合の悪い実装をすると(タワーの性能を過小評価するとか)無駄にお金をつかってしまうことになる。
実際に、自分はタワーの性能を過小評価して予選のマップを完走するのに苦労した。
結局、完璧にはならなかったけど、たまにしかライフが削れなかったので、無視したというかどこが悪いのかよくわからなかった。この辺でも、自分のダメさ加減が・・・。
そんな高速化しておく必要はない。高速なら、それはそれで便利な使い方はあるけど必須ではない。

タワーを置く位置を決める問題について
この点が他の方々より圧倒的に悪かった。ほぼ読む価値はない。
他の方のやり方については、簡単に聞いた感じゴール側から貪欲的にある程度、迷路をつくってから適当なとこで合流地点を決めて、出現位置につなげるらしい・・・。これから少し勉強したり調べたりしたいところ。
自分がとった方法は愚直にタワーを置いてみて評価して、置いてみて評価してという方法。
有効である可能性がある位置は現在の敵のルート上だけだから、他は対象から外して計算量を落としつつ。
評価方法は、各出現位置からゴールまでの距離の総和と、ゴールから一番近い出現位置を足し合わせたもので、ゴールから一番近い出現位置を大き目に評価している。
置いたタワーの位置でハッシュ値をつけて、再度計算しないようにとか多少は工夫したけど・・・。
この方法の致命的なところは
あっという間に計算量がやばいことになること
探索時間を増やしてもほぼ効果がないこと
できが良い時はそこそこのマップになるけど悪い時はすごい出現位置からゴールが近くなること
とかなり問題がある。

タワーを置いていく方法については発想の転換というか、かなり方法があるように思う。
chokudaiさんは最初のマップは難易度が低いので最長経路を狙う必要はない、とおっしゃっていたけど、どれくらいの経路なら大丈夫とか判断するのが結構難しい気がするので建てきっちゃって良い気がする。ラピッド0Lvなら大した問題にならないし、ラピッド0Lv自体そこそこの攻撃能力ももっているので。


次にどのタワーを先に強化していくかという問題
人間的に考えたとき、どのタワーを強化すると効率が良いだろうか?
簡単で、多く攻撃できる可能性が高いマップの中心の方のタワーから強化していけば良いと考えられる。この考え方でほぼ正解で、実際に決勝の方々もビジュアライザをみる限り同じ方法をとっている。
実装については、タワーの位置が中心に近いか調べるのとは少し違う。
まず、敵のルートに評価値をつける。敵が通るところを評価し、合流した後は複数の箇所からでた敵が通るため合流前より大きく評価し、フリーズタワーがあるところは少し大きく評価したりといった感じに。
あとはラピッドを4Lvにした時の射程範囲に含まれるルートの評価値を足し合わせていくと、強化した時のおおよその有効度が得られて、それをソートしておけば強化するのに計算量はほぼかからない。
他にルートではないけど、タワーが建ってないという位置もあるので、そこにタワーを建てたときの有効度も調べて、強化した場合と新たに建てる場合で最も有効度の高い順にやっていけば良い。
そうすると勝手に、マップの中心のほうから強化などをしてくれるようになる。


タワーの設置、強化する順番等、全部マップの最初レベル1の時に計算しておいて、それ以降はシミュレーションでクリアできないと出たときは強化してシミュレーションしてという流れだった。

フリーズタワーについて
自分はゴールの近くに適当にフリーズタワーを建てるという方針を取ってた。
フリーズタワーを11個建てることで完全停止を狙うことができたようだけど
そうしなかった理由は、
一斉にフリーズタワーが1人の敵に攻撃すれば完全停止することは自明だったけど
フリーズタワーの性質、充填が凄く遅いこと、射程範囲がかなり小さいことを考えると
最初に撃ったフリーズタワーの射程から敵が過ぎてしまう可能性があるのではないかと思って11個以上建てる必要があるのかな
と考えていたことが理由。
みなさんのツイートを見る限り11個で完全停止するようですね・・・。

フリーズタワーの有効性については
予選に限ってだけど、フリーズタワーをゴール付近に建てることで3000くらいお金のコストが良くなっていたため決勝でもつかうことにした。
決勝ではライフの戦いになるのかと考えていたので、お金のコストに効果があっても殲滅力としてラピッド以上の効果があるのか、は今の時点でも謎。

フリーズタワーの使い道については
決勝でも詰められてなかった部分で、そういった意味ではまだ伸び代がある。

と、以上のようなことを考えていると何とか決勝に行くことができる。

yuukiさんのような高難易度のマップに対応しようと考えたら、ここからさらに新たな戦略を考える必要がでてくる。すごい!てか大変!


長文になって煩雑になっている気がしてならない・・・。