Google Cloud で作るサッカーのスターティングイレブン最適化パイプライン
これは数理最適化 Advent Calendar 2022 の 14 日目の記事です。
概要
2022 年はワールドカップが冬に開催ということでサッカーを見ながらアドベントカレンダーを執筆しております。
今回は FPL というサッカーに関連するゲームのデータを使ってベストなスターティングイレブンを数理最適化を用いて解く方法を記していきます。
またゲームの都合上、週毎にデータを更新して最適な選手を選ぶ必要があります。
数理最適化の問題を一度解いてインサイトを得ることは難しいですが、それを継続的に新しいデータに対して解くことは更に難しいと思います。
今回は Google Cloud の技術を使いデータ取得から加工、最適化までを一気通貫でできるようにパイプラインを作ったのでそのアーキテクチャの紹介もします。
Fantasy Premier League（FPL）
イングランドのプレミアリーグのリアルなデータを使って遊ぶゲームです。
プレイヤーは週毎に選手を決まった人数選びます。
そして実際のプレミアリーグの試合ごとに出た選手のパフォーマンスによってポイントが算出されます。
自分の選んだ選手のポイントの合計が一番多いプレイヤーが勝利となります。
こんな感じのプレー画面です。
アーキテクチャ
ざっくりこんな感じで、fetch ~ dbt まででデータの更新を行い、optimizer, app で最適化を行う構成です。
以下これらを説明していきます。
データ取得から作成まで
「ゴミデータを使ってなにかやってもゴミしか生まれない」とも言いますし良い最適化も良いデータを作ることが大切です。
最適化のためのデータ作成は 3 フェーズに分かれており、それぞれを Cloud Run jobs にデプロイしています。
Cloud Run jobs は Docker コンテナの Entrypoint を実行してくれるバッチサービスでどんな言語でも Dockerfile にさえ記述できれば実行できます。
例えば fetch のタスクは API のレスポンスを GCS バケットに保存するだけの単純な処理なのでシェルスクリプトで記述しています。
curl http://example.com > result.json # url は適当
gsutil mv result.json gs://fpl-rawfile-bucket/dt=2020-01-01/result.json
FROM gcr.io/google.com/cloudsdktool/google-cloud-cli:alpine
RUN apk --update add curl
ENTRYPOINT ["sh", "entrypoint.sh"]
次に parse では fetch で保存した result.json を csv に変換する処理を行っているのですがデータ加工がしやすい python で記述しています。
dbt では dbt というデータモデリングのツールで SQL によりデータクレジングを行っています。
dbt を使うことでデータのバリデーション（ユニーク制約や null チェック）やテストができるので最適化に入る前にデータの正確性を担保できるため採用しました。
こんな感じでデータ（テーブル）ごとにドキュメントやデータリネージを見ることができるのも便利です。
ドキュメント
リネージ
このように多様な処理を Cloud Run jobs で細切れにしかも違う言語で実現することができます。
最適化の要件によってデータの特性や加工方法は様々なので、自由度の高い実装ができる Cloud Run を採用しています。
※ Cloud Run jobs は執筆当時は GA ではないので注意！
処理の順序関係は Cloud Workflows で管理しています。
Cloud Workflows は yaml を記述することにより Google Cloud サービスを簡単に呼び出すことが可能です。
この処理は週次で呼び出す必要があるためこのワークフローを Cloud Scheduler にて呼び出して運用しています。
cloudrun_jobs:
params: [job]
steps:
- fetch:
call: googleapis.run.v1.namespaces.jobs.run
args:
name: $${"namespaces/" + project_number + "/jobs/fetch"}
location: asia-northeast1
result: resp
- parse:
call: googleapis.run.v1.namespaces.jobs.run
args:
name: $${"namespaces/" + project_number + "/jobs/parse"}
location: asia-northeast1
result: resp
...
※ terraform でデプロイしているため若干記法が違う
最終的に作られたデータは GCS に保存するのだが以下のようなフォーマットとなります。
最適化に使うのが以下のカラムです。
- name ... 選手名
- element_type_name ... ポジション名
- team_name ... チーム名
- now_cost ... 選手獲得にかかるコスト
- expected_points ... 今週獲得できそうなポイント
id name element_type_name team_name now_cost status chance_of_playing total_points expected_points
0 501 NathanielPhillips DEF Liverpool 39 a 1.0 0 0.0
1 378 HarryArter MID Nott'm Forest 43 a 1.0 0 0.0
2 502 ScottCarson GKP Man City 38 a 1.0 0 0.0
3 393 LoïcMbe Soh DEF Nott'm Forest 42 a 1.0 0 0.0
4 328 PhilJones DEF Man Utd 39 a 1.0 0 0.0
最適化部分
今回の最適化では選手を複数人選びポイントを最大化する必要があります。
毎週メンバーを選んでいるので「前週のメンバーから n 人変えてポイントを最大化する」という最適化の要件になります。
最適化に使うモジュールはご存知 pulp です。
またルール上いくつか制約があるのでそれらをコードに落とし込んでいきます。
制約一覧
- 選手獲得の予算
- 同じチームの選手は 3 人以下
- ポジションごとの制約
- FW は 3 人
- MF は 5 人
- DF は 5 人
- GK は 2 人
- ※更にこの中から 11 人選ぶ必要があるがこれは人手で行う想定です。
# lpVariable 生成
fun = lambda x: pulp.LpVariable(f'{x.id}_{x.element_type_name}_{x.team_name}', cat='Binary')
master['variables'] = list(master.apply(fun, axis=1))
# 最適化問題をオブジェクト化
prob = pulp.LpProblem('fpl_planner', sense = pulp.LpMaximize)
#################### 制約一覧 ####################
# ポジション(element_type_name)ごとの人数の制約
PLAYER_LIMIT_BY_POSITIONS = {'GKP': 2, 'DEF': 5, 'MID': 5, 'FWD': 3}
for p in master.element_type_name.unique():
dt = master[master.element_type_name == p]
prob += pulp.lpSum(dt.variables) == PLAYER_LIMIT_BY_POSITIONS[p]
# 同じチーム 3 人の制約
SAME_TEAM_LIMIT = 3
for t in master.team_name.unique():
dt = master[master.team_name == t]
prob += pulp.lpSum(dt.variables) <= SAME_TEAM_LIMIT
# お気に入りチーム選手を絶対一人入れる
FAVORIT_TEAMS = ['Man Utd']
for t in FAVORIT_TEAMS:
dt = master[master.team_name == t]
prob += pulp.lpSum(dt.variables) >= 1
# 前週のスタメンとの交代選手数（例えば前週のメンバーと 3 人変える場合）
TOTAL_PLAYERS = 15
replacement = 3
dt = master[master.id.isin(current.element.values)]
prob += pulp.lpSum(dt.variables) == TOTAL_PLAYERS - replacemen
# コストの制限
COST_LIMIT = 1000
prob += pulp.lpDot(master.now_cost, master.variables) <= COST_LIMIT
# 全体の選手数の制限
TOTAL_PLAYERS = 15
prob += pulp.lpSum(master.variables) == TOTAL_PLAYERS
目的関数は以下。
expected_points はデータ作成時に計算した選手ごとに今週獲得できそうなポイントです。
現在は SQL ベースで単純な四則演算で算出していますが、いずれは機械学習などを用いて算出できるようにしたいです。
# 目的関数
prob += pulp.lpDot(master.expected_points, master.variables)
これを解くと先週の選手からどの選手を変えたらよいか予算や人数の制約を考慮した上で選んでくれます。
{
"expected_points":38.599999999999994,
"out_elements":[
{
"id":285,
"element_type_name":"DEF",
"name":"TrentAlexander-Arnold",
"expected_points":0.2,
"now_cost":72
},
{
"id":340,
"element_type_name":"MID",
"name":"JadonSancho",
"expected_points":0.6,
"now_cost":72
},
{
"id":80,
"element_type_name":"FWD",
"name":"IvanToney",
"expected_points":0.0,
"now_cost":74
}
],
"in_elements":[
{
"id":357,
"element_type_name":"DEF",
"name":"KieranTrippier",
"expected_points":5.4,
"now_cost":59
},
{
"id":427,
"element_type_name":"FWD",
"name":"HarryKane",
"expected_points":6.4,
"now_cost":116
},
{
"id":314,
"element_type_name":"MID",
"name":"PhilFoden",
"expected_points":8.0,
"now_cost":84
}
],
}
アプリケーション部分
上記で実装した最適化のロジックを Web API ベースで呼び出すために flask を使いエンドポイントを作成しました。
またその制約の条件などを細かく設定できるように Next.js ベースのアプリケーションを作ってブラウザから最適化を呼び出せるようにしました。
（サービス自体は IAP で保護しているので一般公開はしていません。）
これも Cloud Run にてサービスをデプロイして実現しています。
Cloud Run はバッチ処理だけでなく Web サービスもデプロイ可能なので便利です。
画面はこんな感じ。
（おまけ）料金感
大体月 20 円程度です。
無料にはできませんでしたが、数理最適化や Google Cloud の勉強代と考えてもコスパの良い料金だと個人的には思います。
一番料金がかかるのが Artifact Registry という Docker イメージを管理するために必要なので仕方ない感じです。
Cloud Run は起動時の CPU, メモリ時間単位での課金になりますが、週 1 回つまり月 4 回程度の実行なので今のところ 2 円程度に収まっています。
まとめ
数理最適化 Advent Calendar なのにその周辺技術の話多めになってしまい恐縮ですが、文中にも書いたとおり、「良い最適化をするためには良いデータを用意する」ところからだと思います。
最適化問題って使い捨てのスクリプトなどで一度解いたらおしまいというケース多いかもしれませんが、継続的に違ったデータを使って行う必要がある場合はこういった構成を参考にしてみてはどうでしょうか？
Discussion