AHC003 参加記
システス後 2.911T点（17 / 1000位）
なにこれ
AHCというプログラミングコンテスト！の３つめ
大まかに書くけど、詳しくは本文をよんでね
- 辺の長さが不明のグリッドグラフ上で、与えられた2点間を結ぶ
- 結んだ長さが大体いくらだったかだけ教えてもらえる
- それを1000回やって、結んだ長さの合計が短いほど高得点
他の人の解法はここにいっぱいあるよ
#AHC003 hashtag on Twitter
かんがえた解き方
例！今4つのパスについて長さを取得したとするよ
一旦これらを正確なものと仮定すると、辺の長さは例えばこう↓なる
この1枚目の画像から、2枚目の画像をなんとなく求める計算がしたい！
でもどうしたらできるの…
悩んだ挙句ひねりだした案↓
- パスの主張を聞いて、辺の長さを推定
- 推定された辺の長さを見て、パスの主張の補正（再配分）
主張って？とりあえずパスの長さを等分してみよう
このピンク文字が、パスが主張する辺の長さです
これを合算して辺の長さを推定しよう
このとき、主張の重みは 1 / パスの辺の数 とします
青字が、パスの主張から推定された辺の長さです
今度は、ここから逆にパスの主張を補正しよう
たとえば6333の下にある辺数4のパス、
今の辺長を足すと6333*2 + 5000*2 = 22666 で、これはパスの長さ20000 を超えてるね
この超過分 2666 を等分しそれぞれの辺への主張から引きます
するとこんなかんじ
ここまでを1巡として、何回もやるよ
ためしに10回やってみた結果↓
うーん…これは…どうなの…？（微妙な結果）
僕の解法はクエリごとにこの計算を1巡します
500クエリ目なら500個のパスを再配分するので重い
解き方ほか
- 辺同士の相互作用
とりあえずM=1用とM=2用で2つモデルをつくって、辺に対し以下の処理をする
M=1: 同じ線上にある29個の辺の平均値に、すこし値を近づける
M=2: 隣の辺の値に、すこし値を近づける
M=2のほうもっと良い案だしたかった
- モデルの切り替え
Mの判別は僕にはできなかったので…
クエリごとに、両モデルに「今の経路長いくつだったと思う？」クイズで正解にどれだけ近かったかという点数をあげる
経路を決めるときは、その時点で点数が高い方のモデルに決めてもらった
ほかにやったこと
- ローカルテスト環境
Rust分からなかったけど、公式が「1ケース生成」と「1ケース実行」を公開してたので、 合体くらいなら出来るかもということで「n個のケースを実行して平均点を求める」にしました。
100ケース実行するのに2 * 100 秒くらいかかるけど、無いよりずっと良かったと思う
並列化はやり方がわからなかった…
- その他
他にも色々あったけど長くなっちゃったから今回は割愛
感想
がんばってブログかいたのにただの絵日記になっちゃって泣いてる
CodinGame Spring Challenge 2021 参加木
17 / 6867位（日本4位）
CodinGame is 何
www.codingame.com
ゲームのBOT(AI)を作って、強さを競うプログラミングコンテスト
自分ががんばって作った子が 戦っているのを見れる！
たのしい！
今回のルール
- 木はSun Pointを生み出す
- Sun Pointを使って木を増やして、そだてて、収穫！
（収穫の部分については諸解釈あり） - 24ラウンド でスコアを競う
詳しいルール（いなにわさんのありがたい日本語訳）
inaniwa.hatenablog.com
やったことの流れ
行動評価型（できる行動に優先度をつけて、高いのをするだけ）
まあまあな順位→どんどん下がるてりーさんという方がDUCT（後述）という探索アルゴリズムで上位に入ったとの発言を見る
→探索したいしロボてりーちゃんが可愛いからマネすることに
でもMCTS（後述）すら知らずwikipediaと論文交互に見ながら苦しむ（5～6日間）なんとかDUCTもどきが出来る、が、あほ弱い
行動評価型を組み直す→Goldの中くらいに
やっぱり探索したくてビームサーチ（未経験）に変更
→盤面評価が下手でだめだった…DUCTに戻って改良
DUCT is 何 again
Decoupled UCT の略。MCTSを同時着手ゲームに使えるようにした感じ？
僕もあんまり分からない
https://dke.maastrichtuniversity.nl/m.winands/documents/sm-tron-bnaic2013.pdf
MCTS is 一体何
モンテカルロ木探索のこと
ボードゲームの手番で手を決めたいときなどに、乱数を使って
良さそうな手ほど深く調べつつ、同時にあまり探索が足りない手ももうちょっと調べるようにバランスを取って探索するよう練られた方法
（説明がよくなかったらごめんなさい）
https://ibisml.org/archive/ibis2014/ibis2014yoshizoe.pdf
- プレイアウト（ロールアウト）
ある状態からお互いランダム（完全ランダムとは限らない）に行動すると仮定し
ゲームを最後まで進め結果を再現する、というMCTSにおける手順
DUCTどんなかんじにしたの
- 取れる行動を減らす
COMPLETEに必要なsize3の木の数＝日ごとに制限緩和
サイズごとの木の個数制限= {1,2,4,7};
SEEDは自分の木の周囲もしくは直線2マスには飛ばさない
（そういう場所が盤面上にないときのみ、好きな場所に飛ばすことを許可） - 探索
一度でも訪れていたノードは拡張する。
1回のプレイアウトで必ず1つだけノードが増えるかんじ - プレイアウト
上記の行動制限をした範囲内で、お互い完全ランダムでゲーム終了までプレイする。 - 評価関数
勝ち=2, 引き分け=1, 負け=0 - ノードの再利用
深さ1のみ
深さ2…つまりWAIT→相手連続行動、のときは難しくてできなかった…
高速化
#pragmaなんちゃら
コードによって効果のほどに差があるようなのでいろいろ試す
（教えてくださった方々ありがとうございます）- ビット演算
しばらくバグらせて苦しんだ… - 可変長でなくて良いなら固定長配列に
これも領域外アクセスのデバッグを何時間もすることに…でも速くなった - メモリの解放・再確保の回数を減らす工夫
Object Pool とか？ - 自明ではない高速化もありうるのでいろいろ試す
ある構造体のサイズが3バイト→（無駄に1バイト増やして）4バイト
上記変更でプレイアウト数が1.1倍ほどになったのは（僕には）非自明でした
- プレイアウト数
高速化前 700回くらい → 4000～5000回くらい（どちらもゲーム内2日目）
そのほか
- 負けた試合を順に見て、その理由をメモしていく
かなり大事。このメモを基に行動制限のルールを組んでいったかんじ
でも最終的に見てて分かるようなミスがなくなったころには、この方法が取れなくなっちゃった…
感想
すごく楽しかった！
なぜかびっくりするくらい上位で仰天したけど…
色んな方のおかげです…
（それでも日本上位3名には一切歯が立たなかった、みなさんすごい）
あと20位以内でもらえるらしいTシャツどうやってもらえるのか誰かおしえて…
【追記】Tシャツについては後でメールが来るそうです。ツカモさんに感謝
ありがとうございます
- ボンド＠競プロさん
こどげオススメしているツイートを見て今回参加しました - TERRYさん
ツイートされてた論文を何度も読ませてもらってがんばりました - iwashi31さん
温かみのある手動追加で200人超のTwitterリストを作ってくださいました - ほかTwitterで知見を共有してくださったりこどげのお話をされていたみなさま
他の方の参加記、解法Tweetなどまとめ
（shirakiaさん作。大変便利）
github.com
