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



Смотри в корень

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



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

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

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

Все.



Смотри в корень

> Группы как таковые отсутствуют (или состоят почти из отдельных игроков). Стыкуются ближайшие по очковому показателю, начиная сверху вниз.
Все.

То есть как это все ??? Это еще даже не начало !!!

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

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

То есть по Вашим словам Ваша принудительная жеребьевка должна обходиться без перебора . Но она требует перебора , разбивания пар и собирания новых методом проб и ошибок .



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

Очень интересно. Готов участвовать в обсуждении.

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

Замечательное начинание!
Хочу поучастовать, но пока не знаю чем :) У меня до Нового Года дел и так раза в 2 больше, чем рук и головы. А потом присоединюсь, если возьмете.
Подзадача проведения турниров интересна, но для меня это никак не месяц работы по вечерам.

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

Сергей Межов,
>Подзадача "оценка позиции" будет мне интересна на всех этапах создания. Работаю над ней давно.

Сергей, а можно поподробнее немножко. Я умышленно назвал подзадачу "Оценка счета", т.к. оценка позиции на мой взгляд намного шире.Оценка счета, помоему, должна вернуть только примерные перевес одной из сторон (ну, с наглядным пособием, типа как в CGoban`е) а "оценка позиции", скорее должна вернуть описательную часть. Т.е. Зоны больших ходов, зоны срочных ходов, характиристики групп (стабильна, живая, мертвая, неопределенная) и некие весовые значения. Т.е. типа этот срочный ход на 30 оков, т.к. делает группу живой, но есть большой ход на 35 очков.

Вам интересно участвовать как идеолог и алгоритмизатор или еще и разработчик?

Сергей Павлов,
>В целом проект мог бы трансформироваться в глобальную задачу создания специализированнного прикладного го-пакета.

Собственно, именно в этом и состоит задача =)

>И эта подзадача может иметь самостоятельный коммерческий результат.

Конечно обе эти задачи могут быть абсолютно автономными и приносить комерческую прибыль... Но! Кто мешает им приносить прибыль в нутри другой задачи? Распространяется один демо пакет. Люди определяются что им нужно и олачиваю, соответственно, только то, что им надо. Те, кто оплатили все, получили все в едином месте, стиле, идеологии. О программе узнает в три раза больше людей, нежли если их распространять раздельно. Распределяется нагрузка по раскрутке и еще много чего. В итоге, по моему мнению, результат от того, что они будут распространяться все вместе (что не лишает их возможности распространяться еще и отдельно) принесет пользу всем, в том числе и мне, чего я и добиваюсь =)

Les,
Спасибо!

Марианна,
>Хочу поучастовать, но пока не знаю чем :) У меня до Нового Года дел и так раза в 2 больше, чем рук и головы. А потом присоединюсь, если возьмете.

Спасибо! Конечно возьмем =)

>Подзадача проведения турниров интересна, но для меня это никак не месяц работы по вечерам.

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



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword

Дим , сделай специальный форум для этой затеи , хоть на Народе .

Серьезное обсуждение должно структурироваться в дерево , а начало получается серьезным и многообещающим



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

Илья,
Я уже думаю на эту тему... Я и здесь могу еще один форум открыть. Единственное, чего я боюсь, это то, что люди не будут одить еще на один форум. Хотя можно сделать у него специальную тематику не под мой проект, а вообще программирование связанное с го и смежные алгоритмы... (рейтинги, жеребьевки)

Что думает по этому поводу аудитория?
И владельцы сайта? =)
Форум будет тогда здесь же, т.е. по ссылке [forum.weiqi.ru]



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword

Эта тенденция характерна для большинства посещаемых форумов - выделять наиболее интересные тематические направления в подфорумы. Может тоже двинуться "по ветру"?



Смотри в корень

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



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

> она требует перебора , разбивания пар и собирания новых методом проб и ошибок

Что есть перебор, товарищи! Перебор - это когда проверяем каждого с каждым или что-то в этом роде...

В нашем случае нет перебора, потому что проверка (встречались ли?) делается только для соседа по турнирной "табели о рангах", а если он не подходит, то для следующего - вниз по "табели". Число проверок (заметим, что дополнительно не надо определять по специальной процедуре, например датчиком случайных чисел или еще как, следующего кандидата, т.к. все уже упорядочны по рангу) не превосходит на каждом шаге для каждого игрока числа уже сыгранных туров и не требует (точнее - почти не требует, если игроков не слишком мало; - учтено замечание Ильи Ветрова) для неподходящих пар разбивки каких-либо других пар из уже определенных ранее. На самом деле очень эффективная и однозначная процедура, в то же время совершенно непредсказуемые вперед на два тура расклады, так как плотность распределения рангов на порядок выше, чем в швейцарке.



Отправка отредактированного (15/11/03 15:39)

Смотри в корень

> не требует для неподходящих пар разбивки каких-либо других пар из уже определенных ранее.

Сергей Владимирович , это процедура требует разбивок ! Пусть есть 6 игроков , пусть их ранги 1 (самый сильный) , 2 ... 6 (самый слабый) . Тогда в первом туре пары 1-2 , 3-4, 5-6 , пусть выиграли нечетные . Во втором туре 1-3 , 2-4 и повтор 5-6 . Но если разбить пару 2-4 , получится 2-5 и 4-6 и все могут играть .

Я же проводил свой "спортивно-форовый" турнир в точности с Вашей принудительной жеребьвкой и наткнулся на эту проблему . Или Вы надеетесь , что при бОльшей густоте рангов такие коллизии будут менее вероятными ? Здравый смысл мне не помог . Я придумал очень сложный алгоритм жеребьевки в один проход , но он катастрофически сложен , даже по сравнению с ручными переразбивками и вообще не доказан , пришлось от него отказаться и переразбивать вручную .



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

ok. Сегодня вечером сделаю отдельный форум посвященный алгоритмам и программированием го и вокруг него.



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword

Конечно, вообще без разбивок - это утверждать некорректно... Правильнее сказать, что вероятность возникновения таких ситуации в новой схеме в верхней части таблицы при достаточно большом числе участников невелика (наверное, меньше чем в швейцарке). Внизу - ну не так страшно. Турниры типа прошедших на КГС - особый случай, так как там слишком мало было участников (для швейцарки и ей подобных турниров соотношение "число участников"/"число туров" должно быть порядка 3-х).



Смотри в корень

> не требует для неподходящих пар разбивки каких-либо других пар из уже определенных ранее.

> Конечно, вообще без разбивок - это утверждать некорректно... Правильнее сказать, что вероятность возникновения таких ситуации в новой схеме в верхней части таблицы при достаточно большом числе участников невелика

Хм... Как говорится , найдите 10 различий ... Я-то надеялся , что проблема решена теоретически . Ну нет так нет .

> Внизу - ну не так страшно.

Это да . Переразбивать приходится только нижние пары .



Наш рот всегда открыт для диалога (c) Владимир ВишневскийOkruzhor (экс-Игозавр)

Я настаиваю на применении принудительной жеребьевки только в схемах с существенно более дробным шагом разбивки игроков по группам, когда понятие "очковой группы" вырождается. В классической швейцарке и ММ это не стоит применять. Хотя вероятность "нестыковок", думаю, снижается, но не очень существенно. Математически все это трудно проверить, да и стоит ли? Практика покажет. Пока нет статистики никакой...



Смотри в корень

Уважаемый PuzzleMan!
В свое время я был главным инженером поекта и делал десятки ТЗ,ТП и РП. Я готов помочь Вам в написании этих проектов.
Что касается задачи " Оценка позиции", то алгоритм четко сформулирован в книге Шикшин В.Д. " Игровой анализ".
Я готов форматизировать его в рамках постановки задачи для программирования.
С уважением

Уважаемый Валерий!

Огромное спасибо за сообщение. С удовольствием воспользуюсь Вашими предложениями. В течении ближайше недели я собираюсь окончательно систематизировать и перенести на бумагу все мысли, которые у меня есть по проекту. После этого я буду готов к более предметному разговору.



С уважением,
Дмитрий Петраков aka PuzzleMan
Elite Japan Crossword