О жеребьёвке

[grep]

As for software...

Существует очень неплохо настраиваемая французская OpenGotha. Софтина довольно умная, позволяет частично ручную жеребьевку, а автоматическая осуществляется по десятку критериев.

Её, конечно, надо доработать напильником, чтобы она понимала украинские реалии, но поскольку она опенсорсная, проблемы это практически не составляет... Если мне дадут нормальное ТЗ, готов поработать на благо комьюнити.

Видимые проблемы: плохо воспринимаются не-латинские буквы в именах (достаточно тривиально) нет поддержки существующего формата рейтингов UFGO (утром формат, вечером стулья)
Написано всё на яве, так что теоретически можно перенести на простой смартфон... только мне лень

[liver]

чтобы дойти до ТЗ нужно чтобы народ хотя бы осмыслил суть проблемы.

и это только первый шаг.

[Небайдужий]

Вибачте за довгу мовчанку... катастрофічно не вистачає на все часу.
З приводу звернення до керівництва Європейської федерації. Я вважаю, що це не доцільно, та і повноважень таких на себе не брав. Ви, звичайно, можете самі проявити ініціативу і почати спілкування з цього приводу. Система Макмагон практично не відрізняється від швейцарської. Просто, при великій кількості учасників, потрібно проводити багато турів, щоб отримати коректні результати турніру і визначити переможців. Тому придумана Макмагон система, яка по суті є швейцаркою на певному етапі (як ніби частина турів швейцарки уже зіграно). Тобто, наприклад, вважається, що 1 кю уже зіграв певну кількість турів і виграв їх у завідомо слабших учасників (20,19,18,…,5 кю,…) і уже має певну кількість очок в турнірі. Ці очки вважаються стартовими очками Макмагон. Кількість цих стартових очок призначається в залежності від рангу учасника (кю, дан). Система Макмагон дає можливість не проводити завідомо безглузді і нецікаві ні для кого партії (1 кю – 20 кю, і т.д.). У верхній групі Макмагон знаходяться учасники, які на цей умовний момент виграли усі свої попередні партії і мають однакову кількість очок. Задача полягає тільки в тому,щоб довести той уявний швейцарський турнір з цього положення до логічного завершення уже не уявно, а в реальному продовженні турніру. Перевага програми MacMahon якраз і є в тому, що можна гнучко кожному учаснику присвоїти в ручному режимі потрібні стартові очки. Усі інші програми для обслуговування турнірів Макмагон умовно вважають, що в турнірі рівномірний склад учасників (від найслабших до найсильніших) і стартові очки призначають автоматично. Такий же автоматичний режим є і в програмі MacMahon. Так що, якщо ви бажаєте, можете скористатись стандартним режимом визначення стартових очок, або призначити їх в залежності від конкретного складу учасників.

Повторюсь в который раз, программу Mac-Mahon невозможно использовать в серьёзных турнирах ввиду плохого сведения пар.

Мене дивує Ваша упередженість по відношенню до цієї програми. Як можна заявляти, що програма дає незадовільне жеребкування, якщо ви не вивчили її як слід, не випробували її на якихось реальних турнірах (хоча б потім, проганяючи турнір через цю програму, щоб побачити відмінність у результатах жеребкування за допомогою різних програм). Як кажуть: ще не пробував, а вже погана… До речі, я пробував набирати деякі проведені в Одесі великі турніри і часто в деяких турах зустрічались варіанти жеребкування, коли противники, які в системі Макмагон не могли б зустрітись із-за того, що мали б деяку різницю стартових очок, у ваших варіантах зустрічаються (навіть через декілька очкових груп).

Мета системи жеребкування полягає в тому, щоб забезпечити учасникам найбільш рівні умови і найближчих по кількості очок в турнірі учасників (тобто мінімізувати нерівні ігри). В багатьох країнах до цієї мети ідуть різними шляхами. Дехто проводить довільне хаотичне жеребкування в одній очковій групі, інші притримуються класичного плану (1-8,2-7,3-6,4-5); Корсак пропонує свій варіант (1-5,2-6,3-7,4-8; а в останньому турі 1-8,2-7,3-6,4-5). У варіанті Корсака вирівнюється, в певній мірі, вірогідність виграшів у всіх учасників одної очкової групи. Тобто, найсильнішому не надається найбільша вірогідність виграшу, а у всіх парах групи ця вірогідність приблизно однакова. Я вважаю цей варіант більш справедливим. Є ще можливість проводити ігри з певним гандикапом (прямим чи зменшеним). Кожен з цих варіантів має певні плюси і мінуси. В ідеалі потрібно було б, щоб кожен зіграв з кожним (кругова система). Але цей варіант можливий тільки в турнірах з дуже малою кількістю учасників (вища ліга, мейдзин, …). Швейцарка дає можливість проводити турніри з більшою кількістю учасників, але знову ж з обмеженням. В шахах не стоїть проблема популяризації. Вони достатньо розвинуті в кожній країні. Щоб добратись до фінального турніру потрібно пройти цілий ряд попередніх турнірів по відбору на різних рівнях (місто, район, область і т.д.). Тому в шахах досить поширені перші дві системи проведення турнірів. В Го ситуація зовсім інша. Тут, при відносно невеликій кількості турнірів, потрібно охопити якнайбільшу аудиторію, з метою популяризації і розвитку Го в країні. Крім того кількість і сила гри учасників в регіонах дуже сильно відрізняється. Тому проводити ряд регіональних турнірів а потім фінальний, у нас немає сенсу. Хіба що у перспективі або в окремих турнірах на зразок Кубка Посла Кореї (Кубка LG).

Програма MacMahon реалізує механізм мінімізації порушення основних принципів. Кожному порушенню принципів при жеребкуванні присвоюється певна числова вагомість (до речі, можна самому виставити вагомість кожного критерію жеребкування (колір, клуб, країна, не поєднувати повторно тих же учасників, велика різниця очок в турнірі і т.д.). Програма оцінює усі можливі варіанти жеребкування як кожної пари окремо, так і суму варіантів для всіх (навіть найнеймовірніші), заносить їх у вагову матрицю і вибирає «найдешевший» варіант жеребкування для всіх. Жеребкування в групі з однаковою кількістю очок в турнірі проводиться за принципом 1-8,2-7,3-6,4-5 (але при умові рівного складу учасників у цій групі – інакше вимоги мінімізації «затрат» можуть поміняти схему жеребкування).

Програма Gotha зручна для викладення результатів турніру на сайт турніру, але для жеребкування вона не така гнучка як програма MacMahon і не має такої кількості різноманітних налаштувань. ЇЇ плюс – відкритість. MacMahon,на жаль, закритого типу і змінити її під наш варіант немає можливості.

Навіть проводячи жеребкування турніру в ручному режимі за набором правил Корсака, при використанні програми MacMahon ми все одно отримуємо певну автоматизацію (підрахунок очок, коефіцієнтів, подача списків при жеребкуванні по очкових групах , автоматичне визначення кольору та багато інших дрібниць, які полегшують жеребкування. Крім того, забезпечивши жеребкування вищої частини турнірної таблиці, при нехватці часу можна для решти учасників провести автоматичне жеребкування, так як це не суперечить основній меті турніру (визначення призерів). Так що говорити, що ця програма не потрібна і не забезпечує автоматизації жеребкування , мабуть буде некоректно.
От якби можна було б доопрацювати програму MacMahon на реалізацію правил Корсака, то це був би найкращий варіант. Але автор програми не розповсюджує її відкритого коду . Єдине, це можна звернутись до автора, щоб він доопрацював програму до наших потреб. Але мабуть це неможливо, так як він займався цією програмою з власної ініціативи і має іншу основну роботу. Тому, як каже Герлах (автор), у нього не вистачає часу на роботу над програмою для підгонки її до тих побажань, які йому надсилають.

[liver]

2 Небайдужий

Спасибо за развёрнутый ответ.
Я действительно не проводил турниры с использованием программы MacMahon, поскольку критерий 1-8, 2-7, 3-6 и т.д. образования пар является неприемлемым для швейцарской системы с дополнительными критериями Бухгольц и Бергер для целей определеня мест.
Этим руководствовался и Корсак, когда отказался от автоматической жеребьёвки при помощи программы MacMahon.
Если Вас и участников турнира устраивает распределение мест, которое возникает в результате использования MacMahon при жеребьёвке турниров, то это Ваше право. Меня не устраивает. Кроме того, такого же мнения придерживается всё шахматное сообщество.
Уточню, что речь идёт о швейцарской системе жеребьёвки, которая, как Вы сами заметили ничем не отличается от системы Мак-Магон.
И если это действительно так(т.е. Мак-Магон отличается лишь в наличии стартовых очков участников, отличных от нуля), то считаю нецелесообразным вообще выделять мак-магон в отдельную систему жеребьёвки. Это лишь одно из начальных условий турнира - наличие очков(коэффициентов Мак-Магона), которые получают игроки в соответствии со своим рейтингом.
От того, существуют они или нет, сам алгоритм жеребьёвки не меняется.

Сказанное выше совсем не отрицает использование схемы 1-8, 2-7,3-6 при жеребьёвке турниров. И она используется и в шахматах, но в других системах жеребьёвки, например, в нокаут-системах.

Мы опять упираемся в начальную проблему - а каков же алгоритм жеребьёвки швейцарской системы применительно для Го? Он существует, либо он копирует взятый из ФИДЕ алгоритм? Об этом нигде нет информации.
И не обращать внимания на эту проблему - это не совсем одно и то же, что её решить.
И пусть программа Герлаха имеет прекрасный алгоритм(но какой?), замечательный интерфейс, но схема 1-8,2-7,3-6 перечёркивает все её преимущества.

Игрок имеет право знать правила, по которым программа образует пары. А программа Mac-Mahon не даёт ему такой возможности. А если даёт, то дайте мне источник, где я могу об этом почитать.
Например, вот ссылка на правила ФИДЕ, которые используют шахматисты:
http://www.fide.com/official/handbook.asp?level=C0402

Что касается одесской системы жеребьёвки, то я знаю о недостатках, которые есть в программе Turbo Swiss, и многие из тех, что были на Одессе Золотой-2007 уже исправлены. Алгоритм пересмотрен и доработан, но опять таки в соответствии с правилами швейцарской системы ФИДЕ, о которых я знаю. Если Корсак сможет формализовать свою систему в упорядоченном виде, где учитываются все возможные варианты ситуаций(вот тогда это уже будет система), то если мне удасться путём введения дополнительных параметров учесть его систему,то я смогу как вариант использовать и систему Корсака. Если же нужно будет писать новую процедуру, то я этого на сегодняшний момент не потяну. У меня тоже есть основная работа.

Ещё раз спасибо за ответ, Вы мне помогли определиться.

[Mustitz]

Хотелось бы узнать, какие штрафы есть в программе Mac-Mahon, а каких не хватает. Я вот вижу, например, такой набор штрафов

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

Что еще?

[grep]

У Герлаха на сайте выложен текст, объясняющий алгоритм (по-немецки, так что за качество перевода не ручаюсь)

Минимизируется по всем возможным жеребьевкам сумма оценок c(i,j) пар, где оценки вычисляются по такой формуле

Код
c(i,j)=AlreadyPlayedEachOther(i,j)*PlayedBefore_Weight
   +(MMSDifference(i,j)/2)**2 *SameGroup_Weight
   if (MacMahonScore(i)<>MacMahonScore(j))
   {
     +(100-SecondCriteriaIndex(i)+SecondCriteriaIndex(j))*OddMan_Weight
   }
   if (i∉TopGroup and j∉TopGroup)
   {
     +SameCountry(i,j)*SameCountry_Weight
     +SameClub(i,j)*SameClub_Weight
     +TooBigStrengthDifference(i,j)*StrengthDifference_Weight
     if (not Handicap(i,j)>0)
     {
        +ColorCosts(i,j)*Color_Weight
     }
   }
   else
   {
     if (MacMahonScore(i)=MacMahonScore(j))
     {
        +|SecondCriteriaIndex(i)+SecondCriteriaIndex(j)-100|*Setting_Weight
     }
   }

[/code]


SecondCriteriaIndex это место в очковой группе по совокупности вторичных критериев, нормированное по шкале 0..100 (самый сильный игрок группы имеет SecondCriteriaIndex=100, самы слабый -- SecondCriteriaIndex=0).

Из формулы очевидно, что программа предпочитает жеребьевку 1-8,2-7... и это неизлечимо.

Все *_Weight вроде как конфигурируемы. По умолчанию, значения такие:
Код
Club_Weight               = 80
Country_Weight            = 20
StrengthDifference_Weight = 80
Color_Weight              = 50
Setting_Weight            = 10
OddMan_Weight             = 100
SameGroup_Weight          = 1000
PlayedBefore_Weight       = MAXWEIGHT (вроде как бесконечность)

[/code]

[Гость_atyk]

А если поставить Setting_Weight<=0?

[liver]

2 grep

схема - 1-8, 2-7, 3-6... - это один из критериев жеребьёвки.

Есть другие критерии.
Например, минимизация разницы очков соперников, цветовые предпочтения.
В случае, если игроки не могут играть, какова последовательность перестановок внутри очковой группы, преследующая цель подбора пар, удовлетворяющих всем критериям.
Что делать, в случае, если невозможно найти пары всем игрокам в группе?
Как выстроены критерии в порядке приоритетности?
По тому алгоритму, который приводит Герлах, невозможно ответить на эти вопросы.
Герлах приводит лишь алогритм, по которому определяются значения весовых коэффициентов матрицы предпочтений для критериев, которые перечислил Mustitz.

Удовлетворяет ли он критериям швейцарской системы жеребьёвки(ШСЖ)? Для того, чтобы ответить на этот вопрос, нужно сначала выяснить, что такое швейарская система жеребьёвки в Го.
Если ШСЖ в Го соответствует ШСЖ ФИДЕ, то однозначно - нет.
Поэтому, чтобы определиться с задачей построения алогритма для ШСЖ, нужно сначала грамотно сформулировать постановку задачи.

В данном случае постановка задачи тождественна формулировке правил ШСЖ.
А где эти правила? Их в Го нет.

Корсак ранее столкнулся с этой проблемой и сформулировал свои правила, назвав их правилами жеребьёвки по-киевски. Но они ещё не охватывают всё множество ситуаций, которые могут возникнуть при формировании пар.

Я предлагал Корсаку наложить его правила на правила ШСЖ ФИДЕ. Он отказался ввиду ряда объектиных причин.

Поэтому считаю целесообразным обращение в ЕФГ с воросом о решении проблемы ШСЖ в Го и при случае предложить систему Корсака(если она будет таковой) для жеребьёвки европейских турниров.

[Mustitz]

2 grep
Что делать, в случае, если невозможно найти пары всем игрокам в группе?
Как выстроены критерии в порядке приоритетности?
По тому алгоритму, который приводит Герлах, невозможно ответить на эти вопросы.
Герлах приводит лишь алогритм, по которому определяются значения весовых коэффициентов матрицы предпочтений для критериев, которые перечислил Mustitz.

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

[liver]

2 Mustitz

Предлагаю выдержку из правил ШСЖ ФИДЕ:

Відносні критерії
(Ці критерії знижуються у порядку пріоритету. Вони повинні виконуватися настільки, як це можливо. Для виконання відносних критеріїв можуть проводитися переміщення вабо обміни гравців, але гравці не повинні спускатися в нижчу групу).
В3. Різниця очок двох гравців, які складають пару, повинна бути якнайменшою, а в ідеалі - нульовою.
В4. Якнайбільше гравців повинні отримати їх очікуваний колір. (Якщо х очкової групи відрізняється від нуля, це правило не повинно враховуватися; х зменшується на 1 кожного разу, коли не може бути здійснена перевага кольору).
В5. Гравець не повинен отримати той самий флотер у двох турах поспіль.
В6. Гравець, який був флотером, не повинен бути флотером два наступних тури.

Действуют ли эти критерии в Го и в какой степени? Либо существуют другие критерии?
И как эти или другие, соответствующие этим, критерии реализованы в программе MacMahon?