Ход исследований

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

Теперь приступим к описанию самих исследований. Они состояли из двух стадий. На первой стадии найдено количество партий, необходимое для проведения чемпионатов по различным системам, с различным числом участников. На второй - получены статистические оценки точности систем. Далее проводится анализ статистических данных. Наконец, на основании критериев ресурсоемкости и точности делаются выводы об эффективности рассмотренных систем.

Первая стадия исследований заключалась в подсчете количества игр, необходимого для проведения одного чемпионата по каждой системе.

Для круговой системы это число определяется формулой: N=N_p(N_p-1), где N - количество партий, N_p - количество игроков. Можно сказать, что количество партий в данной системе растет как квадрат числа участников.

Для олимпийской системы на каждого игрока приходится ровно одна партия, то есть: N=N_p, если N_p=2^d, где d=2,3,4... Для олимпийской системы с матчами имеем оценку сверху: N≤N_p(2k-1), где k - количество партий, которые надо взять, чтобы выиграть матч, N_p=2^d, d=2,3,4... Другими словами, число партий здесь зависит от числа участников линейно, но так же линейно зависит от удвоенного значения параметра k.

Для рекурсивной олимпийской системы число партий будет таким: N=N_p/2d, N_p=2^d, d=2,3,4... Соответственно для рекурсивной олимпийской системы с матчами имеем: N≤N_p/2d(2k-1), N_p=2^d, d=2,3,4...

Считая, что для N_p игроков в швейцарской системе проводится Sw[N_p] туров, количество партий найдем по формуле: N=N_p/2·Sw[N_p].

В данной работе по умолчанию принимаются такие значения: Sw[8]=5; Sw[16]=7; Sw[32]=10; Sw[64]=13. В любом случае, если N_p=2^d, d=2,3,4..., то Sw[N_p]>d, так как при Sw[N_p]=d швейцарская система вырождается в рекурсивную олимпийскую. Заметим еще, что в данной реализации приблизительно выполняется равенство Sw[N_p]=2d. Полная таблица количества партий в разных системах при разном количестве игроков приведена в приложении 2.

На второй стадии исследований были проведены эксперименты при помощи написанной программы и получены некоторые статистические данные. Относительная простота модели и достигнутый уровень оптимизации алгоритмов позволили проводить экспериментальные серии по 100 тысяч чемпионатов, а в случае с N_p=8 - миллион чемпионатов. Результаты серий по разным системам, но с одним набором параметров объединены в таблицы. Всего получено таблиц - 16. Они делятся на четыре группы по пять таблиц для каждого числа участников. В каждой группе первая таблица соответствует параметру А=0,5 и содержит дополнительный столбец с результатами для чемпионатов "без правил", то есть случайного распределения мест. Эта таблица не несет информации о точности системы, а предназначена для оценки адекватности выбранной модели и имеющейся реализации. Четыре последующих, и основных, таблицы соответствуют значениям параметра А=0,65, A=0,75, A=0,85 и A=1. Значение 1 выбрано как другое крайнее и, в основном, для проверки некоторых гипотез и большей наглядности полученных данных. Наиболее соответствующими реальной ситуации являются значения 0,65, 0,75 и 0,85. Для каждой таблицы указаны значения всех описанных параметров модели. Все эти таблицы можно найти в приложении 3.

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