9.2. Обучение игре в шашки

А. Сэмюэль, инженер фирмы ИБМ, написал для игры в шашки хорошие программы в период с 1956 по 1967 г. В шашки играют на доске . Пешки (шашки) могут ходить только вперед, дамки — через поле, вперед и назад. Возможность превращения пешки в дамку требует около 8 ходов.

9.2.1. Запоминание наизусть

Первая программа, написанная Сэмюэлем, относилась к уровню 2. Он просмотрел около 180 000 позиций, взятых из лучших книг, для обучения своей программы! Так как это

довольно много (особенно для машин того времени), Сэмюэль воспользовался тремя процедурами управления памятью.

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

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

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

Рис. 9.2. Схема игровой доски.

Кроме того, некоторые полагают, что его идеи имеют отношение и к размеру слои на машинах ИБМ серий 700 и 7000, когда ему удалось найти хорошее представление для игровой доски (так как пешки ходят только по черным полям). Сэмюэль занумеровал поля расширенной схемы доски так, как показано на рис. 9.2.

Четыре дополнительных поля 9, 18, 27 и 36 играют роль ограничителей и вся доска может быть представлена в виде вектора [1, 36] в одном машинном слове. Чтобы получить допустимые правилами ходы (без взятия), достаточно к номерам черных полей добавлять цифру 4 или 5 (перемещение и превращение).

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

Он выбрал 38 параметров и 38 характеристик среди которых отметим материальный выигрыш, контроль центра, число выдвинутых пешек, мобильность, число V-позиций (свободное поле, окаймленное тремя черными пешками), число угроз, относительную продвинутость обоих лагерей.

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

Воспользуемся описанной программой в трех различных случаях.

9.2.2. Усвоение знаний из книг

Поскольку в памяти находятся все позиции, программа может оценить их во время каждой игры, пользуясь минимаксной процедурой с функцией оценивания Она подсчитывает по Р число Я ходов, лучших по сравнению с хранящимися в памяти, и число худших ходов Если Н мало, велико, между рекомендацией из книг и произведенным оцениванием наблюдается соответствие. В противном случае коэффициент «корреляции» С

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

где — число ходов, стоящих в соответствии с перед наилучшим ходом с число ходов, стоящих в соответствии с после наилучшего хода с

Если отрицательно, нужно уменьшить значения положительных Если положительно, нужно увеличить значения отрицательных Таким образом, программа обучения по книгам «решает» заменить параметр с наибольшим абсолютным значением коэффициента С, полагая

В результате программа сохраняет лишь 16 из 38 исходных характеристик. В каждый момент имеют значение 0. Для каждой партии наименьшее С дает штрафное очко

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

После двадцати партий программа усвоения знаний по книгам выходит на достаточно высокий уровень.

9.2.3. Обучение без учителя

Так как речь идет об игре, то программа может играть сама против себя. Пользуясь разными значениями она может в этом случае усваивать знания самостоятельно!

Пусть А и В— две версии программы с функциями оценивания Если А выигрывает, то слегка изменяются параметры если А проигрывает, она получает штрафное очко. После трех штрафных очков производят взаимный обмен функциями и существенно изменяют параметры Этот вариант представляет собой попытку использовать классический метод градиента с возмущениями в невыпуклом пространстве.

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

9.2.4. Обобщенное обучение

Именно так определил Сэмюэль возможности новой программы. Он не хотел согласиться с тем, что ни одна из его предыдущих программ не могла обучаться во время сеанса игры. Ведь мы отдаем себе отчет в совершении ошибки уже через несколько часов и избегаем ее повторения в текущей партии. Программа с использованием функций оценивания и процедурой альфа — бета также обладает свойством апостериорного оценивания ходов: один раз она встречается с определенной позицией во время оценивания, а другой — через несколько ходов на реальной игровой доске (рис. 9.3).

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

где теперь обозначает число случаев с начала партии, в которых для характеристики выполнялись неравенства

Для алгоритм тот же, но с учетом симметрии.

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

В начале характеристики игры этой последней программы Сэмюэля относительно нестабильны, но в ее распоряжении уже имеется 180 000 ходов, введенных ранее для предыдущей программы, и ночами она может играть против себя.

Рис. 9.3. Два примера оценивания одной позиции. а — ситуация, встречаемая при поиске с использованием процедуры альфа—бета. Ее оценка представляется та же ситуация во время реальной игры: оценка

В результате Сэмюэль постоянно стал проигрывать в шашки своей собственной программе.

Несколько позже эта программа, достигнув беспрецедентного для игровых программ уровня, выиграла у чемпиона штата Коннектикут (К. Nealey, 1962), оказала достойное сопротивление чемпиону мира, хотя и проиграла ему по переписке четыре партии (W. Heilman, 1965).

Программа играла все лучше и быстрее (вероятность наличия текущей позиции среди имеющихся в памяти возрастает с течением времени). Однако такое обобщенное обучение включало определенный риск, и Сэмюэлю повезло его обнаружить: обучение зависит от качества игры противника: если тот играет плохо, то и в программе устанавливаются плохие параметры. Действительно, использование минимаксной процедуры предполагает, что противник играет наилучшим для себя образом. Если же противник играет плохо, программа делает из этого вывод (и неверный), что позиция была недооценена и меняет параметры. А так как обучение связано с каждым ходом (даже в течение партии), то совокупность параметров может быть полностью изменена уже через пятнадцать ходов. И тогда программа начинает сама играть плохо, так что противнику достаточно “неожиданно” начать играть хорошо для выигрыша всей партии!

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

• По построению функция оценивания является линейной по каждой из характеристик. Однако некоторые характеристики должны усиливаться.

Рис. 9.4. (см. скан) Иерархия сигнатур на трех уровнях.

Так, если дают преимущество черным, то член с должен выражать такое преимущество.

• По определению общая функция может быть представлена в табличной форме. Так как на учете имеются 38 характеристик, идеальной была бы таблица, соответствующая отображению

При необходимости должен быть найден компромисс между слишком грубым линейным изменением, с одной стороны, и такой большой таблицей — с другой.

Сэмюэль использовал идею таблиц сигнатур — иерархии таблиц, представляющей хорошее приближение к рассматривает мой выше общей функции: 38 характеристик группируются по типу (некоторые могут входить в разные группы); к одному типу относятся те характеристики, которые считаются, по мнению экспертов и самого Сэмюэля, взаимосвязанными. Каждая из них ограничена тем, что может принимать не более семи различных значений. В то же время коэффициент теперь приписывается всей комбинации значений внутри одного типа. На рис. 9.4 приведена общая схема расположения таблиц сигнатур.

Сэмюэль вновь ввел 180 000 экспертных ходов и рассчитал параметры с использованием метода корреляции. Было установлено, что примерно после 80 000 ходов ситуация стабилизируется. В действительности все происходит так, как если бы каждый матричный элемент был единственным элементом: имеется 315 X 9 элементов для типа А, 125 X 3 для типа В и 343 для типа С, т. е. около 3500 элементов вместо 16 в программе 1.

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

Отметим, что это время весьма незначительно, потому что оценивание представляет просто поиск в таблице. Вычисление происходит по одной инструкции:

Эта программа стала и останется настоящим чемпионом мира игры в шашки. Без использования процедуры альфа — бета она выбирает наилучший ход в случаев (против с полиномиальным оцениванием и со случайным выбором), а с использованием процедуры альфа — бета существенно улучшает ее показатели. Кроме того, рассмотренный подход придает игре регулярность — исключает плохие ходы в течение всей партии.

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

Коллектив исследователей продолжил поиски в этом направлении и спроектировал систему, способную порождать некоторую совокупность действий, полезных для целого ряда ситуаций. Это исследование проводилось в области робототехники, и система называлась STRIPS (Stanford Research Institute Planning System) (Fikes, Nilson, 1973).