LoL内戦のチーム分けアルゴリズム解説（126通り全探索＋ハンガリアン法）
10人を5v5に分けるとき、なぜ126通りなのか。各組み合わせのロール割り当てをハンガリアン法で最適化する仕組み。スコアリング関数の設計まで踏み込んで解説。
LoLのカスタムゲームでチーム分けをするアルゴリズムは、見かけよりずっと複雑です。10人を BLUE と RED に5人ずつ分けるだけ、と思うかもしれませんが、実際には3層の最適化問題になっています。
この記事では、LoL Team Balancer の内部アルゴリズムを技術的に解説します。
第1層：チーム分割（126通り）
10人を5人ずつ2チームに分ける組み合わせは、組み合わせ論で C(10, 5) = 252通り です。ただし「BLUE 側に A〜E、RED 側に F〜J」と「BLUE 側に F〜J、RED 側に A〜E」は実質同じ試合なので半分。126通りです。
実は126通りは全探索できる規模です。1試合分のチーム分け計算で最適解を保証できます。総当たりは賢い方法ではないと思われがちですが、規模が小さいので問題ありません。
C(10,5) / 2 = 126
第2層：ロール割り当て（ハンガリアン法）
チーム5人が決まっても、TOP / JG / MID / ADC / SUP の誰がどこをやるかという問題が残ります。
これは割り当て問題そのもので、ハンガリアン法（O(n³)）で最適に解けます。各プレイヤー × 各ロールに「コスト」を割り振り、合計コストが最小になる割り当てを見つけます。
コスト設計の例： - メインロール = 0 - サブロール = 1 - Fill = 2 - オフロール = 10
オフロールに割り当てるコストを大きくすることで「絶対にオフロールを避ける」最適化になります。Fill ロールが登録されている人は、メインじゃなくても2まで許容、という解釈です。
第3層：候補のスコアリング
126通り × ハンガリアン法で得られた候補を、最終的にスコアで評価します。スコア関数は複数の要素の重み付け和です。
score = -(rateDiff × W1 + roleCost × W2 + maxLaneDiff × W3 + laneStdDev × W4 + varianceDiff × W5)
各項目の意味： - rateDiff: チーム平均レートの差（小さいほど均等） - roleCost: 全員のロール満足度（合計コスト） - maxLaneDiff: レーン対面の最大レート差（一方的レーンの防止） - laneStdDev: レーン対面差の標準偏差（バランスの均一さ） - varianceDiff: チーム内のレート分散の差（パーティーバランス）
重み W1〜W5 はモードによって変えます。例えば「パーティーバランス」モードでは varianceDiff を重く、「レート均等」モードでは rateDiff を重くします。
なぜ複数モードが必要か
「最良の1つを返せばいいんじゃないの？」という疑問があるかもしれません。実は、人間の好みが分かれます。
例： - ある人は「とにかく平均レートを揃えたい」 - 別の人は「ダイヤ1人＋シルバー4人みたいな極端なチームは嫌」 - もう一人は「同じ組み合わせばかりだとつまらない、たまにランダム要素を」
3つのモードで3つの候補を出し、参加者が選ぶ形にすると、合意形成がスムーズです。
ランダム要素の入れ方
完全決定論的なアルゴリズムだと、毎回同じメンバーで同じチーム分けになって飽きます。「ランダム」モードでは、コスト計算に小さな乱数を加えます。
cost = baseCost × (1 + randomness × random())
このランダム度を 0.4 くらいにすると、最適解付近でランダム性が入り、毎回少し違う結果になります。完全ランダムだと滅茶苦茶になるので、上限を設定するのが大事。
計算量と最適化
126通り × ハンガリアン法 (O(125)) ≒ 15,000 回程度の計算です。これは現代の CPU なら数ミリ秒で終わります。
ただし、Web アプリでサーバー側で動かす場合、毎リクエスト 15,000 回計算するとデータベースクエリと合わせて100ms 超えることがあります。十分なキャッシュ戦略と並列化が必要です。
まとめ
「10人を2チームに分ける」だけの問題が、実は3層の最適化問題（チーム分割 → ロール割り当て → スコアリング）になっていることが分かります。
LoL Team Balancer はこの3層をすべて実装しています。126通り全探索 + ハンガリアン法 + 複数モードでのスコアリング、その上で結果を3候補提示します。