マスターズ参加してました。とりあえず酔ってる勢いでもろもろと。
とにかく反省点がめちゃくちゃ多かったけどとっても楽しかったです。
まあ、あめんばーさんは14歳(N進数)なんですけどね(Nは[5,1e18]）
例によって私のブログは誰かのために書くというよりは後への自分のかきなぐりです。（コレ毎回言ってる気がする）
どんな感じで組んだか
VRC競プロ部で部長が「マスターズ出ようぜ！！！」と言ってたので賛同しました。まぁあめんばーさん14歳なんですけどね。
予選までにしたこと
練習試合
最初の作戦会議。最初はみんなでRustで組もうって話になってました。
あとチームでのコード共有にVSCode Live Shareを使おうって話にもなってました。
これについては
- コード共有としては優秀。あまりにもよい
- 一緒に同じ場所を見る場合のレビューはとてもよい
- ただ、画面共有で済むともいう
- ただし同期ズレが結構激しくてやりづらい
- ホストが動かすとスクロールすら共有されるので一緒に違う場所見る場合はだるい
と、一長一短でした。
とりあえずAHC007を使って組んだのですが担当として
- 私ことあめんばーがとりあえずアルゴリズムの考察と実装担当する
- unibopさんが実装兼任とパラメータチューニングとスコア統計をする
- cleanttedさんがビジュアライザを主に担当する
って感じにやっていい感じになってました。
そしてテッドさんが基本的にビジュアライザを担当してて、私とunibopさんのメイン言語がC++だった影響で「C++でよくね？」ってなったりしてました
あとはやっぱり話題別に記録をまとめるところができると良いなぁということでdiscordチャンネル作ったりもしました
予選の流れ
貪欲パンチ！！！
まず予選が始まったときに何をするか
VRChatに入ります
ちなみに第一回マスターズ予選でチームVRC競プロ部はコンテスト開始時まずVRCに入っていたようです
— あめんばー_VRC (@amb_vrc) 2024年4月20日
（※当たり前ですがチームメンバー以外入れないインスタンスです） pic.twitter.com/N6IS59xSUc
これ準備段階でテッドさんが言ったことなんですが、最初はギャグみたいなノリで「なんだよそれ」って感じで流しそうになったのですが、これがシャレにならないレベルでよかったです。
- 全員が場所を選ばず自分の慣れた環境でプログラミングや考察できる
- それでいながら音声・板書・仕草・空間的考察を共有できる
- そもそも全員VRChatでの勉強に慣れている
普通にめっちゃ全員で問題の理解共有して「こういう方針で行きましょう」の共有の板書しまくってとても捗りました（※さすがに作業開始したらHMD外しましたがずっとVRCつけてました）
序盤の問題共有パートや考察共有パートに関しては問題自体の難易度を加味しても全員の理解速度や考察速度は本戦と比べたら爆速だったと思ってます。
その後はそれっぽい解法を7通りくらい出してとりあえず実装の得意そうな貪欲パンチを実装したところなんと提出時4位。
まじで通話しながら大爆笑してしまいました。
なんやかんやチューニングできるパラメータを自分なりにまとめてたんで全部unibopさんにブン投げ。
言い方悪いですが…チューニングといいビジュアライザといい本当に私がヒューリスティックやってる最中にめちゃくちゃ苦手だと思ってた部分を全部味方に投げてました………。
テッドさんのビジュアライザもとても見やすく今のアルゴリズムの弱いポイントもすぐ見えて直し、unibopさんからも細かいパラメータ調整で最適なスコアが出やすい値をもらえ、私もそれぞれを見てアルゴリズム回収……
なんやかんや26位（決勝進出者の番号的には恐らく18位）になりまして、めでたく決勝進出できました。
本当に上記の役割分担がうまくいったなぁって感じでとてもよかったです。本当に作戦が嚙み合ってました（そして私が当たり解法引けて本当に良かった……）
予選の反省点
私のコードがめちゃくちゃ悪い
個人的には全員が社会人なので「チーム開発の重要性を知っている」と思っている部分はあったのですが、そんな感想を真っ向否定する要素が私のコードでした。
見りゃわかりますがあまりにもひどい。歴代のAHCコードを見るとマジで人に見せるものではない。今回の予選も例外ではない。
私のAHCは500行以上のコードは平然と書くし似たような部分はコピペするし他人が理解できる変数名をつけないしコメントなんて一切書かない
業務でやったらブン殴られます。私も殴る。嘘ですでもレビューはボロクソに書く。
というわけで本戦の前にどんな点で書けばよかったのか、という構造体を練ったりしてました。
本戦に向けて
というわけで次の作戦会議をした時にはこんな話になりました
- 回収しやすいようにある程度のコーディング規約を決めた
- 使いやすいようにinput,outputの構造体を決定しておく
- パラメータチューニングの高速化をする
- Optunaを使用する
- コマンドライン引数などでパラメータをコンパイラを通さずに指定できるようにする
- 実験のしやすいsmallケース作成をしておく
とかの話をしました。Optunaはこれマジですごかったです。あれだけ面倒だったパラメーターチューニングがこんなにも簡単にできるのかと。
私の予選の崩壊したコードがみるみるうちに最適化されていきました。上位勢は細かいポイント差が馬鹿にならないので、これすごい。本当にすごい。
結果論を言うと、まあ私の不甲斐なさなんですが
- 回収しやすいようにある程度のコーディング規約を決めた
- 使いやすいようにinput,outputの構造体を決定しておく
→一日で急いで固めたので勘違いが起きてしまった
- パラメータチューニングの高速化をする
- 実験のしやすいsmallケース作成をしておく
→問題が難しすぎてチューニングの段階に入れなかった
となってしまい、若干の裏目でした。結局みんな普段一緒の仕事をしているわけではないので設計の意識がまぁまぁバラバラになってしまっておりました…。
本戦の問題
なんだこれはあああああああああああ！！！！
予選がめちゃくちゃ噛み合ったというならば本戦は本当に嚙み合いませんでした。
加えて今までのAHCがABCを解いている気分なら突然ヤバい回のAGCを見せられてる気分でした………。
- まず私が乱数関わるヒューリスティックがめっちゃ苦手
- AHC022（温度計測）とかAHC029（ビジネスカードゲーム）が大大大大苦手で上位の解説を見ても何もわからなかったまま放置してた
- 貪欲パンチが全然できない
- 問題が歴代AHCと比べてぶっちぎりで難しい
- そもそも全部の目的地を回る事すら不可能
- 事前準備した対策もインタラクティブにはむしろ弱いものだった
- 問題内容が難しすぎてビジュアライザの作成もきつい
- 盤面が10^10とかいうクソデカなので、描画計算量も吟味しないと超大変
- 作業を投げる余裕も考察もない
結果とりあえず最低限の正の点数を取るだけで終わってしまった始末。ここがうまくいったからここを強めていこうと対策したのですが「ここが弱いと何もできない」を突かれました。
噛み合えばしっかりスコアが出る連携が取れたということはそれぞれの担当が太刀打ちできない問題が来れば壊滅状態になるということでした。
とりあえず5個ほど考察考えたんですが全部何かしらの問題が起きた時に復帰ができない始末。
私の反省点としては打ち上げでも話たんですがとりあえず私はレッドコーダーでもなんでもないので最高を目指さずとりあえず動くもん考えろよってことでした。
まあでも今でもまともな動くもん浮かばないんですが……
解説でも話題になったのですが「まったく別の方針とAとBを組み合わせてCの方針にしよう」という形だったものを「Cを万能に解けるもの」でやってしまおうとして死んだ感じでした。前回21だったのが3になってるんだから同じだと思わないほうがよかったです。
そしてマジでわかんない。全然わかんない。まず全員の問題理解共有と方針決定に1時間、考察に3時間、実装大急ぎで2時間で間に合わずって感じでした。
挙句、ギリギリで実装が終わりそうという段階でプレ実装してもらっていた部分の理解をずっと勘違いしていたのに気づかず、そこでWAの嵐を出す始末………
ちなみに終わった後の懇親会でも、その後に打ち上げで向かったVRChatterの聖地である秋葉原のHubでもいろんなここをこうすればよかったという話をひたすらしていました。
でもとてもよかったよ
なんだかんだで不甲斐ない結果になってしまい、終わった後も考察担当通して本当に何もできなかったので申し訳ないと言い続ける始末でした。余りにも悔しい。余りにも不甲斐ない。
でも個人的には本当に楽しい機会だったので感謝もめちゃくちゃ伝えました。
さっきも言ったのですが
- 基本的に全員社会人なので締切間隔・役割分担の重要性を知っている（はず）
- コーディング開発において必要な部分が浮き彫りに出てて、実務的な観点でもたのしい
- その上でのチーム戦らしい要素をふんだんに入れている
- その割に短期コンなので社会人でも比較的時間を合わせやすい
- スポンサーに対してもだいたいは新卒に向けた採用活動が多い中堂々と中途らしい仕事感の話題が聴ける
- あくまで（俗称としての）ネトゲなので、損害が出るわけでもない
- 競プロ部の人たちとの対人関係は基本良好（だと私は思っている）
- 「実力をつける」以外でできた反省点が余りにも多すぎて「次は頑張ろう」という気持ちが非常に強まった
- なんか青木さんが社会人だから故のめっちゃ褒めをしててみててたのしい
楽しいし実りあるし意欲が高まるし、本当に本当にいいイベントのだったと思ってます。
特にいろいろありましてTHIRDさんからはいろんな話を聞けてとても嬉しかったですね。
ちょくだいさんとかも話してみたかったんですが私はどうやら自分がすごいと認識しているコーダーを見かけると目が合っただけでもあまりにも緊張して言動全てが異常になる癖があるみたいなので、まあ無理でした。（と、いいつつ過去に一回だけ話したことあるのですが）
誰とは言いませんが某A社のとある方を見かけた瞬間はガチの挙動不審になってしまったところをお相手さんにも見られてしまいました。つれえ。
たぶんTHIRDブースでWA_TLEさんとかShun_PIさんとかbowwowforeachさんががいるのに気づいていたら緊張してただの不審者にしかならなかったと思います。間違いなく。
次参加するなら
- VRChat競プロ部のメンバーをもっと盛り上げながらやりたい
- 結局競プロ部ではHは強い方には該当するので頑張りたい
- 特に今回のような苦手分野を放置しない
- ビジュアライザや統計部分についてもしっかりできるようにしたい
- 遠方から来る人に美味しい酒を紹介したい
- 全員の設計に対する能力や意識を共有できるようにしておきたい
とかそんなんですかね。
本当に楽しい回だったんでまたあると嬉しいなと思いました。
決勝で考察したけどなんもわからんかったこと書き下す
- 壁の衝突を無視すればXとYの要素は完全に独立で考えられる
- Nターン後の誤差は現在速度は自分が指定した速度に対してN(0,Nε^2)になる
- Nターン後の現在位置は風がない場合を加味してN(0,N(N+1)/2ε^2)になる
- 100ターンも経てばもうどこにいてもおかしくない状態になる
- 最初「壁に衝突してもいいから爆速で突撃する」という作戦が浮かんだが、壁に衝突した場合は到達判定はされない
- 全てのいるマスをベイズ推定したいとも思ったが、マスが多すぎて無理
- 途中で離散分布ではなくて連続型分布で考えようかなとも思った。特にAだとつよい
- 最適ルートに関しては、壁がある場合は壁の端点のちょっと脇の点を持ってきて巡回セールスマン問題に持っていける
- ぶつかったらどうすればいいのか、最後までわからなかった
一晩寝て起きたら考えた方法
- 上記の通り基本的に現在位置は二乗で分散が広がる正規分布になる
- ただしこの正規分布は連続分布関数として考えたらXとYが独立～とかではなく全ての方向で正規分布になる
- もちろんA問題の場合は壁がXYに平行なものしかないので、独立で考えちゃっていい。むしろ都合がいい
- 誤差がない場合は壁の衝突を気にしながら進めばよい
- つまり何かしらの「ロックオンした壁」との距離を意識しながら進む。
- ロックオンする壁は基本的にはビームを打ち続ける。予定よりだいぶ離れているなと思ったら近づくし、近づきすぎていたら大急ぎで離れる
- 基本的には計測で等速直線運動しながら加速でズレた分を治すという作業だけをする。大加速はあまりしない
- 期待値上はそろそろ到着するなと思ったらすぐ止まれるように減速を挟むようにする
- ロックオン壁の距離が突然おかしくなったら目的地に到着したと思えばいい
- ロックオンする壁については基本的にはドロネー三角形分割を作成して領域活用する。壁のない三角形にいる場合は隣接した3つが候補になる
まあ、とにかく壁伝いにめっちゃ慎重かつ迅速に歩くこと、調べながら歩くことはできること
言葉に噛み砕いて現実ならどうやる？と考えるのがかなり大事だったのかなぁとも思えてきました。
車は急には止まれないし、急がないとどんどん加速度の分散が広まってしまうため急がなきゃ～～～！！！と考えすぎていたのが仇だったかもしれませんね。
あ、でもそう考えると
- ドロネー三角形分割をする
- 目的地がない場合は基本的には重心に移動するように意識する
- ドロネー三角形ごとにロックオン壁を決めておいて、今どこにいるか判定しておく
一位解法みたいにコーナーをスルッと抜けるようなことは不可能ですがこれでもよかったかもですね。
いやぁ、おもろいなぁ。でも、時間が溶けるからほどほどにしないとね。今日はスプラトゥーンのフェスじゃ
