hotaruの蛍雪日記

競プロとゲームをしています

CODINGAME SPRING CHALLENGE 2021に参加した(3850/6867位 シルバーリーグ

Spring Challenge 2021に参加した。 結果は3850/6867位 シルバーリーグだ。

今までのコンテスト履歴は次。

  • コンテスト終了時:木1銀1金1
  • コンテスト終了後:木1銀1伝1

5月8日土曜日(コンテスト3日目)

コンテスト初参加。 入力した値を好みの型で保存するように変更。 初期コードはWAITし続けるため、適当に最後に渡された行動を選ぶように変更。 この変更でウッド2→ウッド1→ブロンズに昇格。

ブロンズ底辺をウロウロする。

5月16日日曜日(コンテスト11日目)

ゲーム盤全体を構造体にする。 まあ探索アルゴリズムを書くならゲーム盤構造体は不可欠なのかな。

// ゲーム盤
struct GameBoard {
    Forest forest;     // 森
    int day;                 // 日 0-23
    // 中略

ゲーム盤型変数を構造化束縛する。 メンバにアクセスするときにゲーム盤変数名をプレフィックスしなくてよくてうれしいので。 ゲーム盤変数を毎ターン初期化していなくて、可変長変数に要素がたくさん入って壊れるバグを治す。

    auto &[forest, day, ...] = gb;

行動シミュレータ追加。 行動後のゲーム盤をシミュレートする。 相手の行動は考慮しない。

日付変更後のSUNポイントシミュレータ追加。 木Aが木Bより高ければ木Aは木Bの影に入らないところでつまった。

適当にゲーム盤評価関数を書く。 木の本数、SUNポイント、得点を評価するよう設計した。 ブロンズ200位ぐらいまで上がる。

評価関数をいじって寝る。

5月17日月曜日(コンテスト12日目 最終日)

ランキングを見ると、評価関数をいじってから弱体化していた。 評価関数を戻して最終提出。 再提出して3時間後ブロンズ制覇(Botがボス倒したところ見ていないんですが)。

感想

  • 時間取れなくてできなかった。
  • 今回敵強かった。
  • MCTS書きたくなったらupsolveしたい。
  • 日本人が強かった。
  • reCurseが強い。

メタヒューリスティクス

  • 今回はモンテカルロ木探索(MCTS)が当たり方針だそうだ。
  • 今回は評価関数手作りしにくいからかな
  • ビームサーチしていた人もいた。
  • DUCTというキーワードが散見された。MCTS関係かな。

(PDF) DUCT: An Upper Confidence Bound Approach to Distributed Constraint Optimization Problems

アドホック

  • 種・木の種類を分散させるとSEED``GROWのコストが減って嬉しそう
  • 隣接セルにSEEDするのは無駄そう
  • SEEDは手数が多い割に部分ゲーム木の多様性に寄与しなさそう
  • アドホックにルール決めて枝が生えないようにするのはいいっぽい

Elona Mobile

Elona Mobileにハマっていました。 面白いです。 レシマスクリアしました。

過去コドゲ記事

hotarunx.hatenablog.com

hotarunx.hatenablog.com