はじめに
CodinGameのコンテスト(CodinGame Green Circle)に参加しました
結果は世界19/1,758位(Legend)、日本10/156位でした
技術的負債から目をそらして上手くアプリケーションを5つ作ろう!
ルール
ツカモさんの要約記事がとてもわかりやすいです(ありがとうございます)
tsukammo.hatenablog.com
やったこと
概要
方針:ボーナスを4つCIで貯める
ルールベース+評価関数で行動決め(各フェーズごとに評価、5つ目のアプリの時だけターン全体をシミュレートしてリリース判定を全探索)
初手は先手後手関係なく2で決め打ち、相手に取られてたら5
大体以下のパターン
2 -> 3(4を取る) -> 4(5を取る)
2 -> 4(5を取る)
5 -> 6
移動(MOVE)
基本的には1マスずつ移動(今いるマスから遠いマスほどペナルティ)
手札にボーナスがある時にはCIのマスの評価点を高くする
6にいて、ボーナスをCIできないときは7を無視してadminを通過する
ボーナスを4つ貯めていないときは2の評価を高くして、2 -> 3 or 4の流れをしやすくしてボーナスのCIを優先
敵と隣接するマスは基本的には止まらないようにし、5つ目のアプリケーションをリリースできるマスのときだけ許容
相手にカードの譲渡(GIVE_CARD)
リーサル時以外は止まらないので基本的には発生しない
リーサル時は渡してもリリースできるカードを渡す
通行税の支払い(THROW_CARD)
ボーナス以外を優先的に支払う
リーサル時はGIVE_CARD
と同様に支払ってもリリースできるカードを支払う
カードの使用(PLAY_CARD)
優先順位をつけて、その順番に使用できるか判定をして使用できるならそれを使用する
- 5つ目をリリースできるなら何も使用しない
TASK_PRIORITIZATION
を使って5つ目をリリースできるなら使用するCONTINUOUS_INTEGRATION
(ボーナス4つを優先、それ以外はリリースに使いやすそうかどうかを評価関数で決定)TRAINING
CODING
REVIEW
ARCHITECTURE_STUDY
REFACTORING
DAILY_ROUTINE
TASK_PRIORITIZATION
アプリケーションのリリース(RELEASE)
ボーナスを2個CIするまではリリースしない
ただし、相手の方が自分よりリリースしていたら技術的負債が3以下のリリースを許容
ボーナスが2以上4未満のときは技術的負債が3以下、ボーナスが4以上のときは全部リリース
リリース対象は技術的負債が最も小さいものを選択
技術的負債が同じ場合は、相手がリリースしやすそうなものを評価関数で選択
やりたかったこと
・探索(モンテカルロ系)
・相手の行動も考慮して評価
知見
・ISMCTSというのが適用できるらしい
・NNとか強化学習勢がちらほらいたっぽい、難しそうに見えるけどできるのすごい(8位の人がDQNで完全にランダムからの学習らしい?)
・強いルールベースがあればそれをプレイアウトに使えるらしい
・MCTSの定数Cを木が深くなるごとに小さくしていくといいことがあるかもしれない
感想
コンテスト最初の方はゲーム側のバグとか仕様把握にかなり頭を悩まされた
ボーナスをCIするのが強すぎるのと初手が大体決まっているので戦略の幅が狭かった印象
コンテスト開催知ったのが割と直前だったのでこどげ休暇を取らなかったけどLEGEND行けてよかった
そろそろ不完全情報なくならない?(探索が難しくて評価関数に逃げてしまう)