9.5. Обучение планам

Эта программа Жака Питра воспринимает партии, реально сыгранные мастерами, пытается разобраться в них и вывести планы игр для других партий. Сначала она реализует лишь две элементарные стратегии:

1) если фигура находится под ударом противника, ее следует переместить;

2) если своя фигура атакует фигуру противника рассмотреть ход

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

В работе программы можно выделить три этапа:

1) разбор ситуации;

2) упрощение и обобщение последовательностей действий;

3) запоминание и использование найденного плана.

Рис. 9.8. Начало партии. Ход белых.

Разбор ситуации

Здесь можно отметить два интересных случая:

1. Пусть последний сыгранный ход — взятие фигуры противника. Рассмотрим, например, позицию на рис. 9.8 и следующие три хода:

Рис. 9.9. Дерево разбора хода (шахматы).

В действительности, для того чтобы понять ход III, нужно понять ход I, который его подготовил, а также ответный ему ход

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

В начале партии, которое нас интересует, мы находим для хода черных IV (пользуясь минимаксной процедурой): или же для хода V мы встречаем: (иначе белые выигрывают фигуру), и при ходе VI черным становится ясно, что они теряют пешку. Урок, извлекаемый из ситуации (позже мы увидим, как программа его формирует и запоминает), можно сформулировать так: “чтобы выиграть пешку, охраняемую только одной фигурой, надо пойтн на обмеи этой фигуры”.

2. Ходы второго типа, которыми интересуется программа, — угрозы, т. е. такие перемещения, которые на следующем ходу ведут к захвату фигуры, если противник не отреагирует соответствующим образом. Программа констатирует угрозу, рассматривает, как и почему противник отражает ее, и обучается даже в том случае, если в действительности на шахматной доске ничего серьезного не произошло (рис. 9.10).

Рис. 9.10. Дерево исследования угрозы.

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

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

Упрощение и обобщение

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

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

• Координаты поля не имеют значения, запоминаются лишь отношения между полями и условия расположения фигур. Так, начальная позиция

Белые: Черные: приводит к исходному дереву

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

которое связано с запиранием коня ладьей.

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

где выступает в роли своей фигуры, меньшей или равной ладье; — фигура противника, более сильная или равная коню; — король противника.

Итак, концепция запирания найдена программой исходя из одного случая.

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

Однако одного усвоения недостаточно, нужно еще уметь так представлять усвоенные знания а машине, чтобы использовать их эффективно: ведь будут порождены тысячи разных планов, и их структурирование (а может быть, и “забывание” некоторой части) совершенно необходимо.

И4зменение и использование планов

Обобщенные деревья размещаются в памяти в форме, аналогичной схемам Минского (М. Minsky, 1972). Каждая схема состоит из трех разных частей — обобщенные ходы, поля, само дерево. Поле отыскивается по формальному имени, которое рассматривается как переменная, и по одному из состояний: пусто, своя фигура, фигура противника с указанием соответствующего значения в двух последних случаях.

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

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

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

Наконец, дерево размещено в. памяти и в каждой вершине стоит номер соответствующего хода. Для данной позиции на Шахматной доске теперь нужно найти все подходящие схемы. Однако это может оказаться дорогой операцией, если не принять мер предосторожности.

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

Таблица 9.1 (см. скан)

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

где значение (стоимость) ноля тем больше, чем менее оно определено. Принимается следующая система: 32 очка за пустое поле; 8 очков за поле, занятое пешкой; 4 очка за поле, занятое фигурой; по 1 очку за поле короля, ферзя или уже известное поле. Наименее вероятный ход определяется по минимуму этой функции, и по ней упорядочиваются ходы в самой схеме.

Тем самым план дерева приводит к схеме (табл. 9.1), которая соответствует рис. 9.11 при ходе черных.

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

реальному дереву начинался бы ходом что приводило бы к 14 вариантам. Однако, упорядочив ходы по рассмотренной выше функции, следует сначала рассмотреть ход

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

Следовательно, исходное поле ладьи должно быть и ход (4) должен быть

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

Рис. 9.11. Использование плана (ход черных).

Заключение. Программа обучается лишь после того, как она разобралась в ситуации. Она нечувствительна к плохим ходам: если в реальной партии хороший ход не был найден, обучения не произойдет, если же был найден лучший ход, чем выполненный, то программа кое-чему научится. Усвоение новых знаний зависит от наличного багажа, потому что для разбора новой ситуации программа использует те схемы, которые уже зарегистрированы. Таким образом, может случиться, что на определенной стадии своего развития программа не сделает трудного хода, а выберет его позже после ряда других партий.

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

минимаксной процедурой в соответствии с внешними факторами или на основе другой долговременной стратегии.

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

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