О жеребьёвке

grep

У Герлаха никак не отслеживается история повышений/понижений игроков, так что критерии B5 и B6 не рассматриваются (а надо?). Разница очков является первичным критерием, причем с квадратичным весом, так что экстремальных несоответствий не будет. С выбором повышений/понижений и пар внутри группы всё не так ясно...

Кстати, в приведенной формуле явный баг: если MMS(i)≠MMS(j), то c(i,j)≠c(j,i)
В член с OddMan_Weight надо добавить *sign(i-j)

2 grep

Вопрос насчёт В5 и В6 не ко мне. Но кому его задавать?
ШСЖ в шахматах не только учитывает предпочтения текущего тура, но и выстроена таким образом, чтобы от тура к туру не ухудшались условия для образования приемлемых пар, то есть в самом алгоритме заложено прогнозирование "хороших" условий для образования пар в последующих турах.
Кроме того, учитывается фактор достоверности рейтинга и ищется оптимальное распределение занятых мест в результате применения такой системы жеребьёвки. Ведь в классической швейцарке есть определённые ассоциации с алгоритмами сортировки и поиска.

grep

Ну вообще-то эта задача называется Maximum weighted perfect matching и решается методом Edmonds 'а или производными от него.

2 grep

и что Вы этим хотели сказать?

2 grep

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

Обращаюсь к Владимиру Корсаку по поводу его правил жеребьевки.

Первый вопрос связан со спусками и подъёмами.

Вот цитаты из наиболее полного и упорядоченного описания жеребьёвки по-киевски:
----------------------------------------------------------------------------------------
Правило четвертое.
Любой участник по результатам жеребьевки любого тура не должен иметь более одного нескомпенсированного "подъема" или "спуска". "Спуск" компенсируется "подьемом", и наоборот.

При невозможности составления пар с учетом правил 1, 2, 4, 5 производится замена "повышающегося" из нижней очковой группы игрока (если такой есть) на следующего из нижней подгруппы нижней очковой группы. Если замены нет, то для данной очковой группы исключается из рассмотрения правило 5 и делается попытка составить пары без его учета.

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

Буду говорить про себя.

В третьем туре недавней второй лиги ЧУ меня повысили на Кокозея. Ладно.
В четвёртом меня опять повышают через две группы на Тихого.

После третьего тура моя очковая группа выглядела так:
Ерошкин
Щербина
Ливеринов
Денисенко

Ерошкин в спуске из-за нечета.
Понижаются два человека из верхней группы на меня и Ерошкина.

Вопрос: это жеребьёвка по-киевски в действии или ошибки главного судьи?

Кроме того, меня смутили утверждения на турнире, которые противоречат той схеме, которую ты описывал на форуме Кидо.

Сейчас на турнире ты сказал, что любые флотеры - это плохо. То есть, тобой были пересмотрены взгляды на четвёртое правило?

И ещё одно утверждение, что количество побед не важно. Тогда что же важно? Участие?

Потом не понятно положение Ерошкина после первого тура. Он имеет очков меньше, чем проигравшие участники верхней группы Мак-Магона.
Это своеобразное наказание за неявку?

По запитанню про Єрошкіна можу дати відповідь я. В загальних європейських правилах проведення турнірів, рекомендованих для виконання в усіх федераціях членах Європейської Федерації Го, для учасників верхньої групи Макмагон категорично заборонено пропускати тури. В тих випадках, коли гравець за рейтингом повинен бути зарахований до верхньої групи Макмагон, але точно знає, що з певних причин не зможе прийняти участь в усіх турах, він зараховується в турнір не в вищу групу, а в слідуючу очкову групу (тобто йому надаються нижчі на одне очко стартові очки Макмагон (MMS). Це зроблено для того, щоб такі гравці не вплинули на коефіцієнти призерів турніру, так як основна мета більшості змагань - це визначення призерів, а не точне ранжирування усіх інших учасників.

2 Небайдужий:

Дякую за швидку відповідь. Тепер зрозуміло.

2 Korsak:

Всё же хотелось бы получить ответ на свой вопрос (Apr 22 2008, 10:26 PM)
от главного судьи турнира.

И ещё просьба прокомментировать пункт 3 статьи 7 раздела 4 правил Го, которые поданы в Министерство по делам молодёжи и спорта:

3. У випадку, коли учасник пропускає тур, йому нараховується коефіцієнт Бухгольца, рівний його стартовому нарахуванню. Вільному від гри учаснику (при непарній кількості учасників при жеребкуванні) нараховується коефіцієнт Бухгольца, рівний мінімальному стартовому нарахуванню, яке застосовувалося в цьому турнірі.

То есть, почему так, а не как-то иначе?

Да, действительно, я обещал подробно прокомментировать жеребьевки на этом турнире, да все не хватало времени. Собственно нехватает его и сейчас, но раз народ так настаивает, то придется сделать. Может таким оьбразом раз и навсегда удастся избавится от многих вопросов.
Итак. для начала список верхней части таблицы отсортированный по рейтингу
1 Кравец, Андрей 2488
2 Яценко, Дмитрий 2474
3 Жураковский, Богдан 2460
4 Лопатюк, Константин 2440
5 Плющ, Юрий 2428
6 Скочко, Василий 2403
7 Кокозей, Владимир 2401
8 Кокозей, Виктор 2339
9 Богацкий, Аркадий 2328
10 Ерошкин, Юрий 2261
11 Тихий, Антон 2245
12 Щербина, Артем 2159
13 Захарченко, Мария 2041
14 Ливеринов, Валерий 2041
15 Михалюк, Юрий 2019
16 Денисенко, Андрей 1912
17 Ружанский, Роман 1832
18 Байденко, Борис 1725
19 Кайро, Глеб 1666
20 Гальченко, Григорий 1644
21 Ерошкин, Александр 1555
22 Дорошук, Михаил 1512

Положение перед первым туром (при равенстве очков игроки расположены по рейтингу)
1 Кравец, Андрей 19
2 Яценко, Дмитрий 19
3 Жураковский, Богдан 19
4 Лопатюк, Константин 19
5 Плющ, Юрий 19
6 Скочко, Василий 19
7 Кокозей, Владимир 19
8 Кокозей, Виктор 19
9 Богацкий, Аркадий 19
10 Тихий, Антон 19
11 Щербина, Артем 19
12 Захарченко, Мария 19
13 Ливеринов, Валерий 19
14 Михалюк, Юрий 19
15 Денисенко Андрей 18
16 Ружанский Роман 17
17 Гальченко Григорий 15
18 Ерошкин Александр 14
19 Дорошук Михаил 14
и т.д.
Т.е. в верхней группе 14 человек, они играют по схеме 1-8, 2-9 и т.д. до 7-14
Кравец - Кокозей Викт
Яценко - Богацкий А.
Жураковский - Тихий
Лопатюк - Щербина
Плющ - Ливеринов
Скочко - Захарченко
Кокозей Вл. - Михалюк
Здесь была одна тонкость Ливеринов и Захарченко имели одинаковый рейтинг, поэтому кого из них расположить выше, а кого ниже решил жребий. На этот раз выше стал Ливеринов. В следующий раз в подобной ситуации выше станет Захарченко.
Дальше без проблем пара Денисенко - Ружанский.
А после него Гальченко опускается на имеющего нижний рейтинг Дорошука, а Ерошкин опускается еще ниже.

Идем во второй тур
Положение после первого
1 Кравец, Андрей 20
2 Яценко, Дмитрий 20
3 Жураковский, Богдан 20
4 Лопатюк, Константин 20
5 Плющ, Юрий 20
6 Скочко, Василий 20
7 Кокозей, Владимир 20
8 Кокозей, Виктор 19
9 Богацкий, Аркадий 19
10 Ерошкин, Юрий 18.5
11 Тихий, Антон 19
12 Щербина, Артем 19
13 Захарченко, Мария 19
14 Ливеринов, Валерий 19
15 Михалюк, Юрий 19
16 Денисенко Андрей 19
17 Ружанский Роман 17
18 Дорошук Михаил 15

Ерошкин Юрий включился со второго тура. Иза пропуска тура я его не мог включить в верхнюю группу Мак-Магона и он начал с 18 стартовых очков, но за первый тур он получил полочка. В соответствии с системой жеребьевки те кто имеет дробное количество очков для жеребьевки включаются в более высокую очковую группу, поэтому я его расположил (условно) в списке перед вторым туром в группе с 19-ю очками, но в соответствии с его рейтингом.
Итак в верхней группе 7 человек. Срейдий по рейтингу, а это Лопатюк опускается в нижнюю группу ан первую позицию, а остальные 6 разбиваются так 1-5, 2-6, 3-7, т.е.
Кравец - Плющ
Яценко - Скочко
Жураковский - Кокозей Вл.
Следующая группа выглядит так
1 Лопатюк, Константин 20
2 Кокозей, Виктор 19
3 Богацкий, Аркадий 19
4 Ерошкин, Юрий 18.5
5 Тихий, Антон 19
6 Щербина, Артем 19
7 Захарченко, Мария 19
8 Ливеринов, Валерий 19
9 Михалюк, Юрий 19
10 Денисенко Андрей 19

Десять человек. Играют 1-6, 2-7 и т.д. 6-10.
Но пара 1-6 (Лопатюк - Щербина) уже играла в первом туре. Поэтому для Лопатюка ищем следующего по списку. Ей оказывается Захарченко Маша, которая как и было обещано на этот раз опередила Ливеринова. Ну а Щербине достался Кокозей Виктор
Жеребьевка этой группы
Лопатюк - Захарченко
Кокозей Виктор - Щербина
Богацкий А - Ливеринов
Ерошкин - Михалюк
Тихий - Денисенко
Ну и Ружанский - Дорошук также играют между собой

Переходим к третьему туру
Положение после второго
1 Кравец, Андрей 21
2 Яценко, Дмитрий 21
3 Жураковский, Богдан 21
4 Лопатюк, Константин 21
5 Плющ, Юрий 20
6 Скочко, Василий 20
7 Кокозей, Владимир 20
8 Кокозей, Виктор 20
9 Богацкий, Аркадий 20
10 Ерошкин, Юрий 19.5
11 Тихий, Антон 20
12 Щербина, Артем 19
13 Захарченко, Мария 19
14 Ливеринов, Валерий 19
15 Михалюк, Юрий 19
16 Денисенко Андрей 19

Жеребьевка первой четверки - без никаких проблем 1-3, 2-4
Кравец - Жураковский
Яценко - Лопатюк
Следующая группа - 7 человек
1 Плющ, Юрий 20
2 Скочко, Василий 20
3 Кокозей, Владимир 20
4 Кокозей, Виктор 20
5 Богацкий, Аркадий 20
6 Ерошкин, Юрий 19.5
7 Тихий, Антон 20

Средний Кокозей Виктор опускается на первое место в более низкой группе, остальные жеребятся 1-5, 2-6, 3-7
Плющ - Богацкий
Скочко - Ерошкин
Кокозей Владимир - Тихий

В следующей группе 6 человек
1 Кокозей, Виктор 20
2 Щербина, Артем 19
3 Захарченко, Мария 19
4 Ливеринов, Валерий 19
5 Михалюк, Юрий 19
6 Денисенко Андрей 19
Опять проблема одинакового рейтинга Ливеринова и Захарченко. Первые два тура чередование началось с предпочтения Ливеринова, на этот раз начинаем с предпочтения Захарченко. Пары формируются по схеме 1-4, 2-5 и 3-6, т.е.
Кокозей Виктор - Ливеринов
Щербина - Михалюк
Захарченко - Денисенко.

Переходим к четвертому туру
Положение перед туром
1 Жураковский, Богдан 22
2 Лопатюк, Константин 22
3 Кравец, Андрей 21
4 Яценко, Дмитрий 21
5 Плющ, Юрий 21
6 Скочко, Василий 21
7 Кокозей, Владимир 21
8 Кокозей, Виктор 21
9 Богацкий, Аркадий 20
10 Ерошкин, Юрий 19.5
11 Тихий, Антон 20
12 Захарченко, Мария 20
13 Михалюк, Юрий 20
14 Щербина, Артем 19
15 Ливеринов, Валерий 19
16 Денисенко Андрей 19

Жураковский - Лопатюк без вопросов
Следующая группа шесть человек
1 Кравец, Андрей 21
2 Яценко, Дмитрий 21
3 Плющ, Юрий 21
4 Скочко, Василий 21
5 Кокозей, Владимир 21
6 Кокозей, Виктор 21
жеребятся просто 1-4, 2-5 и 3-6 т.е.
Кравец - Скочко
Яценко - Кокозей Владимир
Плющ - Кокозей Виктор

Следующая группа 5 человек
1 Богацкий, Аркадий 20
2 Ерошкин, Юрий 19.5
3 Тихий, Антон 20
4 Захарченко, Мария 20
5 Михалюк, Юрий 20
Средний Тихий. Он до этого не опускался поэтому ему на спуск.
Остальные должны играть 1-4, 2-5. Но Ерошкин с Михалюком уже играли, поэтому меняем местами в нижней подгруппе Михалюка и Захарченко и получаем пары
Богацкий - Михалюк
Ерошкин - Захарченко
Переходим к очередной группе
1 Тихий, Антон 20
2 Щербина, Артем 19
3 Ливеринов, Валерий 19
4 Денисенко Андрей 19
С сохранением условия что игроки верхней половины очковой группы должны играть с игроками нижней половины очковой группы (а это условие имеет более высокий приоритет чем учет подьемов и спусков) получается только один вариант Тихий - Ливеринов, Щербина - Денисенко, т.к. Тихий с Денисенко уже играли. Если бы этого не было, то была бы жеребьевка Тихий - Денисенко и Щербина - Ливеринов, т.к. у Денисенко подьемов еще не было, а у Ливеринова был в предыдущем туре. Отмечаем по ходу что приоритет учета спусков подьемов все же выше чем недопущение перемешивания внутри верхней или нижней половины очковой группы.
Таким образом остановились на варианте
Тихий - Ливеринов
Щербина - Денисенко.

Переходим к пятому туру
Положение после четвертого
1 Лопатюк, Константин 23
2 Кравец, Андрей 22
3 Яценко, Дмитрий 22
4 Жураковский, Богдан 22
5 Плющ, Юрий 22
6 Скочко, Василий 21
7 Кокозей, Владимир 21
8 Кокозей, Виктор 21
9 Богацкий, Аркадий 21
10 Захарченко, Мария 21
11 Ерошкин, Юрий 19.5
12 Тихий, Антон 20
13 Щербина, Артем 20
14 Ливеринов, Валерий 20
15 Михалюк, Юрий 20
16 Денисенко 19
17 Ружанский 18.5
18 Дорошук 18

Разбираемся с первой пятеркой
1 Лопатюк, Константин 23
2 Кравец, Андрей 22
3 Яценко, Дмитрий 22
4 Жураковский, Богдан 22
5 Плющ, Юрий 22
Простой подход Яценко вниз и Кравец и Лопатюк играют с парой Жураковский и Плющ не проходит по той причине, Кравец уже сыграл с Жураковским и Плющем. Поэтому следующий кандидат на понижение из верхней половины очковой группы это Кравец. В этом случае остается только один вариант без перемешивания верхней половины с нижней это
Лопатюк - Плющ
Яценко - Жураковский
Смотрим следующую очковую группу
1 Кравец, Андрей 22
2 Скочко, Василий 21
3 Кокозей, Владимир 21
4 Кокозей, Виктор 21
5 Богацкий, Аркадий 21
6 Захарченко, Мария 21
Расклад 1-4, 2-5 и 3-6 сразу не проходит т.к. Кравец уже играл с Виктором Кокозеем. Меняем Виктора с Аркадием местами (внутри одной половины очковой группы - это самы нижний приоритет) и все получается
Кравец - Богацкий
Скочко - Кокозей Виктор
Кокозей Владимир - Захарченко

Опускаемся еще ниже
1 Ерошкин, Юрий 19.5
2 Тихий, Антон 20
3 Щербина, Артем 20
4 Ливеринов, Валерий 20
5 Михалюк, Юрий 20
Нечетное колдичество - кандидат на опускание Щербина. Тем более что он еще не опускался
Получаем пары
Ерошкин - Ливеринов
Тихий - Михалюк

Спускаемся еще ниже
13 Щербина, Артем 20
16 Денисенко 19
17 Ружанский 18.5
18 Дорошук 18
С Денисенко Щербина уже играл, поэтому ему выпадает Ружанский, а Денисенко соответственно Дорошук

Переходим к последнему туру
Положение после пятого тура

1 Лопатюк, Константин 24
2 Яценко, Дмитрий 23
3 Кравец, Андрей 22
4 Жураковский, Богдан 22
5 Плющ, Юрий 22
6 Кокозей, Владимир 22
7 Кокозей, Виктор 22
8 Богацкий, Аркадий 22
9 Скочко, Василий 21
10 Тихий, Антон 21
11 Захарченко, Мария 21
12 Ливеринов, Валерий 21
13 Ерошкин, Юрий 19.5
14 Щербина, Артем 20
15 Михалюк, Юрий 20
16 Денисенко 20
17 Ружанский 19.5
18 Дорошук 18

Лопатюк с Яценко уже играли, поэтому формируется большая очковая группа из тех кто набрал 22 и более очков

1 Лопатюк, Константин 24
2 Яценко, Дмитрий 23
3 Кравец, Андрей 22
4 Жураковский, Богдан 22
5 Плющ, Юрий 22
6 Кокозей, Владимир 22
7 Кокозей, Виктор 22
8 Богацкий, Аркадий 22

Поскольку это последний тур, то в нем используется не схема 1-5, 2-6 и т.д., а обратная 1-8, 2-7, 3-6 и 4-5
Причем все удачно сходится, никого даже не нужно переставлять.
Лопатюк - Богацкий
Яценко - Кокозей Виктор
Кравец - Кокозей Владимир
Жураковский - Плющ

Следующая группа
9 Скочко, Василий 21
10 Тихий, Антон 21
11 Захарченко, Мария 21
12 Ливеринов, Валерий 21
Так как Ливеринов уже играл с Тихим, то их черелдование кто выше кто ниже по рейтингу с Захарченко теперь уже значения не имеет. Один вариант
Скочко - Ливеринов
Тихий - Захарченко

Опускаемся еще ниже
1 Ерошкин, Юрий 19.5
2 Щербина, Артем 20
3 Михалюк, Юрий 20
4 Денисенко 20
5 Ружанский 19.5

Опускаться должен средний Михалюк, но в этом случае Щербина сыграл с обоими игроками из нижней половины очковой группы. Таким образом опускаться по любому ему.
И схема первый на последнего дает такие пары
Ерошкин - Ружанский
Михалюк - Денисенко
А Щербине достается Дорошук.

Вот и вся премудрость.
Повторю правила в соответствии с приоритетами
1. Нельзя два раза играть в одном турнире
2. Нельзя чтобы в одной очковой группе играли между собой игроки из верхней по рейтингу половины и из нижней половины
3. Нужно учитывать спуски и подьемы участников
4. Нельзя перемешивать игроков внутри верхней и нижней половины очковой группы.

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

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

С уважением, Корсак