CodinGame Spring Challenge 2021 参加木

f:id:omotchi:20210519013346p:plain
17 / 6867位（日本4位）

CodinGame is 何

www.codingame.com ゲームのBOT(AI)を作って、強さを競うプログラミングコンテスト
自分ががんばって作った子が 戦っているのを見れる！
たのしい！
f:id:omotchi:20210519000057p:plain

今回のルール

  1. 木はSun Pointを生み出す
  2. Sun Pointを使って木を増やして、そだてて、収穫！
    （収穫の部分については諸解釈あり）
  3. 24ラウンド でスコアを競う

詳しいルール（いなにわさんのありがたい日本語訳）
inaniwa.hatenablog.com

やったことの流れ

  1. 行動評価型（できる行動に優先度をつけて、高いのをするだけ）
    まあまあな順位→どんどん下がる

  2. てりーさんという方がDUCT（後述）という探索アルゴリズムで上位に入ったとの発言を見る
    →探索したいしロボてりーちゃんが可愛いからマネすることに
    でもMCTS（後述）すら知らずwikipediaと論文交互に見ながら苦しむ（5～6日間）

  3. なんとかDUCTもどきが出来る、が、あほ弱い

  4. 行動評価型を組み直す→Goldの中くらいに

  5. やっぱり探索したくてビームサーチ（未経験）に変更
    →盤面評価が下手でだめだった…

  6. 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