- В этой теме 49 ответов, 12 участников, последнее обновление 13 лет, 10 месяцев назад сделано
.
-
Сообщения
-
Одним из решений мне видится здесь отказ от принципа, при котором участники не могут встречаться дважды. Это можно было бы сделать для, например 25-30% игроков нижней части таблицы.
И хорошо бы все же ознакомиться с трактовкой ФМЖД по жеребьевке швейцарки. Или с тем, что есть по этому поводу у наших федераций.Тогда получается, что как по круговой системе.
Совершенно верно, Вы когда-нибудь видели чтобы в круговой системе игроки дважды играли друг с другом (в один круг)
Таким образом, можно утверждать что имеется возможность сыграть n-1 туров и по швейцарке. Естественно, если проводить жеребьевку по турам оптимально. Как указал Владимир, при желании можно и извратиться и загнать себя в тупик
Думаю, при желании можно подсчитать количество таких тупиков и поделить на общее количество возможностей провести турнир, не думаю что вероятность будет значительной, так что не думаю что нужно отказываться правила не играть дважды. Хотя интересно, за всю историю применения были ли проблемы со швейцарской системой в турнирах.Это вроде не «задача alkanda’, а скорее моя задача. Читайте внимательнее начало сообщения alkanda.
Извиняюсь, не заметил.
Во всяком случае, известно, что если задача разбиения на пары (насколько я понимаю, при любом количестве мыслимых параметров) имеет решения, то хотя бы одно из них можно найти за время О(n^2), множество всех решений, если хочется сравнить и выбрать наиудачнейший, находится за О(n^3 log n+(n^2)r)
И хорошо бы все же ознакомиться с трактовкой ФМЖД по жеребьевке швейцарки. Или с тем, что есть по этому поводу у наших федераций.
http://www.sportzone.ru/sport/rules.html?sport=chess&chapter=05
Совершенно верно, Вы когда-нибудь видели чтобы в круговой системе игроки дважды играли друг с другом (в один круг)
Таким образом, можно утверждать что имеется возможность сыграть n-1 туров и по швейцарке. Естественно, если проводить жеребьевку по турам оптимально. Как указал Владимир, при желании можно и извратиться и загнать себя в тупик Думаю, при желании можно подсчитать количество таких тупиков и поделить на общее количество возможностей провести турнир, не думаю что вероятность будет значительной, так что не думаю что нужно отказываться правила не играть дважды. В турнире по круговой системе заранее известны не только результаты «жеребьёвки» очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку «оптимально», то какая же это будет «швейцарка»? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур? Пример, который я привёл, — самый простейший и при желании можно привести массу других. Вероятность не так мала как Вам кажется, она неуклонно возрастает с каждым туром.
Хотя интересно, за всю историю применения были ли проблемы со швейцарской системой в турнирах.
Зачем Вам история? Возьмите любую существующую программу, проведите эксперемент при разном числе участников (побольше) и туров, станет всё понятно.
http://www.sportzone.ru/sport/rules.html?sport=chess&chapter=05
Это — правила шахматной федерации, Алканд интересовался мнением шашечных федераций. Впрочем, это как раз то, переводом чего он интересовался. Так что у меня теперь нет необходимости сканировать и пересылать.
В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Лично я не знаю ответ в этой задаче (хотя, возможно, эта задача и имеет известное решение). А если ещё добавить другие критерии типа цвета, спуски-подъёмы и т.п., то задача будет ещё сложнее.Задача не такая простая и элементарная, как может показаться на первый взгляд. И она действительно является принципиальной не только для написания программы жеребьевки, но и вообще для организации соревнований по швейцарке. Сколько конфликтов и скандалов за свою шашечную жизнь я наблюдал, когда при жеребьевке «вручную» один из лидеров опускался более чем на две очковые группы. Судей обвиняли во всех смертных, а на самом деле другого решения и не было. Одним из возможных решений этой проблемы может быть заложение в программу алгоритма, что играется не более определенного количества туров при ккаждом числе участников.
Даже если в некоторых ситуациях и существуют (один или несколько) вариантов разбиения на пары, удовлетворяющих критерию «игроки не играют между собою дважды», но этих вариантов — ничтожное количество в сравнении с общим числом возможных разбиений на пары, то мощностей современных компьютеров для решения этой задачи может просто не хватить (при достаточно большом числе участников). Заметьте, что я виду речь о том, что при жеребьёвке учитывается только один единственный критерий «игроки не играют между собою дважды»; а в реальной «швейцарке» присутствуют и другие: набранные очки, цвет, спуски-подъёмы и т.п. Т.е., я почти утверждаю, что пока в правилах швейцарки критерий «игроки не играют между собою дважды» не перейдёт из разряда незыблемых в разряд «допускающих нарушение в исключительных случаях», эти правила останутся некорректными, что естественным образом отразится на проблеме составления соответствующих программ.
В турнире по круговой системе заранее известны не только результаты «жеребьёвки» очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку «оптимально», то какая же это будет «швейцарка»? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур?
Владимир, «участники не играют между собой дважды» является незыблимым для швейцарки. Хотел было сначала предложить заложить в основу программы предварительную проверку возможности в дальнейшем организовать полностью n-1 тур, в конце концов спуски/подъемы, цвет не столь принципиальны, но увидел Ваши аргументы, что это не реально для существующих компьютеров. Может быть с учетом ограничения числа туров в зависимости от числа участников эта задача становится реальной?
Во всяком случае, известно, что если задача разбиения на пары (насколько я понимаю, при любом количестве мыслимых параметров) имеет решения, то хотя бы одно из них можно найти за время О(n^2), множество всех решений, если хочется сравнить и выбрать наиудачнейший, находится за О(n^3 log n+(n^2)r)
1) Вот тут, пожалуйста, поподробнее. Я тут, между делом, обзвонил нескольких специалистов по близким вопросам с просьбой прокоментировать ваше утверждение, но все разводят руки. Всем кажется, что порядок должен быть факториальный. Если можно, объясните, в чём суть такого алгоритма, или укажите литературу.
2) Правильно ли я Вас понял, что для существования первой оценки достаточно знать то, что решение есть, или всё же его ещё и нужно знать.
3) Если Вы правы, то это снимает все проблемы. Вряд ли проблема перебора кубического порядка является серьёзной для современных компьютеров. Особенно, если n не превосходит сотни с небольшим, как в шашечных турнирах.
4) В связи с п.3 вопрос ко всем: «Какое максимальное число участников когда-либо играло в шашки в турнире по швейцарке?»4) В связи с п.3 вопрос ко всем: «Какое максимальное число участников когда-либо играло в шашки в турнире по швейцарке?»
Наверно число 300 более, чем достаточно, исходя из количества шашистов (наличия инвентаря, большого помещения). Массовые турниры с числом близким к 200 иногда проводятся.
В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Лично я не знаю ответ в этой задаче (хотя, возможно, эта задача и имеет известное решение). А если ещё добавить другие критерии типа цвета, спуски-подъёмы и т.п., то задача будет ещё сложнее.Задача не такая простая и элементарная, как может показаться на первый взгляд. И она действительно является принципиальной не только для написания программы жеребьевки, но и вообще для организации соревнований по швейцарке. Сколько конфликтов и скандалов за свою шашечную жизнь я наблюдал, когда при жеребьевке «вручную» один из лидеров опускался более чем на две очковые группы. Судей обвиняли во всех смертных, а на самом деле другого решения и не было. Одним из возможных решений этой проблемы может быть заложение в программу алгоритма, что играется не более определенного количества туров при ккаждом числе участников.
Даже если в некоторых ситуациях и существуют (один или несколько) вариантов разбиения на пары, удовлетворяющих критерию «игроки не играют между собою дважды», но этих вариантов — ничтожное количество в сравнении с общим числом возможных разбиений на пары, то мощностей современных компьютеров для решения этой задачи может просто не хватить (при достаточно большом числе участников). Заметьте, что я виду речь о том, что при жеребьёвке учитывается только один единственный критерий «игроки не играют между собою дважды»; а в реальной «швейцарке» присутствуют и другие: набранные очки, цвет, спуски-подъёмы и т.п. Т.е., я почти утверждаю, что пока в правилах швейцарки критерий «игроки не играют между собою дважды» не перейдёт из разряда незыблемых в разряд «допускающих нарушение в исключительных случаях», эти правила останутся некорректными, что естественным образом отразится на проблеме составления соответствующих программ.
В турнире по круговой системе заранее известны не только результаты «жеребьёвки» очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку «оптимально», то какая же это будет «швейцарка»? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур?
Владимир, «участники не играют между собой дважды» является незыблимым для швейцарки. Хотел было сначала предложить заложить в основу программы предварительную проверку возможности в дальнейшем организовать полностью n-1 тур, в конце концов спуски/подъемы, цвет не столь принципиальны, но увидел Ваши аргументы, что это не реально для существующих компьютеров. Может быть с учетом ограничения числа туров в зависимости от числа участников эта задача становится реальной?
Александр, что же Вы хотите от людей, если и программам не сладко?
А сколько именно туров Вы считаете можно обеспечить? Пока я думаю, что могу доказать, что можно «обеспечить, что-то типа немного больше, чем двоичный логарифм от числа участников. Но это очень мало.
Незыблемого ничего нет. Кстати в каком-то древнем шашечном или шахматном кодексе СССР я читал, что в самом крайнем случае можно играть дважды. К тому же, что по вашему мнению является менее справедливым со спортивной точки зрения: кто-то сыграет 2-й раз, или лидера в последнем туре опустят через 2 группы. В факте игры 2-й или более раз нет вообще абсолютно ничего несправедливого (это поклон круговой системе, а причём тут она), только некоторое уменьшение интереса, но с этим вполне можно смириться. Представьте ситуацию: двое сильно оторвались от других. Они будут играть между собой, пока кого-то из них не догонят. Но если его догонят, он будет иметь преимущество по Бухгольцу перед догнавшим его.
Представьте, как легко будет проводить жеребьёвку в турнирах с микроматчами (т.е. без учёта цвета), если отказаться от ограничения числа партий между двумя участниками ВООБЩЕ. Учитываем только набранные очки, Бухгольц, далее Бухгольц от Бухгольца или номер по жеребьёвке и всё. Никаких разночтений, и, по сути, никакая программа и не нужна (если судьи будут оперативно считать Бухгольцы после каждого тура). Никаких сомнительных спусков и подъёмов. Может кто-то и сыграет 2, а то и 3 раза. Зато — полная справедливость.1) Вот тут, пожалуйста, поподробнее. Я тут, между делом, обзвонил нескольких специалистов по близким вопросам с просьбой прокоментировать ваше утверждение, но все разводят руки. Всем кажется, что порядок должен быть факториальный. Если можно, объясните, в чём суть такого алгоритма, или укажите литературу.
2) Правильно ли я Вас понял, что для существования первой оценки достаточно знать то, что решение есть, или всё же его ещё и нужно знать.Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда. А вообще работ по смежным темам достаточно, начиная с 50-х годов.
Я конечно не специалист по дискретной математике, но не понимаю почему всех удивляет то, что можно эффективно найти решение на рассматриваемом множестве, но никого не удивляет что скажем шашечные программы перебирают на 20 с лишним полуходов за считанные секунды, при том что 5 в двадцатых степенях число тоже не особо маленькоеПоследнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда. А вообще работ по смежным темам достаточно, начиная с 50-х годов.
Спасибо. А Вы уверены, что «цифры» относятся именно к этой проблеме?
Я конечно не специалист по дискретной математике, но не понимаю почему всех удивляет то, что можно эффективно найти решение на рассматриваемом множестве, но никого не удивляет что скажем шашечные программы перебирают на 20 с лишним полуходов за считанные секунды, при том что 5 в двадцатых степенях число тоже не особо маленькое
Не удивляет, это совершенно разные проблемы. А Вас, Александр, не удивляет, что системы линейных уравнений, если не ошибаюсь, 11-го порядка не под силу современной вычислительной технике?
Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда.
P.S. Ещё раз спасибо. Скачал, приступаю к изучению.
А сколько именно туров Вы считаете можно обеспечить? Пока я думаю, что могу доказать, что можно «обеспечить, что-то типа немного больше, чем двоичный логарифм от числа участников. Но это очень мало.
Конечно 4 тура для 16 участников не достаточно. Интуитивно представляю, что можно обеспечить n/2 туров, неслучайно и Вы не смогли привести пример с меньшим числом. Для выполнения основной функции швейцарки — наиболее объективное определение в наиболее короткие сроки из большого количества участников сильнейшей группы, этого вполне достаточно. Так для 20 участников 10 туров это более, чем нормально, для 24-х 12. На практике теряется смысл дальше увеличивать число туров с ростом числа участников. Организаторы либо смиряются с падением объективности в определении сильнейших при меньшем числе туров, либо применяют другие системы, например полуфиналы. Поэтому, возможно, достаточно доказать число 10 туров для 20 участников, а при большем числе участников меньший процент туров от их числа будет возможен тем более!? Эта задача чистым перебором для компьютера реальна?
К тому же, что по вашему мнению является менее справедливым со спортивной точки зрения: кто-то сыграет 2-й раз, или лидера в последнем туре опустят через 2 группы. В факте игры 2-й или более раз нет вообще абсолютно ничего несправедливого (это поклон круговой системе, а причём тут она), только некоторое уменьшение интереса, но с этим вполне можно смириться. Представьте ситуацию: двое сильно оторвались от других. Они будут играть между собой, пока кого-то из них не догонят. Но если его догонят, он будет иметь преимущество по Бухгольцу перед догнавшим его.
Отвечу тоже примером. Допустим, при Вашем предположении, перед последним туром двое из верхней группы должны играть во второй (а может быть и в третий) раз между собой. Если они уже находятся в выходящей зоне какой результат будет? Правильно ничья, причем на 5-м ходу. Зачем им рисковать если их все равно уже никто не обгонит даже по коэффициенту, они же его встречей между собой не уменьшат.
- Для ответа в этой теме необходимо авторизоваться.