| Автор |
Сообщение |
Shulyupov |
|
Тема сообщения:
 Отправлено: Июль 03, 2005 - 03:16 PM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а):
Это - правила шахматной федерации, Алканд интересовался мнением шашечных федераций. Впрочем, это как раз то, переводом чего он интересовался. Так что у меня теперь нет необходимости сканировать и пересылать. |
|
|
| |
|
|
|
 |
|
Shulyupov |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 03:07 PM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а): Хотя интересно, за всю историю применения были ли проблемы со швейцарской системой в турнирах.
Зачем Вам история? Возьмите любую существующую программу, проведите эксперемент при разном числе участников (побольше) и туров, станет всё понятно. |
|
|
| |
|
|
|
|
|
Shulyupov |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 03:05 PM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а):
Совершенно верно, Вы когда-нибудь видели чтобы в круговой системе игроки дважды играли друг с другом (в один круг) 
Таким образом, можно утверждать что имеется возможность сыграть n-1 туров и по швейцарке. Естественно, если проводить жеребьевку по турам оптимально. Как указал Владимир, при желании можно и извратиться и загнать себя в тупик  Думаю, при желании можно подсчитать количество таких тупиков и поделить на общее количество возможностей провести турнир, не думаю что вероятность будет значительной, так что не думаю что нужно отказываться правила не играть дважды.
В турнире по круговой системе заранее известны не только результаты "жеребьёвки" очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку "оптимально", то какая же это будет "швейцарка"? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур? Пример, который я привёл, - самый простейший и при желании можно привести массу других. Вероятность не так мала как Вам кажется, она неуклонно возрастает с каждым туром. |
|
|
| |
|
|
|
|
|
AlexanderS |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 01:41 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
Nrekto писал(а): Тогда получается, что как по круговой системе.
Совершенно верно, Вы когда-нибудь видели чтобы в круговой системе игроки дважды играли друг с другом (в один круг)
Таким образом, можно утверждать что имеется возможность сыграть n-1 туров и по швейцарке. Естественно, если проводить жеребьевку по турам оптимально. Как указал Владимир, при желании можно и извратиться и загнать себя в тупик Думаю, при желании можно подсчитать количество таких тупиков и поделить на общее количество возможностей провести турнир, не думаю что вероятность будет значительной, так что не думаю что нужно отказываться правила не играть дважды. Хотя интересно, за всю историю применения были ли проблемы со швейцарской системой в турнирах.
Shulyupov писал(а): Это вроде не "задача alkanda', а скорее моя задача. Читайте внимательнее начало сообщения alkanda.
Извиняюсь, не заметил.
Во всяком случае, известно, что если задача разбиения на пары (насколько я понимаю, при любом количестве мыслимых параметров) имеет решения, то хотя бы одно из них можно найти за время О(n^2), множество всех решений, если хочется сравнить и выбрать наиудачнейший, находится за О(n^3 log n+(n^2)r)
Alkand писал(а): И хорошо бы все же ознакомиться с трактовкой ФМЖД по жеребьевке швейцарки. Или с тем, что есть по этому поводу у наших федераций.
http://www.sportzone.ru/sport/rules.htm ... chapter=05 |
|
|
| |
|
|
|
|
|
Alkand |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 12:11 PM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
Одним из решений мне видится здесь отказ от принципа, при котором участники не могут встречаться дважды. Это можно было бы сделать для, например 25-30% игроков нижней части таблицы.
И хорошо бы все же ознакомиться с трактовкой ФМЖД по жеребьевке швейцарки. Или с тем, что есть по этому поводу у наших федераций. |
|
|
| |
|
|
|
|
|
Shulyupov |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 12:04 PM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а): Таким образом, k в задаче alkanda будет равно n-2
Это вроде не "задача alkanda', а скорее моя задача. Читайте внимательнее начало сообщения alkanda. |
|
|
| |
|
|
|
|
|
Shulyupov |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 11:58 AM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а): [Не особо силен в математике со школьных годов, но, очевидно, при такой постановке вопроса - единственном условии игроки дважды не играют друг с другом, количество туров, которые они могут сыграть друг с другом равно n-1 
Таким образом, k в задаче alkanda будет равно n-2
Надеюсь строгое доказательство не потребуете?
Этот факт не только не является очевидным, он просто является неверным.Поэтому, вместо того, чтобы требовать с Вас доказательство, приведу простое его опровержение. Пусть в турнире играет 18 человек (вместо 18 подойдёт любое число, делящееся на 2, но не делящееся на 4). Сыграно 9 туров, причём получилось так, что в них каждых игрок с №№1-9 переиграл со всеми участниками с №№10-18 и наоборот, это как раз по 9 партий, никто из игроков с №№1-9 (точно также как и никто из игроков с №№10-18 ) , очевидно, не играл между собой. Перед нами стоит задача разбить участников на пары в 10-м туре. Как мы с нею справимся? Никак. Действительно, игроки, например, из группы с №№1-9 могут играть только междц собой (с другими они переиграли), но их нечётное число и на пары разбить их НЕВОЗМОЖНО. Таким образом, доказано, что при 18 участников можно гарантировать не более чем 9 туров. Заметьте, что я сказал "не более 9 туров", а не "9 туров", так как не исключено, что существует пример, когда не получится провести и меньшее число туров. Но проблема не только в этом. Даже если в некоторых ситуациях и существуют (один или несколько) вариантов разбиения на пары, удовлетворяющих критерию "игроки не играют между собою дважды", но этих вариантов - ничтожное количество в сравнении с общим числом возможных разбиений на пары, то мощностей современных компьютеров для решения этой задачи может просто не хватить (при достаточно большом числе участников). Заметьте, что я виду речь о том, что при жеребьёвке учитывается только один единственный критерий "игроки не играют между собою дважды"; а в реальной "швейцарке" присутствуют и другие: набранные очки, цвет, спуски-подъёмы и т.п. Т.е., я почти утверждаю, что пока в правилах швейцарки критерий "игроки не играют между собою дважды" не перейдёт из разряда незыблемых в разряд "допускающих нарушение в исключительных случаях", эти правила останутся некорректными, что естественным образом отразится на проблеме составления соответствующих программ.
Думаю, что непониманием этой проблемы во многом объясняется тот факт, что множество программистов, берущихся за решение "элементарной" задачи программирования либо бросают это гнилое дело, либо долго борятся с зависанием программы, не отдавая себе отчёт об истинных причинах этого явления. |
Последний раз редактировалось Shulyupov в Июль 03, 2005 - 12:12 PM; всего редактировалось 1 раз
|
| |
|
|
|
|
|
Nrekto |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 11:08 AM
|
|
Зарегистрирован: Июль 02, 2005
Сообщений: 4
|
|
| Тогда получается, что как по круговой системе. |
|
|
| |
|
|
|
|
|
AlexanderS |
|
|
Тема сообщения: Re: Александр, не заморачивайтесь вы по поводу алгоритмов
Отправлено: Июль 03, 2005 - 06:58 AM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
Shulyupov писал(а): Отлично! Может тогда Вы поделитесь ответом на вопрос, чему равно k?
Не особо силен в математике со школьных годов, но, очевидно, при такой постановке вопроса - единственном условии игроки дважды не играют друг с другом, количество туров, которые они могут сыграть друг с другом равно n-1
Таким образом, k в задаче alkanda будет равно n-2
Надеюсь строгое доказательство не потребуете? |
|
|
| |
|
|
|
|
|
Shulyupov |
|
|
Тема сообщения:
Отправлено: Июль 03, 2005 - 02:50 AM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
Alkand писал(а): Может кто-нибудь переведет этот текст на русский?
Переводить ничего не надо. У меня где-то лежат правила ФИДЕ, изданные на русском языке. Там всё это есть. Завтра найду, отсканирую и пришлю. |
|
|
| |
|
|
|
|
|
Shulyupov |
|
|
Тема сообщения: Re: Александр, не заморачивайтесь вы по поводу алгоритмов
Отправлено: Июль 03, 2005 - 02:41 AM
|
|
Зарегистрирован: Авг 27, 2002
Сообщений: 190
Откуда : Тула
|
|
AlexanderS писал(а): Всё это уже давно известно в математике и информатике, и велосипед изобретать не надо. Собственно, была бы федерация заинтересована в наличии такой программы давно бы уже заказала разработку, думаю, любой приличный студент старших-средних курсов справился бы
Отлично! Может тогда Вы поделитесь ответом на вопрос, чему равно k? ФИДЕ более богатая организация, чем, например, ФМЖД, ФШР, ФМШ, но почему-то до конца решить проблему не может. Может не попался такой студент. Алгоритмы - это отлично (если не трудно, укажите список литературы, хочу почитать), но, похоже, эти алгоритмы в определённых ситуациях не работают. Может потому, что в этих ситуациях вообще нет решения??? Рад буду ошибиться. |
|
|
| |
|
|
|
|
|
AlexanderS |
|
|
Тема сообщения: Александр, не заморачивайтесь вы по поводу алгоритмов
Отправлено: Июль 01, 2005 - 11:34 PM
|
|
Зарегистрирован: Авг 29, 2002
Сообщений: 845
Откуда : Якутск
|
|
Всё это уже давно известно в математике и информатике, и велосипед изобретать не надо. Вопрос только кто из программистов захочет сделать удобный интерфейс к этому алгоритму
Собственно, была бы федерация заинтересована в наличии такой программы давно бы уже заказала разработку, думаю, любой приличный студент старших-средних курсов справился бы ) |
|
|
| |
|
|
|
|
|
Alkand |
|
|
Тема сообщения:
Отправлено: Июль 01, 2005 - 09:42 AM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
А вот замечания Владимира Шулюпова по вопросу работы над программой жеребьевки (печатается в надежде, что автор не обидится, что это с ним не согласовано).
Я бы в обсуждении этого вопроса немного сместил акценты. Считаю, что нужно, чтобы С.Старцев или какой-либо иной автор будущей программы вначале создал бы мало-мальски работающий вариант, а лишь потом мы бы стали обсуждать, что в ней изменить. Дело в том, что, как мне кажется, написать программу, которая жеребила бы с учётом одного-единственного критерия: "Игроки не играют между собой дважды", даже не учитывать очки, - и то не просто. Если Вы считаете, что я преувеличиваю проблему, то дайте мне ответ в следующей, по сути, чисто математической задаче:
В турнире по швейцарке играют n (n - чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: "Игроки не играют между собой дважды".
Лично я не знаю ответ в этой задаче (хотя, возможно, эта задача и имеет известное решение). А если ещё добавить другие критерии типа цвета, спуски-подъёмы и т.п., то задача будет ещё сложнее. Зачем я говорю о всём этом? Да дело в том, что это только свиду кажется, что написал порядок критереев, то программу легко написать. А на деле оказывается, что на каком-то этапе в какой-то группе (для простоты предположим, что в каждой очковой группе имеется по чётному числу участников) не удаётся сформировать группы, приходится двоих "опускать" ниже и т.д., а если ничего не получится, то приходится "поднимать" и и т.д. Короче, с точки зрения программирования, процесс теряет управляемость и нет уверенности, что он всегда приведёт к "решению". Чем с этим бороться? Теоретически - просто: составляем множество всех "корректных разбиений на пары, придумываем функцию "несправедливости", зависящую от параметров, т.е от количества пар с разным количеством очков, с "плохим цветом" и т.п. и выбираем то разбиение на пары, где значение этой функции меньше, т.е. "оптимальное" разбиение. Но на деле число таких пар (корректных и некорректных вместе) равно 1*3*5*...*(n-3)*(n-1), т.е. имеет порядок факториала, поэтому даже при n порядка нескольких десятков, уровень развития современной вычислительной техники не позволяет перебрать все разбиения на предмет корректности. Возьмите известную Вам по Оводову sw-46rus (кстати, Вы читали sw-46rus.txt?). Как Вы видели, жеребьёвка проходит мгновенно. Но это только в таких турнирах. Я провёл эксперимент. Составил тестовый турнир с 200 участниками, с номерами от 1 по 200, "перемешал" их. Для простоты принял, что всегда побеждает меньший номер. И что же? В первых турах жеребьёвка идёт мгновенно, а вот дальше: всё дольше и дольше. Причём при жеребьёвке программа спрашивает, какой метод (ветвей и границ или взвешивания) применять - я не знаю, что это за методы, видимо какой-то неполный перебор. В некоторых случаях у меня не хватило терпения дождаться результатов жеребьёвки. Видимо, даже ФИДЕ понимает, что до сих пор нет нормальной программы. В 2001-2002 годах на сайте ФИДЕ усиленно рекламировался Chess Tournament Administrator, как самая лучшая программа и всем предлагалось её скачать. Я скачивал вначале бету, потом релиз. Впечатление такие: это супернавороченная программа, с функциями типа того, что Вы затронули в письме, но в плане швейцарки всё примерно так, как в sw-46rus, но она почему-то регулярно зависает. Но вот в 2003 году все упоминания об этой программе бесследно исчезли с сайта. Если у Вас нет этой программы, то готов прислать - 2 886 144 байт, посмотреть на неё полезно. |
|
|
| |
|
|
|
|
|
Alkand |
|
|
Тема сообщения:
Отправлено: Июль 01, 2005 - 07:32 AM
|
|
Зарегистрирован: Июль 16, 2002
Сообщений: 3653
Откуда : Москва
|
|
Что-то обсуждение данной темы заглохло давненько. А желающие сделать программу жеребьевки не исчезли.
Может кто-то из судей или энтузиастов прислать четко сформулированные правила жеребьевки турниров? Пока же я предлагаю реккомендации ФМЖД по этому вопросу. Может кто-нибудь переведет этот текст на русский? |
| Описание: |
| Официальные реккомендации ФМЖД для швейцарки. |
|
Скачать |
| Имя файла: |
Swiss.rar |
| Размер: |
13.22 KB |
| Скачано: |
621 Раз(а) |
|
| |
|
|
|
|
|
Artom |
|
|
Тема сообщения:
Отправлено: Авг 20, 2004 - 07:41 AM
|
|
Зарегистрирован: Фев 10, 2003
Сообщений: 17
|
|
Для швейцарской системынеплохо бы добавить возможность выбывыния, в зависимости от того, сколько игрок потерял очков. Например, при постановке опции (-2) шашисты, которые посте двух туров наберут 0 очков, выбывают, после трёх не более 1 и т.д.
Круговую систему действительно надо бы добавить. Кроме того, неплохо, чтоб были ещё три системы:
-Матч
-Схвенингемская
-Олимпийская |
|
|
| |
|
|
|
|
|
|
|
Главная 
FAQ
Поиск
Регистрация
Войти и проверить личные сообщения
Войти 
Под-Форум
Maximize
Поиск по сайту