はじめに
こんにちは、『あんさんぶるスターズ！！Music』開発エンジニアのN.Sです。
この記事では、今年の3月頃に改修を行った、「あんスタ！！Music」の「おまかせ編成機能」の実装についての解説をします。
おまかせ編成機能について
「あんスタ！！Music」では、ライブを行う際に「ライブメンバー5人＋サポートメンバー2人」のユニットを編成します。
ここで編成した「ライブメンバー5人」のカードの組み合わせから算出される総合値によって、ライブ中のスコアが変動します。
簡単に言うと、総合値が高ければ高いほどノーツ1つあたりのスコア上昇値が高くなります。
（ライブスキルの影響などもありますが、ここでは一旦考えない事にします）
つまり、おまかせ編成に期待されるのは「総合値が高くなるユニットが自動的に編成される」機能だと言えます。
総合値の計算について
総合値はカードの元のステータスに加えて、以下のボーナスの影響を受けて計算が行われます。
- センターカードの持つセンタースキル（例：BrilliantタイプのVocalを120％アップ、Sparkleタイプの全パラメータを50％アップなど）によるボーナス
- 楽曲ボーナス
- 楽曲と同じ属性のカードへのボーナス
- 楽曲のオリジナルメンバーと同じキャラクターのカードへのボーナス
楽曲によって適切にカードを選択することで、元のカードのステータスが最大2倍以上にもなるため、カードのステータスの高さだけではなく、これらのボーナスを考慮してユニット編成を行うことが重要となります。
「あんスタ！！Music」リリース時点のおまかせ編成機能では、これらの影響を考慮せずにカードのステータスのみを参照して選択していたため、ほとんどの場合おまかせ編成よりも手動で編成した方が総合値が高くなるという状況になっており、実質的におまかせ編成が機能していませんでした。
それは良くないという事で、各種ボーナスも考慮した上で最も総合値が高くなる組み合わせを選択できるように改修する事になりました。
最適な編成を求めるアルゴリズムについて
ここからは、総合値が最も高くなるユニット編成をどのようにして求めるかを考えていきます。
最も単純なアルゴリズム
単純に考えれば、手持ちのカードについて全ての組み合わせを試してその総合値を計算すれば、確実に最も総合値が高くなる組み合わせを導きだすことができそうです。
しかし、その方法では計算量が極めて多くなってしまい、サーバーのパフォーマンスに悪影響を与える可能性が高いです。
所持カード数をnとすると、センターカードと残り4枚を選ぶ時の組み合わせの数は…
…いまいちピンと来ないですが、流石にまずそうです。
試しにn = 200（デフォルトのカード所持数上限）として計算してみたら、126億7825万200通りと出ました。
という事で、もっと効率よく編成を求めるための方法を考えてみます。
効率の良いアルゴリズム
計算量が増える最大の原因は、センターカードと残りの4枚の組み合わせを求める部分です。なので、ここを効率化することを考えます。
センターカード以外の残り4枚の組み合わせを効率よく選ぶ方法
先にセンターカードを決めれば、残りのカードはセンタースキル（と楽曲ボーナス）を適用した後の総合値を求めて上から順番に4枚選べば良いだけなので、もっと計算量は減らせそうです。
それでも、全てのカードで試すとなるとまだ計算量はそれなりに大きくなりそうです。
ソートの計算量を O(nlogn) と仮定すると、ソートをカード枚数分行うため O(n^2logn) くらいになります。
先程と比べるとかなり現実的な範囲になりましたが、まだ n^2 が存在するためカード枚数が増えると計算量が急激に増えてしまうことになります。
現在はカード所持数上限は最大250枚までしか拡張できないためそこまで壊滅的な重さにはならないかもしれませんが、できればより効率の良い方法を考えたい所です。
そこで、センターカードの候補を絞り込むことで、さらに計算量を減らすことを考えました。
センターカードを絞り込む方法
センタースキルの効果はいくつかの種類があり、カードのレア度によって効果値が違います。
例を挙げると…
- BrilliantタイプのVocalを120％アップ
- GlitterタイプのDanceを80％アップ
- FlashタイプのPerfを50％アップ
- Sparkleタイプの全パラメータを50％アップ
このような形で、4属性×4パラメータの合計16種類が存在します。
ここで、同じ種類（対象の属性とステータスが同じ）のセンタースキルの場合は、効果値が一番高いスキルを持つカードのほうがほぼ確実に（※）総合値は高くなると言えます。
※ 理論上はカードのステータスが高ければ逆転する可能性はありますが、実際にはレア度が高い≒総合値が高いカードのほうがスキル効果値も高く設定されているため、逆転が起きるケースは極めて稀としてここでは考慮しない事にしています
そのため、まず各センタースキルタイプで効果値が最も高いカードを抽出することにします。
次に、抽出されたカードの中から各センタースキルタイプごとにセンタースキル（＋楽曲ボーナス）込みでのカード単体の総合値が最も高くなるカードを選び、それをセンターカードの候補とします。
つまり、センターカードの候補はセンタースキルの種類分、最大16枚選ばれることになります。
最後に、16枚のセンターカード候補に対して残りの4枚を先述のアルゴリズムで選び、ユニットを16個作ります。
その中で最も合計の総合値が高かったユニットが最終解答の編成となります。
この方法で、計算量は O(nlogn) の範囲内に収まりました。
n^2 が無くなったので十分安心できる範囲内に収まったのかなと思います。
おわりに
このようにゲームの仕様を考慮したアルゴリズムで実装することで、効率よく最適なユニット編成を導き出す実装を行うことができました。
なお、今回は簡略化のため説明を省きましたが、実際には同じキャラクターを1つのユニットに編成することは出来ないという仕様が存在するため、それも考慮した実装になっています。
より厳密には、ライブスキルの種類によっては総合値が最高にはならないユニット編成のほうが最終スコアが高くなる可能性もあるのですが、そこまでを考慮するのは実装がとても複雑になる事と、全てがおまかせ編成機能で完結してしまうと自分でユニット編成を考える楽しみが失われてしまうので、さらにスコアを突き詰めたいという人向けのやりこみ要素として残しています。
ちなみに余談ですが、次回アップデートにておまかせ編成に「サポートメンバーを固定する」機能を追加予定です！（こちらの機能追加は別の方が担当されました）
おまかせ編成を行う際に「サポートメンバーをおまかせで変更しない」のチェックをオンにすることで、現在設定中のサポートメンバーのカードを変更せず、ライブメンバーのカードのみを変更することが出来るようになります。
より使いやすくなったおまかせ編成機能を是非お試しください！
Discussion