総当たりトーナメント

10人の参加者による総当たりトーナメントの例

ラウンドロビン方式のトーナメントまたはオールプレイオールトーナメントは、各出場者が通常順番に他の参加者全員と対戦する競技形式です。[ 1 ] [ 2 ]ラウンドロビン方式は、一定数の勝敗で参加者が敗退するエリミネーショントーナメントや、参加者が現在のスコアに応じてマッチングされるスイス式トーナメントとは対照的です。

用語

ラウンドロビンという用語は、フランス語の「ruban」(リボン)に由来しています。時が経つにつれて、この用語は慣用句的に「ロビン」と呼ばれるようになりました。[ 3 ] [ 4 ]

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

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

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

アプリケーション

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

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

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

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

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

シーズン最終戦となるテニストーナメント、 ATPファイナルWTAファイナルでも、準決勝の前にラウンドロビン形式が採用されています。

評価

利点

ラウンドロビン方式のトーナメントでは、引き分けの可能性がない限り、最も多くのゲームに勝利した出場者が優勝者となります。

理論上、総当たり戦は、既知の固定人数の出場者から優勝者を決定する最も公平な方法です。出場者を事前にシード分けする必要がなく、特定のペア間での対戦が妨げられることがないため、各出場者(選手またはチーム)は他のすべての対戦相手に対して平等なチャンスを持ちます。1、2回の不調が最終的な勝利のチャンスを台無しにするわけではないため、ノックアウト方式に比べて運の要素は少なくなります。参加者の最終記録は、同じ相手とのより長い期間の成績を表すという意味で、より正確です。

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

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

さらに、FIFAやICCワールドカップなどの大会では、4チームずつのグループによるミニラウンドロビン方式の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人の競技者はそのラウンドでゲームを行いません。

サークル法

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

第 1 ラウンド (1 は 14 をプレイし、2 は 13 をプレイし、...)
12 3 4 5 6 7
14 13 12 11 10 9 8

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

第 2 ラウンド (1 は 13 をプレイし、14 は 12 をプレイし、...)
114 2 3 4 5 6
13 12 11 10 9 8 7
第 3 ラウンド (1 は 12 をプレイし、13 は 11 をプレイし、...)
113 14 2 3 4 5
12 11 10 9 8 7 6

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

第 13 ラウンド (1 は 2 をプレイし、3 は 14 をプレイし、...)
13 4 5 6 7 8
2 14 13 12 11 10 9

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

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

次に、競争相手でないペアの場合、一方の競争者がもう一方の競争者の位置に到達するために実行する必要がある回転の回数を、 その距離とします。

示された例 ( ) では、は からまでの距離があり、は から までの距離があり、はから までの距離があります。

ラウンドでは、左端以外の位置( は含まない)には、固定距離の競技者しか入ることができません。例のラウンドでは、2番目の位置で競技者はと対戦し、その距離は です。ラウンドでは、この位置は競技者と が占めており、距離も となっています。同様に、次の位置(ラウンドでは と対戦、ラウンドではと対戦など)には、距離 - の競技者しか入ることができません。

任意の に対して、ちょうど 個の距離ペアが存在する 。ラウンドが存在し、それらはすべて同じ位置で 1 つの距離ペアを実現する。明らかに、これらのペアは 1 対 1 で異なる。結論として、すべての距離ペアは実現される。

これはあらゆる に当てはまるので、あらゆるペアが実現されます。

出場者が奇数の場合、ダミー選手を追加することができます。ダミー選手の対戦相手は、特定のラウンドで試合に出場せず、不戦勝となりますそのため、ダミー選手を通常の選手(固定またはローテーション)として計算することができます。

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

このスケジュールは、すべての試合が異なる時間に行われる「非同期」ラウンドロビン方式のトーナメントにも適用できます(例えば、会場が1つしかない場合など)。試合は各ラウンドで左から右へ、そして第1ラウンドから最終ラウンドまで行われます。競技者の数が偶数の場合、このスケジュールは試合間の休憩時間など、試合の質と公平性の指標に関して良好なパフォーマンスを示します。一方、競技者の数が奇数の場合、このスケジュールはあまり良好ではなく、これらの指標に関しては別のスケジュールの方が優れています。[ 14 ]

ベルガーテーブル

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

第1ラウンド 1~142~133~12歳4~115~106~9歳7~8
第2ラウンド 14 – 89~710~611 – 512 – 413 – 31~2
第3ラウンド 2~143-14~135~12歳6~11歳7~108~9
... ...
第13ラウンド 7~14歳8~69~5時10 – 411 – 312 – 213 – 1

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

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

斜めのスキーム
× 234567891011121312345678910111213
1 12345678910111213
2 12345678910111213
3 12345678910111213
4 12345678910111213
5 12345678910111213
6 12345678910111213
7 12345678910111213
8 12345678910111213
9 12345678910111213
10 12345678910111213
11 12345678910111213
12 12345678910111213
13 10111213
ラウンドロビンスケジュール
× 12345678910111213
1 12345678910111213
2 23456789101112131
3 34567891011121312
4 45678910111213123
5 56789101112131234
6 67891011121312345
7 78910111213123456
8 89101112131234567
9 91011121312345678
10 10111213123456789
11 11121312345678910
12 12131234567891011
13 13123456789101112

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

ラウンドロビンスケジュールスパン図

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

ニモニック

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

 会場 = 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 >>> ... 

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

リチャード・シューリグによるペアリングテーブルのオリジナルの構築(1886年)

シュリグ[ 19 ]は、競技者の数が偶数または奇数の場合、縦列と横列からなる表を作成します。そして、左上隅から1から までの数字列を繰り返し、表に記入していきます。以下は、競技者が7人または8人の場合の表の例です。

第1ラウンド 1 2 3 4
第2ラウンド 5671
第3ラウンド 2345
第4ラウンド 6712
第5ラウンド 3456
第6ラウンド 7123
第7ラウンド 4567

次に、対戦相手を得るために2つ目の表を作成します。各横列には、前の表の行と同じ数字が入ります(最後の行には元の表の最初の行の数字が入ります)。ただし、順番は逆(右から左)です。

第1ラウンド – 1 – 7 – 6 – 5
第2ラウンド – 5– 4– 3– 2
第3ラウンド – 2– 1– 7– 6
第4ラウンド – 6– 5– 4– 3
第5ラウンド – 3– 2– 1– 7
第6ラウンド – 7– 6– 5– 4
第7ラウンド – 4– 3– 2– 1

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

第1ラウンド 1-1 2~7 3~6 4~5
第2ラウンド 5 – 56 – 47 – 31~2
第3ラウンド 2 – 23-14~75~6
第4ラウンド 6 – 67~51~42~3
第5ラウンド 3 – 34 – 25-16~7
第6ラウンド 7 – 71~62~53~4
第7ラウンド 4 – 45 – 36 – 27-1

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

対戦表は、マスタートーナメント開催に関する取り決めに関する付録として公表された。シュリグは自身のアルゴリズムの証明も根拠も示さなかった。[ 21 ]

参照

参考文献

  1. ^ a bウェブスターの第3新国際英語辞典、完全版(1971年、G. & C. Merriam Co)、1980ページ。
  2. ^オーカット、ウィリアム・ダナ (1895).オフィシャル・ローンテニス・ブレティン. 第2巻. ニューヨーク: 編集者. pp. 1, 3.
  3. ^ Strehlov, Richard A; Wright, Sue Ellen編 (1993). 『より良いコミュニケーションのための用語の標準化:実践、応用理論、そして結果』 Vol. 1166. ASTM. pp.  336– 337. ISBN 0-8031-1493-1
  4. ^ Brewer's Dictionary of Phrase & Fable . ニューヨーク: Harper & Brother Publishers. p. 786.
  5. ^ 「ビリヤード関連用語集」『ビリヤード・マンスリー』 、英国アマチュア・ビリヤード協会。1912年2月。2022年3月3日時点のオリジナルよりアーカイブ。アメリカン・トーナメント:各プレイヤーが他のすべてのプレイヤーと順番に対戦するトーナメント。
  6. ^アライド。「アメリカン・トーナメント」チェンバーズ21世紀辞典。アライド出版社。38ページ。ISBN 978-0550106254. 2012年8月1日閲覧
  7. ^ミード、シェパード (1977). 『テニスで成功する方法:プロが教えられない、テニスの簡単なやり方』マッケイ. p. 130. ISBN 9780679507499. 2012年8月1日閲覧
  8. ^ 「USCF定格トーナメント入門」(PDF) .米国チェス連盟. 2006年2月23日. 2022年2月23日時点のオリジナルよりアーカイブ(PDF) 。
  9. ^ 「インドはパキスタンでICCチャンピオンズトロフィーに出場するのか:ロヒット・シャルマ主将が沈黙を破る」ザ・ウィーク誌2024年11月10日。 2024年11月10日閲覧
  10. ^ウォーカー、ピーター、シディック、ハルーン(2012年8月1日)「オリンピックのバドミントン選手8人が『試合を投げる』行為で失格」ガーディアン紙」 20128月1日閲覧
  11. ^ 「UCバークレークイズボウル:スケジュールの作成方法」 UCバークレーオープンコンピューティング施設
  12. ^ Dinitz, Jeff (2004年11月13日). 「リーグとトーナメントのスケジュール設計」(PDF) . Jeff Dinitzのホームページ. マウント・セント・メアリー大学: グラフ理論 48日目. 2022年2月23日時点のオリジナルよりアーカイブ(PDF) .
  13. ^ Le livre de l'arbitre : édition 2008 (PDF) (フランス語)。フランス・デ・エシェック連盟。 2008.p. 56.ISBN 978-2-915853-01-82013年1月19日時点のオリジナルよりアーカイブ(PDF)
  14. ^ Suksompong, Warut (2016). 「非同期ラウンドロビントーナメントのスケジューリング」.オペレーションズ・リサーチ・レターズ. 44 (1): 96– 100. arXiv : 1804.04504 . doi : 10.1016/j.orl.2015.12.008 . S2CID 4931332 . 
  15. ^ Table de Berger (フランス語)、参加者30名までのラウンドロビンスケジュールの例。
  16. ^「C. トーナメントの一般規則および技術的推奨事項 / 05. 競技会の一般規則 / 競技会の一般規則。付録1:ベルガー表の詳細 /」。FIDEハンドブック。FIDE。(目次)
  17. ^ベルガー、ヨハン (1893)。Schach-Jahrbuch für 1892/93 (ドイツ語)。ライプツィヒ。26 ~ 31ページ 。OCLC 651254787 {{cite book}}: CS1 メンテナンス: 場所の発行元が見つかりません (リンク)
  18. ^バーガー、ヨハン (1899)。Schach-Jahrbuches für 1899/1900: Fortsetzung des Schach-Jahrbuches für 1892/1993 (ドイツ語)。ライプツィヒ。21 ~ 27ページ 。OCLC 651254792 {{cite book}}: CS1 メンテナンス: 場所の発行元が見つかりません (リンク)
  19. ^ a bリチャード・シューリッグ (1886)。 「Die Paarung der Theilnehmer eines Turniers」。Deutsche Schachzeitung (ドイツ語)。41 : 134–137。OCLC 556959107  HathiTrust Digital Library の Deutsche Schachzeitung
  20. ^ルーカス、エドゥアール (1883)。「レ・ジュー・ド・モワゼル」Récréations Mathématiques (フランス語)。パリ:ゴーティエ・ヴィラール。161–197ページ 
  21. ^アーレンス、ヴィルヘルム (1901)。 「XIV アノルドヌングスの問題、§ 1 アノルドヌンゲン・イム・クライゼ、アウフガベ 2」。Mathematische Unterhaltungen und Spiele (ドイツ語)。ライプツィヒ:BG・トイブナー。ページ 259–272。ark :/13960/t2w37mv93。
「 https://en.wikipedia.org/w/index.php?title=ラウンドロビントーナメント&oldid =1324117738」より取得