CodinGame Spring Challenge 2020 に参加した

ツイッターで何度か流れてきたので途中から試しに参加してみたらめちゃくちゃ熱を上げてしまった。わりとしっかりしたメモを残していたうえ、思いがけずかなり気持ちになってしまったので感想を書いておくことにする。

まずコドゲに登録した日が1週間くらい前になるらしい。正直に言うと最初にルールを読むだけで疲れてコードを初めて書いたのは何日か経ってからだった。

13日にコードをいじり始めたが、そもそもAtCoderしかしたことがないので初期コードを読むだけで一苦労だった。とりあえずwoodでは使わないとコメントされているスキル周りの受け取りを削った。これで受け取りはできていると思ったので、出力をいじるためにペレットの情報を受け取ったら、スーパーペレットから順に一番近いペレットにそれぞれのパックを向かわせることにした…ところ見事に出力が壊れた。パックをちゃんと指定できていないのかなあと思って色々試しても何も変わらなかった。結局この日は途中で投げ出してしまった。

14日になって、woodでは使わないとなっていたスキル周りの入力もされているのではないか？とふと思いついた。さっそく初期コードに戻して同じように近くのペレットに向かわせたらあっさりwoodを抜けてしまって拍子抜けした。もしかしたらこのままbronzeも抜けられたりしないか！？と思ってそのまま出したがもちろんそんなことはなかった。そもそも全部のペレットの情報を教えてもらえなくなっていたから当然である。ルールの変更に合わせて適当に色々いじっていたらいい時間になっていたので切り上げた。最初はそんなに一生懸命になるとも思っていなかったので、自分でもそろそろ切り上げて寝たほうがいい時間だなと自然に思った時はびっくりした。寝たほうがいいのは分かっててもまだやりたいと思えるのはありがたいことである。今回は定石的なものはなにも調べずに思いつきだけでやってみてもいいかなと当初は考えていたが、丸一日ウンウンうなってそこにこだわるより関心が高まっている時に調べて調べてやったほうがよさそうだなという結論になった。

次の日はさすがに根本的に方針を変えようということで、こちらの記事を参考に方針を練ることにした。

競技プログラミングにおけるゲーム木探索の面白さ - Qiita

この記事を書いているツカモさんのツイートを見てコドゲを始めたので、自然な流れでビームサーチってのがあるんだ～やってみよ～という話になった(自分の中で)。地獄の始まりである。15日はひたすらビームサーチやらゲームAIやらの記事を読んで過ごした。

翌16日、いよいよ実装だぞ～と元気よくパソコンの前に座る。まずはお試しで盤面の情報と動かしたいパック一つの情報を持たせて10ターンほど探索させてみようかなということになった。というわけでもちろん実装できない。バグってから原因を特定してC++でpriority_queueにpairを入れて降順に並べることができるようになるのに3時間くらいかかった。AtCoderで分からないことがあっても問題名とコンテスト名で検索すればいくらでもわかりやすい解説が出てくるけれど、今回はもちろんそういうわけにはいかないので苦労した。うまく検索する能力も鍛えないといけないし、コードのどこが悪いのかも適切に判断しないといけない。この1週間で今まででは考えられないくらいリファレンスやAPG4bを読み込んだ。ひとまず優先度付きqueueはそれらしい動作を始めたのでいったんわきに置いて、簡単に改善できそうな延々ぶつかり続ける味方同士の処理やじゃんけんまわりのコードをいじってみた。すぐに分かるバグがなかったので提出したところburonzeの200位後半まで浮上した。woodを抜けた時はいきなりすぎて喜ぶよりも呆れてしまったけれど、全然できん！と思って考えて調べて書き換えて調べて書き換えて考えて書き換えてを繰り返したコードが途中で止まることなく動いているのを見ると勝ち負けに関係なくめちゃくちゃ嬉しかった。この日はじゃんけんで負ける相手に特攻するのをやめさせるのに残りの時間をつぎ込んだ。いつの間にか夜中の3時になっていて、ここ最近1時には寝ていた人間としては自分のはまり具合にちょっと引いた。

17日になって、ビームサーチのやってることだいたいわかりましたし、ちゃんと自分の手持ちパック全部を同時に動かして一番いい手を取らせますわ(ドヤ顔)といって探索部分を一から書き直した。結果から言うとコンテストが終わるまでにちゃんと書き切ることができなかった。グリッドの状態をint型の二次元配列で持たせてちゃんと更新処理していけばいいと思ったのに…。各ターン手持ちパックを順に一つ選び、ある方向に動かしては次のパック…と最大5パック分繰り返して計1024通りのうちよさげな20個くらいを候補にしたらいいだけのはずなのに…。timed outがかなり出ていたので、基本的なところの見落としで意味の分からないループをしたりとかそんなことだと思うけれど結局そこから一日半かけても満足に動かせなかった。探索ターンを短くするとびっくりするくらい反復横跳びをし始めて笑ってしまった。そもそもデータの持たせ方がよくないとか、サーチの理解が間違ってるとか、コピーに時間がかかってるとか、原因はいくらでもありそうなのでコンテストは終わったけれど少しずつ解消していきたい。やりたいことはいっぱいあったんだよね…。基本的に相手に近づくのは倒されるかもしれないし、相手に近い位置にあるはずのペレットはとられるしで悪手なので、勝確の時以外は相手がいるとわかっている方向は評価を下げて、存在が(見えていて)確定しているペレットは100、未確定のペレットは50点にしたいとか。あるいは相手のスキルが使えるようになるまでにこちらがスピードを使えば確実に追いついて倒せるときは倒すとか。逆にスキルが使えない時に負ける手の相手が出てきたら逃げるとか。今の相手の位置とその前に見た位置から通ったところを逆算して未確定ペレットを確定させたりとか。出来たらいいなあと夢を見ていたら夢のまま終わってしまった。一応収穫もあって、コメントでは代名詞を使わないほうがいい(書いてるときは自明すぎるので面倒くさいが、次に読むときは30分後でも覚えていないので冗長なくらいに書かないと書いてないのと同じくらい分からない、睡眠を挟むと驚くほど覚えてなかった)とか、グリッドに持たせる数値はそれぞれ最初に変数として宣言しておいて(壁は wall = -1,自パックは mypac = 10とか)、変数に入れる値を変えることで一括で管理しておいたほうがバグらせずに済む(const INF = 1e9 ってこういうことなのか？)とか。それなりに長いコードを書くのは初めてだったので勉強になることはたくさんあった。

最終的にはパックをそれぞれ探索したコードにいくつか手を入れて提出した。結局最後に加えた変更は改悪だったようで、bronze1700位でフィニッシュした。自分でもびっくりするくらい悔しくて、こんなに熱くなることがまだあったんだなあと我ながら感心した。仕事を探すために始めたプログラミングでこんなに夢中になるとは思わなかった。自分のやってみたいことが出来たときにこんなにうれしいのも予想外だったし、逆にやりたかったことが全くできないときにこんなに悔しいのも予想外だった。このブログに感情マシマシの記事を書く気なんてサラサラなかったけれど、これは書いておいたほうがいいなと思った。

楽しかった。次も絶対に参加するし、その時は自分のやりたいことをやり切れるようにしておく。