Исследованные системы

Применение методов искусственного интеллекта в переборных алгоритмах

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

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

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

Следующая система - олимпийская с матчами. Она в точности повторяет олимпийскую за исключением того, что прохождение в следующий тур решается не партией, а матчем. В матче участвуют два игрока, побеждает тот, кто первым выиграет k партий. Матч завершается сразу после определения победителя.

Еще две рассмотренные системы суть производные олимпийских. Они отличаются тем, что в них исключается возможность занятия участниками совокупных мест. Участники, не прошедшие в следующий тур, делят доставшиеся им места по той же самой системе. Назовем эти системы соответственно олимпийская рекурсивная и олимпийская рекурсивная с матчами.

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

Итого, исследовано шесть систем проведения чемпионатов. Как видно, среди них есть и похожие, и весьма разные.

А.В.Мосеев, underwood.narod.ru, 1999 год