[Содержание] [Предыдущая глава] [Следующая глава]
При создании программ, играющих в такие позиционные игры, как шахматы или нарды, в основном используется так называемая эвристическая схема Шеннона (подробнее в [1], [9]). Дерево игры исследуется на фиксированную глубину. Далее применяется метод максимина для выбора наилучшего хода. Существуют и другие подходы к созданию играющих программ, например метод горизонтов (в книге [2]) , но ни один из них не дал пока результатов, существенно лучше, чем у рассмотренного здесь метода Шеннона.
Для выбора лучшего хода по методу максимина возникает потребность в априорной оценке незаключительных позиций. Другими словами, нужен метод оценки позиции, который не требует информации о возможных вариантах развития ситуации, а использует только информацию о нынешнем расположении фигур или шашек. Такой метод должен давать некоторую численную оценку, по которой можно было бы сравнить любые две позиции и одной из них отдать преимущество, причем желательна по возможности наибольшая адекватность реальному соотношению позиций в игре. Последнее требование корректно в силу того, что любые две позиции в игре, в принципе, действительно можно сравнить и выбрать из них более предпочтительную, либо сделать вывод об их эквивалентности в смысле предпочтения. Это можно сделать при помощи того же метода максимина, если построить полное дерево соответствующей игры. Такую оценку будем считать идеальной, и именно к ней устремлять нашу априорную оценку.
Эвристический метод, используемый для получения подобных оценок, в общем, заключается во введении некоторой числовой функции на множестве позиций, зависящей от ряда переменных, которую называют оценочной функцией (evaluation function). Переменными, обычно служат разного рода элементарные оценки позиции, такие как, например, материальный перевес, пешечные структуры, угрозы фигурам. Функция должна быть легко вычисляема, поэтому её обычно строят в виде линейной функции соответствующих переменных. Некоторые исследователи ищут развитие этого метода в усложнении вида оценочной функции путем введения в нее нелинейных элементов или использования булевых функций. Тем не менее, сложность расчета такой функции имеет критическое значение, так как должна быть оправдана отказом от исследования дальнейшего развития ситуации. Иными словами, время, потраченное на вычисление слишком сложной оценочной функции, может быть с гораздо большим успехом потрачено на просчет ходов из данной позиции, и расчет более простой оценочной функции в полученных позициях.
Так или иначе, оценочная функция определяется набором переменных, видом, и набором параметров. Выбор переменных производится путем анализа экспертных знаний. На этом этапе иногда есть возможность обратиться к литературе по теории данной игры, каковой в избытке можно найти по шахматам. Кроме того, на практике часто очень полезны даже самые элементарные соображения экспертов, имеющих опыт игры. Это очень важно в случае с играми, для которых не создано такой внушительной теоретической базы. В некоторых, достаточно простых играх хватает всего трех переменных, и такая функция делает игру программы сносной; в шахматах их число обычно достигает нескольких сотен. Вид функции, как уже говорилось, определяется сравнительной легкостью вычисления. Последним этапом построения оценочной функции, а зачастую и всей программы, является подбор параметров при переменных (нелинейных или булевых слагаемых), то есть весов соответствующих критериев оценки позиции. Здесь анализа экспертных знаний всегда недостаточно. Часто критерии кажутся несоотносимыми, хотя требуют точнейшей сравнительной оценки. Большое количество переменных, а соответственно и параметров, делает более-менее адекватный их априорный выбор просто невозможным. Еще одна проблема при выборе параметров - их нестабильность в том смысле, что в разных фазах игры, а иногда и в разных игровых ситуациях, наиболее сильной игре соответствуют разные оценочные функции. Может появиться необходимость в течение игры менять как параметры оценочной функции, так и её структуру. В случае с фазами игры можно заранее предусмотреть такую замену, а в случае с различными игровыми ситуациями (которых на практике может оказаться больше, чем в теории) потребуется в процессе игры выбирать адекватную программу. Причем существуют варианты: выбирать из готовых, и/или адаптировать существующую программу, получая новую. Эта частная задача относится к классу задач самообучения игровых программ, который подробнее рассматривается ниже.
Учитывая то, что прочие аспекты построения программ, играющих в сложные позиционные игры (такие как порядок обхода дерева игры и построение частичных оценок позиций), довольно тщательно изучены, и результаты соответствующих исследований широко применяются, можно полагать, что решающую роль в написании таких программ в настоящее время играет именно нахождение наилучшей процедуры выбора оценочной функции. Данная работа рассматривает некоторые проблемы связанные с задачей подбора параметров в оценочной функции на этапе, когда её вид и набор переменных уже заданы (либо существует несколько вариантов таковых).
Раньше в литературе (например, в [4]) можно было встретить следующее определение: процесс изменения свойств системы, позволяющий ей достигнуть наилучшего или по крайней мере приемлемого функционирования в изменяющихся условиях, называется адаптацией. В то же время обучение определялось (там же) как передача знаний или приемов решения задач от обучающего к обучаемому. Как видим, самообучением в таком случае можно назвать получение системой информации, помогающей решать задачи, из собственного опыта работы. Теперь, если в определении адаптации изменить соответствующее условие на "в постоянных или изменяющихся условиях", а как субъект процесса изменения свойств указать саму систему, то полученное определение будет также подходить к понятию самообучения. Именно в таком смысле применяется понятие самообучения в современных работах по сложным позиционным играм (например, в [10]).
Самообучением в этой области в наше время принято называть выбор структуры или подбор параметров системы на основе исследования их оптимальности путем непосредственной подстановки, оценки полученных характеристик системы и соответствующей корректировки. Имеется в виду, что система в процессе работы улучшает свои характеристики, изменяя параметры и приближая их к идеальным, и таким образом "учится" на своем опыте. В применении к сказанному выше можно сказать, что игровую программу можно обучать, изменяя некоторые ее параметры, заставляя ее играть с экспертом или другой программой и закрепляя благоприятные изменения. Наиболее подходящими (но не единственными) параметрами для таких манипуляций являются параметры оценочной функции, так как их изменение не подразумевает никаких изменений в структурах данных или алгоритмах и, соответственно в тексте самой программы. В то же время, эти параметры существенно влияют на качество игры программы.
Одним из самых распространенных подходов к проблеме обучения в подобных ситуациях стал так называемый метод вскарабкивания на холм (hillclimbing, описание программы играющей в короткие нарды и использующей этот метод - в [10]). Он заключается в следующем. За основу берется некоторый стартовый набор параметров. Затем один из параметров изменяют. Программы с неизмененным и с измененным параметром играют друг с другом. Дальнейшие действия производятся с победившей программой и сводятся к повторению предыдущих шагов. Очевидно, что с каждым шагом программа играет не хуже. Даже более того, в силу сказанного выше о существенности параметров оценочной функции, на каком-то шаге программа непременно должна начать играть лучше. Кроме того, если получено повышение качества игры при изменении некоторого параметра, можно исследовать этот параметр в направлении благоприятного изменения с достаточно маленьким шагом и получить своего рода экстремум по этому параметру с соответствующей выбранному шагу точностью. Вообще, если предположить, что качество игры можно численно оценить то нашу задачу можно считать задачей поиска максимума этой оценки как функции, зависящей от набора параметров оценочной функции как от переменных. Теория экстремальных задач предлагает здесь метод покоординатного спуска, возможность использования которого рассматривается далее.
Реально, нет никаких гарантий, что такая функция вообще существует, но часто удобно предполагать её существование, так как у исследуемого объекта иногда проявляются некоторые свойства функции. Главная проблема в такой постановке задачи заключается в заведомом отсутствии градиента и вообще каких бы то ни было частных производных этой функции. Точнее, частные производные и градиент вероятно существуют, но нет никаких подходов к их поиску. Таким образом, пойти в этом направлении дальше метода покоординатного спуска не представляется возможным. С другой стороны, такая аналогия приводит к выводу о том, что метод вскарабкивания на холм поможет нам найти лишь локальный экстремум нашей гипотетической функции. Учитывая, что о характере этой функции не известно практически ничего, можно предположить, что локальный экстремум в данной ситуации может находиться сколь угодно далеко от глобального. Если так, то мы найдем совсем не то, что искали. Предположим теперь, что рассматриваемая игра относится к сложным, и её оценочная функция имеет не меньше десятка параметров. Мы оптимизируем один из них, затем переходим к другому, оптимизируем его.
Одна проблема здесь заключается в том, что следующий параметр может не оптимизироваться при новом значении параметра, оптимизированного первым. При этом не исключено, что его (этот следующий параметр) можно было оптимизировать раньше, а результаты его оптимизации могли превосходить полученные на деле. В результате обнаруживается возможность, выбрав не тот параметр на каком-то шаге, вступить не на тот холм.
Другая проблема возникает уже при выборе третьего параметра для оптимизации, так как совершенно не исключено, что наилучших результатов можно достигнуть, выбрав параметр, уже подвергшийся изменению, вместо десятков ещё не тронутых. Такие рассуждения приводят к выводу, что порядок, в котором должны выбираться параметры для их изменения, может оказаться практически любым. Исключение составляют только случаи, когда один параметр выбирается дважды подряд, ввиду того, что мы договорились искать экстремум по выбранному параметру. Но даже этот момент на деле может подвести. Возможно, дойдя до экстремума по выбранному параметру, мы прошли мимо очень крутого подъема по какому-то другому, и надо было остановиться на половине пути или пройти вдвое дальше. Таким образом, долгое прохождение по значениям параметра для поиска экстремума может быть не оправдано, по сравнению одним случайным, но удачным шагом.
Итак, окончательный вывод выглядит так: при выборе очередного параметра для изменения невозможно учитывать предыдущий порядок выбора параметров. То есть каждый раз, выбирая очередной параметр, мы стоим на распутье, где неоткуда получить никакой априорной информации, куда идти. Два выхода из такой ситуации это: выбрать параметр случайно или попробовать все и остановиться на том, который дает лучший результат. Второй выход сопряжен с огромным расходом времени. Кроме того, что параметров много, неизвестно, на сколько надо их менять. Таким образом, количество проб в таком случае приблизительно равно произведению числа параметров на число предполагаемых вариантов длины шага. Учитывая то, что каждая проба подразумевает состязание двух программ, которое в свою очередь обычно заключается в проведении нескольких партий, делаем вывод, что перебор всех вариантов - задача трудновыполнимая. Кроме того, даже при таком подходе отнюдь не исключается возможность пропустить верную дорогу, так как она может оказаться "за поворотом", то есть необходимо исследовать все возможности на два шага вперед, на три и т.д. Первый выход по крайней мере выполним. В таком методе обучение программы отдаётся на волю случая. Этот подход называют также эволюцией в популяции из двух особей (см. [10]). "Особями" здесь выступают конкурирующие программы, из которых "выживает" сильнейшая, даёт "потомство", которое "мутирует", то есть изменяет один из параметров своей оценочной функции.
Преимуществом этого метода является сравнительная простота. Процесс обучения можно запускать несколько раз из одной стартовой точки и если программы забрались на разные холмы, то можно выбрать забравшуюся на высочайший. Правда не решается проблема зависимости от стартовой оценочной функции. Если стартовую точку и некий холм разделены "оврагом", то программа никогда не заберется на него. Чтобы взобраться на холм, нужно по крайней мере, чтобы стартовая оценочная функция попала на его склон. И даже это не дает гарантии, что программа на него все-таки поднимется вообще и если поднимется, то за конечное время. На практике использование подобных методов нередко приводило, например, к бесконечному кружению по спирали по подножию холма.
Одна из проблем метода вскарабкивания связана с транзитивностью отношения "более сильный - более слабый" игровых программ. Если программа A чаще всего выигрывает у программы B, а та в свою очередь чаще всего выигрывает у программы C, то последняя может чаще всего выигрывать у программы A. То есть транзитивность этого отношения стоит под вопросом. Программа, играющая на среднем уровне, может в силу стечения обстоятельств иметь, скажем, всего одну, но очень эффективную стратегию против гораздо более сильной программы и постоянно её обыгрывать. При этом эта стратегия не действует против других более сильных программ. Такие примеры существуют в жизни. Так, величайшего шахматиста Александра Алёхина, очень часто обыгрывал шахматист значительно менее высокого уровня Лайош Асталош. Известны и другие случаи подобного "везения", в том числе и в командных играх, что говорит о том, что это свойство нетранзитивности не является результатом каких-то психологических феноменов, а присуще самим играм, в особенности сложным позиционным.
Возможность такого свойства игр ставит под угрозу подход к обучению игровых программ, в котором все решается путем состязания только двух программ. Нередко может возникать ситуация когда предпочтение будет отдано программе более слабой, но знающей всего один изъян в стратегии другой. Учитывая то, что такой неверный выбор может быть сделан неоднократно в течение одного сеанса обучения, можно опасаться, что в результате программа вообще скатится вниз. Таким образом, невозможно быть уверенным даже в том, что описанный выше метод вскарабкивания на холм корректен. Он может привести к неконтролируемому понижению качества игры программы, что может выяснится слишком поздно. Возможна (и встречалась на практике - [10]) ситуация, в которой на некотором шаге метод вернется к исходной или уже встречавшейся оценочной функции. Все это требует поиска иного подхода к решению задачи обучения.
[Содержание] [Предыдущая глава] [Следующая глава]