Ответы в темах
-
Сообщения
-
Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда.
Там эта формула просто приводится без объяснений. Но это не важно, мне примерно понятно, откуда берётся такая оценка. Но верно это в типичных случаях, но не в критических, о чём идёт речь.
P.S. На самом деле, для нас гамильтоновость графа — это даже слишком много. Нам достаточно иметь всего лишь (при n=18):
1-2, 3-4, 5-6, …, 17-18, а вовсе не обязательно:
1-2-3-4-5-6-…-16-17-18-1.Более точное достаточное условие — это теорема Хватала: Если G -обыкновенный граф и d1<= ... <= dn - последовательность степеней вершин графа, то если для всех k верно, что из
dk(т.е. d катое)<=k=n-k, то граф гамильтонов. 1) Обыкновенный граф — это тот, когда любые 2 вершины соединины не более 1 раза?
2) То есть предполагается, что есть одновременно вершины со степенями как меньшими, так и большими n/2? Но какое тогда эта теорема имеет отношение к нашей задаче? К тому же, у нас степени всех вершин вообще одинаковые (=n-1-число сыгранных туров).
Программа очень понятная и простая в освоении и пользовании. Пока не заметил ничего лишнего. Не понятно назначение жирных и тонких горизонтальных линий в списке игроков и в финальных итогах. По-моему совсем не много надо переделки, чтобы применить к шашечным соревнованиям.
1. Отредактировать набор критериев, добавить «количество побед» и «результат личной встречи»
2. Предусмотреть возможность импорта списка игроков из TDam, в идеале возможность связать эти программы так, чтобы набор партии в TDam автоматически вводил информацию(результат) в Администратор, и наоборот клик на результате вызывал партию из TDam.
3. Добавить в окно создания турнира поле «Вид шашек» с автоматическим изменением способа записи результата (1/2:1/2 или 1:1)
4. До конца сделать перевод интерфейса на русский язык.
5. Переработать формы отчетов, таблиц, карточек применительно к принятым в шашках, возможно формы бланков необходимо заложить на 3-х языках.
6. Не нашел форму таблицы «Движение по турам»
7. Проверить систему критериев по котором составляются пары.1. Ну лишнее — это специпично шахматные документы для отправки в ФИДЕ, поддержка рейтинг-листа в форме, в которой он раньше публиковался на его сайте, теперь там другая форма, поддержка электронных досок (у нас это только развивается, впрочем, последнее — Вам видней).
2. Нет таблицы с указанием соперников, не говоря уже о кросс-таблице, а всё это есть даже в более древней шахматной программе SW-46.
3. При жеребьёвке, простановке результатов и т.д. бестолковая необходимость периодически открывать и закрывать окна.
4. Сказать честно, я не вижу (даже без учёта следущего пункта) никаких преимуществ над sw46. Если только то, что написана под Windows, а не под DOS. Эта программа (начиная с беты) у нас уже 3 года, но мы используем по прежнему sw46. Кажется никакие шахматисты Chess Tournament Administrator не используют.
5. Но всё это ерунда по сравнению с главным. Проведите эксперемент (я это делал несколько раз несколько лет назад). Заведите турнир на 200 человек, ставьте от фонаря результаты, пусть, например, выигрывает всегда товарищ с меньшим номером. У Вас не зависло?
В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Владимир, подкинул вчера Вашу задачку на форум ВМиК МГУ, пока за сутки родилось достаточно тривиальное «если мы смогли организовать n-2 тура, то n-1 — й тур возможен всегда.» Но заинтересовавшиеся есть.
Да я эту задачу (при 6 участниках) раньше в разные годы несколько раз давал школьникам на матолимпиадах и матбоях. Правда — не выше областного уровня. Никто не решил..
Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда.
P.S. Ещё раз спасибо. Скачал, приступаю к изучению.
Я конечно не специалист по дискретной математике, но не понимаю почему всех удивляет то, что можно эффективно найти решение на рассматриваемом множестве, но никого не удивляет что скажем шашечные программы перебирают на 20 с лишним полуходов за считанные секунды, при том что 5 в двадцатых степенях число тоже не особо маленькое
Не удивляет, это совершенно разные проблемы. А Вас, Александр, не удивляет, что системы линейных уравнений, если не ошибаюсь, 11-го порядка не под силу современной вычислительной технике?
Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда. А вообще работ по смежным темам достаточно, начиная с 50-х годов.
Спасибо. А Вы уверены, что «цифры» относятся именно к этой проблеме?
В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Лично я не знаю ответ в этой задаче (хотя, возможно, эта задача и имеет известное решение). А если ещё добавить другие критерии типа цвета, спуски-подъёмы и т.п., то задача будет ещё сложнее.Задача не такая простая и элементарная, как может показаться на первый взгляд. И она действительно является принципиальной не только для написания программы жеребьевки, но и вообще для организации соревнований по швейцарке. Сколько конфликтов и скандалов за свою шашечную жизнь я наблюдал, когда при жеребьевке «вручную» один из лидеров опускался более чем на две очковые группы. Судей обвиняли во всех смертных, а на самом деле другого решения и не было. Одним из возможных решений этой проблемы может быть заложение в программу алгоритма, что играется не более определенного количества туров при ккаждом числе участников.
Даже если в некоторых ситуациях и существуют (один или несколько) вариантов разбиения на пары, удовлетворяющих критерию «игроки не играют между собою дважды», но этих вариантов — ничтожное количество в сравнении с общим числом возможных разбиений на пары, то мощностей современных компьютеров для решения этой задачи может просто не хватить (при достаточно большом числе участников). Заметьте, что я виду речь о том, что при жеребьёвке учитывается только один единственный критерий «игроки не играют между собою дважды»; а в реальной «швейцарке» присутствуют и другие: набранные очки, цвет, спуски-подъёмы и т.п. Т.е., я почти утверждаю, что пока в правилах швейцарки критерий «игроки не играют между собою дважды» не перейдёт из разряда незыблемых в разряд «допускающих нарушение в исключительных случаях», эти правила останутся некорректными, что естественным образом отразится на проблеме составления соответствующих программ.
В турнире по круговой системе заранее известны не только результаты «жеребьёвки» очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку «оптимально», то какая же это будет «швейцарка»? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур?
Владимир, «участники не играют между собой дважды» является незыблимым для швейцарки. Хотел было сначала предложить заложить в основу программы предварительную проверку возможности в дальнейшем организовать полностью n-1 тур, в конце концов спуски/подъемы, цвет не столь принципиальны, но увидел Ваши аргументы, что это не реально для существующих компьютеров. Может быть с учетом ограничения числа туров в зависимости от числа участников эта задача становится реальной?
Александр, что же Вы хотите от людей, если и программам не сладко?
А сколько именно туров Вы считаете можно обеспечить? Пока я думаю, что могу доказать, что можно «обеспечить, что-то типа немного больше, чем двоичный логарифм от числа участников. Но это очень мало.
Незыблемого ничего нет. Кстати в каком-то древнем шашечном или шахматном кодексе СССР я читал, что в самом крайнем случае можно играть дважды. К тому же, что по вашему мнению является менее справедливым со спортивной точки зрения: кто-то сыграет 2-й раз, или лидера в последнем туре опустят через 2 группы. В факте игры 2-й или более раз нет вообще абсолютно ничего несправедливого (это поклон круговой системе, а причём тут она), только некоторое уменьшение интереса, но с этим вполне можно смириться. Представьте ситуацию: двое сильно оторвались от других. Они будут играть между собой, пока кого-то из них не догонят. Но если его догонят, он будет иметь преимущество по Бухгольцу перед догнавшим его.
Представьте, как легко будет проводить жеребьёвку в турнирах с микроматчами (т.е. без учёта цвета), если отказаться от ограничения числа партий между двумя участниками ВООБЩЕ. Учитываем только набранные очки, Бухгольц, далее Бухгольц от Бухгольца или номер по жеребьёвке и всё. Никаких разночтений, и, по сути, никакая программа и не нужна (если судьи будут оперативно считать Бухгольцы после каждого тура). Никаких сомнительных спусков и подъёмов. Может кто-то и сыграет 2, а то и 3 раза. Зато — полная справедливость.Во всяком случае, известно, что если задача разбиения на пары (насколько я понимаю, при любом количестве мыслимых параметров) имеет решения, то хотя бы одно из них можно найти за время О(n^2), множество всех решений, если хочется сравнить и выбрать наиудачнейший, находится за О(n^3 log n+(n^2)r)
1) Вот тут, пожалуйста, поподробнее. Я тут, между делом, обзвонил нескольких специалистов по близким вопросам с просьбой прокоментировать ваше утверждение, но все разводят руки. Всем кажется, что порядок должен быть факториальный. Если можно, объясните, в чём суть такого алгоритма, или укажите литературу.
2) Правильно ли я Вас понял, что для существования первой оценки достаточно знать то, что решение есть, или всё же его ещё и нужно знать.
3) Если Вы правы, то это снимает все проблемы. Вряд ли проблема перебора кубического порядка является серьёзной для современных компьютеров. Особенно, если n не превосходит сотни с небольшим, как в шашечных турнирах.
4) В связи с п.3 вопрос ко всем: «Какое максимальное число участников когда-либо играло в шашки в турнире по швейцарке?»http://www.sportzone.ru/sport/rules.html?sport=chess&chapter=05
Это — правила шахматной федерации, Алканд интересовался мнением шашечных федераций. Впрочем, это как раз то, переводом чего он интересовался. Так что у меня теперь нет необходимости сканировать и пересылать.
Хотя интересно, за всю историю применения были ли проблемы со швейцарской системой в турнирах.
Зачем Вам история? Возьмите любую существующую программу, проведите эксперемент при разном числе участников (побольше) и туров, станет всё понятно.
Совершенно верно, Вы когда-нибудь видели чтобы в круговой системе игроки дважды играли друг с другом (в один круг)
Таким образом, можно утверждать что имеется возможность сыграть n-1 туров и по швейцарке. Естественно, если проводить жеребьевку по турам оптимально. Как указал Владимир, при желании можно и извратиться и загнать себя в тупик Думаю, при желании можно подсчитать количество таких тупиков и поделить на общее количество возможностей провести турнир, не думаю что вероятность будет значительной, так что не думаю что нужно отказываться правила не играть дважды. В турнире по круговой системе заранее известны не только результаты «жеребьёвки» очередного тура, но и сразу всех. По швейцарке такого нет. Если мы будем проводить жеребьёвку «оптимально», то какая же это будет «швейцарка»? Мы же не знаем, как закончатся результаты последующих туров. К тому же, что Вы, по сути предлагаете. Вы предлагаете, чтобы к факторам, учитываемым при жеребьёвке, добавить ещё один: проверку на то, чтобы программа себя не загнала в дальнейшем в тупик. Ничего себе задача! Вы знаете, как её решать, если не хотите попасть в простак хотя бы через тур? Пример, который я привёл, — самый простейший и при желании можно привести массу других. Вероятность не так мала как Вам кажется, она неуклонно возрастает с каждым туром.
Что касается звания гроссмейстер, то согласен, нужны изменения в классификации, о чем сейчас и идут дискуссии. Если и оставлять возможность присвоения ГР по переписке, то это звание должно касаться только заочных турниров, как это есть в шахматах.
Почитайте внимательнее классификацию. Там нигде не написано, что заочные звания приравниваются к очным, или наоборот (или звания по 100 к званиям по русским). Проблема не в классификации, а в том, что шашечные власти её не выполняют. Проще всего свалить всё на Госкомспорт, который не влезая в детали, присваивает просто звания по «шашкам международным и русским». Но так во всех видах спорта, но ни кто же не приравняет мс по толканию ядра к мастеру спорта по бегу на 100 м, хотя оба они — «мастера спорта по лёгкой атлетике». Для этого и существуют федерации.
А лишить заочников возможности повышения звания — проще всего. Так и нужно делать, если стоит задача «убить заочные шашки» под благородным поводом развития компьютерных программ. Если же такая задача не стоит, то дайте им другие стимулы для игры (например, призовые как в теннисе). Тогда никому в голову и не придёт задумываться о разрядах и званиях.
У нас что, огромное число шашистов в стране? А если ещё откинутся заочникм, то что останется?
По существу. Конечно развитие программ уменьшает среднюю результативность в партиях, но ведь не обнуляет её же. С этим вполне можно пока бороться увеличением числа участников в турнирах, числом сыгранных партий.Да, возможно развитие компьютерных программ и убъет заочную игру, что для многих шашистов будет потерей.
А зачем, вообще, об этом рассуждать? Конечно, ни что в мире не вечно. Критерий очевиден. Заочные шашки существуют, пока есть достаточно желающих в них играть.
P.S. Извиняюсь, что моё высказывание не имеет абсолютно ни какого отношения к теме. Но, как говорится, «не я начал».
