- В этой теме 49 ответов, 12 участников, последнее обновление 13 лет, 10 месяцев назад сделано
.
-
Сообщения
-
Пока такой не существует. Может быть кто из программистов возьмется увековечить свое имя? Постановку задачи сделаем сообща. Редко кто не сталкивался с проблемой жеребьевки на турнирах. Сейчас кто-то пользуется досовской прогрпммой, с лоскутным переводом Верховых, кто-то голландской, кто-то вообще шахматной программой, которая учитывает цвет в первой партии 😯
Сколько может стоить создание такой программы?
Сергей,
вы беретесь сделать такую программу? Вот молодчина! Со своей стороны я обещаю партий в PDN
Я могу вам прислать то, чем сейчас пользуются. Вроде у голландцев есть демка на сайте. И, если я верно понимаю, пол-программы — это точная постановка задания. Прошу тех, кто судит соревнования высказываться, какие критерии бывают существенными при определении пар в швейцарке?
Вот, что я вижу навскидку —
— набранные очки
— рейтинг
— коэффициент (а они считаются по разным схемам)
— «спуски» и «подъемы»
— случайный жребийИ нужно иметь возможность задавать любой порядок и число таких критериев для определения пар по жребию.
Александр,
конечно присылайте. Но, обязательно, напишите комментарии и несколько общих слов от себя. Многих очевидных для Вас вещей я просто не знаю, поэтому лучше формализовать все зараанее.
Сергей
Tut ne tolko shveytsarka, Nado postavit krugovuyu systemu tozhe. Napriver vce byvshie russkie shashisti postoyanno pitayutsya «korrectirovat» amerikantsev kotorie polzuyutsya izumiteleno prostoy «round robin» systemoy.
Ya predstavlyayu sebe programmu na internete gde mozhno budet zasunut list uchastnikov, rezultati tura, i poluchat rasspisanie! Ya kogda to kupil shahmatnuyu programu v Avstralii — ne podoshla…Для швейцарской системынеплохо бы добавить возможность выбывыния, в зависимости от того, сколько игрок потерял очков. Например, при постановке опции (-2) шашисты, которые посте двух туров наберут 0 очков, выбывают, после трёх не более 1 и т.д.
Круговую систему действительно надо бы добавить. Кроме того, неплохо, чтоб были ещё три системы:
-Матч
-Схвенингемская
-ОлимпийскаяЧто-то обсуждение данной темы заглохло давненько. А желающие сделать программу жеребьевки не исчезли.
Может кто-то из судей или энтузиастов прислать четко сформулированные правила жеребьевки турниров? Пока же я предлагаю реккомендации ФМЖД по этому вопросу. Может кто-нибудь переведет этот текст на русский?А вот замечания Владимира Шулюпова по вопросу работы над программой жеребьевки (печатается в надежде, что автор не обидится, что это с ним не согласовано).
Я бы в обсуждении этого вопроса немного сместил акценты. Считаю, что нужно, чтобы С.Старцев или какой-либо иной автор будущей программы вначале создал бы мало-мальски работающий вариант, а лишь потом мы бы стали обсуждать, что в ней изменить. Дело в том, что, как мне кажется, написать программу, которая жеребила бы с учётом одного-единственного критерия: «Игроки не играют между собой дважды», даже не учитывать очки, — и то не просто. Если Вы считаете, что я преувеличиваю проблему, то дайте мне ответ в следующей, по сути, чисто математической задаче:
В турнире по швейцарке играют 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 байт, посмотреть на неё полезно.
Всё это уже давно известно в математике и информатике, и велосипед изобретать не надо. Вопрос только кто из программистов захочет сделать удобный интерфейс к этому алгоритму
Собственно, была бы федерация заинтересована в наличии такой программы давно бы уже заказала разработку, думаю, любой приличный студент старших-средних курсов справился бы)Всё это уже давно известно в математике и информатике, и велосипед изобретать не надо. Собственно, была бы федерация заинтересована в наличии такой программы давно бы уже заказала разработку, думаю, любой приличный студент старших-средних курсов справился бы
Отлично! Может тогда Вы поделитесь ответом на вопрос, чему равно k? ФИДЕ более богатая организация, чем, например, ФМЖД, ФШР, ФМШ, но почему-то до конца решить проблему не может. Может не попался такой студент. Алгоритмы — это отлично (если не трудно, укажите список литературы, хочу почитать), но, похоже, эти алгоритмы в определённых ситуациях не работают. Может потому, что в этих ситуациях вообще нет решения??? Рад буду ошибиться.
Может кто-нибудь переведет этот текст на русский?
Переводить ничего не надо. У меня где-то лежат правила ФИДЕ, изданные на русском языке. Там всё это есть. Завтра найду, отсканирую и пришлю.
Отлично! Может тогда Вы поделитесь ответом на вопрос, чему равно k?
Не особо силен в математике со школьных годов, но, очевидно, при такой постановке вопроса — единственном условии игроки дважды не играют друг с другом, количество туров, которые они могут сыграть друг с другом равно n-1 💡
Таким образом, k в задаче alkanda будет равно n-2
Надеюсь строгое доказательство не потребуете?[Не особо силен в математике со школьных годов, но, очевидно, при такой постановке вопроса — единственном условии игроки дважды не играют друг с другом, количество туров, которые они могут сыграть друг с другом равно 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 туров», так как не исключено, что существует пример, когда не получится провести и меньшее число туров. Но проблема не только в этом. Даже если в некоторых ситуациях и существуют (один или несколько) вариантов разбиения на пары, удовлетворяющих критерию «игроки не играют между собою дважды», но этих вариантов — ничтожное количество в сравнении с общим числом возможных разбиений на пары, то мощностей современных компьютеров для решения этой задачи может просто не хватить (при достаточно большом числе участников). Заметьте, что я виду речь о том, что при жеребьёвке учитывается только один единственный критерий «игроки не играют между собою дважды»; а в реальной «швейцарке» присутствуют и другие: набранные очки, цвет, спуски-подъёмы и т.п. Т.е., я почти утверждаю, что пока в правилах швейцарки критерий «игроки не играют между собою дважды» не перейдёт из разряда незыблемых в разряд «допускающих нарушение в исключительных случаях», эти правила останутся некорректными, что естественным образом отразится на проблеме составления соответствующих программ.
Думаю, что непониманием этой проблемы во многом объясняется тот факт, что множество программистов, берущихся за решение «элементарной» задачи программирования либо бросают это гнилое дело, либо долго борятся с зависанием программы, не отдавая себе отчёт об истинных причинах этого явления.
- Для ответа в этой теме необходимо авторизоваться.