ICFPC 2019 参加記 - 長文書くところ

ICFPC 2019にチームdot cubeとして参加した． dot cubeは私が所属する宮崎大学のプログラミングサークルの名前．チーム全員，ICFPC初参加．

メンバー

zenito (私)
kai
Takahiro55555
twugo

今回の我々の目標は，「正の点数を取ること」とした．私以外のメンバーは，長時間でのコンテストは今回が初めての参加． ICFPCは基本的にスタートラインがめちゃくちゃ遠いコンテストなので，最悪ビジュアライザだけ作って手動で解くのでもよしって感じ．ゲーム制作はある程度みんな経験があるので，まあビジュアライザなら作れるでしょって気持ち．

チームでのコンテスト参加は初だけど，全員ハッカソンへの参加経験はあるので，チームでの情報共有はわりとすんなり決まった．会話はSlack，データ共有はDropbox，タスク管理とか情報共有はTrello．

以下ログ．Slackの会話とか見ながら記憶を頼りに書いているので，ところどころ怪しい気もする．

初日 (6/21)

AM 10:00
開始時刻を9時間間違える（今年の開始時刻は 6/21 AM10:00 (UTC) ）．そういえば日本に住んでいましたね． Rustで書くつもりなので，structoptとかreqwestとかの使い方を見たり，Slack botの作り方入門したりして過ごす．なお，最終的にstructoptしか役に立てられなかった．

PM 7:00 以降
開始．問題を読む．TOEIC最低点180点な集団なのでみらい翻訳に投げ込む作業．なんかすげー普通のマラソン問題っぽくない？？？？実行時間制限もコンピュータリソース制限も無いマラソンをチームで3日間でやる感じ．とりあえず入力がやたら扱いが面倒な形式なので，みんなで夜ご飯食べながら，入力をグリッドに変換する方法を考える．グリッドへの変換プログラムを私がRustで書き始める．残りのメンバーはみんなでビジュアライザを作り始めた (Python in Processing)．

深夜2時ごろにグリッドへの変換ができるようになって，ようやくスタートラインに立てたぞ〜って盛り上がる．一段落したので帰宅．

なお，このグリッドへの変換がバグっていて，2日目3日目のかなりの時間を浪費する．見やすいビジュアライザを自前で作るのって大事ね．

2日目 (6/22)

私以外の人々はビジュアライザ制作の続き．私はAIの制作に入る．マニピュレータの視線の判定のために，グリッドに直線を書くアルゴリズムを調べる．ブレゼンハムのアルゴリズムばっかり出てきて困る．近似されると困る．結局teratailにドンピシャなやつがあったので，参考にしながら実装した．なお，結局最終日まで全くブースターに対応しなかったので，これは完全に無駄になった．

視線に対応できたので，とりあえず動きのシミュレーションを実装する．気合でゴリゴリ．一発書きでも全然バグが出ないRustは最高．盤面カバー率が高い方を優先するビームサーチ(1手だけ進める遷移)を書いて，全く解けねえ〜って悲しくなる．このAIをaragogと名付ける．枝がたくさん伸びるため．

途中でいろいろルールが追加されているものの，初日のルールですらまともに解が作れていないし，ルール見た感じ探索空間がめちゃ増える感じだったので，とりあえず新ルールたちは無視することにする． Lightningが終わって，なにやらルールにマイニングという文字が見えたものの，まあ無視していいでしょっつってもはやまともにルールすら読まずに無視．

aragogのビームサーチの改良を考える．遷移で1手しか進まないので，角とかですでに塗ったマスに囲まれるとランダムムーブしかできないな〜って思ったので，評価関数に「一番近い未到達マスまでの直線距離」を含めることにする．いい感じに進むものの，直線で進もうとするのでハマりまくってダメ．ということで，bfsして「一番近い未到達マスまでの最短移動距離」を求めることにする．実装するものの，めちゃくちゃ重くてまともに探索できない．

めちゃ強い雨が降り出して帰れなくなり，3時くらいまで作業．

とにかく正の点がとりたいので，マニピュレータも回転も完全に無視して，己の通った道のみで盤面を全部埋めるbfsを書く．一番近い未到達マスまで最短で移動するだけ．このAIをdementorと名付ける．適当にターゲットを定めてそこまでグワーッと行くため．とりあえずこれで正の点が獲得できるようになって，深夜3時ごろに初めての提出．99位になって，やった〜2桁順位だ！と盛り上がる．これがチームとしての最高順位になった．一段落したし雨もやんだので帰宅．

なお，グリッド生成がバグっているので，51番以降の盤面で途中で壁に突っ込んで死ぬ．グリッド生成側のことをまったく疑っていないので，延々とbfsのバグを探し続ける．今考えればめちゃくちゃ時間を無駄にしてしまった．

3日目 (6/23)

私以外のメンバーはビジュアライザ制作の続き．

私はaragogのビームサーチを改良．前日に実装したbfsがバグっていて，visitを保存していない（！）とかいうゴミみたいなミスをしていた．直したらかなりまともに探索できるようになって，50番までは時間をかければまあまあマシな解がつくれるようになった（まあ評価関数がヘボなのでアレなんですけど……）．相変わらずグリッド側がバグっているので51番以降は死ぬ．

マラソンマッチのブログ記事とか読んでたら，ビームサーチは遷移が大事，必ず評価の上がる遷移を考えろ，とのことだったので，それをやることにする．とりあえず，1手しか進めないで評価するのはめちゃくちゃダメじゃね？って気持ちになって，5手分全部の動きをしてみて評価するようにしてみる．めちゃくちゃ重くなったけど，ちょっとは良くなった．

公式ビジュアライザで動きを見てると，結構近場の未到達マスを見逃して後から取りに戻る動きをしている．うーんちっちゃいマスなら多分最適解が作れるんだろうな〜と思って，それを繋げたりするときれいに塗れるな〜ってぼんやり考える．しかし悲しいことに，それを実装できるだけのアルゴリズム力は自分には無いのであった……．

夜になって，最初に自分のいたマスを到達地点として塗るのを忘れていたバグに気づく．変な挙動がそこそこ取り除かれる．また，チームメンバーが作っていたビジュアライザが完成して，ようやくグリッドの生成がバグっていることに気づく．ビジュアライザを自前で作るのって大事ね．

最終日 (6/24)

3日間のコンテストなのに4日目で頭がバグるね．

月曜日なので，チームメンバーは講義があって動けず．自分は講義なし．

とりあえず，5手全探索のaragogを自宅のデスクトップマシンで10並列で回す．12時間以内に解き終わるかどうかのお祈り． ……だったはずが，残り3時間になった時点で，修正されたグリッド生成プログラムでグリッドを生成し直していないことが発覚．もう時間的に無理や……と絶望する．グリッドをちゃんと生成し直す．

とりあえず自分ができることの最善策として，dementorをマニピュレータに対応させる．拡張も回転もまったく考えないので，一瞬で対応できる．また，bfsの探索順を，これまでは左側から開始する時計回り方向だったものを，下→左→右→上の順で探索するように修正．これで下の方を重点的に攻めるようになって塗り残しが減り，prob-297の手数が1万手近く減った．

aragogで解ける範囲のものはできるだけaragogに解かせたいので，時間いっぱいaragogを回す．めちゃくちゃ時間がかかるので，4並列でギリギリ． aragogとdementorの解のスコアを比較して，いいほうだけを提出用ディレクトリにコピーするスクリプトを書く．提出期限の19時が迫る中，シェルスクリプトと格闘しながらaragogの計算が無事終わるのを祈り続ける． 18時58分に提出完了して，初ICFPCは無事終了！

感想

悔しい〜〜〜〜〜〜〜〜〜！私にもっとアルゴリズム力やら実装力やらが備わっていれば……って気持ち．終了後のTLを眺めてたら，まさにやりたかったこと（小さい範囲で区切って最適解構成，それらを2-optでつなぐ）をやっているチームがいて，いやそれだよそれそれ〜！ってなるなどした．小さい範囲での最適解構成，どうすればいいんだろうなあ……．

また，盤面の評価値をどうつければいいか，どう遷移させればいいか，も全く考えつかなかった．そもそも遷移をまともにするにはまともに評価値をつけられなければならない（気がする）ので，そういうのをもっとうまくなりたい．

チームでの参加について．多分1人での参加だと途中でやる気を失っていただろうと思うので，やっぱりチームでやるってのは楽しい．欲を言えば，コード書いたらいい感じに自動でタスクを流したり，定期的にこれまで得られた一番いい解を提出したりする環境が作れると，いろいろ実験を回せたりするのかなあ……と思う．まあ，そもそものアルゴリズム力が無なのでそういう環境があったとしても無な気はするけど……．個人的にインフラ側にも結構興味があるので，Jenkinsとかを触ってダッシュボードっぽいの作ったりしてみたい．自分が探索とかを書かなくても大丈夫にならないとそこまで手が回らないけど．でもJavaScriptを書く気は全く起きないので，早くWeb Assemblyがすべてを解決してほしい．Rustで全部終わるようになってくれ．シェルスクリプト力も足りないので，いろいろ強化すべき点だらけだなあ．

全体として，もっともっと実装力アルゴリズム力をつけたいねって感じ．私自身も，チームメンバーも．チームメンバーが基本的にあんまり探索とかに明るくないっていうのはわりとつらくて，AIとかを考えるときに全部一人でやらなくちゃならない．ビジュアライザを複数人がやってるってのもなかなか無駄が多い面があると思うので，やっぱりそれぞれが得意な分野をもっているようなチームのほうがいいよなあって思う．まあ，チームが組めるというのはそれだけでかなり恵まれているので，時間を割いてくれたチームメンバーには感謝の嵐なのだけど．

悔しいところが多かったけど，やっぱり長時間のコンテストは楽しかった．今回は追加ルールを完全に無視したので，次に参加するときは，追加ルールも楽しみたい．