🎴

Legends of Code & Magic(LOCM)でLegend Leagueに入った

に公開
競技プログラミング
CodinGame
tech

概要

Legends of Code & Magicは、2人対戦のカードゲームを行うボットを作成し、その強さを競うプログラミングコンテストです。コンテストはCodinGameで常設されています。

前回の記事では、ルールの紹介と、カードゲームを統計的に分析するときに何に注目するか、何が読み取れるか等を書きました。

https://zenn.dev/northward/articles/e68c7c5a1ecb4b

上の記事で述べた分析を活用し、Legend Leagueに入ることができたので、どういう方針で実装を行ったか、工夫した点などについて振り返りたいと思います。

  • 実装の方針
  • 細かいテクニック

実装の方針

まず、実装の流れを書きます。

  1. 対戦フェーズのボットを実装する。
  2. ランダムにドラフトを行う自己対局を繰り返してデータを収集する。
  3. 収集したデータを利用したドラフトフェーズのボットを実装する。
  4. 自己対局を繰り返して更にデータを追加する。

このように、対戦フェーズのボットを実装し終わってから、ドラフトフェーズのボットを実装しました。[1]

対戦フェーズとドラフトフェーズの開発を別々に行った理由は、ドラフトのボットに統計データを利用することを考えた場合、質の良いログを集められないと、正しく評価を行うことができないためです。

対戦フェーズ

自分は、ゲームの情報を評価する評価関数を設計し、ゲーム木を探索することで、最適な行動を計算することにしました。

他によくあるゲームの探索アルゴリズムとしては、モンテカルロ木探索が挙げられます。ただ、不確定要素が多く、実行時間制限(100 \text{ms})が短いので、プレイアウトの回数を確保するのが難しくなります。そのため、今回は採用しませんでした。

また、カードゲームと同じく不確定情報ゲームである麻雀のAIで、Lucky Jというものがあります。Tencentによる公式の紹介記事(その翻訳記事)によると、強化学習を拡張した方法を使って作成しているそうです。なので、LOCMでも強化学習を使った強いボットを作ることは可能なのかもしれません。

評価関数・探索アルゴリズムの設計

まずは、評価関数の設計についてです。

以下のような要素を考慮すればよい、というのはすぐに分かります。

  • 自分と相手のHP
  • 自分と相手の盤面にいるクリーチャー
    • クリーチャーの攻撃力、体力、キーワード能力
  • 次のターンのドロー枚数
  • 残っている手札

これらの要素を適当に重み付けしながら関数を設計すればよいです。

例えば、自分の盤面に攻撃力a、体力hのクリーチャーがいるとします。これがWardをもっているかどうかで評価関数の返り値はどう変わるべきかを考えます。(Ward: 自身が次に受けるダメージを1度だけ無効にします。)

Wardを失わせるためには、一度0より大きいダメージを与える必要があります。このとき、相手のクリーチャーはaのダメージを受けます。つまり、Wardをもっているなら、aに比例する利得があると考えることができます。また、攻撃力a、体力hのクリーチャーと攻撃力a、体力1のクリーチャーがいる状況よりは、明らかに損です。そのように考えると、比例定数をどうすべきかもある程度決まります。

このような考察は、他の要素、キーワード能力についても同様に行うことができます。
例えば、以下のような質問にどう答えればよいかを考えてみると分かりやすいかもしれません。[2]

  • 「自分の盤面に攻撃力a、体力hのクリーチャーが2体いる」と「自分の盤面に攻撃力2a、体力2hのクリーチャーが1体いる」はどちらが嬉しいか？
  • 「自分の盤面に攻撃力a、体力hのクリーチャーが2体いる」と「自分の盤面に攻撃力a、体力2h + 1のクリーチャーが1体いる」はどちらが嬉しいか？
  • 「自分の盤面に攻撃力a、体力hのクリーチャーが2体いる」と「自分の盤面に攻撃力2a + 1、体力hのクリーチャーが1体いる」はどちらが嬉しいか？
  • 「自分の盤面に攻撃力1、体力h Lethal のクリーチャーが2体いる」と「自分の盤面に攻撃力1、体力2 h Lethal のクリーチャーが1体いる」はどちらが嬉しいか？

次に、探索アルゴリズムの設計についてです。

標準入力でターン開始時の状態が与えられるので、ここから自分のターンでできる合法手をプレイして到達できる状態を列挙します。列挙されたそれぞれの状態に対して、相手のターンに進みます。
相手の手札は分からないので、相手の盤面に残っているクリーチャーの攻撃を合法手として、到達できる状態を列挙します。

そうして自分のターン、次の相手のターンまでを終えて到達できる状態を評価し、自分にとって最も評価の高い状態を実現できる合法手を探索します。

下は状態遷移のイメージ図です。始状態Aが入力で与えられたとして、評価を行うのはF, G, \dots, Oということです。

相手のクリーチャーの攻撃を考慮するのは、自分から見えている確定情報の中で、最も深い探索になります。探索をより深く行っていれば、評価関数の設計が多少悪くても、それなりに良いプレイングを探索できるようになります。

例えば、自分の盤面に3/3のクリーチャーAがいて、相手の盤面に1/1 LethalのクリーチャーBがいるとします。そこで、クリーチャーAでクリーチャーBを攻撃するか、相手を攻撃するかを選択する状況を考えます。(Lethal: 自身がクリーチャーにダメージを与えたとき、そのクリーチャーは破壊されます。)

自分でクリーチャーBを攻撃しなくても、相手のターンにクリーチャーBでクリーチャーAを攻撃してくれそうな局面です。その展開になれば、相手のHPをより多く減らすことができます。

相手のクリーチャーの攻撃を探索しない場合、以下の2パターンの比較になります。

  • 自分のクリーチャーAでクリーチャーBを攻撃して、両方破壊されること
  • 相手を攻撃して、クリーチャーA, Bはそのままで相手の体力が3減ること

上の評価が高いとき、クリーチャーAはクリーチャーBを攻撃します。

相手のクリーチャーの攻撃を探索する場合、以下の2パターンの比較になります。

  • 自分のクリーチャーAでクリーチャーBを攻撃して、両方破壊されること
  • 相手を攻撃してクリーチャーA, Bはそのままで相手の体力が3減り、その後相手のターンにクリーチャーBでクリーチャーAを攻撃し、両方破壊されること

この比較であれば、評価関数がそれなりに真っ当な場合、後者を選択できます。

高速化の工夫

手札の枚数が多く、お互いの盤面にクリーチャーが多く並んでいるときは、ゲーム木を構築するのに時間がかかってしまいます。

盤面に6体ずつクリーチャーがいるときは、攻撃の順番と攻撃対象の選択で最悪6! \times 7^{6} = 84707280通りの合法手の組み合わせがあります。現実的にはここまで組み合わせの多い盤面にはなりませんが、それでも可能な範囲で高速化をしたほうがよいです。

LOCMでは、クリーチャーの攻撃、クリーチャーの召喚、カードの使用は順番を入れ替えても結果が変わらないことが多くあります。そのため、一度探索し終えた状態と同じ状態を探索すると無駄が大きく、重複した状態を見ないようにすることの効果が大きいです。

重複した状態を見ないようにするには、探索の順番を制御することも重要です。例えば、クリーチャーの召喚を後回しにするように探索すれば、クリーチャーの攻撃のパターンを取り尽くしたあとで、クリーチャーの召喚のパターンを取り尽くすように探索でき、ランダムな場合と比べて実行時間が短くなることが期待されます。[3]

ドラフトフェーズ

結論から言うと、3つの中からDrawnWRが高いものを選び続けるだけで、Legend Leagueに入れました。(DrawnWR: あるカードがドローされた試合における勝率)

データベースを作成し、ボットはそこからDrawnWRを計算して、ドラフトを行うようにします。
試合が終了したら、その結果をもとにデータベースを更新します。これを繰り返して、DrawnWRをより正確にします。

コンテストに提出するときは、単独のソースコードを提出するので、データベースから計算したすべてのカードのDranwWRの値を埋め込んで利用します。

更に戦略を発展させる場合、マナカーブを考慮してドラフトを行うような戦略は妥当だと考えられます。
ドラフトがある程度済んだ状況を考えると、データベースから計算されるDrawnWRは、現時点でのデッキに加えたときに期待されるDrawnWRと異なることは明らかなので、より強いボットを作成する上ではマナカーブを考慮する必要があります。

実際、1位の方と対戦させて振る舞いを観察していましたが、そのような戦略を取っていることが確認できました。

ただ、Legend Leagueに到達する程度であれば、DrawnWRだけを見てドラフトしても十分戦えます。

LOCMでDrawnWRが指標として優れている理由

LOCMは、デッキにあるすべてのカードは同じ頻度でドローされます。
これは当たり前のように感じるかもしれませんが、一般的なカードゲームでは、デッキから自分で選んでカードをドローできる効果をもったカードはよくあります。そのような場合、カードごとに引かれる頻度が異なるので、カードの強さの指標としてDrawnWRを単純に使うのは難しいです。

例えば、カードAを使用するとカードBをドローできるとします。そうすると、カードBをドローするのは、以下の2パターンになります。

  1. 普通にカードBをドローする。
  2. カードAを使用してカードBをドローする。
    • 普通にカードAをドローする頻度は、普通にカードBをドローする頻度と大して変わらないと考えます。

ここで、2のパターンでカードBをドローするかどうかは、カードAを使用すべき状況かどうかに依存します。そのため、カードAを引いたとき、すでに勝率が高そうな場合は、カードAを使用できるが、勝率が低そうな試合では、カードAを使用できないという構図があるとき、カードBのDrawnWRは、他のカードのDrawnWRに対して歪んでしまうことが分かります。

LOCMでは、上のようなカードは実装されていないので、DrawnWRをカードの強さの指標として利用しやすいです。

あとがき

Legend Leagueに到達して一区切りついたので、戦略や実装についても書いておきたいと思い、そこに焦点を当てて記事を書きました。
当初はもう少し工夫しないとLegend Leagueには行けないかなと考えていましたが、DrawnWRを利用したドラフト戦略がかなり効果的で、そこまで苦労せずに到達できました。
ドラフト戦略はまだ工夫の余地があるので、それを分析しつつ、もう少し上位が狙えると良いなと考えています。

CodinGameのCode of Conductによれば、

Sharing of code is encouraged, as part of the CodinGame's solution system. Please refrain from sharing "ready to copy & paste" code in the forum or on GitHub for example.

とあります。実装の詳細に触れない範囲で、振り返りを行うようにしました。

脚注

  1. 実際は、自己対局を繰り返しているときに対局を見て対戦フェーズのボットの修正を行っています。 ↩︎

  2. 決まった答えがある質問というわけではないです。 ↩︎

  3. ここではキーワード能力 Charge は考えないことにしています。 ↩︎

Discussion