hotaruの蛍雪日記

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

CODINGAME FALL CHALLENGE 2020に参加した(🥇ゴールドリーグ🥇・全体順位186位)

https://www.codingame.com/replay/509855212

コンテストのページ

ゲームAIコンテストCODINGAME FALL CHALLENGE 2020に参加した。 結果は🥇ゴールドリーグ🥇・全体順位186位でした。 150位ぐらいは取りたかった。

  • 全体順位:186/7,043位
  • 🥇ゴールドリーグ🥇順位:105/477位
  • 日本順位:54/320位

キーワード

CodinGame・ゲームAI・BOT・ゲーム木・ビームサーチ・評価関数。

CodinGameとは

CodinGame(コーディンゲーム・コドゲ)はプログラミング学習サイト。 CodinGameの目玉はBOT PROGRAMMING。 BOT(ゲームAI)をコーディングして互いに戦わせる。

FALL CHALLENGE 2020もそうだがBOT PROGRAMMINGは定期的にコンテストを開催している。 このコンテストは5つのリーグに分かれる。

  • ☠Legend: このへんだと高く評価されるらしい。
  • 🥇Gold: 焼きなまし法とかゲーム木のビームサーチ書ければ行けると思う。
  • 🥈Silver: 全探索・BFSなどが書ける程度の能力があれば上がれると思う。
  • 🥉Bronze: 全探索・BFSなどが書ける程度の能力があれば上がれると思う。
  • 🌳Wood: 一番下。

FALL CHALLENGE 2020

とりあえず動画を見て。 このようなゲーム。

  • このゲームの目的は薬を調合して相手より報酬を稼ぐこと。
  • 薬を調合するには4種類の材料🔵🟢🟠🟡が必要。
  • 詠唱すると材料が増えたり高い価値の材料が手に入る。
  • 魔法の書庫から新しい呪文を学習できる。
  • ほとんどの呪文は1ターンに複数回唱えることもできる。
  • 適切に薬を調合していこう。

詳しくはこれ読んで。 codingame:Fall Challenge 2020 ルール要約&内部パターン紹介

このゲームの攻略法

材料・呪文・薬

薬の報酬についての材料🔵🟢🟠🟡の価値はvalues = {1,2,3,4}である。 薬の報酬は基本的には-recipe.delta * valuesである。

  • 薬の報酬:基本は-recipe.delta * values
  • 緊急ボーナス:+3または+1。ルール参照。
  • 材料種類ボーナス:4種類の材料を使うなら+2。3種類の材料を使うなら+1。

材料の総価値を材料の価値の重み付き和inv * valuesとおく。 呪文を詠唱すると材料の総価値が+1~4増える。

学習した呪文かつ消費がある呪文は連続で詠唱できる。

強い呪文

短いターン数で報酬を稼ぐには、材料の価値の総和を早く増やす必要がある。 呪文を詠唱すれば+1~4増えるが、連続詠唱すればそれ以上増やすこともできる。 極端な例だがdelta = {-2,2,0,0}を5連続詠唱すれば材料の総価値は10増える。

材料の総価値を早く増やすのが強い行動だと考える。 呪文{-2,2,0,0}, {0,0,0,1}, {-3,0,0,1}が強いと考える。

薬の材料数ボーナスを考えると複数の材料を得る呪文が強い。 材料が足りない・消費できないとき詰まないために全部の素材を獲得・消費できる呪文を覚えておきたい。

呪文学習

f:id:hotarunx:20201123213923g:plain

  • 強い呪文を覚えると材料の総価値を増やす速度が大きく増加する。序盤に学習するべき。
  • 強い呪文を優先して覚える。
  • 最初の6~8ターンは学習に費やしてよい。
  • 材料獲得中にも学習したい。
  • 呪文を学習しすぎると調合が遅れて負ける。
  • 先読み税をたくさん相手に渡すと調合が遅れて負ける。
  • 弱い呪文は相手に押し付けたい。

材料獲得

f:id:hotarunx:20201123213936g:plain

次を繰り返すのが強いと思う。

  1. 在庫を🔵🟢で埋める。
  2. 🟢🟠🟡に変換する。
  3. 薬を調合する。
  4. 余った🟠🟡を🔵🟢に戻す。
  5. 1に戻る。

こういう行動ができる呪文が強い。

終盤の行動

自分が薬を6つ調合するのが強いと思う。

戦略

ゲーム木を探索して、価値が最も高いノードへの最初のエッジの行動をする。

  • ノード:自分の在庫・消費呪文・学習呪文・行動履歴。
  • エッジ:自分の詠唱・調合・学習・休憩。
  • 行動履歴は前の頂点へのリンクにするべきだった。

ゲーム木をビームサーチする。 ビームサーチの幅は100にした。 ビームサーチの深さは計算時間ギリギリにした。実測では6ターンほど。

段階

ゲームを序盤・中盤・終盤に分ける。

  • 序盤:強い呪文を学習する。
    • 序盤は最初の9ターンとする。
  • 中盤:詠唱・調合して報酬を稼ぐ。
  • 終盤:十分なターン数で報酬を稼いでゲームに勝てるなら勝つ。
    • 終盤は自分が薬5つまたは相手が5ターン以内にゲーム終えられるとき。

序盤

最初の9ターン強い呪文を貪欲に学習する。 呪文の評価は次。

  • 増やせる呪文の総価値。
    • 在庫を8としてできるだけ連続詠唱したときの呪文の総価値。
  • 呪文を学習後の在庫の総価値を足す。
    • 先読み税の支払いにペナルティをつけたい。
  • 🟠🟡を使う/増やせる呪文を覚えているなら評価を足す。

中盤

報酬と在庫の総価値が増える行動をする。 深さは実測6。 ノードの評価は次。

  • 1.5*報酬+在庫の総価値。
    • 報酬に重みをつけた。
    • 🟡10個で詰まないようにしたい。
  • 休息か学習したなら評価を少し足す。

学習を枝刈りした。 学習は最初の2ターン以内に1回までしかできないようにした。

このターンに相手だけが調合できる薬は調合しないようにした。

終盤

ゲームが終わるまでに素早く薬を調合したり🟢🟠🟡を集めてスコアを稼ぐ。

  • 相手が6個目の薬を作ってスコアが今の自分を上回るなら、できるだけスコアを稼ぐ。
  • 相手が4個以上薬を作っていて、5ターン以内に6個目の薬を調合できるなら、5ターン以内最短に相手のそのときのスコアを上回る行動をする。

実装

  • 言語:C++
  • 総行数:620行。
  • サイズ:23KB。
  • 各行動の情報をグローバルの配列に格納して、各関数はそのIDのみを持つようにした。
  • ノードは構造体。消費呪文・学習呪文などのIDをもつ。
    • 消費呪文・学習呪文などはvector<int>, set<int>で管理する。
    • ノードに自分の評価を返す評価関数をもたせる。
    • ノード同士を比較する評価関数を定義する。
    • ノードがでかすぎると思う。
  • 引数がノードとエッジで戻り値が次のノードの関数Node nextNode(Node n, int action_id)を用意した。
    • つながってないエッジを渡すとNULLを返したい。
  • 評価関数を切り替えたい。
  • ゲーム木探索関数は自分も相手も探索できるようにしたかった。

問題

  • レジェンドになれる程度に強くしたい。
  • 5%程度の確率でゲーム終盤で突然死する。
  • 早いターンの調合を評価できておらず休息→調合してしまう。
  • 相手の調合を潰したい。
  • 先読み税を相手に渡したくない。
  • 呪文の評価関数。
    • 呪文の評価関数は試行錯誤したが現段階より明確に強くはならなかった。

感想

コドゲTL見て面白いツイートかブログがあれば追記します。

ゲームの感想

  • よいゲーム。
  • ゲーム木ビームサーチを組むと最適な調合が始まって楽しい。
  • どの呪文を学習するのかが難しい。
  • ゼルダのコウメとコタケやん。
  • 相手の行動を深く読むのはコスパが悪い。

実装の感想

  • ビームサーチ初めて書いた。
  • 1ターンに600ノードしか探索できなかった。
  • アルメリアの薬の報酬に減衰率[tex:0.9t]をかけるのはかなりよさそう。
  • パラメータ調整は不毛。

CodinGameの感想

  • UIはかなり良い。
  • ゲームのシミュレータの出来はかなり良い。
  • 挿絵は良い。
  • TLEとREの違いを教えてほしい。
  • コードを入力してから対戦が始まるまでが長い。
  • おそらく毎回コンパイルしてると思う。再コンパイルせずに対戦させてほしい。
  • 今のBOTの強さを定量的に評価したい。

コンテストの感想

  • 面白い。
  • BOTが劇的に強くなると楽しい。
  • レジェンドになってプログラマーとしての評価をつけたい。