Этюды для программистов - [14]

− 1.

Оказавшись между двумя крайностями, выберем компромиссное решение — швейцарскую систему. В первом круге соперник, «посеянный» первым, встречается с последним, второй — с предпоследним и т. д. После каждого круга соперники упорядочиваются в соответствии с набранными очками. Внутри каждой группы (с равным количеством очков) соперники упорядочиваются по среднему числу очков у побежденных ими противников (тем самым ничья не учитывается). В следующем круге соперник, стоящий в описанной классификации на первом месте, встречается с соперником, занимающим наиболее высокое место из тех, с кем он еще не играл. Остальные пары определяются аналогичным образом: соперники должны иметь почти равное количество очков, причем повторные встречи не допускаются. В табл. 5.1 показан возможный трехкруговой турнир по швейцарской системе с восемью участниками. Крупный шахматный деятель Харкнесс утверждает, что турнир по швейцарской системе в

кругов, где N — число игроков, правильно расставит k + 1 первых игроков (и, из соображений симметрии, k + 1 последних игроков). Швейцарская система справедливее немедленного выбывания и гораздо быстрее круговой. Она позволяет всем соперникам играть в каждом круге. Вопрос состоит в том, как ведут себя подобные турниры в условиях реальных соревнований. Предположим, имеется 2ⁿ соперников. Соперник 1 — сильнейший, соперник 2 — второй по силе, …, соперник 2ⁿ — слабейший. Для начала проведем круговой турнир, записывая результаты каждого матча. Если встречаются соперники i и j, i < j, положим вероятность победы игрока i равной

1/2 + (j − i)/2ⁿ⁺¹.

Тем самым более сильный соперник побеждает с вероятностью, превышающей половину. Упорядочим соперников в соответствии с набранным в круговом турнире количеством очков. Внутри каждой группы команд с равным количеством очков упорядочим их по среднему числу очков, набранных побежденными ими соперниками. Если и здесь наблюдаются совпадения, соперники упорядочиваются по исходным номерам. В результате получается круговая классификация, которую мы будем считать самой «справедливой»; она используется для оценки других способов организации турниров.

Следующий шаг состоит в том, чтобы с одной и той же базой данных провести турниры по швейцарской системе и с немедленным выбыванием. Для разбиения соперников на пары в каждом из этих турниров берутся результаты кругового турнира. Заметьте, что в обоих турнирах два соперника могут встретиться лишь однажды. Швейцарская классификация — это упорядочение после заключительного круга (всего n кругов), причем все оставшиеся неясности разрешаются в соответствии с начальным упорядочением. Затем начните турнир с немедленным выбыванием, составив пары для первого круга случайным образом. В классификации по выбыванию победитель финальной встречи идет первым, побежденный — вторым, и, вообще, проигравшие в i-м круге располагаются перед ранее выбывшими и после всех победивших в i-м и следующих кругах. Внутри группы побежденных в i-м круге соперники располагается в соответствии с итоговыми местами победивших их команд.

Чтобы сравнить эти классификации, используем новую и старую статистики, Старая статистика — это корреляция мест определяемая как

R = 1 − 6 

(х_i − y_i)²/(N³ − N),

где x_i — место соперника i в одной классификации, у_i — место в другой классификации, N — общее число соперников (в данном случае 2ⁿ). Другая статистика подсчитывает совпадения и определяется как

М = max_i (∀j) (j ≤ i ⊃ х_j = у_j).

Тем самым М равно максимальному числу мест (считая от сильнейших к слабейшим), в которых обе классификации в точности совпадают. Статистика R характеризует близость двух классификаций в целом, а M — совпадение верхних частей классификаций[11].

Тема. Напишите программу, читающую исходное значение n, проводящую каждый из трех турниров для 2n соперников и вычисляющую статистики R и M для каждой из трех пар классификаций. Проведите эксперимент большое число раз с постоянным значением n и подсчитайте средние значения M и R. Сравните, какая из двух систем — швейцарская или с немедленным выбыванием — лучше повторяет результаты кругового турнира.

Указания исполнителю. Разумеется, нужно досконально разбираться в разных системах проведения турниров, нужно эффективно программировать подбор пар. Но не упустите из виду еще один момент. Размеры кругового турнира заставляют эффективно запрограммировать внутренний цикл и экономно расходовать память для хранения результатов встреч. Разумеется, вам понадобится хороший генератор случайных чисел для определения результатов встреч. Наконец, при швейцарской системе возможны попытки дважды свести одну и ту же пару соперников, поэтому либо докажите, что такого не произойдет, либо измените алгоритм, избегая повторных встреч, но подчиняясь общему правилу: старайтесь сводить в пары соперников, набравших почти равное количество очков.

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