組合せ最適化によるスプラトゥーンのチーム分け

Summary

• 数理最適化の応用事例として、スプラトゥーンのプライベートマッチにおけるチーム分け問題を紹介します。
• 問題は組合せ最適化として定式化され、その結果の例を示します。
• 数理最適化の視点を越えて、スプラトゥーンにおける数理にも触れます。

スプラトゥーン

スプラトゥーン全体像

スプラトゥーンは、インクを弾として撃ちあうアクションシューティングゲームです。
2015年にスプラトゥーン1が発売を皮切りに、2022年9月9日に最新作スプラトゥーン3が発売されました。
国内販売本数が、発売後3日間で345万本を突破し、これは、Nintendo Switch向けソフトの発売後3日間の国内販売本数として、トップクラス¹の販売本数となっており、人気の高さがうかがえます[1]。

筆者自身大好きなゲームで、かなりやりこんでいて²、かなり面白いゲームですが、本記事の目的である数理最適化からは逸れるため、興味を持たれた方はぜひ参考文献[2-4]をご覧ください。

以下に全体感を書きますが、実際の動画[5]で見る方が分かりやすいかもしれません。
自分のチームの色のインクは、イカになって泳ぐことができます。一方で、相手のチームの色のインクに触れると、ダメージを受けたり、動きが鈍くなってしまいます。
つまり、自分のチームの色のインクで塗り広げることが重要になります。

また、5つのルールがあり、勝利条件がそれぞれ異なります。
3分間ステージを塗り、総面積が多いチームが勝つ、ナワバリバトルなどです。
本記事では、5つのルールのうち、ガチエリアを対象にします³。
ガチエリアは、ステージ内の「ガチエリア」を塗って、一定時間確保したチームが勝利となります。
ガチエリアを塗るために、相手を倒したり、自分のチームの色のインクで塗り広げて、相手を近寄らせないなどを繰り返すことになります。
なお、ガチエリアの1試合は5分です。

スプラトゥーンにおけるブキ

準備としてスプラトゥーンにおけるブキについて説明します。
スプラトゥーンには様々なブキがあります。
インクの弾を連射する「シューター」、筆のような「フデ」、溜めたインクを発射する「チャージャー」など、特性が様々です。
シューターにも、インクがブレることなく発射されるものもあれば、ブレは大きいが高威力のものなど、様々あります。

また、インクが発射される距離にも差があります。本記事では、これを射程と呼びます。
想像に難くないですが、射程は長い方が有利です。
ただし、射程が長いブキは発射速度が遅く、懐に入られると不利になります。

スプラトゥーンにおける実力の指標

もう一つの準備としてスプラトゥーンにおける実力について説明します。
スプラトゥーンには「ウデマエ」と呼ばれるプレイヤーの実力を示す指標があります。
基本的にはこれを上げることを目指すことになります。（もちろん上げることに目指さずゲームを楽しむこともできます）

ウデマエはC-から始まり、C, C+, B-,...,A+, S, S+0, S+1, ...S+50と上がっていくことになります。
ウデマエがS+0になると、Xマッチに参加することができ、Xパワーという値でウデマエが定量化されます。
XPに値域は特に制限はありませんが、およそ1100~3000程度の値を取ります。
ただし、本記事では1800~2600程度に制限されます。
なお、定量化されたウデマエ、Xパワーを以下ではXPと表記することにします。

ゲーム上、ウデマエS以下は、ウデマエが定量化されませんが、ユーザー開催の非公式大会ではSは1700などと、ウデマエを定量化することがよく行われます。
本記事でもこれに倣ってS以下のウデマエを定量化することとします。

スプラトゥーンにおけるチーム分けの課題

ここで、人が集まったとして、チームに分けることを考えます。
32人集まれば8チーム、8人集まれば2チームできます。
例えば8チームできた場合、総当たりやトーナメントなどの大会を行うことができます。
2チームできた場合、チームどうしで戦うことができます⁴。

このとき、以下のような課題が生じます。

1. チーム間の実力差をなるべく近くしたい。
   例えば、片方のチームがとても強くなることなどは避けたいです。
   一方的な練習にならない、楽しくないといったデメリットが生じてしまうためです。
2. それぞれのチーム内のブキのバランスを良くしたい。
   例えば、片方のチームが射程が長いブキが集まったり、強いブキが集まることなどは避けたいです。
3. 実力によらず、そのときの調子に応じて、チーム分けをしたい。
   ウデマエは平均的な実力を表しますが、ばらつきがあります。本来は2500の実力でチームを割り当てられた人が、たまたま調子が悪く、数値通りの実力を発揮できないことがあります。逆のことも起きます。
   そのため、数値ではなく、そのときの調子でチーム分けをしたい。

以降の章で、このような課題を解決するチーム分けの事例と定式化を紹介します。
※課題3に対応する事例は時間の関係で、省きました。。。別の機会に執筆させてください。

チーム分け１　ー　小規模大会におけるチーム分け

問題設定

4N (Nは自然数)の人数が集まり、大会を開催することを考えます⁵。
このとき、1. チーム間の実力差をなるべく近くしたい、2. それぞれのチーム内のブキのバランスを良くしたい、この２つの条件を満たすNチームに分ける必要があります。
チーム分けを行う最適化問題を考えます。以下で、その定式化を行います。

なお、以下で考えるのはスプラトゥーンにおけるプライベートマッチと呼ばれるモードになります。
プライベートマッチでは、8~10人のプレイヤーが参加し（※部屋に入る）、各プレイヤーをチームに割り当てます。チームは2チームで、それぞれアルファチームとブラボーチームと呼ばれます。
9人以上の場合、1人または2人はチームに割り当てられず、観戦に割り当てられる（上空から試合を見る）ことになります。
このチーム分けでは1チーム4人で、プライベートマッチ中、各プレイヤーのチームは固定になります。

定式化

定式化は書籍[8]を参考に行いました。
変数を$x_{t,m}\in{0,1}$とします。
この変数は、メンバー$m$をチーム$t$に割り当てるとき1、そうでないときに0の値をとる変数になります。
なお、$T$はチームのリストで、$M$はメンバーのリストとします。

以下に条件を記載します。
・各メンバーは1つのチームに割り当てられる

\sum_{m \in M}x_{t,m}=1 \ (t \in T)

・各チームの人数は4人

\sum_{t \in T}x_{t,m}=4 \ (m \in M)

ここまでの条件は、スプラトゥーンにおけるチーム分けの基本になります。
一方で、まだチーム分けの課題である、

1. チーム間の実力差をなるべく近くしたい
2. それぞれのチーム内のブキのバランスを良くしたい

は解決されていません。以下で、この課題を解決する定式化を行います。

1.チーム間の実力差をなるべく近くしたい
チームの実力をXPの合計と考えることにすると、チーム間でXPの合計に差がなるべく小さくなるようにすると、
この課題は解決できそうです。
$P$をXPのリストとし、$p_m$をメンバー$m$のXPとします。
また、$z_{min},z_{max}$をそれぞれ、チーム間のXPの合計値の最小値と最大値を表す変数とします。
チーム間でXPの合計に差がなるべく小さくなるようにしたいので、

z_{max}-z_{min} \leq D,

と条件付けます。ただし、$D$はあらかじめ設定しておく値で、本記事では$D=50$とします。
また、このままでは$z_{min},z_{max}$が意味を持たないので、併せて、以下の条件も加えます。

\begin{align}
z_{min}\leq&\sum_{m \in M}p_mx_{t,m},\\
&\sum_{m \in M}p_mx_{t,m}\leq z_{max}
\end{align}

これは、各チームに割り当てられたメンバーのXPの合計が$z_{min}$以上、$z_{max}$以下になる条件になります。

2.それぞれのチーム内のブキのバランスを良くしたい
これは実現しようとするとかなり難しく、実際のゲーム内でも苦心されている点だと思っています。
ここでは、「射程が長いブキ（後衛）は同じチームに1人以下」だけを考えます⁶。
$R$を後衛を使うメンバーのリストとすると、条件は、

\sum_{m \in R}x_{t,m}\leq1 \ (t \in T),

となります。

また、これを応用することもできます。
プライベートマッチでは、何かしらのアプリ (Discord等)で通話し、互いの状況等を共有しながら試合をすることが多いです。
しかし、家庭の都合などで、通話の音声を聞くことはできるが、喋れない人がいることがあります。
この人を「聞き専」と呼ぶことにします。
聞き専の人が特定のチームに偏ると、チーム間で、試合中の共有される情報が少なくなり、不利になってしまいます。
そこで、「聞き専のメンバーはチームに1人まで」といった制限をかけたいわけです。
先ほどの条件の$R$を聞き専のメンバーのリスト$H$に置き換えればよいことになります。

結果

16人の参加者が集まったとします。
メンバーそれぞれのXP、後衛のリスト、聞き専のリストをまとめたのが以下の表です。
一番左はメンバー名を表していて、XP列がその行のメンバーのXPになります。
rear_guards列が、後衛のリストで、値に1が入っている行のメンバーが、後衛のブキを持つメンバーです。
hear_only列が聞き専のリストで、値に1が入っている行のメンバーが、聞き専のメンバーです。
このときには聞き専のメンバーがいなかったため、聞き専の列には全て0が入っています。

なお、これは実際に使ったリストですが、その際に参加したメンバーの名前はアルファベットでマスクし、
XPは適当に入れ替えてあります。

先の定式化をPythonのライブラリPulp[7]を用いて実装し、ソルバーにはCBC[8]を用いました。
その結果が以下です。

後衛を持つ"B", "F", "P"さんは別々のチームに割り当てられています。
cost SUMがXPの合計になりますが、全チーム同じ値になっていて、チーム間で数値上の実力差が無いことが分かります。

以下に参加したメンバーの感想を要約します。
・一方的な試合がなく、とても楽しめた。
・ギリギリ勝ったり、負ける試合が多く、白熱した。
感想ではありますが、先に3勝したチームに勝ち星が付くというルールで開催されていた大会のなか、
3-0となった組み合わせは1つも無かったようで、実力差が小さいことが実証されていたように思います。

課題と定式化の失敗

（もう一つの事例を書く時間が無いからここを追記して誤魔化そうだなんて...）
課題は上記でも述べたように、「良い編成」への考察を深めることがあると考えています。
ただし、これは明確な答えがあるわけではなく、大会のコンセプトや主催者の色が出る部分になると思っています。
また、敵を倒すことが得意な人、塗るのが得意な人、といったように、実力をスキルとして細分化することも考えられます。

定式化の失敗を挙げます。
各チームに割り当てられたメンバーのXPの合計が$z_{min}$以上、$z_{max}$以下になる条件を考えました。
最初は、各チームのXPの合計が平均±100以内という条件にしていました。
しかし、このようにしたとき、確かにこの条件を満たすようチーム分けはでき、チーム間の実力差もある程度抑えられます。
一方で、平均±100以内であれば良いので、あるチームは低く、あるチームは高くても、条件は満たしているわけです。
これを回避するために、$z_{min}$以上、$z_{max}$以下という条件に変更したという経緯があります。
このように、定式化をして、結果を見て、定式化を見直すというのは、実践では非常に大切だと感じています[9]。

最適化の視点を越えて、スプラトゥーンにおける数理

強化学習によるプレイヤーの学習

別のゲームの話になりますが、マインクラフトというゲームでは、映像から動作を学習し、あるタスクを人間が実行するよりも早くできるモデルを作ることできています[10]。
これを応用してスプラトゥーンをする機械学習モデルを作れないかな...？と考えています。
ただし、これが任天堂の規約上可能かどうかは調べていないので、もし実行される場合は、自己責任でお願いします。

プレイヤーのデータ分析

1試合において、自分がどれだけ塗ったか、敵を倒したか、やられてしまったかなどのデータを得ることができます。
では、このようなデータを用いて、試合に勝つにはどのような要素が大切なのか調べることができないかと考えています。
さらに、このデータを使って、プレイヤーのスキルを可視化できていないか？と想像しています。
敵を倒して勝つことが得意なプレイヤー、生存することが得意なプレイヤー、塗りが上手なプレイヤー etc...
このようにスキルを可視化することで、今回紹介したような事例のチーム分けに使えないだろうか...？
この話はチーム単位にも拡張できると考えています。

最後に

初めて技術記事を書きましたが、モチベーションの維持が難しいですね。。。
結果、中途半端な記事になってしまったな...と反省しています。
質問やコメントはTwitter chiaki_at_cakeでもどこでも、いただければ、
可能な限り回答したいと思います。ただし、保証はできません。

本当はもう一つ事例があったのですが、また別の機会とさせてください。

参考文献

[1] Nintendo Switch向けソフト『スプラトゥーン3』の国内販売本数が発売後3日間で345万本を突破

[2] スプラトゥーン3紹介映像

[3] スプラトゥーン3（公式サイト）

[4] これから始める「スプラトゥーン」

[5] 「第4回スプラトゥーン甲子園」闘会議2019 DAY2 全国決勝大会

[6]
https://twitter.com/melon1_game?ref_src=twsrc%5Egoogle%7Ctwcamp%5Eserp%7Ctwgr%5Eauthor

[7]Pulp
https://coin-or.github.io/pulp/

[8]CBC
https://github.com/coin-or/Cbc

[9]梅谷俊治. "組合せ最適化による問題解決の実践的なアプローチ." 人工知能学会研究会資料 人工知能基本問題研究会 115 回. 一般社団法人 人工知能学会, 2021.

[10]
https://openai.com/blog/vpt/
(日本語記事)https://www.itmedia.co.jp/news/articles/2206/28/news067.html

脚注

1. 2022年11月24日時点での最高は、スプラトゥーン3以降に発売されたポケットモンスタースカーレット・バイオレットです。
   https://www.nintendo.co.jp/corporate/release/2022/221124.html?utm_source=twitter&utm_medium=social&utm_content=20221124&utm_campaign=ir ↩

2. 最新作スプラトゥーン3は初心者の方にも自信をもっておすすめできます。興味を持たれた方、ぜひ一緒に遊びましょう。 ↩

3. 本記事で取り扱う定式化では、ルールは考慮しないため、どのルールでも問題はありません。ただし、話を簡単にするために、ガチエリアを対象にします。 ↩

4. 予めチームを組んだチームどうしで対戦する、対抗戦の方が一般的かもしれません。ここでは、8人(例えば知り合いどうし)がチームを組んでいない状態で集まった場合を考えます。 ↩

5. 実際にやったときには4の倍数には限定しませんでしたが、話を簡単にするため、今回はこのように限定します。 ↩

6. スプラトゥーンにおける用語を使った補足になります。
   ここで採用した条件である「射程が長いブキ（後衛）はチーム内に1人」というのは、極端に尖った編成を避けるという意味合いが強いという話をします。
   「射程が長いブキ（後衛）はチーム内に1人」の他に、塗りが強いブキが最低1人以上は必要や前衛4人はNG、なども考えられます。
   しかし、どのブキが塗りが強い、前衛などと定義するのかは難しいですし、プレイヤーによって意見は様々です。
   チーム内でのブキの構成を編成と呼ぶことにしますが、上記のような理由から「バランスが取れた良い編成」を定義することは、かなり難しい問題です。
   加えて、バランスが取れていないが、尖った編成というのも考えることができて、これも決して悪いわけではないです。
   その意味で、ここで採用した条件である「射程が長いブキ（後衛）はチーム内に1人」というのは、極端に尖った編成を避ける条件と言った方が正確だと考えています。
   もちろん、これも悪い編成ではないと考えることもできます。しかし、ここで考えているのは、集まった人を即席でチーム分けすることです。そのため、合意無く極端に尖った編成を割り当てることは避けようという意図の条件になります。 ↩