Новый подход к самообучению

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

Сущность предлагаемого подхода (развитие и применение которого является предполагаемой темой дальнейшей работы) заключается в постоянном сравнении силы игры сразу нескольких программ. Вместо ряда партий между двумя противниками и нахождения сильнейшего из них, предлагается на каждом шаге проводить своего рода турнир (или серию турниров) для определения одного или нескольких лидеров. Этот подход может быть использован несколькими способами. Например, можно усовершенствовать метод со случайным выбором параметра для изменения. Вместо одного, будем выбирать, скажем, семь параметров и изменять их. В результате получим 8 разных оценочных функций, считая исходную (может случиться так, что все семь потомков неудачны). Среди них проводится серия чемпионатов и выбирается сильнейшая программа. Таким образом, мы частично решаем проблему выбора следующего параметра для изменения.

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

Данный метод можно еще усложнить. Пусть на каждом шаге выбирается лучшая половина программ. Потом каждая из этих программ дает потомка, и так далее. При таком подходе программы, не достигшие наилучших показателей на этом этапе, получают шанс существенно их улучшить на следующем и, возможно, даже обогнать текущих лидеров. Таким образом, решается проблема с возможностью достижения хорошего результата лишь через несколько шагов, как это было названо выше "когда верная дорога находится за поворотом".

Для получения преимуществ обоих описанных методов сформулируем наш алгоритм в более общем виде. Пусть после предыдущего шага мы получили n программ. Постоим от каждой из них m-1 случайных потомков. Проведем серию чемпионатов и выявим среди полученных n·m программ n лучших. На этом текущий шаг цикла завершается. При этом числа n и m лучше выбирать так, чтобы они равнялись степеням двойки с тем, чтобы их произведение, а следовательно и количество участников чемпионатов, было степенью двойки. Это требование связано с тем, что многие схемы проведения чемпионатов рассчитаны именно на такое число участников. С другой стороны, если выбранная схема проведения чемпионатов позволяет, произведение n·m может быть любым, скорее всего от него потребуется лишь четность. Для окончательного определения всей процедуры остается только описать метод выбора первых n программ. Здесь можно взять одну программу и построить n-1 ее случайных потомков. Другой вариант - выбрать n совершенно разных стартовых точек. При этом можно также провести турнир среди гораздо большего количества производных программ. Вероятно, можно найти и другие варианты. Основная идея в том, чтобы стартовые позиции не зависели друг от друга. Это решает проблему локального экстремума, так как стартовые позиции могут оказаться на склонах разных холмов. На этом описание выбора подхода к проблеме обучения игровых программ завершено. Еще раз взглянем на полученную процедуру.

Шаг 0. Подготовка. Выбор вида и набора переменных величин эвристической оценочной функции для данной игры.

Шаг 1. Инициализация. Выбор n независимых наборов параметров для оценочной функции.

Шаг 2. Для каждого из n наборов параметров выполняется шаг 3.

Шаг 3. m-1 раз выполняется шаг 4.

Шаг 4. В текущем наборе параметров случайным образом выбирается один, изменяется, полученный набор добавляется к потомкам.

Шаг 5. Начальные n наборов объединяются со своими n(m-1) потомками. Проводится серия чемпионатов до достижения необходимой точности. Выбираются лучшие n наборов.

Шаг 6. Если выполняется критерий остановки, то переход на шаг 7, иначе переход на шаг 2.

Шаг 7. Остановка.

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

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

Нужно добавить, что в качестве параметров, подвергающихся улучшению, можно использовать не только параметры оценочной функции. Их роль могут играть любые параметры игровой программы, существенно влияющие на качество игры и легко изменяемые, если их невозможно точно определить более простым способом. Такие параметры обычно появляются при использовании различных эвристик и служат в качестве внутренних характеристик для этих эвристик.

Заметим, что данный подход в несколько другом виде уже используется исследователями. К примеру, существует метод так называемой эволюции в популяции из нескольких особей (смотрите "Р.Клемент. Генетические алгоритмы: почему они работают? когда их применять? - Компьютерра, 1999, N11, с.20-23"). Наряду с вышеизложенными приемами, там используется прием кроссинговера, то есть скрещивания. Потомка в этом методе получают не только путем мутации одного из предков, но и как производное двух предков. Таким образом, достигается наследование прогрессивных признаков обоих. В нашем случае эффективность кроссинговера находится под сомнением ввиду сильной зависимости параметров друг от друга. Скрещивание двух хорошо играющих программ даст практически такой же результат, как и выбор случайной программы. Хотя этот вопрос остается открытым, и быть может, ждет дополнительных исследований.

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