#しぶんぎメモ

なんもわからん。

CodinGame SPRING CHALLENGE 2021に参加しました

はじめに

ボードゲームのAIを10日くらいで作って戦わせるコンテストに参加していました

www.codingame.com

全体38位、日本人としては6位と、非常に好成績を残すことができ満足しています

以下にコンテストの概要や、自分の戦略、反省などをまとめていきます

どんなボードゲーム？

盤面内で木を育成し、伐採することで勝利点を得るゲームです。

いなにわさんがルールの日本語訳をまとめてくださっているので、詳しくはこちらを参照してください。

inaniwa.hatenablog.com

以下はあるゲームのリプレイのURLです。ゲームの雰囲気がわかると思います https://www.codingame.com/replay/557676455

やったこと、考えたこと

  • 盤面の評価関数を作って貪欲
    • コンテスト2日目のBronzeリーグで真ん中あたりに収束
    • ゲームの進行度によって良い盤面が変化していくので、評価関数を作るのが非常に難しい
    • 評価関数が作れないとなると、貪欲をビームサーチに書き換えても良い結果は得られないと考え、別の方針を探す

  • ルールベースbot
    • 上位勢の対決を観戦し、このボードゲームで強そうな行動の条件を列挙した
    • complete > grow > seed > wait の優先度で、条件に見合う行動があれば出力
    • たぶんこの時点でGoldにすすめるくらいには強くなった

  • ルールベースbot改
    • 上のルールベースだと同じ種類の行動で条件を満たす行動が複数あった場合、どれが選ばれるかはランダムであった
    • 盤面の評価関数を作るのは難しいが、同じ種類の行動ならある程度優劣はつけやすいと考え、各行動について評価する関数を作った
    • 条件を満たし、優先度が一番高い行動を出力
    • 評価関数をある程度整備した時点でLegend解放後のGoldリーグで100位切るくらいの強さ

  • DUCT
  • ルールベースbot改 + DUCT
    • 既に作ったルールベースbot改くんを使ってrolloutやexpandで考える手を絞る
    • 各種類の行動について評価値上位2手ずつを合法手とする
    • それっぽいrolloutをしてくれるようになった

最終的な自分の戦略

ルールベースbot改 + DUCT が私の最終的な方針です。DUCT部分には特に工夫をしていないのでルールベースや各行動の評価関数について紹介します。

Complete

以下の3つの条件いずれかを満たすときのみcompleteを合法手に加えます。

  • サイズ3の木が4本以上
  • サイズ3の木が3本以上かつnutrientsが16以下
  • nutrientsが12以下

評価関数は

  • その木を伐採することで以降3日間で他の自分の木が得られるようになるsun値
  • その木が以降3日間で得られるsun値

を考慮します。

相手のサイズ2が成長しうるときはサイズ3の木として扱う、3日後より1日後のsun値を重く考える、のような工夫も入っています。

Grow

伐採が最終日に間に合わないGrowを合法手から外しています。

評価関数は

  • 木のサイズが大きい
  • 土壌が良い

ほど加点し、

  • 以降3日間に相手を妨害できるか

を参考にしています。Growの評価が一番良くわかりませんでした。

Seed

自分の種が既に盤面にあるとき、もしくは19日目以降はSeedを合法手に加えません。

Seedは自分の他の木と干渉しにくい場所ほど高評価としました。相手の木との干渉は考えていません。

Wait

終盤を除き、他に有効な手がないときのみ合法手に加えました。

その他

  • playoutは序盤で400回程度でした。
  • 次のターンに使い回せる部分の木を残す処理は行っていません。

反省

  • 上位の人は盤面の評価関数を頑張って作っていた
    • こっちのみが当たり解法だったら、爆死していた


  • MCTSについての理解が甘い
    • 今回はMCTSの内部についてほとんど変更を加えていない
    • もうちょっと柔軟に扱えるようになっておきたい

まとめ

次回もLegendいけるようにがんばります。