Codingame Spring Challenge 2021 参加記

問題

www.codingame.com

いなにわさんのわかりやすい日本語訳があり、ありがたく利用させてもらいました。

inaniwa.hatenablog.com

結果

Gold 1116位でした。
もうちょっと頑張りたかったけど、何もわからなかったのでどうしようもない。

やったこと

1日単位で Action の集合を生成する beam search を 5日分やりました。
1日単位での Action の集合を列挙するために、内部で possible_action() みたいな関数をベースに wait が終了条件の BFS をしました。 Zobrist hash とか基本的な重複除去は一通り取り込んでいます。 Action の列挙の際には、以下のような Action を省く戦略を埋めました。

  • completion → grow2 → grow1 → grow 0 → seed 以外の手順はやらない
  • seed で種を置く対象のマスに対して、高々3か所しか木を指定しない
  • 自分の木がある隣接マスには種をまかない
  • 自分の木と桂馬の関係にあるマスにしか種をまかない

3, 4 つ目の条件を両方満たす位置の候補がそんなにないせいで、sun 出力が伸びなくて厳しい盤面があったりしたのだけど、単に候補列挙のルールに優先順位をつければよかったということに感想戦で気づいた。

評価関数は、最初に適当に指定した

  • 最初16日: 直近6日で得られる sun の合計スコア
  • 後半8日: スコア

がそのまま採用されました。色々工夫を試していたけど、結局あまり強くなってくれなかった。

所感

  • 今回で3回目だったけど、1, 2 回目と比べてよりゲームの文脈で考察できるポイントが増えてきた気がする
    • それに比例して強い bot が作れているわけではないのが悲しいところ
  • 1, 2回目と比べて、意味不明なエラーで落ちて泣いてる時間がかなり少なかった
    • これは Rust の恩恵な気がしていて(これまでは C++)、まだ実装やライブラリ選定が不慣れな分を差し引いても、かなり元が取れていると感じる
  • パラメータチューニングを前提にした評価環境は最初に作りたい
    • 後半で評価関数のパラメータチューニングをやろうと思った時に、時間をかけて作るのが億劫になってしまう
    • コドゲのサービス上で動かすと、stderr の一部が切れて表示されないことを半年たつといつも忘れる気がするし、そもそも timeout があるから不便
  • MCTS をしたい状況が体感できた。
    • コスト関数の設計苦手なので、MCTS できるタイミングは積極的に探していきたい
    • 秋のコンテストまでには、MCTS でこの問題を解きなおすのはやっておきたい
  • ルールベースの bot も書いてみていいなと思った
    • 評価関数の設計や枝を刈るいい練習になる気がする

おまけ：コンテスト中のやったことメモ(時系列、自分用)

Wood 2

自分の木を選んで Complete。

Wood 1

1本ずつ Grow。

Bronze以降

実装①: 試合を見るための仮ソルバ作成

相手を無視したスコア関数を元に貪欲をして、とりあえず試合運びを確認する。 序盤は sun の最大化、終盤はスコアの最大化

考察: 自分以外の試合を見て重要そうなポイント

  • 盤面の richness は、中央であるほど高いので固定らしい
  • 一方で、完全に中央は日が遮られやすいので、注意が必要
  • 場所の強さが mod6 で異なるので、mod6 で育てる場所を変えたい
    • 中央に size 3 木を残しておいて、強い場所に1手で撒けるようにする
  • 桂馬っぽいの関係で正三角形を作ると、少なくとも自分で自分を遮ることがなくて強い
  • 相手のそばに置いて、相手の sun 取得を妨害するような動きができると良さそう
    • 相手の木に対して、多対一で接していると、妨害効果が強そう？
    • 相手から妨害される未来が見える時には得点に変換してしまうのが良い？

考察: 自分のソルバがダメそうな所

  • richness が高そうな場所に seed をまいてくれない
  • grow のコストが過剰に低く見積もられている

実装②: ビームサーチ化

基本的には自分のみを考慮 + 相手の行動や状態を基に若干のボーナスをつけて、ビームサーチ。 1 Action が 1ターン。

  • コスト関数
    • 12手以前は、それ以降で得られる sun の最大化
      • 今の手持ちの sun は加えない
    • 12手以降は スコアの最大化
      • ボーナス①：Complete した時に、相手が次ターン以降に行うと思われる Complete の回数 / 1.5ビームサーチの手数 で加える
        • 時間減衰させないと無限に後回しにする
        • 相手が次ターン以降に行うと思われる Complete の回数 = max(10 - これまでに complete した回数, 相手が今持つ size 2 以上の木の個数)
      • ボーナス②：Seed した時に、richness の分だけ加える
        • seed を撒くにしても richness の大きさも考慮したい
  • ビーム幅
    • 12手以前は 400
    • 12手以降は 600
  • 手数
    • 12手以前は 20 手
    • 12手以前は 40 手
  • その他
    • 候補を作る際、sun が少なかったり候補手が空出ない限りは、Wait をしない
      • 本当は入れたくないけど、ターン数が経過してしまうことを表現する方法が思い付かないので苦肉の策
    • 重複除去として、同一の (直前ターン盤面 id, action id) を2つまでしか持たないようにした

考察: 自分のソルバがダメそうな所

  • size 2 -> size 3 Grow を打ってから、Completion してる…
    • Grow に対する Action Bonus はないけど、Completion に対する Action Bonus がない、かつ Action Bonus は累積しないのが問題
      • 後ろで Action Bonus を選んだ方が有利になってしまうため
    • Bonus を累積的にして調整するなども検討したが、結局 possible_move で直前の action も状態に持たせたうえで上記の遷移を禁止
  • どうも richness の差が結構効いているように見える
    • ありえないけど、全部 richness 3 のマスで木を生やせたら、めっちゃ強いよねやっぱり
  • 初手の動きがかなり弱い
    • 自分の動きは、地震に隣接する場所に置かないのだけど、どうも初手で中央を制圧されてしまうことが richness の差で負ける要因にもなっている気がする
    • 最初は、速やかに中央を制圧するための手順を読むのがいいのかも？

アルゴリズム上の問題点

  • Action を評価するのが良くなさそう
    • 良いものにバイアスがかかる得点を入れるより、悪いものを選択しないようにするほうが調整が楽だし、ターン数に対するコスト値の普遍性もある
  • 1 つの Action を beam search の1ターンにしているのが良くなさそう
    • wait すると sun が入るので、wait を連打するのが比較的良好な戦略になってしまいやすい
      • 実際、seed を撒くような数日後によくなる手は、ビーム幅が狭いこともあって全部消えてた

実装③: 1日単位で行うビームサーチ

  • 実装簡略化のため、実装②のビームサーチの内部で、1ターンずつ進める BFS をやって、1日が終わるまでの盤面を生成する
  • ビーム幅
    • 100
  • 手数
    • 3日分
  • コスト関数
    • 前半16日: 直近6日で得られる SUN 値
    • 後半8日: スコア

ただし、時間制限が来たら途中で終わる実装を入れていて、実際中盤などは途中で終了していた。 これでギリギリ Gold には入れた。

実装④: コスト関数の設計

ビームサーチのスコアがさすがに雑なので、visualizer を見て試行錯誤していた。

  • スコア
  • size 0 ～ 3 の木の本数がそれぞれ [2, 2, 2, 5] に近い
  • 直近 N ターンで自分がもらえる sun の合計値 * 2 - 直近 N ターンで相手がもらえる sun の合計値

あたりを頑張って重みづけしようとしてたけど、思ったように動いてくれなかった。