練習会の対戦組合せにおける公平性と計算量の壁
テニス練習会の対戦組合せ生成では「公平性」と「計算可能性」の両立が本質的な課題になる。参加者数やラウンド数が増えると組合せ空間が爆発し、全探索（厳密解）では現実的な時間内に解を得られなくなる。
さらに厄介なのは運用上の制約の多さ。同じペアの再登場を防ぐ、連続休憩を避ける、グループ属性を考慮する、出場回数の偏りを抑える――これらを同時に満たす組合せを見つける必要がある。8人なら1ラウンドの組合せはC(8,4)=70通りだが、ラウンド数Rが増えると状態空間は指数的に膨れ上がる。
この記事では、全探索とモンテカルロ100回試行を比較し、ペナルティスコア7種の重み設計とその検証を示す。
候補方式の比較
対戦組合せ生成のアプローチとして、以下の2方式を検討した。
| 属性 | 全探索（厳密解） | モンテカルロ（100回試行） | |------|------------------|--------------------------| | 最良解保証 | あり | なし（確率的） | | 計算量 | 指数的 | 線形に近い（試行回数に比例） | | 実装複雑度 | 高い | 低い | | 応答性 | 低（大規模で破綻） | 高（試行回数で制御） | | エッジケース耐性 | 高い | 中（生成戦略次第） |
全探索方式（不採用）
全ての組合せを列挙し、ペナルティスコアが最小のものを選ぶ方式。理論上の最良解を保証できるが、参加人数NとラウンドRに対して計算量がO(C(N,k)^R)に近づく。8人で4ラウンドなら70^4 ≒ 2400万通り。12人になるとC(12,4) = 495通りで、6ラウンドなら495^6 ≒ 1.5×10^16。ブラウザ上のリアルタイム応答はまず不可能になる。
モンテカルロ法100回試行方式（採用）
ランダムに組合せを生成し、ペナルティスコアで評価する試行を100回繰り返す方式。最良解の保証はないが、計算コストを100回の生成＋評価に固定できるため応答性が安定する。ランダム生成にはグループインターリーブ（AグループとBグループを交互に配置）を加え、初期解の質を底上げしている。
なぜモンテカルロ100回を選んだか
全探索は12人6ラウンドで状態空間が10^16オーダーに達し、ブラウザ上の即時応答は不可能。一方モンテカルロは試行回数を固定することで応答時間を制御でき、100回の試行で実用上十分な品質の解が得られることを実測で確認した。期待値の収束特性から、100回あれば「極端に悪い解を引く確率」は十分に低くなる。
実装の詳細
計算の流れ
- 入力を受け取る: 参加者リスト、固定ペア、グループ属性、コート数、ラウンド数
- 参加者をシャッフルする（グループ属性を考慮したインターリーブ配置）
- 1ラウンド分の割当を生成する（シングルス/ダブルス判定を含む）
- 全ラウンドのペナルティスコアを算出する
- ステップ2〜4を100回繰り返し、最小スコアの割当を保存する
- 最小スコアの割当を出力する
ペナルティスコア7種の重みと計算例
7種の違反にそれぞれ重みを設定し、合計スコアで組合せの品質を評価する。スコアが小さいほど良い組合せ。
ペナルティスコアの重み設計:
同じペア再登場: +10（参加者の満足度に直結）
同じ対戦再登場: +8（ペア同士の再戦も避けたい）
連続休憩: +5（不公平感を生む）
連続休憩重大違反: +20（3回以上の連続は重大）
出場回数偏差: +3×偏差（累積効果を偏差に比例させる）
グループ違反: +15（ルール破壊に相当）
Bグループシングルス: +12（初心者のシングルスは避ける）
計算例（8人・1ラウンド分）:
参加者: A1, A2, A3, A4, B1, B2, B3, B4
過去履歴: A1-A2が前回ペア、A3は連続休憩中
生成した割当での違反検出:
同じペア再登場: A1-A2 が再登場 → +10
同じ対戦: なし → +0
連続休憩: A3 が連続休憩 → +5
出場回数偏差: 平均1.0回に対しA4が2回 → 偏差1 → +3
グループ違反: Bメンバーの配置ルール違反 → +15
Bグループシングルス: B1がシングルス割当 → +12
合計ペナルティ = 10 + 0 + 5 + 3 + 15 + 12 = 45
設計判断のポイント
重みの配分は運用上の優先度に基づく。ペアの再登場は参加者の満足度に直結するため+10と高めに設定し、グループ違反はルールの根幹を壊すため+15とした。連続休憩は中程度の不公平として+5だが、3回以上連続する重大違反には+20で強いペナルティを課す。出場回数偏差は偏りが大きいほど不公平になるため、偏差に比例する+3×偏差とした。
生成時のグループインターリーブは、AグループとBグループのメンバーをキュー化して交互にコートへ配置する方式。Bグループが特定コートに偏在する確率を下げ、初期解の品質を底上げしている。スコアは整数で扱い、比較は単純な大小比較。浮動小数点の丸め誤差を排除し、実装の透明性を保っている。
設定保持やラウンド履歴の一時保存にはlocalStorageを利用し、ブラウザ内完結を維持している。
検証結果
ケース1: 8人・4ラウンドの標準運用
練習会で最も多い構成。8人、4ラウンド、コート2面の想定。
入力値:
- 参加者: 8人（Aグループ4人、Bグループ4人）
- ラウンド: 4
- コート: 2面
- 制約: 固定ペアなし、過去履歴に同ペア1件、連続休憩2名
計算結果:
- 全探索（理論上の最良）: 最小ペナルティ推定 28
- モンテカルロ（100回）: 最小ペナルティ 30（中央値 42、最悪 68）
→ 解釈: モンテカルロ100回の最良解は全探索に対して約7%の差。実運用では体感できない差であり、応答性を優先する場面では100回試行で十分実用的。
ケース2: 12人・6ラウンド・固定ペア2組
大規模な練習会。参加者12人、6ラウンド、固定ペア指定が2組。組合せ空間が桁違いに大きくなるケース。
入力値:
- 参加者: 12人
- ラウンド: 6
- コート: 3面
- 制約: 固定ペア2組
計算結果:
- 全探索: 計算量爆発で未完了（C(12,4)^6 ≒ 1.5×10^16）
- モンテカルロ（100回）: 最小ペナルティ 58、平均 74、最悪 120
→ 解釈: 全探索が物理的に不可能な規模でも、モンテカルロは安定して結果を返す。固定ペアなどの制約が増えると良解が見つかりにくくなるため、生成時に固定ペアを優先配置するヒューリスティックが品質向上に寄与する。
エッジケース: 奇数人数と最小構成
奇数人数（9人）では必ず1人が休憩に回るため、連続休憩のペナルティが品質を左右する。連続休憩の重み+5と重大違反+20の2段階設定が、休憩の均等化と他の制約とのバランスを調整している。4人2面シングルスでは全員が同時にプレイ可能なため、出場回数偏差は0に近づき、モンテカルロでも安定して最小スコアが得られる。
よくある質問（FAQ）
Q: 固定ペアを指定するにはどうすればよいか
参加者入力時にペアIDを付与することで指定できる。システムはペアIDを持つメンバーを優先的に同一ペアとして割当て、残りの参加者をランダムに配置する。
Q: 100回で十分な品質が得られるのか
8人4ラウンドの実測では、100回試行の最良解は全探索の最良解に対して7%程度の差に収まる。試行回数を200回に増やしても改善幅は小さく、100回がコストと品質のバランスで妥当な設定と判断した。
Q: データはサーバーに送信される？
すべてブラウザ内で処理される。参加者名やラウンド履歴がサーバーに送信されることはない。localStorageに一時保存されるが、ブラウザを閉じれば消える。
Q: 制約が多すぎて良い組合せが見つからない場合はどうなるか
100回試行しても全ての違反をゼロにできない場合は、最もペナルティが低い「妥協解」が出力される。固定ペアが多すぎる場合は事前に制約充足性をチェックし、ユーザーに調整を促すUIを表示する設計としている。
まとめ
ペナルティスコア7種の重みと100回のモンテカルロ試行は、対戦組合せの公平性と応答性を両立する合理的な方式。全探索は12人以上で計算量が爆発するため、ブラウザ上のリアルタイム生成にはモンテカルロが妥当な選択となる。
対戦表を試したいときはテニス組み合わせ職人を使ってみて。ランダム性の制御という共通テーマでは、公平な配置係もFisher-Yatesシャッフルで順番決めやチーム分けを扱っている。
不具合や要望があれば、お問い合わせページから気軽に教えてほしい。