HOW IT WORKS

試合表は、どうやって
作られているのか

バドミントンの練習会で「次は誰と誰が、どのコートか」を決める。人がやると地味に面倒なこの作業を、ShuttleMatch は一瞬で終わらせます。その中身を、予備知識ゼロから順に見ていきましょう。数式は出てきますが、意味はぜんぶ日本語で言い直します。

1何を決める仕事なのか

体育館にコートが2面、集まったのが13人。ダブルスなので1コートに4人入ります。つまり1回に8人が試合をして、5人が休みます。これを10回くり返す—— そういう練習会を思い浮かべてください。

このとき決めることは、たった2つです。

誰が出て、誰が休むか
出る人を、どのコートに振り分けるか

これを10回ぶん決めれば試合表の完成です。ここまでなら、じゃんけんでもくじ引きでもできます。面倒なのは、現場に守りたい暗黙のルールがあるからです。

現場が求めていること

出る回数を平等に — 5回出た人と2回しか出ていない人がいたら不満が出ます。
2回続けて休ませない — 逆に出ずっぱりも疲れます。
いろんな人と当たる — 「またこの4人か…」が続くと飽きます。
「この2人は組ませて」に対応 — 親子やペア練習など。
遅刻・早退に対応 — 途中で人が増減しても、それまでの回数は引き継ぎたい。

このうち、いちばんやっかいなのが3つ目の「いろんな人と当たる」です。出場回数を揃えるだけなら順番に回せば済みますが、「誰と誰が一緒になったか」は組み合わせの問題で、しかも過去の全部の回に影響されます。第7セットで誰を同じコートに入れるべきかは、第1〜6セットで誰と誰が会ったかを全部覚えていないと判断できません。

この先で使う言葉 — 「同じコートに入った」

2人が同じコートの試合に入ることを、このページでは「出会った」と表現します。味方だったか敵だったかは区別しません。実際の練習会では、コートに入ってからじゃんけんでペアを決め直すことも多く、体験として残るのは「あの人と同じコートだったな」という記憶だからです。この割り切りが、後で計算をぐっと楽にしてくれます。

2全部ためせばいいのでは？

いちばん素直な作戦は「考えられる試合表を全部作って、いちばん良いものを選ぶ」です。コンピュータは速いので、それでいける気がします。数えてみましょう。

13人・2コートで、1回ぶんを決める方法は何通りあるか。

13人から出場する8人を選ぶ … 1,287通り
その8人を4人ずつ2つのコートに分ける … 35通り

かけ算して、1回ぶんで 45,045通り。ここまでなら余裕です。問題は、これを10回くり返すところ。 1回目に45,045通り、その一つ一つに対して2回目が45,045通り……と枝分かれしていきます。

セット数	組み合わせの数	どれくらいか
1回	45,045	すぐ終わる
2回	約20億	数秒
3回	約9京	数年
10回	3のうしろに0が46個	宇宙が終わっても終わらない

最後の数字がどれくらいかというと、宇宙にある星の数（10のうしろに0が24個くらい） を全部数え上げても、まだ足りません。1秒に10億通り調べられる計算機を使っても、宇宙の年齢の何兆倍もかかります。

ここが分かれ道

「1つ増えるごとに選択肢が掛け算で増える」——これを組み合わせ爆発といいます。こうなると「全部ためして最良を選ぶ」は原理的に不可能です。そこで方針を変えます。最良である保証は捨てて、十分に良いものを、一瞬で見つける。この割り切りをした方法を ヒューリスティック（発見的手法）と呼びます。ここから先は、ぜんぶそのための工夫の話です。

31セットずつ、順番に決める

10回ぶんを一気に考えるから爆発するのです。ならば、 1回目を決める → 記録する → 2回目を決める、と順番に進めればどうでしょう。

こうすると、各回で考えるのは45,045通りだけ。10回ぶんでも45万通り程度で、一瞬で終わります。そして「今までに誰が何回出たか」「誰と誰が出会ったか」を記録しながら進むので、1回1回の判断は、それまでの歴史を踏まえたものになります。

これを何と呼ぶか — 貪欲法（どんよくほう）

「先のことは考えず、いまこの瞬間にいちばん良さそうな選択をする」やり方を 貪欲法（greedy algorithm）といいます。目の前のごちそうに飛びつく、という意味の名前です。速いのが長所、目先で最善でも全体では最善とは限らないのが短所。この短所は9章で手当てします。

ShuttleMatch が1回ぶんを決める手順は、こうなっています。

これを1セットずつくり返す

1 誰が出るかを選ぶ
出場回数が少ない人から順に。同じなら、連続で出ていない人を優先。

↓ 顔ぶれの候補を何通りか作って、いちばん新鮮な組を選ぶ

2 コートに振り分ける
2人ずつ入れ替えてみて、「出会いすぎ」が減るなら採用。減らなくなるまで続ける。

↓ 決まった結果を記録して、次のセットへ

↓ 10セットぶん終わったら…

3 ここまでを丸ごと4回やり直す
試合表を4通り作って、いちばん混ざっている1つだけを採用する。

ここから、各ステップを順に見ていきます。

4誰が出るか — 並べて上から取るだけ

「出場回数を平等に」は、実はとても簡単に実現できます。毎回、全員を出場回数の少ない順に並べて、上から8人取る。それだけです。

6人・1コート（毎回4人が出て2人休み）で追ってみましょう。

セット	並び（出場回数の少ない順）	出る人	終了後の回数
1	A0 B0 C0 D0 E0 F0	A B C D	A1 B1 C1 D1 E0 F0
2	E0 F0 A1 B1 C1 D1	E F A B	A2 B2 C1 D1 E1 F1
3	C1 D1 E1 F1 A2 B2	C D E F	A2 B2 C2 D2 E2 F2

なぜこれで「差は最大1」が保証されるのか

少ない人から順に取るので、回数が多い人が出るのは、少ない人を全員出したあとだけです。つまり誰かが2回目に出るのは、全員が1回出たあと。3回目に出るのは全員2回出たあと。だから、どの時点で止めてもいちばん多い人といちばん少ない人の差は1回以内に収まります。複雑な計算はいりません。並べ替えという単純な操作が、条件を自動的に守ってくれます。

さらに「2回続けて休ませない」も、同じ並べ替えで面倒を見ます。 出場回数が同じ人が並んだとき、連続で休んでいる人を先に出すようにするのです。順位を決めるものさしを、上から順に：

出場回数が少ない人（これが最優先）
同じなら、連続で休んでいる人
それも同じなら、ランダム

上のものさしで差がついたら、下のものさしは見ません。辞書で単語を引くとき、1文字目が違えば2文字目を見ないのと同じ考え方です（これを辞書式の比較といいます）。

3番目の「ランダム」が効いている

出場回数も連続休みも同じ人が5人並んだとき、どう選んでもルール上は正しい。ここをあえてランダムにすることで、「ルールは完全に守ったまま、顔ぶれだけが違う候補」を何通りも作れます。この自由度を、次の「混ざり」の改善に使います（7章）。

5「混ざっている」を点数にする

ここからが本題です。「よく混ざった試合表」を機械に選ばせたい。でも機械は「混ざってる感じ」が分かりません。 比べられる数字にしてやる必要があります。

そこで、こう決めます。悪いほど点数が高い。そして点数がいちばん低いものを選ぶ。ゴルフのスコアと同じで、少ないほうが良いという約束です。

これを何と呼ぶか — コスト関数

解の良し悪しを1つの数字にする仕組みをコスト関数といいます（「目的関数」とも）。ここで何を高い点数にするかが、そのまま そのアルゴリズムの価値観になります。設計でいちばん頭を使うところです。

材料はシンプルです。全員の組み合わせについて、これまで何回出会ったかを数えた表を持ちます。 1試合はコートに4人なので、試合が1つ決まるたびに、その4人から2人を選ぶ6通りの組の回数を1ずつ増やします。

	A	B	C	D
A	—	2	0	1
B	2	—	1	0
C	0	1	—	3
D	1	0	3	—

こういう表を持ち歩きます。AとBは2回、CとDは3回すでに出会っている。AとCはまだ一度も会っていない。

6点数の付け方が、いちばん大事

さて、「すでに2回会っている人同士」をまた同じコートに入れるとき、何点の罰にすればいいでしょうか。

素直に考えれば「会った回数ぶんの点数」——2回会っていれば2点、です。ところがこれには落とし穴があります。次の2つを比べてください。

	状況	「回数ぶん」の点数
あ	AB が2回、CD が2回出会っている	2 + 2 = 4
い	AB だけが4回出会っている	4

同点になってしまいました。 でも現場の感覚では、「い」のほうが明らかに悪い。 AとBは4回も顔を合わせているのに、他の人とは会えていないからです。 点数の付け方が、人間の感覚とずれているのです。

そこで ShuttleMatch は、会うたびに罰を4倍ずつ跳ね上げます。

これまでに会った回数	0回	1回	2回	3回	4回
もう一度会わせる罰	−2	3	15	63	255

この表には2つの仕掛けがあります。

初対面はマイナス点（＝ごほうび） — まだ会っていない2人を同じコートに入れると、点数が下がります。「知らない人同士を会わせる」ことを積極的に狙いに行きます。
再会するほど、罰が急激に重くなる — 5回目の再会は255点。 1回目の3点とは比べものになりません。

さっきの「あ」と「い」を、この点数で比べ直してみます。

	状況	新しい点数	判定
あ	AB が2回、CD が2回	15 + 15 = 30	こちらが良い
い	AB だけが4回	255	8倍以上ひどい

これが効く理由

罰が急カーブで増えるので、「同じ合計なら、散らばっているほうが安い」という性質が生まれます。すると、点数を下げようとするだけで、自然と特定の人だけが何度も当たる状態を避けるようになります。「いちばん会いすぎている組を減らす」と直接指示しなくても、点数の付け方だけで実現できる。これは最適化の世界で定番のテクニックです。

あとは、各コートの4人が作る6つの組ぜんぶの点数を足すだけ。これで「この振り分けと、あの振り分け、どっちが混ざるか」を、数字ひとつで比べられるようになりました。

7出る人を選ぶ時点で、先を見ておく

4章で「同じ条件の人が並んだらランダムに選ぶ」と書きました。ということは、実行するたびに違う顔ぶれが出てくるということです。 ShuttleMatch はこれを利用します。

出場者の選抜を何度もやり直して、「出場回数のルールはまったく同じだけど、顔ぶれが違う候補」を16通りほど集め、その中から いちばん出会いが新鮮な組を採用します。公平さのルールは1ミリも緩めずに、ランダムの揺らぎだけを混ざり改善に使うわけです。

評価のとき、コート割りをまだ考えない理由

候補を評価するとき、「実際にコートに振り分けたあとの点数」で比べたほうが正確そうに思えます。でもこれには罠があります。

すでに何度も会っているAとBが両方選ばれていても、 「今回は別のコートに分ければ点数は増えない」ので、その候補が高く評価されてしまうのです。けれど、AとBを一緒に選び続けていれば、いつかは同じコートに入れざるを得なくなります。問題を先送りしただけです。

なので評価は「選ばれた8人の全組み合わせ」で行います。コート割りは見ません。選ぶ段階で、まだ会っていない人同士を集めておくほうが、長い目で見て混ざる。目先の配置より、選択肢の豊かさを優先する判断です。

82人を入れ替えて、少しずつ良くする

出る8人が決まりました。次は誰をどのコートに入れるかです。 2コート8人でも35通り、3コート12人なら5,775通りあります。全部ためすこともできますが、コートが増えると同じ爆発が起きます。

そこで、こうします。

まず適当に振り分ける。
違うコートの2人を入れ替えてみる。点数が下がれば、その交換を採用。
どの2人を入れ替えても下がらなくなったら、そこで終了。

これを何と呼ぶか — 山登り法

いまの状態から少しだけ変えてみて、良くなるときだけ受け入れる。これを山登り法（hill climbing）といいます。目隠しをして山を登るとき、足元を探って一歩ずつ高いほうへ進むイメージです（今回は点数を下げたいので、正確には「谷下り」ですが、呼び名は山登りのままです）。

ただし、この方法には有名な弱点があります。

左右どちらへ動いても点数が上がってしまうので、ここで止まる。でも本当はもっと低い谷が右にある。

局所最適という落とし穴

「まわりを見渡すと、これ以上良くならない」場所にはまって動けなくなることがあります。これを局所最適といいます。本当の最良（全体最適）は別の場所にあるのに、そこへ行くには一度悪くなる方向へ進まなければならず、山登り法は悪くなる方向を受け入れないので、たどり着けません。

9一発勝負をやめる

局所最適の対処法は、驚くほど単純です。スタート地点を変えて、何回もやる。 そしていちばん良かった結果だけを採用する。

最初の振り分けはランダムなので、やるたびに違う場所からスタートします。別の場所から始めれば、たどり着く谷も変わる。何回か試せば、そのうちどれかが深い谷にたどり着きます。

これを何と呼ぶか — マルチリスタート

開始点を変えて探索を何度もやり直し、最良の結果を採用する方法を マルチリスタートといいます。頭の良さではなく、 回数で殴るやり方ですが、非常によく効きます。

ShuttleMatch はこれを2段階で使っています。

コート割りのなかで — 1回ぶんの振り分けを、違う初期配置から数回試す。
試合表まるごと — 10セット全体の生成を最初から4回やり直し、いちばん混ざっている1つを採用する。

後者が、3章で触れた貪欲法の弱点（序盤の引きに全体が引きずられる）への答えです。序盤でたまたま悪い引きをしても、丸ごと作り直した別の試合表が救ってくれます。

10現場のわがままに応える

ここまでが骨格です。ただ、実際の練習会にはもう少し細かい事情があります。

人数が多いと「2グループ」に分かれてしまう

16人・2コートのように、休む人が出る人と同じくらい多いとき、素直に「回数の少ない順」で回すと、8人ずつの2グループが交互に出入りするだけになります。グループをまたいだ対戦が永遠に生まれません。

そこで、出場回数が同じ人が並んだときのランダムの出番を増やして、グループの境目を意図的に崩します。公平さのルールは守ったまま、メンバーの入れ替わりだけを起こす仕組みです。

休む人の顔ぶれも、毎回変える

出る人だけでなく、「休む人の組み合わせ」も同じ顔ぶれが続かないように見ています。毎回同じ3人がベンチで一緒、というのも避けたいからです。

「この2人は必ず組ませて」

固定ペアの指定があるときは、その2人を1つのかたまりとして扱います。選ぶときも振り分けるときも、常にセットで動かす。こうすると、他の仕組みを一切変えずに固定ペアを実現できます。

遅刻・早退・「もう1セットだけ」

途中で人が増減したり、セットを追加したりするときは、 これまでの出場回数と出会いの記録を引き継いだまま、まだ始まっていないセットだけを作り直します。終わった試合はそのまま。だから、当日どれだけ状況が変わっても、公平さと混ざりは通算で保たれます。

11さわって確かめる

ここまでの仕組みを、簡略化してこのページ上で動くようにしたものです。同じ「公平な輪番」を使いながら、コート割りを完全にランダムにした場合と、 ここまで説明した点数付けで最適化した場合を並べて比べられます。

見どころはヒートマップです。色が濃いマスは「その2人が何度も同じコートになった」印。最適化ありのほうが色が薄く、均一に散らばることを確かめてみてください。

簡易シミュレーター

参加者 13 人コート 2 面セット 10 回

出会いの表 — 縦と横の番号が交わるマス = その2人が同じコートになった回数

出場回数

試合表 — 数字は参加者番号。「・」がチーム、「vs」がコート内の対戦

これは学習用の簡略版です（固定ペア・休み組の反復回避・セット追加などは省いています）。実物は backend の MatchingDomainService.java にあり、骨組みはこのページで説明したとおりです。

12出てきた言葉のまとめ

このページで出てきた用語を、もう一度短くまとめておきます。これらは試合表づくりに限らず、シフト表・時間割・配送ルートなど「割り振りを決める」問題すべてに共通する道具です。

組み合わせ爆発: 要素が1つ増えるだけで、選択肢が掛け算で膨れ上がること。全部ためす作戦が使えなくなる原因。
ヒューリスティック: 最良である保証は捨てて、実用的な時間で「十分よいもの」を見つける方法。
貪欲法（greedy）: 先を読まず、その時点でいちばん良さそうな選択を積み重ねるやり方。速いが、全体最適の保証はない。
コスト関数: 解の良し悪しを1つの数字にする仕組み。何を高い点数にするかが、そのアルゴリズムの価値観になる。
山登り法: いまの状態を少し変えてみて、良くなるときだけ受け入れる探索。単純で速い。
局所最適: まわりを見渡すと改善できないが、実はもっと良い答えが遠くにある状態。山登り法がはまる落とし穴。
マルチリスタート: 開始点を変えて何度もやり直し、いちばん良かった結果を採用する方法。局所最適への現実的な対処。
辞書式の比較: 複数の基準を優先順位つきで比べる方法。上位の基準で差がついたら、下位は見ない。

もっと知りたくなったら

山登り法の発展形として、あえて悪くなる方向にも進んでみることで落とし穴を抜け出す「焼きなまし法」、最近通った道を通行止めにして前へ進ませる「タブーサーチ」、答えを何通りも作って掛け合わせる「遺伝的アルゴリズム」などがあります。どれも「たくさん試して、点数で選ぶ」というこのページの骨格の延長線上にあるので、ここまで読めた方なら入っていけるはずです。

この試合表の問題そのものは、数学ではソーシャルゴルファー問題という名前で知られています。「ゴルファー32人を毎週4人ずつの組に分け、同じ人と2度同じ組にならないよう何週続けられるか」という問いで、単純に見えて厳密に解くのは非常に難しいことが分かっています。興味があれば調べてみてください。

試合表は、どうやって作られているのか