[Содержание] [Предыдущая глава] [Следующая глава]
Как было замечено в главе 4 одним из первый этапов разработки самообучающейся программы по новому методу должен быть выбор эффективной процедуры отбора программ-игроков. Нужно, чтобы среди нескольких алгоритмов определялась группа лидеров, и чтобы это делалось по возможности точно и быстро. По аналогии с людьми, это будет происходить в форме своего рода чемпионатов. Их участниками будут разные программы-игроки, проводиться они будут программой-судьей. Под программой-игроком на самом деле понимается отнюдь не отдельный исполняемый файл, а лишь некая абстрактная программа, которая складывается из алгоритма и какого-то зафиксированного набора изменяемых свойств этого алгоритма. Программа-судья - это и есть самообучающаяся система, которая содержит алгоритм игры и различные фиксированные наборы свойств (различных игроков), она же осуществляет алгоритм самообучения и проводит чемпионаты на одном из шагов этого алгоритма.
Данная работа содержит описание и результаты подробных исследований различных систем проведения чемпионатов (в дальнейшем СПЧ или система) на предмет их эффективности применительно к описанной выше задаче. Определим требования к такой системе.
Партия в шахматы между людьми может длиться часами. Партия в нарды тоже занимает немало времени. Нередко компьютер тратит на выбор хода не меньше времени, чем человек. Чемпионат по шахматам среди людей обычно длится несколько дней (месяцев, лет - зависит от масштаба). При этом много времени уходит на отдых игроков, то есть на промежутки между партиями, зато несколько партий могут проводиться одновременно. Так как ресурсы, которыми сможет пользоваться реальная программа обучения, скорее всего будут ограничены одним процессором, то одновременное проведение двух или более партий не будет рациональным, или по крайней мере, не даст никакого выигрыша по времени. Ввиду этого будем полагать, что партии программой играются последовательно. Так как все партии в нашем случае на деле играются одной программой, то есть соперничающие программы пользуются одними и теми же структурами данных, то перерыв между партиями требуется только для запоминания результата предыдущей партии и выбора следующих противников. Первое делается практически мгновенно, второе, даже для самой сложной системы и большого количества участников, также занимает на много порядков меньше времени, чем одна партия. Следовательно, критическим параметром для СПЧ является количество игр для данного числа участников. Другой критерий выбора системы - это её точность, т. е. на сколько верно она выбирает лучших. Реально, данный критерий распадается на несколько различных численных оценок системы. В данной работе выбраны следующие три:
Количество игр и точность - это два основных критерия. Есть ещё ряд косвенных. Первый - динамичность оценок точности. Это значит что предпочтительнее метод, в котором можно достичь требуемых оценок точности, увеличив соответственно количество партий. Заметим, что это можно сделать для любой системы по крайней мере одним способом - проводя чемпионат несколько раз. Второй - ограничения, накладываемые на число участников. При прочих равных характеристиках, предпочтение, конечно, следует отдать более гибкой системе. Итак, мы ищем СПЧ со сравнительно небольшим числом партий для данного числа игроков, определяющую лидеров с наибольшей точностью, причем желательно иметь возможность повышать эту точность, увеличивая число партий, и чтобы ограничения на число участников по возможности отсутствовали.
Для простоты в дальнейшем будем считать, что ничья исключена. Это также связано с ориентированностью на нарды, где ничья действительно исключена.
Теперь посмотрим, какими СПЧ мы располагаем для выбора, и что они из себя представляют.
Первая - это круговая система. Каждая пара участников играет одну партию. За каждую победу игроку записывается одно очко, за поражение - ноль. Места распределяются в соответствии с количеством набранных очков. При равенстве очков двух игроков более высокое место занимает выигравший у другого партию (о трудностях реализации этого правила подробнее рассказано при описании программы). В результате каждый участник занимает одно место в таблице. Никаких ограничений числа участников. Варианты системы с большим количеством партий для каждой пары не рассматриваются в связи с тем что сводятся к многократному проведению чемпионата.
Вторая система - олимпийская. Предполагается число участников равное степени двойки. Чемпионат проводится в несколько туров. В туре все игроки разбиваются на пары, каждая пара играет одну партию, победители проходят в следующий тур. В последнем туре играют два участника, и он называется финалом. Предпоследний тур называется полуфиналом, проигравшие полуфиналисты играют между собой за третье место. В результате все четыре полуфиналиста распределяются по первым четырем местам, а все остальные игроки занимают совокупные места: с пятого по восьмое, с девятого по шестнадцатое и т. д.
Следующая система - олимпийская с матчами. Она в точности повторяет олимпийскую за исключением того, что прохождение в следующий тур решается не партией, а матчем. В матче участвуют два игрока, побеждает тот, кто первым выиграет k партий. Матч завершается сразу после определения победителя.
Еще две рассмотренные системы суть производные олимпийских. Они отличаются тем, что в них исключается возможность занятия участниками совокупных мест. Участники не прошедшие в следующий тур делят доставшиеся им места по той же самой системе. Назовем эти системы соответственно олимпийская рекурсивная и олимпийская рекурсивная с матчами.
Последняя из исследованных систем называется швейцарской и часто используется шахматистами. Сначала определяется число туров для данного числа участников. Обычно оно немного превосходит число туров в олимпийской системе для того же числа участников. При этом на число участников накладывается только требование четности. В каждом туре участников разбивают на пары так, чтобы в каждой паре оказались игроки с наиболее близким количеством очков. Следят также, чтобы по возможности каждый участник играл каждый раз с новым (в реализации для простоты это правило опущено). Очки начисляют за каждую выигранную партию по одному. Каждая пара играет одну партию. Итого, исследовано шесть СПЧ. Как видно, среди них есть и похожие, и весьма разные.
Из двух шахматистов более сильным считается тот, который чаще у другого выигрывает, чем проигрывает ему. Тем не менее, более сильный шахматист может проиграть менее сильному. Существует подобная вероятность и для игровых программ. Положим, что всем участникам чемпионата можно найти объективные оценки силы их игры, как числа в диапазоне от 0 до 1. Будем обозначать Fn такую оценку силы n-го игрока. Положим также, что эти оценки удовлетворяют следующим условиям. Если игрок n не слабее игрока m, тогда Fn>=Fm, при этом вероятность того, что партия будет выиграна игроком n, равна 0,5, если (Fn-Fm)=0, равна некоему числу A из отрезка [0,5..1], если (Fn-Fm)=1, и линейно зависит от разности (Fn-Fm) на интервале (0..1). Оценки Fn и число A зависят от набора игроков. Число A характеризует близость по силе игры игроков в группе. При А=1 самый сильный игрок может постоянно выигрывать у самого слабого. При А=0,5 все игроки играют наравне. Распределение оценок Fn по отрезку [0..1] никак не ограничивается, но сами оценки выбираются так, чтобы занять весь отрезок (в реализации использовано равномерное распределение). Таким образом, мы описали модель группы игроков, участвующих в чемпионате. Эта модель обладает основными свойствами реальной системы, хотя и упрощена. Её немаловажным преимуществом является легкость в программировании. Аналогом используемых в модели оценок Fn в жизни можно считать рейтинг, который вычисляют для крупных шахматистов. В данном случае группа игроков весьма велика, оценка игрока определяется отношением его рейтинга к самому высокому рейтингу из имеющихся. Остается только правильно подобрать параметр А. Разница заключается в том, что наши оценки Fn мы полагаем абсолютно объективными, в то время как рейтинг шахматистов зависит от их участия и успехов в соревнованиях.
Итак, определена процедура моделирования игроков, партии между двумя из них и нахождения победителя в ней.
Теперь рассмотрим вопрос о том, как же получить требуемые оценки СПЧ. Используя описанную выше модель игроков и партий, можно также создать модель чемпионата. В результате появится возможность сравнить, места, которые заняли игроки, с тем порядком в котором идут их объективные оценки. В силу того, что характеристики модели описываются вероятностно, то результаты единичного чемпионаты не будут информативными. Для получения исчерпывающей информации о системе, необходимо многократное проведение чемпионата. Такое многократное проведение чемпионата по одной системе будем называть серией. Численные оценки системы в таком случае будем вычислять как среднее арифметическое от оценок всех чемпионатов в одной серии. Точность полученных оценок будет зависеть от количества чемпионатов в серии, поэтому окупит себя простота выбранной нами модели.
На основе вышеизложенной теории и при помощи современного инструмента программирования 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) считается как действительное число и равна 0, если сильнейший один занял первое место, 0 если он на первое место не попал и 1/s, если в месте с ним первое совокупное место делят s игроков. В трех других оценках (EvalDif, EvalMid, EvalTri) в случае, когда игрок попадает на совокупное место, его место считается, как среднее между краями данного совокупного.
Класс с перечисленными полями и методами можно использовать для проведения единичных чемпионатов.
Для проведения серий описан его потомок (tStat), содержащий ряд дополнительных полей и методов. Добавлены следующие поля: число чемпионатов в серии (number), система проведения (system), четыре суммарные оценки (sumwin, sumdif, summid, sumtri) и четыре результирующие (win, dif, mid, tri). Соответственно добавлены методы интерфейса и три метода, ответственных за стадии эксперимента. Первая стадия (Start) - инициализация, вторая (Step) - шаг, включающая проведение одного чемпионата и изменение суммарных оценок, третья (Stop) - завершение, где определяются результирующие оценки. Вот основные моменты реализации приводимой программы.
Теперь приступим к описанию самих исследований. Они состояли из двух стадий. На первой стадии найдено количество партий, необходимое для проведения чемпионатов по различным системам, с различным числом участников. На второй - получены статистические оценки точности систем. Далее проводится анализ статистических данных. Наконец, на основании критериев ресурсоемкости и точности делаются выводы об эффективности рассмотренных систем.
Первая стадия исследований заключалась в подсчете количества игр, необходимого для проведения одного чемпионата по каждой системе.
Для круговой системы это число определяется формулой:
N = Np*(Np-1), где N - количество партий, Np - количество игроков. Можно сказать, что количество партий в данной системе растет как с квадрат числа участников.
Для олимпийской системы на каждого игрока приходится ровно одна партия, то есть:
N = Np, если Np=2^d, где d = 2,3,4… Для олимпийской системы с матчами имеем оценку сверху:
N < = Np*(2*k-1), где k - количество партий, которые надо взять, чтобы выиграть матч, Np= 2^d, d = 2,3,4... Другими словами число партий здесь зависит от числа участников линейно, но так же линейно зависит от удвоенного значения параметра k.
Для рекурсивной олимпийской системы число партий будет таким:
N = Np/2*d, Np = 2^d, d = 2,3,4...
Соответственно для рекурсивной олимпийской системы с матчами имеем:
N < = Np/2*d*(2*k-1), Np = 2^d, d = 2,3,4…
Считая, что для Np игроков в швейцарской системе проводится Sw[Np] туров, количество партий найдем по формуле:
N = Np/2*Sw[Np].
В данной работе по умолчанию принимаются такие значения:
Sw[8] = 5; Sw[16] = 7; Sw[32] = 10; Sw[64] = 13.
В любом случае, если Np = 2^d, d = 2,3,4…, то Sw[Np] > d, так как при Sw[Np] = d швейцарская система вырождается в рекурсивную олимпийскую. Заметим еще, что в данной реализации приблизительно выполняется равенство Sw[Np] = 2*d.
Полная таблица количества партий в разных системах при разном количестве игроков приведена в приложении 2.
На второй стадии исследований были проведены эксперименты при помощи написанной программы и получены некоторые статистические данные. Относительная простота модели и достигнутый уровень оптимизации алгоритмов позволили проводить экспериментальные серии по 100000 чемпионатов, а в случае с Np = 8 - 1000000 чемпионатов. Результаты серий по разным системам, но с одним набором параметров объединены в таблицы. Всего получено таблиц - 16. Они делятся на четыре группы по пять таблиц для каждого числа участников. В каждой группе первая таблица соответствует параметру А = 0.5 и содержит дополнительный столбец с результатами для чемпионатов "без правил", то есть случайного распределения мест. Эта таблица не несет информации о точности системы, а предназначена для оценки адекватности выбранной модели и имеющейся реализации. Четыре последующих, и основных, таблицы соответствуют значениям параметра А = 0.65, 0.75, 0.85 и 1. Значение 1 выбрано как другое крайнее и, в основном, для проверки некоторых гипотез и большей наглядности полученных данных. Наиболее соответствующими реальной ситуации являются значения 0.65, 0.75 и 0.85. Для каждой таблицы указаны значения всех описанных параметров модели. Все эти таблицы можно найти в приложении 3.
Для начала проанализируем данные из таблиц для значения A = 0,5. Эти таблицы выделяются среди прочих лишним столбцом, который находится сразу за столбцом с обозначениями оценок, отмечен знаком "-" и содержит информацию о чемпионатах "без правил". Значения наиболее легко вычисляемых полей в этом столбце можно найти и чисто теоретически, что мы и сделаем. Итак, если в чемпионате участвуют Np игроков, то вероятность, что какой-то из них, а значит и лучший, окажется на первом месте, равна 1/Np. Для 8, 16, 32 и 64 игроков это составит соответственно 0.125, 0.0625, 0.03125 и 0.015625. Оценка первых трех в свою очередь составит T(Np) = 3*(Np+1)/2-6 = 3*(Np-3)/2, то есть 7.5, 19.5, 43.5, 91.5. Теперь посмотрим на соответствующие поля в таблицах и убедимся, что экспериментальные данные отличаются незначительно. Это подтверждает то, что используемый датчик случайных чисел работает удовлетворительно, по крайней мере в плане распределения вероятностей. Далее, в указанных таблицах сравним значения по строкам. В идеале все значения в одной строке должны совпадать, совпадение свидетельствовало бы о полном соответствии моделей и методов вычисления реальной ситуации. Как видим, отличия здесь есть, но небольшие. Причем наибольшие расхождения соответствуют возможному появлению совокупных мест. Так, например, в таблице 16, в строке D, содержащей полную невязку. Наибольшим отличием от столбца "-" обладают олимпийские нерекурсивные системы, а наименьшим - олимпийские рекурсивные. При этом первые предполагают весьма объемные совокупные места - до половины участников, а вторые исключают совокупные места совсем. Итак, можно говорить о том, что проверка при помощи подстановки параметра А = 0.5 подтвердила непротиворечивость полученных экспериментальных данных.
Теперь обратимся к основным данным. По показателю частоты победы сильнейшего имеем следующие результаты. При Np = 8, 16, лучшие оценки принадлежат олимпийским системам с матчами, затем идет круговая система, затем, с небольшим отрывом, швейцарская, затем олимпийские без матчей. При Np = 32, 64 круговая система "обходит" соперниц и увеличивает разрыв. Разрыв между швейцарской системой и олимпийскими с матчами с ростом Np сокращается. Олимпийские без матчей безнадежно "отстают". По показателям невязки и первой тройки имеем аналогичные результаты, причем с ростом Np швейцарская система обходит олимпийские по всем этим показателям и уступает только круговой. Общий вывод таков: круговая система имеет непревзойденные показатели точности, за ней идут швейцарская и олимпийские с матчами, затем олимпийские без матчей, причем с ростом числа участников швейцарская приближается к олимпийским с матчами по частоте побед сильнейшего и опережает их по остальным критериям. Однако, сопоставляя эти выводы с данными по количеству партий, можно сказать, что показатели точности круговой системы оправдывают себя только при самых малых значениях Np, а среди приемлемых по числу партий систем лидирует швейцарская, так как требует меньшее количество партий, чем олимпийские с матчами, а свое отставание по показателям точности при малых Np компенсирует значительно меньшим числом партий. Далее следует вспомнить о дополнительных критериях отбора СПЧ, а именно о гибкости оценок точности. Увеличить точность в олимпийской системе без матчей можно, лишь превратив её в олимпийскую систему с матчами. Точность круговой системы и без того высока, а увеличивать в ней количество партий вовсе не имеет смысла. Самые гибкие системы - это олимпийская с матчами и швейцарская. Напомним, что увеличить точность в первой можно, увеличив число партий в матче, а во второй - увеличив число туров. При этом число партий с каждым шагом в первом случае будет увеличиваться на 2*Np, а во втором - на Np/2. Очевидно преимущество здесь на стороне швейцарской системы. Наконец, все олимпийские системы имеют один общий недостаток - их алгоритм прост лишь при количестве игроков, равном степени двойки, в то время как для швейцарской системы это требование ограничивается лишь четностью. Заметим, что рекурсивные олимпийские системы исследованы, в основном, для более точной оценки невязки соответствующих олимпийских систем и сами по себе отдельного интереса не представляют.
Итак, в соответствии с вышеизложенным, скажем, что наиболее приемлемой системой проведения чемпионатов для задачи обучения игровых программ является швейцарская, но не исключается также возможность использования круговой системы при небольшом количестве участников (порядка восьми), а также олимпийской системы с матчами. Нужно сказать, что подобных выводов можно было ожидать на основании предварительного анализа условий проведения чемпионатов по выбранным системам, но реальные экспериментальные данные отметают по этому поводу все сомнения, а кроме того, могут быть использованы в дальнейшем для адаптации параметров систем под самые конкретные требования реализуемых методов обучения игровых программ. Планируется также использовать приведенную программу для получения в дальнейшем дополнительных необходимых экспериментальных данных по системам проведения чемпионатов.
Важно заметить, что проведенная работа позволяет сделать осознанный выбор системы проведения чемпионатов, а также адаптацию её параметров, для использования в предложенной самообучающейся системе. Таким образом, сделан шаг в направлении усовершенствования и практической реализации нового подхода к написанию программ играющих в сложные позиционные игры.
[Содержание] [Предыдущая глава] [Следующая глава]