Партнеры

Счетчики








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

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

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

Итак, каждому игроку сопоставлено случайное число Fn из отрезка [0..1]. Эти числа хранятся в массиве (tChampionship.list). Таким образом, набору из Np игроков соответствуют первые Np чисел этого массива. Массив является полем единственного используемого в программе класса tChampionship (не считая классов VCL). Еще ряд полей соответствуют параметрам проведения чемпионатов: число игроков Np (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 год