Программа исследования систем

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

На основе вышеизложенной теории и при помощи современного инструмента программирования Delphi 4 написана программа для получения статистических численных оценок систем проведения чемпионатов. Программа позволяет проводить серии чемпионатов по любой из выбранных шести систем с количеством чемпионатов от ста до миллиона. Для сопоставления результатов различных систем количество игроков ограничено выбором из восьми, шестнадцати, тридцати двух или шестидесяти четырех. Обеспечена возможность изменять следующие параметры: параметр широты спектра участников - А, количество выигранных партий, необходимое для победы в матче - k, количество туров в швейцарской системе для данного числа игроков - Sw[N_p] (где N_p - количество игроков). Для генерации наборов игроков, а также для определения победителя в партии используется датчик случайных чисел. Кроме того, в целях тестирования и сопоставления реализовано проведение чемпионата "без правил", то есть случайное распределение мест. Ниже будут подробнее рассмотрены некоторые особенности реализации данной программы. Исходные тексты программы находятся в приложении 1.

Итак, каждому игроку сопоставлено случайное число F_n из отрезка [0..1]. Эти числа хранятся в массиве (tChampionship.list). Таким образом, набору из N_p игроков соответствуют первые N_p чисел этого массива. Массив является полем единственного используемого в программе класса tChampionship (не считая классов VCL). Еще ряд полей соответствуют параметрам проведения чемпионатов: число игроков N_p (num), параметры А, k, массив Sw (paramA, ngam, swnum). За генерацию наборов игроков отвечает соответствующий метод этого класса (CreateList). Отдельный метод отвечает за проведение партии (Game). Он принимает в качестве параметров номера первого и второго участников партии и в зависимости от результата возвращает значение равное first или second. Условия выигрыша в партии соответствуют описанному в теории. Еще один метод реализует матчи (Match) и имеет тот же интерфейс, что и предыдущий. Для получения результатов чемпионата определены еще три поля. Первое - массив натуральных чисел (reso) - для распределения точных занятых мест. Второе - массив натуральных границ интервалов (rest) - для распределения занятых совокупных мест. Третье - флаг (tflag) - для указания в каком из первых двух содержится результат последнего чемпионата. Для хранения реального порядка игроков отведено отдельное поле (order) - массив натуральных чисел. Для определения этого порядка используется первый из следующих двух методов. Эти два метода предназначены для нахождения порядка, причем первый (FindOrder) порождает порядок без совокупных мест, а второй (FindTable) - с ними. На входе эти методы принимают массив действительных чисел. Все остальные методы делятся на три группы: отвечающие за интерфейс (GetXXX, SetXXX), проводящие чемпионат, считающие численные оценки результатов. Остановимся на последних двух.

Метод для круговой системы (SystemRound) заполняет таблицу нулями и единицами, затем считает суммы по строкам. Его результат содержит совокупные места. Это связано с невозможностью реализации правила, исключающего подобные ситуации. Дело в том, что редко получается так, что равное количество очков набирают всего два участника. Чаще всего образуются группы по несколько игроков с одной суммой, при этом в плане личных встреч они зачастую образуют сложные циклы. В результате редко появляется возможность выделить в такой группе хотя бы одного игрока, победившего всех остальных и заслуживающего более высокой позиции в итоговой таблице. Кроме того, информация о том, что два игрока набрали одно количество очков, говорит гораздо больше об их равенстве, чем результат всего одной партии - о чьем-то превосходстве. Итак, результат реализованного чемпионата по круговой системе может содержать совокупные места. Так же как и сами системы, методы, отвечающие за олимпийские системы, незначительно отличаются от методов соответствующих олимпийских систем с матчами. Обычные олимпийские системы (SystemOlimpic, SystemOlimpicMatch) в итоговых таблицах содержат совокупные места, а рекурсивные (SystemOlimpicA, SystemOlimpicMatchA) - не содержат. Швейцарская система (SystemSwis) также не исключает совокупных мест и не соблюдает правила предпочтительной игры с новым игроком. Во всех олимпийских системах первые четыре места занимают по одному игроку, в то время как в круговой и швейцарской не исключено, что первое место станет частью совокупного места. Все методы, проводящие чемпионаты, не имеют ни входных, ни выходных параметров, но оперируют напрямую с полями класса. Результаты работы этих методов, содержащиеся в тройке полей (reso, rest, tflag), обрабатываются методами вычисления оценок.

Оценка вероятности победы сильнейшего (EvalWin) считается как действительное число и равна 1, если сильнейший один занял первое место, 0 если он на первое место не попал и 1/s, если вместе с ним первое совокупное место делят s игроков. В трех других оценках (EvalDif, EvalMid, EvalTri) в случае, когда игрок попадает на совокупное место, его место считается как среднее между краями данного совокупного.

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

Для проведения серий описан его потомок (tStat), содержащий ряд дополнительных полей и методов. Добавлены следующие поля: число чемпионатов в серии (number), система проведения (system), четыре суммарные оценки (sumwin, sumdif, summid, sumtri) и четыре результирующие (win, dif, mid, tri). Соответственно добавлены методы интерфейса и три метода, ответственных за стадии эксперимента. Первая стадия (Start) - инициализация, вторая (Step) - шаг, включающая проведение одного чемпионата и изменение суммарных оценок, третья (Stop) - завершение, где определяются результирующие оценки. Вот основные моменты реализации приводимой программы.

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