bowwowforeachの日記

競技プログラミングをします。主にヒューリスティック/マラソン/ゲームAI。

CodinGame Green Circle参加記

CodinGame Green Circle に参加しました。

www.codingame.com

 

結果

優勝したぞー

 

ゲーム内容

tsukammoさんいつもありがとうございます。

tsukammo.hatenablog.com


やったこと

MCTS。不完全情報ゲームなのでちょっと工夫。


探索

MCTSベースの方法（ISMCTSというらしい？）

  • ノードに状態は持たせない。
    MCTSの選択処理の時にノードをたどりながら状態を計算していく。
    不確定情報はランダムに決める⇒同じノードでも通るたびに状態が違う。
    次のノードはその時の状態で合法なものから選択する。

  • プレイアウトは6ターン（MOVE～RELEASEまでを1ターンとして）で打ち切り、評価関数で判定。
    • ゲーム終了している時、勝ってるなら+1点、負けてるなら-1点。
    • ゲーム終了していない時、評価関数で少しでも勝ってるなら+0.5点、負けてるなら-0.5点、さらに評価値を-0.5～+0.5の範囲にして加算、みたいな感じ。

 

評価関数

  • ゲーム内の実スコア
  • スキルカードは多い方が良い
  • CONTINUOUS_INTEGRATIONカードは多い方が良い
  • 負債は少ない方が良い
  • 永続化効果は多い方が良い
  • アプリ評価
    • リーチ状態だと良い
      アプリリリースに必要なスキル8個分中4個分を自動化できている状態をリーチ状態とする。リーチ状態だと手札1枚＋移動後に1枚拾うことで負債0でリリースできる。
    • リリースに必要なカードがデッキ内に存在すると良い
  • 最終リリース評価
    • アプリ4個リリース済みの時、リーチ状態のアプリをリリースするために必要なカードをドローする確率が高いほど良い。デッキに1枚もない場合は少し減点。

行動の枝刈り

  • 最初の1手は CONTINUOUS_INTEGRATION か DAILY_ROUTINE のどちらか
    2手目以降は特に制限しない方が強かった。
  • score=4の時は、RELEASEフェーズまで全探索して勝ち確定の手があれば必ずそれを選ぶようにする。
  • リリースしたときに負債が5個以上のアプリはリリース禁止
    ただし自分のスコアが3以上または相手のスコアが4の時は制限なし
    • 自分のスコア3以上の時：負債の少ないアプリを5個目のリリースにとっておくために、4個目のリリースは負債が多くても良い
    • 相手のスコアが4の時：相手の最終リリースアプリを先にリリースして妨害するため負債を無視する
  • 序盤はGIVEする場所への移動を禁止
  • DAILY_ROUTINEは2回まで
  • 同一基本スキルの自動化は2枚まで

 

その他

  • 1ターン当たりのプレイアウト回数は8000回ぐらい
  • 後手番の時、相手が CONTINUOUS_INTEGRATION にいると探索の結果初手 REFACTORING に行こうとするので DAILY_ROUTINE に矯正してた。自己対戦で勝率低いからやめさせてたけど提出したら勝率そんなに変わらなかった。理由がよく分からないから採用しなかったけど。
  • カードの枚数を64bit整数で管理した。
    全種類のカードまとめて足し引きしたり、アプリリリースしたときの負債数の計算がビット演算で高速にできる。
  • 相性そんなにないゲームかと思ってたけどパラメータによって大負けする相手が出てくる。最終的には平均的に勝てるような調整にした。


感想とか

  • 不完全情報ゲームでMCTSは初めてだったのでうまくいってよかった。今後も使えそう。
  • ゲームルールを理解するのに時間がかかった。勘違いしてることも多くて他の人のTweetで気づけて助かった。
  • シミュレーション部分はRefereeコードを使わずに自前実装したけど、細かいルール勘違いしているところもあったので移植したほうが良かった。
  • カード毎の有用度で評価値調整したかったけど難しくてできなかった。（CONTINUOUS_INTEGRATIONだけ0.6でそれ以外は全部0.1）
    評価値を機械学習的な奴で調整するの覚えたい。
  • 次回も頑張る！