この記事はドミニオン Advent Calender 2021 12日目の記事です。
事の発端
今から一週間前、「ドミニオンアドカレのネタどうしようかな〜〜〜。無難に好きなカードについて語るかな〜〜。」などと考えていたときに、ふと電波が降ってきました。
そういえば、ドミニオンのデータを集めて遊んだことなかったな〜と思い、このネタにチャレンジしてみることにしました。
今振り返ると、このネタをやるのであればもう少し早い段階から動き出すべきでした。短い期間で取り組んだ結果、中途半端なクオリティとなってしまいましたが、ご容赦ください…。
また、データ収集・分析などエンジニアリングよりな話も多くなってしまうこともご容赦ください…。ドミニオンに関する情報だけ知りたい方は「データの前分析」から読み始めることをおすすめします。
問題整理
目的を達成するために、まずはいまやろうとしていることを改めて整理してみることにしました。
- ゴール: ドミニオンのサプライ情報から、終了ターンを予測する機械学習モデルを作る
- 期間: 一週間
- やらないといけないこと / その時の課題
- ドミニオンオンラインのゲームの情報を集める
- どのようなデータを集めるか
- どのようにデータを集めるか
- 集めたデータを整形する
- なんとかなる気がする
- 機械学習モデルを作る
- なんとかなる気がする
- 結果を分析する
- なんとかなる気がする
- ドミニオンオンラインのゲームの情報を集める
整理した結果、一番の課題はやはり「どのように、どのようなデータを集めるか」というところにありそうです。そこから先のフェーズは、これまでの経験からそれほど時間をかけずに取り組める気がしました。
データ収集
小一時間考えた結果、以下の作戦で行くことに決めました。
- どのような: サプライにあるカード名の一覧、ゲームの終了ターン
- どのように: ドミニオンオンラインの過去ゲーム読み込み機能を使う
具体的には以下のプロセスを踏むことにしました。
- データを集めるプレイヤー名一覧を集める
- プレイヤーの直近のgame idを集める
- game idからそのゲームの情報を集める
データを集めるプレイヤー名一覧を集める
サプライからゲームの終了ターンを予測したいですが、ゲームの終了ターンはプレイヤーのスキルによって大きく変動する値になります。「サプライ情報とプレイヤースキルを入力して、終了ターンを予測する」という問題設定も考えられましたが、面倒くさいため問題が複雑になるため今回は「レートが58以上の上級者プレイヤー[1]“上級者”の定義は諸説あるが、今回は集められるデータ量なども鑑みてこのくらいの値を設定しました」を対象とすることにしました。
今現在レートが58を超えているプレイヤーの名前一覧を取得するのは、ドミニオンオンラインの画面上からはできなさそうでした。
なので今回は、今年開催されたドミニオンの世界大会「ドミニオンチャンピオンシップ2021」の参加登録情報を使わせてもらい、当時レートが58以上あったプレイヤー名一覧を取得してくることにしました。
結果として、合計83名のプレイヤー名を集めることができました。
プレイヤーの直近のgame idを集める
次に、収集したプレイヤーの直近のgame idを集めることにしました。game idはドミニオンオンラインのサイトで行われたゲームに割り振られるidであり、この情報があれば過去に行われたゲームを読み込むことができます。
ここでは、discordのbotである「dombot」を活用することにしました。dombotの情報は、SSLYさんのこちらの記事が詳しいです。dombotには、「プレイヤー名を入れると、そのプレイヤーの直近のゲームの結果とgame id」を教えてくれる機能があるため、こちらを使ってgame idを集めていきます。
83回この作業を行うことは苦しいため本当は自動化したかったのですが、うまい方法が思いつかなかったため今回は手動で頑張りました…。83プレイヤーが直近行ったゲームを収集し、7211ゲームのgame idが収集できました。 (8300ゲームにならなかったのは、おそらく長い期間遊んでいないなどの理由でdombotが集められなかったことなどが原因)
game idからそのゲームの情報を集める
さて、ここが一番の難所です。
はじめは、ここも「game idを入れるとその情報を返してくれる」dombotの機能を使って情報を収集する算段でした。
一見、欲しい情報は全て取れているように思えますが、なんとサプライの情報は画像で表示されています。結果をわかりやすくする作者様の配慮だと思いますが、これはすなわち「サプライの情報を手打ちで整理しなければならない(プログラムを使ってテキストを整理することができない)」ということです。7211ものゲームの情報を手打ちで集めることは流石に厳しすぎる…
そこで前述の通り、「ドミニオンオンラインの過去ゲーム読み込み機能」を使って情報を収集することにしました。ブラウザの操作、ページの情報収集ならばプログラムで自動化することができます。ドミニオンオンラインの数々の仕様に苦しめながらも出来上がったスクリプトがこちらです。
ページを開いては閉じてを繰り返しているだけのように見えますが、手元にはちゃんとゲームの情報が集まっています。左から、「サプライのカードの情報(金銀銅などの基本的なカードは除外)」、「ゲームの終了ターン(例えば後手の12T目で終われば、12.5が入る)」、「そのゲームがゲーム終了条件(属州or植民地枯れ、三山枯れ)を満たして終了したか」の情報が並んでいます。
このプログラムをサイトに負荷をかけないように回し、エラーで止まったら再実行させるを何度も繰り返して、約3日間で3197ゲームの情報を集めることができました。
データの前分析
ある程度の数のゲームの情報を集めることができ、ようやく分析や機械学習モデル構築を行うことができるようになりました。まず行うのは、探索的データ分析(EDA)と呼ばれる「収集したデータの前分析」のフェーズです。使用したコードはこちら。
ゲーム終了判定について
ゲームの終了判定を満たしていたゲーム数は以下の様になっていました。
| 終了条件を満たしたゲーム | 投了で終了したゲーム |
| 775 | 2422 |
全体の約3/4のゲームが「投了」によって終了しているようでした。実際には「ゲーム終了が確定したため投了(例えば、属州が残り1枚の段階で仮想金で8金が出た)」というケースもそれなりにあるはずなので、「ゲームの途中で大差がついたため投了」というケースはもう少し少なくなる気がしています。
ゲームの終了ターンについて
集めたゲーム情報の終了ターンについて見てみましょう。
平均の終了ターンは以下のような感じでした。昨今のカードパワーインフレによって早期に終了するゲームが多い印象でしたが、ゲーム終了まではだいたい15T前後かかるようです。
| 終了条件を満たしたゲーム | 投了で終了したゲーム |
| 15.27 | 13.62 |
終了ターンの分布も見てみます。
面白い結果に見えます。
- ゲーム終了条件を満たしたゲームは、きれいな正規分布を描いている
- 投了で終了したゲームは、凸凹したヒストグラムになっている
- 思いつく仮説としては「先手のほうが有利になりやすく、先手のプレイ中に投了が起きやすい」など？
- 投了で終了したゲームは0~5ターン目という通常だと終了がありえないような早期ターンでもゲームが終わっている
- 「ゲーム開始後、相手が操作しないので投了にした」、「嫌いなカードがあった」、「5-2と4-3の格差が大きいときに裏目を引いた」などが理由？
- 上記のゲームは、モデリングの際はノイズとなりそうなので除く
サプライについて
サプライに関する分析では、とりあえず出現するカードの頻度を見てみました。
| 出現頻度上位5カード | 出現頻度下位5カード |
| 馬 (261回) | card-of-the-mouse? (1回) |
| 共同墓地 (68回) | 支配 (1回) |
| 草茂る屋敷 (68回) | card-of-the-horse? (2回) |
| 納屋 (68回) | 鍛錬 (3回) |
| 白金貨 (55) | 山賊の砦 (5回) |
結果を出してみて、データ収集時に以下のカードを除去していない失敗に気が付きました。これらのカードは「このカードが有るとき、ある他のカードが出現していることが確定している」ものと「データ取得時のバグ」のものであり、機械学習モデルの入力としてはノイズとなりうる情報なため除去します。
- 避難所
- 願い
- 家宝
- splitカードの片割れ
- 騎士
- 城
- トラベラー(騎士見習い、農民)
- pig (女魔術師？)
- card-of-the-XXX (修正を取るときのバグっぽい)
- ゾンビ(ネクロマンサー)
- コウモリ
こちらを修正して再集計した結果がこちらです。(白金貨、避難所、イベントランドマークなど除く)
| 出現頻度上位5カード | 出現頻度下位5カード |
| ラクダの隊列 (54回) | 支配 (1回) |
| 漁師 (50回) | 浮浪児 (3回) |
| 動物見本市 (49回) | 国境警備隊 (8回) |
| デストリエ (48回) | 枢機卿 (8回) |
| 貸し馬屋 (44回) | 馬上槍試合 (9回) |
出現頻度上位は見事に移動動物園(拡張)のカードで占められていました。これはおそらく、ドミニオンオンラインの特別ルール「移動動物祭」の影響によるものだと考えられます。
出現頻度下位は、以下にも上級者プレイヤーがBAN指定していそうなカードが並んでいました。国境警備隊だけ自分の感覚的にここにいるのは不思議ですが…。
サプライ x 終了ターンについて
最後に、サプライと終了ターンの組み合わせの定性結果を見てみましょう。
ゲーム終了条件を満たしたゲーム集合の中から、最短のゲーム、最長のゲームをそれぞれピックアップしてみます。
最短ゲーム10件はこんな感じ。
英語でわかりづらく恐縮ですが、以下のような感じでしょうか？
- 最短のゲームは「行進-馬」なので納得…
- 2番目に短いゲームは「mastermind」と「groom」が暴れた？
- それ以外のゲームも、基本山が枯れるカード(発明家、ヴィラ、石工、大学など)が入ってそう？
最長ゲーム10件はこんな感じ。こちらはより顕著な傾向が出てました。
- 一番遅かったゲームは「狂信者」と「羊飼い」でグダグダゲームになった？
- 騎士が複数回登場している… やっぱり良くないカード
- 城も複数回登場している。城 vs. 属州 はロングゲームになりやすい
- その他、不正利得やぶどう園など、納得なカードが入っているゲームが多い
機械学習モデル構築
ようやくモデル構築です。サクッとやっていきます。
今回使うモデルはシンプルな線形回帰モデルです。学習された重みを見ることで、ゲームの終了ターンに大きく影響するカードを調べることが容易だからです。
コードはこちら。
線形回帰モデルの構築結果
まずはゲーム終了条件を満たしたゲーム 775ゲームを使った結果から。
MSEは小さいほど良い結果、R^2は大きいほど良い結果を表しています。
また、train_dataは学習に使ったサプライに対する予測性能、test_dataは未知のサプライに対する予測性能を表しています。
| MSE | R^2 | |
| train_data | 2.246 | 0.798 |
| test_data | 19.451 | -1.474 |
この結果を一言で表すなら「ヒドい」です…。
未知のサプライに対する予測が全く上手くいっておらず、学習に使ったサプライのデータに過学習している様子が見て取れます。
原因としてはやはり、学習に使ったデータ数が少なすぎることがありそうです。
次に全データを使った結果はこちら。
| MSE | R^2 | |
| train_data | 10.818 | 0.309 |
| test_data | 18.453 | -0.035 |
多少マシになりましたが、やはり学習に使ったデータと未知のデータの間の予測性能の差が大きく、これでもまだデータ数が少なすぎるように思えました。
次に、構築したモデルの重みから、ゲーム終了ターンに影響するカードを見てみます。
| 終了ターンを 早めるカード | 終了ターンを 遅くするカード | |
| 1 | 絹証人 | 騎士 |
| 2 | 宴会 (イベント) | 城 |
| 3 | 徴募官 | 香具師 |
| 4 | 寄付 (イベント) | 念視の泉 |
| 5 | 宮廷 | パトリキ |
| 6 | 保存 (イベント) | 魔女集会場 |
| 7 | 施し (イベント) | 狂信者 |
| 8 | ヴィラ | 襲撃者 |
| 9 | 海路 (イベント) | 羊飼い |
| 10 | ギルド集会場 (イベント) | 儀式 (イベント) |
個人的には、概ね納得感がある結果となりました。
ゲーム終了ターンを早める要因となるのはイベントが多いようです。一つだけ、宴会がこの位置にいるのがとても不思議です。上級者になるほど宴会の使い方がうまくなるのかもしれませんが、今回集められたデータ量的に「たまたま」の可能性も高そうです。
ゲーム終了ターンを遅くする要因となるカードには、やはりアタックカードが多く含まれています。これらのアタックカードはいずれも食らうとデッキ構築が遅れてしまうため、納得感があります。面白いのは城、パトリキ、羊飼い、儀式で、これらのカードの共通点は「属州以外の勝利点行動につながるカード」です。相手に属州を先行され、逆転するための手段としてこれらのカードが使われた結果ゲーム終了が遅くなるのかもしれませんね。
表現力の高い機械学習モデルを使った結果
線形モデルでも過学習した今回のデータですが、他のモデルを使うとどうなるかは素朴に気になったため、より表現力の高いモデルを使った結果も見てみます。
今回はpycaretというAutoMLライブラリを用いてガーッと計算してしまいます。
各モデルと性能は以下の通り。
先程利用した線形回帰モデル (Linear Regression) よりも性能が高いモデルがたくさんありました。今回最も性能が良かった Gradient Boosting Regressor を用いて評価をやってみます。
少しごちゃごちゃしていますが、注目したいところは2点で、
- Test R^2がTrain R^2と比べて非常に小さいため、このモデルでも過学習が起きてしまっている。
- 学習に使ったデータ(青)のドットに注目すると、Residuals = 0 の黒太線から大きく離れたドットが多く存在する。学習に使ったデータセットですら、あまりうまく予測できていなさそう。
ということが言えそうです。
まとめ
今回は、ドミニオンオンラインの上級者のデータを頑張って収集し、簡単な分析や機械学習モデルの構築を行いました。
今回の結果から考えられるnext actionとしては、以下がありそうです。
- もっともっともっとたくさんのデータを集める。現在存在するカードから作られるサプライの組み合わせは膨大であり、今回収集できたデータはその中でも極極極一部分。
- カードのシナジーを考慮できるような特徴量表現やモデルを利用する。今回の特徴量表現だと、例えば「ギルド集会場-物乞い」や「行進-馬」といったゲーム終了ターンに大きく影響する「カードの組み合わせ」を表現できていないため、予測性能が低くなる可能性が高い。
正直データを集めるところがしんどすぎる[2]dombotがどうデータを集めているか気になる。同じことができたらもっと良いものが作れそう…ので、次はないかと思います笑
コメント