Добавлен: 28.11.2018
Просмотров: 8361
Скачиваний: 76
Тема 3: Составление и оценка турнира
Едва ли не каждый из нас в свое время был болельщиком местной, чуть ли не самой сильной команды. Состоявшийся в конце сезона турнир должен был выявить чемпиона города, округа, штата, страны, мира или Вселенной. Но какое невезение — местные герои проиграли будущему победителю уже в первом круге турнира с немедленным выбыванием. Игра оказалась малоинтересной — никто даже не успел размяться. И ведь как обидно: самые настоящие слабаки в итоге занимают место, которое по праву должно принадлежать нашим парням, а болельщиков вместо волнующей борьбы в финале ждет убогое зрелище.
А виноват во всем турнир с немедленным выбыванием. Пусть имеется 2n команд, n > 0. Тогда в первом круге команда 1 играет с командой 2, команда 3 с командой 4, …, команда 2n − 1 с командой 2n. Проигравшие вылетают, а победители выходят в следующий круг.
Рисунок 3.1. Простой турнир с немедленным выбыванием. Окончательное упорядочение, как это определено в тексте, имеет вид 1, 3, 5, 2, 8, 6, 4, 7.
На рис. 3.1 изображен турнир восьми команд. Если предположить, что более сильная команда всегда выигрывает (т. е. что не бывает срывов), лучшая команда, очевидно, завоюет первое место. Однако второй участник финальной игры может занимать в общей табели о рангах лишь место 2n−1 + 1 при условии, что все более сильные команды оказались в одной группе с победителем. Победитель по мере своего продвижения выведет из розыгрыша хорошие команды, и слабой команде достанутся совсем никудышные соперники. Избежать подобной ситуации можно несколькими способами. Во-первых, команды (в дальнейшем будем называть их соперниками) можно рассеять, чтобы сильные соперники (оценка дается по итогам предыдущих выступлений) разместились по всей турнирной сетке. Например, самый сильный соперник попадает в позицию 1, второй по силе — в 2n−1 + 1, третий — в 2n−1 + 2n−2 + 1, четвертый — в 2n−2 + 1 и т. д. Если предварительная оценка была достаточно точной, сильные соперники не выбьют друг друга в первых кругах. Во-вторых, можно устроить турнир с отложенным выбыванием, когда выбывают после двух поражений. Но на самом деле идеальным решением (хорошо бы еще и практичным!) был бы круговой турнир, в котором все соперники играют друг с другом ровно один раз. В предположении отсутствия срывов сильнейший соперник выиграет 2n − 1 встреч и проиграет 0, второй по силе соответственно 2n — 2 и 1 (уступит лишь сильнейшему), …, а самый слабый — 0 и 2n − 1 (проиграет всем). Трудность в том, что в круговом турнире нужно провести 2n−1(2n − 1) встреч, в то время как в турнире с немедленным выбыванием лишь 2n − 1.
Таблица 3.1. Пример турнира по швейцарской системе
|
Круг 1 Пары |
Победители |
Круг 2 Пары |
Победители |
Круг 3 Пары |
Победители |
Итоговые результаты |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 (3-0) |
|
8 |
|
2 |
|
3 |
|
3 (2-1) |
|
2 |
2 |
3 |
3 |
5 |
2 |
2 (2-1) |
|
7 |
|
5 |
|
2 |
|
4 (2-1) |
|
3 |
3 |
8 |
8 (Срыв) |
4 |
4 |
5 (1-2) |
|
6 |
|
7 |
|
8 |
|
6 (1-2) |
|
4 |
5 (Срыв) |
6 |
4 |
6 |
6 |
8 (1-2) |
|
5 |
|
4 |
|
7 |
|
7 (0-3) |
Этот турнир недостаточно велик, чтобы показать достоинства швейцарской системы.
Оказавшись
между двумя крайностями, выберем
компромиссное решение — швейцарскую
систему. В первом круге соперник,
«посеянный» первым, встречается с
последним, второй — с предпоследним и
т. д. После каждого круга соперники
упорядочиваются в соответствии с
набранными очками. Внутри каждой группы
(с равным количеством очков) соперники
упорядочиваются по среднему числу очков
у побежденных ими противников (тем самым
ничья не учитывается). В следующем круге
соперник, стоящий в описанной классификации
на первом месте, встречается с соперником,
занимающим наиболее высокое место из
тех, с кем он еще не играл. Остальные
пары определяются аналогичным образом:
соперники должны иметь почти равное
количество очков, причем повторные
встречи не допускаются. В табл. 3.1 показан
возможный трехкруговой турнир по
швейцарской системе с восемью участниками.
Крупный шахматный деятель Харкнесс
утверждает, что турнир по швейцарской
системе в 
кругов,
где N — число игроков, правильно расставит
k + 1 первых игроков (и, из соображений
симметрии, k + 1 последних игроков).
Швейцарская система справедливее
немедленного выбывания и гораздо быстрее
круговой. Она позволяет всем соперникам
играть в каждом круге. Вопрос состоит
в том, как ведут себя подобные турниры
в условиях реальных соревнований.
Предположим, имеется 2n соперников.
Соперник 1 — сильнейший, соперник 2 —
второй по силе, …, соперник 2n —
слабейший. Для начала проведем круговой
турнир, записывая результаты каждого
матча. Если встречаются соперники i и
j, i < j, положим вероятность победы
игрока i равной 1/2 + (j − i)/2n+1.
Тем самым более сильный соперник побеждает с вероятностью, превышающей половину. Упорядочим соперников в соответствии с набранным в круговом турнире количеством очков. Внутри каждой группы команд с равным количеством очков упорядочим их по среднему числу очков, набранных побежденными ими соперниками. Если и здесь наблюдаются совпадения, соперники упорядочиваются по исходным номерам. В результате получается круговая классификация, которую мы будем считать самой «справедливой»; она используется для оценки других способов организации турниров.
Следующий шаг состоит в том, чтобы с одной и той же базой данных провести турниры по швейцарской системе и с немедленным выбыванием. Для разбиения соперников на пары в каждом из этих турниров берутся результаты кругового турнира. Заметьте, что в обоих турнирах два соперника могут встретиться лишь однажды. Швейцарская классификация — это упорядочение после заключительного круга (всего n кругов), причем все оставшиеся неясности разрешаются в соответствии с начальным упорядочением. Затем начните турнир с немедленным выбыванием, составив пары для первого круга случайным образом. В классификации по выбыванию победитель финальной встречи идет первым, побежденный — вторым, и, вообще, проигравшие в i-м круге располагаются перед ранее выбывшими и после всех победивших в i-м и следующих кругах. Внутри группы побежденных в i-м круге соперники располагается в соответствии с итоговыми местами победивших их команд.
Чтобы сравнить эти классификации, используем новую и старую статистики, Старая статистика — это корреляция мест определяемая как
R = 1 − 6 
(хi −
yi)2/(N3 − N),
где xi — место соперника i в одной классификации, уi — место в другой классификации, N — общее число соперников (в данном случае 2n). Другая статистика подсчитывает совпадения и определяется как М = maxi (∀j) (j ≤ i ⊃ хj = уj).
Тем самым М равно максимальному числу мест (считая от сильнейших к слабейшим), в которых обе классификации в точности совпадают. Статистика R характеризует близость двух классификаций в целом, а M — совпадение верхних частей классификаций.
Тема. Напишите программу, читающую исходное значение n, проводящую каждый из трех турниров для 2n соперников и вычисляющую статистики R и M для каждой из трех пар классификаций. Проведите эксперимент большое число раз с постоянным значением n и подсчитайте средние значения M и R. Сравните, какая из двух систем — швейцарская или с немедленным выбыванием — лучше повторяет результаты кругового турнира.
Указания исполнителю. Разумеется, нужно досконально разбираться в разных системах проведения турниров, нужно эффективно программировать подбор пар. Но не упустите из виду еще один момент. Размеры кругового турнира заставляют эффективно запрограммировать внутренний цикл и экономно расходовать память для хранения результатов встреч. Разумеется, вам понадобится хороший генератор случайных чисел для определения результатов встреч. Наконец, при швейцарской системе возможны попытки дважды свести одну и ту же пару соперников, поэтому либо докажите, что такого не произойдет, либо измените алгоритм, избегая повторных встреч, но подчиняясь общему правилу: старайтесь сводить в пары соперников, набравших почти равное количество очков.
Развитие темы. Большинство расширений включает более подробный анализ и сравнение систем проведения турниров. Во-первых, заметьте, что нижняя часть классификации по итогам турнира с немедленным выбыванием носит довольно произвольный характер. Кроме того, соперникам, попавшим в эту часть классификации, весьма тоскливо, ибо они рано вылетели. Для утешения можно организовать турниры с немедленным выбыванием среди неудачников каждого круга. Результаты этих турниров, а не приведенное выше правило, расставят неудачников по местам. Поскольку и в этих побочных турнирах будут проигравшие, организуйте турниры неудачливых неудачников, и так до посинения. Заметьте, что турнир по-прежнему пройдет в n кругов, но теперь все соперники будут участниками всех кругов. Если во всех встречах побеждают сильнейшие, этот, более тщательно организованный турнир превращается в законченный алгоритм сортировки.
Вообще, турниры — это сортировка участвующих в них соперников, хотя правило сравнения и носит вероятностный характер. На основе любого метода сортировки, не нарушающего двух основных правил турниров, можно организовать состязание. Вот основные правила:
1. Ни один из соперников не должен участвовать более чем в одном матче одного круга, а число кругов должно примерно равняться логарифму числа участников.
2. Никакие два соперника не должны встречаться больше одного раза.
Используя изложенные идеи, вы можете оценить и классические способы проведения турниров, такие, как отложенное выбывание, и способы, придуманные вами.
В голову приходит также несколько статистических вопросов. Как влияет частичное или полное рассеивание на турниры с немедленным выбыванием? Как влияет случайная жеребьевка (т. е. случайное составление начальных пар) на ход турниров по швейцарской системе? Каков будет эффект введения иной функции превосходства? Наконец, поскольку для получения итоговой статистики по нескольким экспериментам, видимо, нельзя просто усреднять две наши статистики, спрашивается: какая статистическая операция должна быть использована?
Тема 4: Управление предприятиями и машинное моделирование
Моделирование нередко оказывается удобным средством для изучения тех или иных ситуаций, которые характерны для реальной жизни. Процесс моделирования дает нам кроме множества курьезов некоторые знания об изучаемом объекте. В самом деле, многие так увлекаются исследованием модели, что уже не возвращаются к объекту как таковому. Попробуйте, что получится у вас.
Деловая игра Менеджмент[12]
Решением совета директоров крупного промышленного концерна вы назначены президентом компании. Компания владеет несколькими фабриками. Каждый месяц компания покупает сырье, обрабатывает его и продает изготовленную продукцию публике, ждущей ее с нетерпением. Вам теперь придется решать, сколько и каких товаров выпускать, стоит ли и когда именно расширять производственные мощности, как финансировать их расширение и как принять скромно-застенчивый вид, отчитываясь о незаконных прибылях. Перед тем как приступить к работе, вы строите модель промышленности в целом, чтобы в частном порядке отработать свою линию поведения. И вот какую игру вы в результате изобрели.
Начальная ситуация
Моделирование ведется с шагом по времени в один месяц. В начале игры каждый игрок (президент компании) получает две обычные фабрики, четыре единицы сырья и материалов (сокращенно ЕСМ), две единицы готовой продукции (сокращенно ЕГП) и 10000 долл. наличными. Игроки занумерованы от 1 до N, и в первом круге игрок 1 — старший. С каждым кругом (т. е. ежемесячно) роль старшего переходит к следующему по порядку номеров игроку, после N-го старшим становится опять первый (так что номер старшего в круге Т вычисляется по формуле (Т mod N) + 1). На торгах при прочих равных условиях выигрывает самый старший игрок (тот, кто будет старшим в следующем круге).
Ежемесячные операции
Описанные ниже сделки происходят каждый месяц и именно в таком порядке. Если в какой-то момент компания не может выполнить своих финансовых обязательств, она немедленно объявляется банкротом. Ее имущество пропадает, и она выходит из игры (так что лучше иметь наготове запас наличных). Все денежные расчеты происходят между отдельными игроками и одним общим банком. Невозможна передача денег прямо от игрока к игроку, что исключает сговор, направленный против какой-либо компании. Банк, кроме того, контролирует источники сырья и скупает всю готовую продукцию.
1. Постоянные издержки. Каждый игрок (в порядке убывания старшинства, начиная со старшего) платит 300 долл. за каждую имеющуюся у него ЕСМ, 500 долл. за каждую наличную ЕГП, 1000 долл. за владение каждой обычной фабрикой и 1500 долл. — за владение автоматизированной. Это постоянные ежемесячные издержки каждого игрока, даже если он в этом круге не предпринимает никаких других действий.
2. Определение обстановки на рынке. Банк решает и сообщает игрокам, сколько ЕСМ продаст в этот раз и какова их минимальная цена. Объявляется также, сколько ЕГП в общей сложности будет закуплено и какова максимальная цена.