кругов, где 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 или другой язык обработки массивов, если только вы сумеете так организовать турниры, чтобы стала выгодной параллельная обработка всех соперников.

Длительность исполнения. Одному исполнителю на 2 недели.

Развитие темы. Большинство расширений включает более подробный анализ и сравнение систем проведения турниров. Во-первых, заметьте, что нижняя часть классификации по итогам турнира с немедленным выбыванием носит довольно произвольный характер. Кроме того, соперникам, попавшим в эту часть классификации, весьма тоскливо, ибо они рано вылетели. Для утешения можно организовать турниры с немедленным выбыванием среди неудачников каждого круга. Результаты этих турниров, а не приведенное выше правило, расставят неудачников по местам. Поскольку и в этих побочных турнирах будут проигравшие, организуйте турниры неудачливых неудачников, и так до посинения. Заметьте, что турнир по-прежнему пройдет в n кругов, но теперь все соперники будут участниками всех кругов. Если во всех встречах побеждают сильнейшие, этот, более тщательно организованный турнир превращается в законченный алгоритм сортировки.

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

1. Ни один из соперников не должен участвовать более чем в одном матче одного круга, а число кругов должно примерно равняться логарифму числа участников.

2. Никакие два соперника не должны встречаться больше одного раза.

Используя изложенные идеи, вы можете оценить и классические способы проведения турниров, такие, как отложенное выбывание, и способы, придуманные вами.

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

Харкнесс (Harkness К.). Official Chess Handbook. David McKay, New York, NY, 1967.

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

Кнут (Knuth D. E.). The Art of Computer Programming/Seminumerical Algorithms. Addison-Wesley, Reading, MA, 1969. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. — М.: Мир, 1977.]

Глава 3 этой «библии» посвящена случайным числам, их порождению и использованию. Вы узнаете об опасности трюкачества в этой области. Рекомендуем вам воспользоваться генератором Макларена — Марсальи, который Д. Кнут описывает в алгоритме М.

Хоэль (Hoel G.) Introduction to Mathematical Statistics. Wiley, New York, NY, 1971.

Для нестатистиков корреляция и прочая статистическая магия кажутся совершенно недоступными человеческому разуму. Автор строго излагает основы статистики, не обманывая читателя.

* Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск», п. 5.3.3. Пер. с англ. — М.: Мир, 1978.

* Шахматный кодекс СССР. — М.: Физкультура и спорт, 1977.