総当たりトーナメント

ラウンドロビントーナメントまたはオールプレイオールトーナメントは、各出場者が通常順番に他のすべての参加者と対戦する競技形式です。^{[1] [2]}ラウンドロビンは、参加者が一定数の勝ち負けの後に脱落する エリミネーショントーナメントとは対照的です。

ラウンドロビンという用語はフランス語のruban（「リボン」）に由来しています。時が経つにつれて、この用語はロビンという慣用句になりました。^{[3] [4]}

1回のラウンドロビン方式では、各参加者は他の参加者全員と1回ずつ対戦します。各参加者が他の参加者全員と2回対戦する場合、これはしばしばダブルラウンドロビンと呼ばれます。この用語は、参加者全員が互いに2回以上対戦する場合はほとんど使用されず、^[1]北米の主要プロスポーツリーグのほとんどで当てはまるように、1人の参加者が他の参加者と不均等な回数対戦する場合は決して使用されません。

イギリスでは、テニスやビリヤードなどのスポーツでは、通常シングルエリミネーション（または「ノックアウト」）トーナメントが行われるため、ラウンドロビントーナメントはアメリカントーナメントと呼ばれてきましたが、現在ではほとんど行われていません。^{[5] [6] [7]}

4人のプレイヤーによる総当たり戦は「クアッド」または「フォーサム」と呼ばれることもある。^[8]

シーズン中に多数の競技試合が行われるスポーツでは、ダブル・ラウンドロビン方式が一般的である。世界のほとんどのサッカーリーグはダブル・ラウンドロビン方式で編成されており、各チームはリーグ内の他のチームとホームで1回、アウェーで1回対戦する。この方式は、 FIFAワールドカップや大陸別トーナメント（例：UEFA欧州選手権、CONCACAFゴールドカップ、AFCアジアカップ、CONMEBOLコパ・アメリカ、CAFネイションズカップ）などの主要なトーナメントの予選でも使用されている。また、クリケット、ブリッジ、チェス、ドラフト、囲碁、アイスホッケー、カーリング、スクラブルのトーナメントでもラウンドロビン方式が採用されている。 2005年と2007年に開催された世界チェス選手権では、8人のプレーヤーがダブル・ラウンドロビン方式でトーナメントを行い、各プレーヤーが白と黒の2つのチームとして他のすべてのプレーヤーと1回ずつ対戦することが決定された。2025年のICCチャンピオンズトロフィーを含むICCイベントを含むいくつかの主要な国際クリケットトーナメントがこの形式で開催されています。^[9]

もっと極端な例として、野球のKBO リーグでは、16 回の総当たり戦が行われ、10 チームがそれぞれ 16 回対戦し、チームあたり合計 144 試合が行われます。

LIDOM（ドミニカ共和国の野球ウィンターリーグ）では、4 つの分類されたチームによる準決勝トーナメントとして、18 回の総当たり戦が行われます。

グループトーナメントのランキングは通常、さまざまなタイブレーカー基準に基づいて、勝利数と引き分け数によって決まります。

より大規模なトーナメント内のプールステージは、多くの場合、総当たり戦で実施される。総当たり戦が1回のみの例として、サッカーではFIFAワールドカップ、UEFA欧州サッカー選手権、UEFAカップ（2004～2009年）、南半球のスーパーラグビー（ラグビーユニオン）の過去のスーパー12およびスーパー14（後の15チームおよび18チーム形式は除く）、クリケットワールドカップとインディアンプレミアリーグ、主要なトゥエンティ20クリケットトーナメント、カンファレンスUSA（現在9チーム）などの多くのアメリカンフットボール 大学カンファレンスが挙げられる。UEFAクラブ大会とコパ・リベルタドーレスのグループフェーズは、ユーロリーグのレギュラーシーズン（および以前のトップ16フェーズ）を含む米国外のほとんどのバスケットボールリーグと同様に、ダブル総当たり戦で争われる。ユナイテッド・フットボール・リーグは、2009年と2010年の両シーズンでダブル・ラウンドロビン方式を採用しました。

シーズン最終戦のテニストーナメントでも、準決勝の前にラウンドロビン形式が採用されます。

総当たりトーナメントでは、引き分けになる場合を除き、最も多くのゲームに勝った出場者が優勝者となります。

理論上、総当たりトーナメントは、既知で固定数の出場者の中から優勝者を決める最も公平な方法です。出場者の事前のシード付けがなく、特定のペア間の試合が妨げられることがないため、各出場者 (プレーヤーまたはチーム) は他のすべての対戦相手に対して平等なチャンスを持ちます。1回か 2 回の悪いパフォーマンスで競技者の最終的な勝利のチャンスが台無しになることはないことから、ノックアウト方式に比べて運の要素は少なくなると考えられます。参加者の最終記録は、同じ対戦相手とのより長い期間の結果を表すという意味で、より正確です。

このシステムは、勝者を決めるだけでなく、参加者全員の順位付けにも適しています。これは、他のステージや競技への出場資格や賞金獲得のために、最強から最弱までの全競技者の最終順位を決定するのに役立ちます。

チームスポーツでは、トーナメントが通常シングルエリミネーション形式に従うカップ優勝者ではなく、総当たり戦のメジャーリーグチャンピオンが一般的に国内で「最強」のチームとみなされます。

さらに、FIFA や ICC ワールドカップなどのトーナメントでは、4 チームからなるグループ間で数回のミニ ラウンドロビンで構成される第 1 ラウンド ステージにより、チームが数千マイルも移動して、ストレート ノックアウト方式で 1 ​​回の不振で敗退する可能性が回避されます。これらのグループの上位 1、2、または場合によっては 3 チームが、トーナメントの残りの期間、ストレート ノックアウト ステージに進みます。

デス・サークルでは、引き分けがなくても、ラウンドロビン方式のトーナメントで優勝者が出ない可能性がありますが、ほとんどのスポーツには、この問題を解決するタイブレーカー・システムがあります。

ラウンドロビン方式は、他のトーナメント形式に比べて長すぎるという欠点があり、後から予定された試合が実質的な意味を持たない可能性があります。また、同点の場合は決着手続きが必要になる場合もあります。

スイス方式のトーナメントでは、ラウンドロビン方式とエリミネーション方式の要素を組み合わせて、引き分けや負けを許容しながら、ラウンドロビン方式よりも少ないラウンドで立派なチャンピオンを選出しようとします。

ラウンドロビン トーナメントの主な欠点は、完了するまでに時間がかかることです。各ラウンドの後に参加者の半数が敗退するノックアウト トーナメントとは異なり、ラウンドロビンでは参加者数より 1 ラウンド少なく済みます。たとえば、16 チームのトーナメントは、ノックアウト形式ではわずか 4 ラウンド (つまり 15 試合) で完了します。ダブル エリミネーショントーナメント形式では 30 (または 31) 試合が必要ですが、ラウンドロビンでは各参加者が 1 回ずつ対戦する場合、終了までに 15 ラウンド (つまり 120 試合) が必要になります。

その他の問題は、ラウンドロビン形式の理論上の公平性と実際のイベントでの実践の違いから生じます。勝者は複数のラウンドをプレイして徐々に決定されるため、成績が悪く、タイトル争いからすぐに脱落していたかもしれないチームは、残りの試合をプレイすることを余儀なくされます。したがって、試合は、勝つチャンスが残っていない競技者同士の競技の終盤でプレイされます。さらに、後半の試合では、まだ勝ち目がある競技者と、勝ち目がない競技者が対戦することもあります。また、競技者がラウンドロビンで最強の相手と立て続けに対戦する一方で、他の競技者は弱い相手と断続的に対戦する可能性もあります。この非対称性は、同じ相手と対戦することが必ずしも完全に公平ではないことを意味します。

また、トーナメントの最後の試合で（偶然にも）2人の選手が対戦し、その試合の結果で優勝が決まるという場合を除き、ショーケースとなる決勝戦は予定されていません。そのような出来事の顕著な例としては、1950年のFIFAワールドカップのウルグアイ対ブラジルの試合が挙げられます。

ラウンドロビンがより大きなトーナメントの予選ラウンドとして使用される場合には、さらに問題が生じます。最終戦の前にすでに次のステージへの出場権を獲得している競技者は、(次のフェーズのリソースを節約するため) 一生懸命にプレーしないか、(下位の予選の予定されている次のフェーズの対戦相手が上位の予選の対戦相手よりも簡単であると認識されている場合) わざと負ける可能性もあります。

2012年オリンピックのバドミントン女子ダブルスでは、次のラウンドに進出していた4組のペアが、同胞やランキング上位の相手を避けるためにラウンドロビンで負けようとしたため、競技から退場させられた。 ^[10]オリンピックのラウンドロビンは新しく導入されたものであり、これらの潜在的な問題は大会前に容易に認識されていたため、次のオリンピックの前には、このような事態の再発を防ぐために変更が行われた。

もう一つの欠点は、特に小規模なラウンドロビンの場合、「死の輪」と呼ばれる、直接対決の成績ではチームを分けられないという点である。3チームのラウンドロビンで、AがBに勝ち、BがCに勝ち、CがAに勝った場合、3チームとも1勝1敗の成績となり、チームを分けるにはタイブレーカーが必要となる。^{[11]これは}1994年のFIFAワールドカップグループEでよく知られた出来事で、4チームすべてが1勝1引き分け1敗の成績で終わった。この現象は、投票理論における コンドルセのパラドックスに類似している。

が競技者の数である場合、純粋な総当たり戦トーナメントにはゲームが必要です。が偶数の場合、十分なリソース (テニストーナメントのコートなど)があれば、各ラウンドでゲームを同時に実行できます。が奇数の場合、各ラウンドでゲームが行われ、そのラウンドで 1 人の競技者はゲームを行いません。 ${\displaystyle n}$${\displaystyle {\begin{matrix}{\frac {n}{2}}\end{matrix}}(n-1)}$${\displaystyle n}$${\displaystyle (n-1)}$${\displaystyle {\begin{matrix}{\frac {n}{2}}\end{matrix}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\begin{matrix}{\frac {n-1}{2}}\end{matrix}}}$

サークル方式は、ラウンドロビン トーナメントのスケジュールを作成するための シンプルなアルゴリズムです。すべての競技者に番号が割り当てられ、最初のラウンドでペアが組まれます。

次に、表の最初または最後の列の競技者の 1 人を固定し (この例では 1 番)、他の競技者を時計回りに 1 つずつ回転させます。

これは、次の反復が最初のペアリングに戻るまで繰り返されます。

競合相手の数が偶数の場合、このアルゴリズムは競合相手のあらゆる可能な組み合わせを実現します (つまり、実現されるすべてのペアはペアごとに異なります)。 ${\displaystyle n}$

まず、アルゴリズムは、競争相手の 1 人が(移動していない競争相手と) 等しい場合、すべての競争相手のペアを明らかに実現します。 ${\displaystyle 1}$

次に、非競争者のペアの場合、一方の競争者がもう一方の競争者の位置に到着するために必要な回転回数を その距離とします。${\displaystyle 1}$${\displaystyle k<{\frac {n}{2}}}$

与えられた例 ( ) では、は からまでの距離があり、 はから までの距離があり、 はから までの距離があります。 ${\displaystyle n=14}$${\displaystyle 2}$${\displaystyle 1}$${\displaystyle 3}$${\displaystyle 14}$${\displaystyle 6}$${\displaystyle 8}$${\displaystyle 9}$

ラウンドでは、左端以外の位置（ は含まない）には、固定距離の競技者しか入ることができません。例のラウンドでは、2 番目の位置で競技者が と対戦する場合、その距離は です。ラウンドでは、この位置は競技者と が占めており、距離も です。同様に、次の位置（ラウンドではと対戦、ラウンドでは と対戦など）には、距離 - の競技者しか入ることができません。 ${\displaystyle 1}$${\displaystyle 1}$${\displaystyle 2}$${\displaystyle 13}$${\displaystyle 2}$${\displaystyle 2}$${\displaystyle 14}$${\displaystyle 12}$${\displaystyle 2}$${\displaystyle 3}$${\displaystyle 12}$${\displaystyle 1}$${\displaystyle 2}$${\displaystyle 11}$${\displaystyle 2}$${\displaystyle 4}$

あらゆる に対して、距離 のペアが正確に 個存在します 。 ラウンドが存在し、それらはすべて同じ位置で 1 つの距離ペアを実現します。明らかに、これらのペアはペアごとに異なります。結論として、あらゆる距離ペアが実現されます。 ${\displaystyle k<{\frac {n}{2}}}$${\displaystyle n-1}$${\displaystyle k}$${\displaystyle n-1}$${\displaystyle k}$${\displaystyle k}$

これはあらゆる に当てはまるので、あらゆるペアが実現されます。 ${\displaystyle k}$

競技者の数が奇数の場合、特定のラウンドで予定されている対戦相手がプレーせず、不戦勝であるダミー競技者を追加できます。したがって、スケジュールは、ダミーが固定またはローテーションの通常のプレーヤーであるかのように計算できます。

1つの位置を回転させる代わりに、互いに素な任意の数が完全なスケジュールを生成します。上段と下段は、スポーツのホーム/アウェイ、チェスの白/黒などを示します。公平性を確保するために、競技者1は常に最初の行にあるため、これはラウンド間で交互に表示する必要があります。たとえば、競技者3と8が第3ラウンドで試合を完了できなかった場合、両方の競技者がすでにそれらのラウンドで他の対戦相手と対戦しているため、他のラウンド外で再スケジュールする必要があります。より複雑なスケジュール制約には、より複雑なアルゴリズムが必要になる場合があります。^{[12]このスケジュールは、プレーヤーが物理的にテーブルの周りを移動する、ラピッドゲームのチェスとドラフトのトーナメントに適用されます。フランスでは、これは}カルーセルベルジェシステム（Système Rutch-Berger）と呼ばれています。 ^[13]${\displaystyle (n-1)}$

このスケジュールは、すべてのゲームが異なる時間に行われる「非同期」ラウンドロビントーナメントにも使用できます（たとえば、会場が1つしかない場合など）。ゲームは各ラウンドで左から右へ、第1ラウンドから最終ラウンドまでプレイされます。競技者の数が偶数の場合、このスケジュールは、ゲーム間の休憩時間などの品質と公平性の尺度に関して優れたパフォーマンスを発揮します。一方、競技者の数が奇数の場合、パフォーマンスはあまり良くなく、これらの尺度に関しては別のスケジュールの方が優れています。^[14]

あるいは、オーストリアのチェス名人ヨハン・ベルガーにちなんで名付けられたベルガー表^[15]は、トーナメントの計画に広く使用されています。^[16]ベルガーは、その発明者であるリチャード・シューリヒに言及しながら、 2冊のチェス年鑑^{[17] [18]}でペアリング表を発表しました。 ^{[19] [20]}

これは、プレーヤー 14 の位置が固定され、他のすべてのプレーヤーの位置が反時計回りに回転するスケジュールを構成します。このスケジュールは手動で簡単に生成できます。次のラウンドを構成するには、最初のラウンドの最後のプレーヤー 8 がテーブルの先頭に移動し、プレーヤー 9 とプレーヤー 7、プレーヤー 10 とプレーヤー 6 が続き、プレーヤー 1 とプレーヤー 2 が対戦します。算術的には、これはプレーヤー を除いて、前の行に加算することと同じです。加算の結果が より大きい場合は、合計から を 減算します。${\displaystyle {\frac {n}{2}}}$${\displaystyle {\frac {n}{2}}}$${\displaystyle n}$${\displaystyle (n-1)}$${\displaystyle (n-1)}$

このスケジュールは、プレイヤー同士が対戦するラウンドを表す (n-1, n-1) テーブルとして表すこともできます。たとえば、プレイヤー 7 はラウンド 4 でプレイヤー 11 と対戦します。プレイヤーが自分自身と対戦する場合は、不戦勝またはプレイヤー n との対戦を示します。ラウンドのすべてのゲームは、テーブル内の対角線を構成します。

上記のスケジュールは、以下に示すようにグラフで表すこともできます。

グラフとスケジュールは両方とも^[21]でレクリエーション数学パズルとしてエドゥアール・ルーカスによって報告されました。ルーカスは、この方法を単純かつ独創的であると述べ、その解決法をリセ・コンドルセの教師であるフェリックス・ワレツキに帰しています。ルーカスは、スライディングパズルによる代替の解決法も提案しました。

この方法を簡単に覚えるために、次の記憶法を使うことができます。最初のラウンドから、

                       会場 = 1  
 ╭─────────────────── ────┐
1—ω >>> 2—13 >>> 3—12 >>> 4—11 >>> 5—10 >>> 6—9 >>> 7—8

次のラウンドが構築されます:

ω—8 >>> 9—7 >>> 10—6 >>> 11—5 >>> 12—4 >>> 13—3 >>> 1—2

その後、

2—ω >>> 3—1 >>> 4—13 >>> 5—12 >>> 6—11 >>> 7—10 >>> 8—9
ω—9 >>> ...

プレイヤー数が奇数の場合、最初の会場のプレイヤーが不戦勝となります。プレイヤー数が偶数の場合、追加されたプレイヤー(ω)が対戦相手となります。

競技者の数が偶数または奇数の場合、シュリグ^[20]は縦の列と横の列を持つ表を作成します。次に、左上隅から始めて、1からまでの一連の数字を繰り返して入力します。以下は、競技者が7人または8人の場合の表の例です。 ${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n/2}$${\displaystyle n-1}$${\displaystyle n-1}$

次に、対戦相手を取得するために 2 番目のテーブルが作成されます。各水平行には、前のテーブルの行と同じ数字が入力されます(最後の行には、元のテーブルの最初の行の数字が入力されます)。ただし、順序は逆 (右から左) です。 ${\displaystyle x}$${\displaystyle x+1}$

上記の表を結合すると次のようになります。

次に、最初の列が更新されます。競技者の数が偶数の場合、プレーヤー番号が1 番目と 2 番目の位置に交互に置き換えられますが、競技者の数が奇数の場合は、代わりに不戦勝が使用されます。 ${\displaystyle n}$

ペアリング表はマスタートーナメント開催の取り決めに関する付録として公開された。シュリグは彼のアルゴリズムの証明も理由も示さなかった。^[22]

• グループトーナメントのランキングシステム（同点決着システムの詳細を含む）
• 組み合わせ設計、 n次のバランスのとれたトーナメント設計（BTD( n )）
• トーナメント（グラフ理論）、ラウンドロビントーナメントの数学的モデル
• マクマホン方式トーナメントは、スイス方式のバリエーションで、トーナメント前のランキングを組み込んで、早い段階での不均衡な組み合わせを防ぐものである。
• ショーネシープレーオフシステム、4チームが参加するシングルエリミネーショントーナメントの一種
• マッキンタイア方式は、シングルエリミネーション方式とダブルエリミネーション方式の特徴を組み合わせた一連のトーナメント形式である。
• ブリッジの動きを複製する
• 総当たり戦チェストーナメント一覧
• スケベニンゲン方式では、一方のチームの各メンバーがもう一方のチームの各メンバーと対戦する。
• コープランド法
• コンドルセ法
• コンドルセ基準
• 勝利には3ポイント、ラウンドロビンでは異なる得点システムの影響