サークルテニス ダブルス組み合わせ最適化

はじめに

サークルテニスでは、各プレイヤーが各ラウンドごとに写真１のような対戦表の組み合わせに従いコートに入り対戦する。だが、組み合わせが不完全だと、同じ相手と多く対戦したり、対戦しない相手が多かったりして不満が出る。
2コート（8人）の場合でも、その順列（全プレイヤーの並び順の単純計算）は 8! = 40,320 通りにも及び、7ラウンドでの全対戦パターン数は約1.7×10³²通りに達する。そのため、PCを用いて全てのパターンを単純にチェックするのは計算時間的に不可能だ。
筆者は、組み合わせに制約を加えてパターンを正規化し、ラウンドごとに貪欲法に基づいた逐次構築法を用いることで、探索すべきパターン数を大幅に削減し、2コートの場合であれば、一般的なパフォーマンスのPCでも最適な組み合わせを生成することに成功した。
本稿では、そのアルゴリズムの詳細を述べる。

写真１：

ダブルス組み合わせ対戦表

筆者が参加しているテニスサークルでは、毎回十数人が参加し、2～4面のコートを使用し、2時間で7～8ラウンドのダブルス試合を行う。各プレイヤーは、参加当日の到着順に1からNまでの番号を割り当てられる。そして、コート数および参加人数ごとに、各プレイヤー番号に基づいた組み合わせ表（写真１）があらかじめ用意されており、プレイヤーはその組み合わせに従い対戦する。

たとえば、2面8人の場合、対戦表の最初のラウンドは (1,2 : 3,4) (5,6 : 7,8)、次のラウンドは (1,3 : 5,7) (2,4 : 6,8) といった具合である。

筆者のテニスサークルでは、試合時間のばらつきを抑えるため、1ラウンドは4ゲームのみとし、平均15分程度で終了する。そのため、2時間で8ラウンド程度の試合を行うことが可能だ。

従来、この組み合わせは人手で作成されていた。しかし、組み合わせに偏りがあり、同じ相手と多く対戦したり、逆に対戦しない相手が多かったりして、不満が出ることもあった。人手で偏りのない完全な組み合わせ表を作成することは非常に困難である。

ちなみに、最初のラウンドは、例えば2面8人の場合 (1,2 : 3,4) (5,6 : 7,8) のように固定する。これは、プレイヤー番号の単純な入れ替え（例：ペア内の(1,2)と(2,1)、コート間の(1,2:3,4)(5,6:7,8)と(5,6:7,8)(1,2:3,4)など）では本質的に同じ対戦の組み合わせであり、計算対象を効率化するための正規化の一種と見なせるからである。

組み合わせ評価目的関数

組み合わせ最適化問題では、組み合わせの良し悪しを判定するために目的関数が利用される。目的関数は、組み合わせが最適に近いほど小さい値をとる場合と、大きい値をとる場合の二種類があるが、本稿では最適に近いほど小さい値をとるものとする。

本稿では、このペア回数のばらつきを評価するため pair_counts[][] の値の標準偏差を計算し、これをペア回数の評価値 ev_pair_counts とする。標準偏差を用いる理由は、各プレイヤー間のペア回数が均等であるほど値が小さくなり、理想的な状態（全てのペア回数が等しい）では0となるためである。逆に、特定のペアが極端に多い、あるいは全く組んでいないペアが存在するなど、回数にばらつきが大きいほど標準偏差の値は大きくなる。これにより、ペア回数の公平性を数値的に捉え、より均等な組み合わせを探索するための指標として機能するからだ。

例えば、2面8人の場合、各プレイヤーは1ラウンドで一人の相手とペアになる。したがって、7ラウンド行えば、理論上は全員と1回ずつペアを組むことが可能である。この理想的な状態では、全ての pair_counts[p1][p2]（ただし p1 ≠ p2）が 1 となり、標準偏差、すなわち ev_pair_counts は 0 となる。一方、組み合わせに偏りがあり、一度もペアを組まない相手がいたり、同じ相手と複数回ペアを組んだりした場合、pair_counts[p1][p2] の値には 0 や 2 以上のものが現れ、標準偏差（ev_pair_counts）は正の値を取る。

同様に、対戦した相手の回数の公平性も評価する。oppo_counts[p1][p2] は、プレイヤー p1 と p2（ただし p1 ≠ p2）が何回対戦相手として顔を合わせたかを表す。この oppo_counts[][] の値についても、その標準偏差を計算し、これ対戦回数の評価値 ev_oppo_counts とする。これもペア回数と同様に、対戦回数が全プレイヤー間で均等であればあるほど値が小さくなり、0に近づく。

最終的な組み合わせの評価は、これら二つの評価値を組み合わせた目的関数 ev で行う。具体的には、以下の式で計算される。

ev = ev_pair_counts * W1 + ev_oppo_counts * W2

ここで、W1 および W2 は正の定数であり、それぞれの評価値に対する重みを表す。本稿の目的では、ペアを組む相手の偏りをより重視するため、W1 を W2 よりも大きな値に設定する（例: W1 > W2 > 0）。この目的関数 ev が小さいほど、ペアを組む回数と対戦する回数の両方において、より公平でバランスの取れた組み合わせであると判断できる。

組み合わせ正規化

ペア (p1, p2) と (p2, p1) は、プレイヤーの記述順が異なるだけであり、実際には同一のペアを表す。このため、組み合わせを扱う上でこれらの区別は無意味である。本稿では、ペア内のプレイヤー番号は常に昇順、すなわち p1 < p2 となるように制約を加え、表現を正規化する。

これに加え、さらに組み合わせの表現を一意にするための正規化を行う。
まず、1つのコートで行われる対戦 (ペアA : ペアB) を考える。例えば、プレイヤー p1, p2 のペアとプレイヤー p3, p4 のペアが対戦する場合、(p1, p2 : p3, p4) と表記しても (p3, p4 : p1, p2) と表記しても、行われる試合内容は同一である。この表記の冗長性を排除するため、本稿では、対戦する二つのペアを、それぞれのペアを構成する最小のプレイヤー番号が昇順になるように並べることとする。具体的には、ペアA = (p1, p2)、ペアB = (p3, p4) とし、p1 < p2 かつ p3 < p4 であるとき、min(p1, p2) < min(p3, p4) となるように (ペアA : ペアB) の順で記述する。もし min(p1, p2) = min(p3, p4) となるケース（これは実際にはあり得ないが、概念として）があれば、次の要素で比較するなどのルールを適用するが、通常はペアの最小プレイヤー番号で一意に定まる。

さらに、複数コートで同時に試合を行う場合、どのコートでどの対戦が行われるかという記述順序も、ラウンド全体の組み合わせの本質を変えるものではない。例えば、コート1で試合X、コート2で試合Yが行われるのと、コート1で試合Y、コート2で試合Xが行われるのは、プレイヤーから見れば同じラウンド構成である。そこで、各コートで行われる対戦を、その対戦に参加する全プレイヤーのうち最小のプレイヤー番号（すなわち、そのコートの試合を構成する4人のプレイヤー番号のうち最小のもの）で比較し、昇順にソートされた状態で表現することとする。

これらの正規化ルールを適用することにより、本質的に同じ組み合わせを異なる表現で重複して生成・評価することを避け、探索すべき組み合わせパターンの数を大幅に削減し、計算効率を向上させることが可能となる。

例えば、2面8人のプレイヤーで1ラウンドのダブルス組み合わせを考える場合を例に挙げる。
もし正規化を行わず、単純に8人のプレイヤーをコートに割り当てる順列だけを考慮しても、その数は 8! = 40,320 通りにもなる。しかし、これはペア内の順序、対戦ペアの順序、コート間の順序を区別しているため、本質的に同じ対戦内容を含む多数の重複した組み合わせをカウントしていることになる。
これに対し、前述したペア内のプレイヤー番号の昇順化、対戦ペア間の最小プレイヤー番号による昇順化、そしてコート間の最小プレイヤー番号による昇順化といった正規化ルールを全て適用することで、2面8人の場合の1ラウンドにおける本質的に異なる組み合わせの数は、わずか 315 通りにまで大幅に減少させることができる。
このように、正規化は探索すべき組み合わせの対象空間を劇的に縮小させ、計算による最適解の探索を現実的なものにする上で極めて重要な役割を果たす。

貪欲法に基づいた逐次構築法

前述の正規化ルールを適用することで、例えば2面8人の場合、1ラウンドにおける本質的に異なる組み合わせの数は、8! = 40,320通りからわずか315通りにまで大幅に削減される。これは探索空間の劇的な縮小であり、計算効率向上に大きく貢献する。
しかしながら、この削減効果をもってしても、複数ラウンドにわたる全ての組み合わせパターンを網羅的に探索することは依然として困難である。仮に7ラウンドの組み合わせを考えるとすると、単純計算でも 315⁷（およそ 3 × 10¹⁷）通りという天文学的な数の組み合わせが存在することになる。これほどの規模になると、たとえ1ラウンドあたりの組み合わせ数が削減されたとしても、PCを用いて全パターンを評価し尽くすことは計算時間的に到底不可能である。
したがって、全ラウンドの最適な組み合わせを一度に見つけ出す全探索アプローチではなく、より現実的な計算時間で質の高い組み合わせを見つけ出すための、別の効率的な探索戦略が必要となる。

そこで本稿では、この問題に対処するため「貪欲法に基づいた逐次構築法」を採用する。このアプローチの具体的な手順は以下の通りである。

1. 第1ラウンドの固定:
   まず、最初のラウンド（第1ラウンド）の組み合わせは、正規化ルールに基づき、例えば2面8人の場合は (1,2 : 3,4) (5,6 : 7,8) のように一意に定まるものとして固定する。これは探索対象ではなく、初期状態と見なす。
2. 逐次的なラウンド最適化:
   次に、第2ラウンドの組み合わせを決定する。ここでは、第1ラウンドの結果を固定した上で、第2ラウンドとして考えられる正規化された315通りの組み合わせを全て試す。それぞれの組み合わせを第1ラウンドの結果に追加した際の目的関数（例えば、ペア回数や対戦回数の標準偏差の加重和）を計算し、その値が最も小さくなる（最も良い評価となる）組み合わせを第2ラウンドの組み合わせとして採用する。
3. 以降のラウンドへの適用:
   第3ラウンド以降も同様の手順を繰り返す。すなわち、直前までのラウンドで決定された組み合わせを固定した上で、現在のラウンドで可能な315通りの組み合わせを全て試し、累積の目的関数が最も小さくなるものをそのラウンドの組み合わせとして選択する。このプロセスを目標とする最終ラウンド（例えば7ラウンド）まで行う。

この貪欲法に基づいた逐次構築法を用いることで、探索が必要となる組み合わせの総数は大幅に削減される。第1ラウンドは固定されるため、実際に探索と比較を行うのは第2ラウンドから第7ラウンドまでの6ラウンド分である。各ラウンドで評価する組み合わせは正規化された315通りなので、総評価回数は 315通り × 6ラウンド = 1,890回 となる。
これは、全探索の場合の 315⁷（約3 × 10¹⁷）通りと比較して劇的に少ない計算量であり、一般的なPCでも現実的な時間内に質の高い組み合わせ表を生成することを可能にする。ただし、この方法は各ステップで局所的な最適解を選択するため、必ずしも全体最適解が得られるとは限らない点に留意が必要であるが、多くの場合で実用上十分に良好な解を得ることが期待できる。

実装結果

本稿で説明した対戦パターンの正規化、貪欲法に基づいた逐次構築法を用いたアルゴリズムを Godot 4 GDScript で実装した結果、下記に示す2面8人・7ラウンドのダブルス組み合わせ表を、一般的なパフォーマンスのPCにおいて1秒未満という短時間で生成することに成功した。

	コート#1	コート#2
R1	1,2 : 3,4	5,6 : 7,8
R2	1,3 : 5,7	2,4 : 6,8
R3	1,5 : 2,6	3,7 : 4,8
R4	2,3 : 6,7	1,4 : 5,8
R5	2,5 : 4,7	1,6 : 3,8
R6	1,8 : 2,7	3,6 : 4,5
R7	2,8 : 3,5	1,7 : 4,6

この生成された組み合わせ表は、以下の特徴を持つ、極めて質の高いものである。

• ペア回数の完全な均等化: 全てのプレイヤーが、他の7人のプレイヤーそれぞれと必ず1回ずつペアを組んでいる。これにより、ペア回数の標準偏差（ev_pair_counts）は0となる。

• 対戦回数の高い均等性: 全てのプレイヤーが、特定の相手と2回ずつ対戦する形となっている。これにより、対戦回数の標準偏差（ev_oppo_counts）も0となる。

したがって、本アルゴリズムによって生成されたこの組み合わせは、ペア回数と対戦回数の両方において全く偏りがなく、目的関数の値が0となる理想的な解の一つであると言える。

評価

本稿で提案したアルゴリズムを用いて、具体的な条件下での組み合わせ表生成とその評価を行った。

まず、コート数が2面、プレイヤー8人、7ラウンドのケースについて検証した。その結果、提案アルゴリズムは、ペア回数および対戦回数の偏りが全くない（目的関数値が0となる）、いわゆる完全な組み合わせ表を、一般的なパフォーマンスのPCにおいて1秒未満という極めて短時間で生成することに成功した。これは、従来の手法では達成が困難であった質の高い組み合わせを効率的に得られることを示しており、本アルゴリズムの有効性を強く裏付けるものである。

次に、コート数が3面以上の場合についても予備的な評価を行った。コート数が増加すると、1ラウンドあたりに考慮すべき正規化された組み合わせの数は、2面の場合と比較して大幅に増加する。例えば、（もし具体的な数字があればここで言及。なければ概念的な説明に留める）といった状況になる。このため、本稿で採用した貪欲法に基づいた逐次構築法では、各ラウンドで評価するパターン数が膨大となり、組み合わせ表の生成に要する計算時間が実用的とは言えないレベルまで増加する傾向が見られた。具体的には、（もし具体的な処理時間や問題の規模があれば記述。例：「3面12人の7ラウンドで数時間以上」など）といった結果となった。

このことから、提案アルゴリズムは2面コートの条件下では非常に高いパフォーマンスを発揮するものの、コート数が増加した場合には計算コストの観点から課題が残ることが明らかになった。

おわりに

本稿では、サークルテニスにおけるダブルス組み合わせの偏りを解消し、より公平な対戦機会を提供することを目的として、組み合わせの正規化と貪欲法に基づいた逐次構築法を組み合わせたアルゴリズムを開発し、その有効性について検討した。
提案アルゴリズムは、特に一般的なサークル活動で頻度の高い2面コートでの運用において、極めて質の高い（目的関数値0の）組み合わせ表を、実用的な計算時間内に生成できることを実証した。これは、参加者の満足度向上に直接的に貢献しうる成果であると言える。
一方で、コート数が3面、4面と増加する多コート環境においては、1ラウンドあたりの組み合わせ数が爆発的に増加するため、本稿で採用した逐次構築法では計算時間が過大となるという課題が明らかになった。 これは、アルゴリズムの適用範囲における現状の限界点を示している。
今後の展望としては、この多コート環境における計算量の問題を克服するためのアルゴリズム改良が主要な課題となる。具体的には、以下のようなアプローチが考えられる。

• より洗練された枝刈り戦略の導入: 逐次構築の過程で、明らかに最適解に繋がらないと判断できる探索経路を早期に除外するロジックの強化。
• メタヒューリスティクスの活用: 焼きなまし法、遺伝的アルゴリズム、タブーサーチといった発見的手法を導入し、厳密解ではなく質の高い近似解を効率的に探索する。
• 問題分割や並列処理: 大規模な問題をより小さなサブ問題に分割して処理したり、計算処理を複数のプロセッサで並列実行したりすることで、全体の計算時間を短縮する。

これらの改良を通じて、より多様な運用条件に対応可能な、汎用性の高い組み合わせ生成システムの実現を目指したい。本研究が、多くのテニス愛好家にとってより快適で公平なプレー環境の構築に少しでも貢献できれば幸いである。