Круговой турнир - Round-robin tournament

Пример кругового турнира с 10 командами-участниками

А круговой турнир (или же универсальный турнир) это конкуренция в котором каждый участник встречает всех остальных участников по очереди.^[1][2] Раунд-робин контрастирует с отборочный турнир, в котором участники выбывают после определенного количества проигрышей.

Терминология

Период, термин по-круговой происходит от французского термина рубан, смысл "Лента ". В течение долгого времени термин был испорченный и идиомизированный к Робин.^[3][4]

В одиночный круговой алгоритм расписание, каждый участник играет с каждым другим участником один раз. Если каждый участник играет всех остальных дважды, это часто называется двойной круговой алгоритм. Термин редко используется, когда все участники играют друг с другом более двух раз,^[1] и никогда не используется, когда один участник играет с другими неравное количество раз (как это имеет место почти во всех основных профессиональных спортивных лигах США - см. AFL (1940–41) и Всеамериканская футбольная конференция за исключениями).

В Великобритании круговой турнир часто называют американским турниром по таким видам спорта, как теннис или бильярд. нокаутировать турниры.^[5][6][7] По-итальянски это называется girone all'italiana (буквально «трасса в итальянском стиле»). В сербский она называется системой Бергера (Бергеров систем, Система Бергерова), после шахматиста Иоганн Бергер. Круговой турнир с четырьмя игроками иногда называют «четверной» или «четверкой».^[8]

Использовать

В видах спорта с большим количеством соревновательных матчей за сезон распространены двойные круговые турниры. Наиболее ассоциация футбола лиги в мире организованы по двойному круговому алгоритму, в котором каждая команда играет со всеми остальными в своей лиге один раз дома, а другой - на выезде. Эта система также используется при квалификации к крупным турнирам, таким как Чемпионат мира по футболу и континентальные турниры (например, Чемпионат Европы УЕФА, Золотой кубок КОНКАКАФ ). Есть также круговой мост, шахматы, Черновики, идти, хоккей на льду, вьющийся, и Скрэббл турниры. В Чемпионат мира по шахматам В 2005 и 2007 годах было принято решение о двойном круговом турнире с участием восьми игроков, в котором каждый игрок сталкивается с каждым другим игроком один раз белым и один раз черным.

В более крайнем примере КБО Лига из бейсбол играет 16-кратный круговой алгоритм, при этом каждая из 10 команд играет друг с другом по 16 раз, в общей сложности 144 игры на команду.

Рейтинг групповых турниров обычно выбираются по количеству выигранных и ничьих матчей с любым из множества критериев тай-брейка.

Часто, этапы пула в рамках более широкого турнира проводятся по круговой схеме. Примеры с единым циклическим планированием включают Чемпионат мира по футболу, Чемпионат Европы по футболу, и Кубок УЕФА (2004–2009) в футболе, Супер регби (регби ) в Южном полушарии во время его прошлых итераций как Super 12 и Super 14 (но нет в более поздних форматах из 15 и 18 команд), Чемпионат мира по крикету вдоль Пакистанская Суперлига & Индийская Премьер-лига, два крупных турнира по крикету Twenty-20 и многие американский футбол конференции колледжей, такой как Большой 12 (который в настоящее время насчитывает 10 участников). Групповые этапы Лига чемпионов УЕФА и Кубок Либертадорес Америки оспариваются как двойной круговой алгоритм, как и большинство баскетбол лиги за пределами США, включая регулярный сезон и этапы лучших 16 Евролига; то Объединенная футбольная лига использует двойной круговой алгоритм для обоих 2009 и 2010 сезоны.

В теннисных турнирах по окончании сезона также используется круговой формат до полуфиналов на этапах.

Оценка

Преимущества формата

В круговом турнире чемпион - это участник, выигравший наибольшее количество игр.

Теоретически круговой турнир - это самый справедливый способ определить чемпиона среди известного и фиксированного числа участников. Каждый участник, будь то игрок или команда, имеет равные шансы против всех других оппонентов, потому что нет предварительного распределения участников, которое исключает матч между любой данной парой. Видно, что элемент удачи уменьшается по сравнению с система выбивания поскольку одно или два плохих выступления не обязательно должны разрушать шансы участника на окончательную победу. Итоговые записи участников более точны в том смысле, что они представляют результаты за более длительный период времени против одного и того же противодействия.

Система также лучше подходит для ранжирования всех участников, а не только для определения победителя. Это полезно для определения окончательного ранга всех участников, от самого сильного до самого слабого, с целью квалификации для другого этапа или соревнования, а также для получения призовых.

В командный вид спорта (по круговой системе) чемпионы высшей лиги обычно считаются "лучшей" командой в стране, а не (устранение ) обладатели кубков.

Более того, в турнирах, таких как чемпионаты мира по футболу FIFA или ICC, этап первого раунда, состоящий из нескольких мини-круговых игр между группами по 4 команды, защищает от возможности того, что команда может проехать тысячи миль только для того, чтобы вылететь после всего лишь одного бедняка производительность в прямой нокаут-системе. Одна, две, а иногда и три лучшие команды в этих группах затем переходят к стадии плей-офф до конца турнира.

В кругу смерти (см. Ниже) возможно, что чемпион не выйдет из кругового турнира, даже если нет ничьей. Однако в большинстве видов спорта есть система тай-брейков, которая решает эту проблему.

Недостатки формата

Раунд-робины могут оказаться слишком длинными по сравнению с другими типами турниров, а игры, запланированные на более позднее время, могут не иметь существенного значения. Они также могут потребовать процедуры разрешения конфликтов.

Турниры по швейцарской системе попытаться объединить элементы кругового формата и форматов на выбывание, чтобы обеспечить достойного чемпиона, использующего меньшее количество раундов, чем при круговом, при этом допуская ничьи и поражения.

Продолжительность турнира

Главный недостаток кругового турнира - время, необходимое для его прохождения. В отличие от турниров на выбывание, где половина участников выбывает после каждого раунда, в круговой системе требуется на один раунд меньше, чем количество участников. Например, турнир из 16 команд может быть завершен всего за 4 раунда (т.е. 15 матчей) нокаутом (одиночное исключение ) формат; а двойное исключение Формат турнира требует 30 (или 31) матча, но для завершения кругового турнира потребуется 15 раундов (то есть 120 матчей), если каждый участник встретится друг с другом один раз.

Другие проблемы связаны с разницей между теоретической справедливостью кругового формата и практикой на реальном мероприятии. Поскольку победитель постепенно достигается через несколько раундов игры, команды, которые плохо выступают и которые могли быть быстро выброшены из борьбы за титул, вынуждены играть оставшиеся игры. Таким образом, игры проводятся в конце соревнования между конкурентами, и у них нет шансов на успех. Более того, в некоторых более поздних матчах один участник, которому еще есть за что играть, будет объединяться в пары с другим, у которого его нет. У одного из участников также может быть возможность сыграть с сильнейшими соперниками в круговой системе в быстрой последовательности, в то время как другие будут играть с ними периодически с более слабым соперником. Эта асимметрия означает, что игра с одними и теми же соперниками не обязательно полностью равноправна.

Также нет запланированного финального матча-показа, если (по совпадению) два участника не встретятся в последнем матче турнира, и результат этого матча определяет чемпионство. Ярким примером такого события стал 26 мая 1989 г. матч между Арсенал и Ливерпуль.

Квалифицированные команды

Дополнительные проблемы возникают, когда круговой алгоритм используется в качестве квалификационного раунда в более крупном турнире. Участник, уже прошедший квалификацию в следующий этап перед своей последней игрой, может либо не сильно стараться (чтобы сохранить ресурсы для следующего этапа), либо даже намеренно проиграть (если запланированный соперник следующего этапа для квалификации, занявшей более низкое место, считается легче, чем на более высокий).

Четыре пары в Олимпийские игры 2012 г. Женщины, пары, бадминтон, прошедшие квалификацию в следующий раунд, были исключены из соревнований за попытку проиграть в раунд-робине, чтобы избежать соотечественников и более сильных соперников.^[9] Этап круговой системы на Олимпийских играх был новым введением, и эти потенциальные проблемы были хорошо известны до турнира; изменения были внесены до следующих Олимпийских игр, чтобы предотвратить повторение этих событий.

Круг смерти

Еще один недостаток, особенно в небольших круговых играх, - это «круг смерти», когда команды не могут быть разделены по результатам личных встреч. В круговой системе с тремя командами, где A побеждает B, B побеждает C, а C побеждает A, все три участника будут иметь рекорд из одной победы и одного поражения, и необходимо будет использовать тай-брейк для разделения команд.^[10] Как известно, это произошло во время 1994 Чемпионат мира по футболу Группа E, где все четыре команды закончили с рекордом: одна победа, одна ничья и одно поражение. Это явление аналогично Парадокс Кондорсе в теории голосования.

Алгоритм планирования

Если ${ displaystyle n}$ количество участников, чистый круговой турнир требует ${ displaystyle { begin {matrix} { frac {n} {2}} end {matrix}} (n-1)}$ игры. Если ${ displaystyle n}$ четно, то в каждом из ${ Displaystyle (п-1)}$ раунды ${ displaystyle { begin {matrix} { frac {n} {2}} end {matrix}}}$ игры могут проводиться одновременно при наличии достаточных ресурсов (например, корты для теннис турнир). Если ${ displaystyle n}$ странно, будет ${ displaystyle n}$ раундов, каждый с ${ displaystyle { begin {matrix} { frac {n-1} {2}} end {matrix}}}$ игр, и у одного участника не было игр в этом раунде.

Круговой метод

Круговой метод является стандартным алгоритм создать расписание кругового турнира. Всем участникам присваиваются номера, а затем они попадают в пары в первом раунде:

Затем фиксируется один из участников в первом или последнем столбце таблицы (номер один в этом примере), а остальные поворачиваются по часовой стрелке на одну позицию.

Это повторяется до тех пор, пока вы почти не вернетесь в исходное положение:

Чтобы увидеть это - с четным числом ${ displaystyle n}$ конкурентов - этот алгоритм реализует каждую возможную их комбинацию (эквивалентно, что все реализованные пары попарно различны), мы рассуждаем следующим образом.

Во-первых, алгоритм, очевидно, реализует каждую пару конкурентов, если один из них равен ${ displaystyle 1}$ (неподвижный конкурент).

Далее, для пар не-${ displaystyle 1}$ конкуренты, пусть их расстояние будет числом ${ Displaystyle к <{ гидроразрыва {п} {2}}}$ Иногда необходимо произвести ротацию, чтобы один участник занял позицию, которую занимал другой.

В приведенном примере (${ displaystyle n = 14}$), ${ displaystyle 2}$ имеет расстояние ${ displaystyle 1}$ к ${ displaystyle 3}$ и чтобы ${ displaystyle 14}$ и это расстояние ${ displaystyle 6}$ к ${ displaystyle 8}$ и чтобы ${ displaystyle 9}$.

В раунде не крайняя левая позиция (не включая ${ 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}$ конкуренты.

Для каждого ${ Displaystyle к <{ гидроразрыва {п} {2}}}$, есть ровно ${ displaystyle n-1}$ пары расстояния ${ displaystyle k}$. Есть ${ displaystyle n-1}$ раундов, и все они реализуют одну дистанцию ​​-${ displaystyle k}$ пара в одной позиции. Ясно, что эти пары попарно различны. Вывод таков: каждое расстояние -${ displaystyle k}$ пара реализована.

Это справедливо для каждого ${ displaystyle k}$, следовательно, каждая пара реализуется.

Если количество участников нечетное, может быть добавлен фиктивный участник, чей запланированный соперник в данном раунде не играет и имеет до свидания. Таким образом, расписание можно рассчитать, как если бы манекен был обычным игроком, фиксированным или вращающимся. Вместо поворота одной позиции любое число относительно простой к ${ Displaystyle (п-1)}$ создаст полное расписание. Верхние и нижние ряды могут указывать дома / на выезде в спорте, белый / черный в шахматы, так далее.; для обеспечения справедливости раунды должны чередоваться, поскольку участник 1 всегда находится в первом ряду. Если, скажем, участники 3 и 8 не смогли завершить свое приспособление в третьем раунде, его нужно было бы перенести на другие раунды, поскольку оба спортсмена уже столкнулись бы с другими соперниками в этих раундах. Более сложные ограничения планирования могут потребовать более сложных алгоритмов.^[11]Этот график применяется в шахматных и шашечных турнирах по быстрым играм, где игроки физически перемещаются вокруг стола. Во Франции это называется Карусель -Система Бергера (Système Rutch-Berger).^[12]

Расписание также можно использовать для «асинхронных» круговых турниров, где все игры проходят в разное время (например, потому что есть только одно место). В каждом раунде игры проходят слева направо, от первого до последнего. Когда количество участников четное, это расписание хорошо работает с точки зрения качества и справедливости, таких как количество отдыха между играми. С другой стороны, когда количество участников нечетное, это не так хорошо, и другой график лучше в отношении этих мер.^[13]

Столы Бергера

В качестве альтернативы столы Бергера,^[14] названный в честь Австрийский шахматный мастер Иоганн Бергер, широко используются при планировании турниров. Бергер опубликовал таблицы пар в своих двух Шах-Ярбюхер (Шахматные однолетники),^[15][16] со ссылкой на его изобретателя Ричарда Шурига.^[17][18]

Это составляет график, в котором игрок 14 занимает фиксированную позицию, а все остальные игроки вращаются по часовой стрелке. ${ displaystyle { frac {n} {2}}}$ позиции. Это расписание легко создается вручную. Чтобы построить следующий раунд, последний игрок, номер 8 в первом раунде, перемещается во главе стола, за ним идет игрок 9 против игрока 7, игрок 10 против 6, пока игрок 1 против игрока 2. Арифметически это равняется добавление ${ displaystyle { frac {n} {2}}}$ к предыдущей строке, за исключением игрока ${ displaystyle n}$. Когда результат сложения больше, чем ${ Displaystyle (п-1)}$, затем вычтите ${ displaystyle ({ frac {n} {2}} - 1)}$.

Это расписание также может быть представлено в виде таблицы (n-1, n-1), отражающей раунд, в котором игроки встречаются друг с другом. Например, игрок 7 играет против игрока 11 в раунде 4. Если игрок встречается с самим собой, это означает прощание или игру против игрока n. Все игры в раунде представляют собой диагональ в таблице.

Приведенное выше расписание также можно представить в виде графика, как показано ниже:

Диаграмма диапазона расписания циклического перебора

И график, и расписание были представлены Эдуард Лукас в^[19] как развлекательную математическую головоломку. Лукас, который описывает этот метод как простой и гениальный, приписывает решение Феликсу Валецки, учителю в Lycée Condorcet. Лукас также предложил альтернативное решение с помощью раздвижная головоломка.

Оригинальная конструкция таблиц сопряжения Ричарда Шурига (1886 г.)

Для 7 или 8 игроков Schurig^[18] строит стол с ${ displaystyle n / 2}$ вертикальные ряды и ${ displaystyle n-1}$ горизонтальные ряды, а именно:

Затем создается вторая таблица (с отсчетом от конца), как показано ниже:

Объединяя приведенные выше таблицы, мы получаем:

Затем обновляется первый столбец: если ${ displaystyle n}$ четно, номер игрока ${ displaystyle n}$ поочередно заменяется на первую и вторую позиции, тогда как если ${ displaystyle n}$ нечетно, вместо этого используется «до свидания».

Таблицы пар были опубликованы в качестве приложения, касающегося организации проведения мастер-турниров. Шуриг не предоставил ни доказательства, ни мотивации своего алгоритма. Для получения дополнительных исторических сведений см. Аренс.^[20]

Смотрите также

• Система рейтинга групповых турниров, в том числе детали систем разрыва связи
• Комбинаторный дизайн, сбалансированный турнирный дизайн порядка п (BTD (п))
• Турнир (теория графов), математическая модель кругового турнира
• Другие турнирные системы:
  • Турнир по швейцарской системе
    • Турнир по системе Макмэна, разновидность швейцарской системы, которая включает предтурнирные рейтинги, чтобы предотвратить раннее формирование односторонних пар
  • Турнир на выбывание
    • Система плей-офф Шонесси, тип турнира на выбывание, в котором участвуют четыре команды.
  • Турнир с двойным выбыванием
  • Система Макинтайра, серия форматов турниров, сочетающих в себе особенности турниров с выбыванием одного и двух игроков.
• Мост:
  • Повторяющиеся движения моста
• Шахматы:
  • Список круговых шахматных турниров
  • Система Схевенингена, где каждый член одной команды играет каждого члена другой
• Голосование:
  • Метод Кондорсе
  • Критерий Кондорсе

Рекомендации

внешняя ссылка

• Круговая дискуссионная доска ссылка на дискуссионное сообщество и расписания (сбалансированные, циклические, оптимальные, вист).
• Таблицы циклической системы (оценка - программа)
• Бесплатная печать скобок Round Robin