1

Тема: Повторные матчи в швейцарской системе

Не хочется засорять другие темы про форматы турниров.
Мой вопрос один и достаточно простой.

В швейцарке игроки после каждого тура выстраиваются по ранжиру. Это смысл швейцарки.
С другой стороны запрещены повторные игры.

Каков должен быть алгоритм действий составителя турнирной таблицы (человека или программы) для устранения противоречия, если очередная пара оказалась повторной?

С уважением, Назим Ахундов.

2

Re: Повторные матчи в швейцарской системе

На мой субъективный взгляд, должно быть обеспечено выполнение следующих условий:
1. Повторная пара может быть только в том случае, если один из игроков этой пары уже играл со всеми оставшимися в турнире игроками.
2. В туре должно быть минимально возможное число повторных пар.
3. В приоритете для создания поворотной пары должны быть игроки, находящиеся ниже в турнирной таблице.

3

Re: Повторные матчи в швейцарской системе

Sandr пишет:

На мой субъективный взгляд, должно быть обеспечено выполнение следующих условий:
1. Повторная пара может быть только в том случае, если один из игроков этой пары уже играл со всеми оставшимися в турнире игроками.
2. В туре должно быть минимально возможное число повторных пар.
3. В приоритете для создания поворотной пары должны быть игроки, находящиеся ниже в турнирной таблице.

  Со всем этим можно согласиться. Но вопрос не в этом.
Вопрос в том, КАК это сделать. Т.е. я прошу описать некую процедуру, с помощью которой можно одновременно выполнить оба требования:
а) Игроки ранжированы и игра идет между соседними по ранжиру игроками
б) Игроки не играют повторно

А если нельзя оба одновременно, то как выполнить:

1) вообще, хоть как-нибудь
2) пункт б) максимально сохраняя пункт а)

Процедура вручную или алгоритм для программы - любой вариант устроит.

Меня что удивляет:

Все играют швейцарку. В разных видах соревнований. Много онлайн сервисов. Многие проводят очные турниры и как-то ведут таблицы по швейцарке.
Но нет ни одного упоминания КАК все они избегают повторов.

Или это профессиональная тайна?

С уважением, Назим Ахундов.

4

Re: Повторные матчи в швейцарской системе

Рекомендую ознакомиться
https://en.m.wikipedia.org/wiki/Swiss-system_tournament

Там масса информации: достоинства и недостатки, описание вариантов для разных видов спорта и т.д.

Ключевая, на мой взгляд, фраза

The detailed pairing rules are different in different variations of the Swiss system. As they are quite complicated, and it is undesirable to have a long delay between rounds to decide the pairings, the tournament organizer often uses a computer program to do the pairing.

Мой перевод

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

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

Замечу, что встречал серьезные исследования, где доказывалось, что случайная жеребьевка ничем не хуже составления пар на основании очковых групп. И я не понимаю, почему надо всеми силами избегать повторных матчей между игроками. На финише швейцарки до N поражений повторы идут один за другим. Если убрать это ограничение, то работа организатора станет намного легче и можно будет обойтись без компьютера.

5

Re: Повторные матчи в швейцарской системе

panbg2 пишет:

Рекомендую ознакомиться
https://en.m.wikipedia.org/wiki/Swiss-system_tournament

Там масса информации: достоинства и недостатки, описание вариантов для разных видов спорта и т.д.

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

panbg2 пишет:

Мне очень нравится сайт DrawBoss - бесплатен, понятен, удобен в управлении, ход турнира виден всем желающим через интернет.

Зарегистрировался, посмотрел. Наверное кому-то пригодится. Наверное - удобно.
Но на вопрос темы не отвечает.

С позицией, что надо отказаться от стремления избегать повторы - лично я согласен полностью. И, если бы я решал, что делать - то на этом бы и закрыл вопрос.

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

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

В таких случаях применяют эвристику. А это нераспаханная целина.

Возможно, стоило бы поискать Эйлеров цикл (или путь). Алгоритм его поиска на порядки быстрее. Но тогда нужны дополнительные процедуры отсеивания не подходящих нам вариантов.

Так что с точки зрения дискретной математики - задача исключения повторов в швейцарке тянет на серьезное научное исследование.

Возможно, кто-то уже это сделал. Я не нашел.
Если кто видел, слышал, читал - дайте ссылку, буду благодарен.

С уважением, Назим Ахундов.

6

Re: Повторные матчи в швейцарской системе

https://handbook.fide.com

Про швейцарку С.04

Официальные документы на русском
http://www.consultant.ru/document/cons_ … 95c950a41/
https://www.consultant.ru/document/cons … ad7fb8f01/

Обсуждение программистов
https://coderoad.ru/28629235/%D0%A8%D0% … 0%B8%D1%8F

7

Re: Повторные матчи в швейцарской системе

Андрей!

Спасибо за информацию.
Первую ссылку на документацию ФИДЕ я не осилю.
В этом океане текста найти то, что мне нужно - непосильная для меня задача.
Хотя именно там наиболее вероятно найти полный ответ.

Консультант открыть не смог. Но попробую найти тех, у кого есть доступ и почитаю.

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

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

С уважением, Назим Ахундов.

8

Re: Повторные матчи в швейцарской системе

Перевод правил ФИДЕ на русский.

Post's attachments

FIDE-arbierts-instruction-2020.pdf 5.61 mb, 3 downloads since 2021-05-11 

You don't have the permssions to download the attachments of this post.

9

Re: Повторные матчи в швейцарской системе

panbg2 пишет:

Перевод правил ФИДЕ на русский.

Спасибо! Изучаю.

С уважением, Назим Ахундов.

10

Re: Повторные матчи в швейцарской системе

panbg2 пишет:

Перевод правил ФИДЕ на русский.

Из всего этого большого объема информации следует, на мой взгляд:

1. Недопущение повторной игры является для ФИДЕ абсолютным приоритетом.

2. В инструкциях ФИДЕ даны только целеполагания: .."то-то надо сделать так, чтобы то-то..." Это в нашем случае ничем не помогает.

3. Составление пар, как процедура описанная в материале по ссылке - некоторое количество громоздких и сложных для реализации правил "спаривания" и процедур "перемешивания". Никаких намеков на методику, как избежать повторов нет.

4. Это не решает главный вопрос.

Я на этом изыскания закончу.

Но все равно спасибо. Посмотрел, как работает регуляторная система ФИДЕ. Было познавательно.

С уважением, Назим Ахундов.

11

Re: Повторные матчи в швейцарской системе

Методика есть вот в этом научном труде.
https://www.google.com/url?sa=t&sou … NR3fh8aB1P

12

Re: Повторные матчи в швейцарской системе

panbg2 пишет:

Методика есть вот в этом научном труде.
https://www.google.com/url?sa=t&sou … NR3fh8aB1P

Да. Кажется, это именно то, что надо.
Буду изучать.

Кстати, основной вывод из работы, что нет смысла городить огород с швейцаркой. Никакой разницы она по сранению с чистым рандомом на все туры не дает.

Не знаю, насколько автор прав...

И автор подчеркивает, что просчитать рассадку швейцарки можно только с использованием современных алгоритмов взвешенных графов.
Это за пределами моих познаний в теории графов.
Дам почитать сыну.
Потом напишу.

Спасибо, Андрей!

С уважением, Назим Ахундов.