Эвристическое программирование

К моменту появления компьютеров разрозненные данные психологии, этнологии, зоопсихологии, педагогики и методологии науки свидетельствовали о том, что интеллект удобно представлять как способность к решению задач (проблемных ситуаций), а сам процесс решения (мышление) реализуется как поиск такой цепочки действий, которая начальную ситуацию (условие задачи) переводила бы в конечную ситуацию (ответ). Начиная с некоторого уровня развития живых организмов, перебор действий путем их фактического исполнения заменяется «виртуальным» перебором «свернутых» действий. В математике в это время в целях строгого описания правильных рассуждений было формализовано понятие алгоритма, развертывающегося в зависящую от исходных данных последовательность действий и описывающего решение задачи в общем виде. Компьютеры были созданы как устройства, автоматически выполняющие алгоритмы, т. е. решающие задачи, представленные в символьной форме. Однако оставался ключевой вопрос: как находить сами алгоритмы или хотя бы линейные цепочки последовательных действий? Из-за NP-полноты или даже неразрешимости общей проблемы поиска полный перебор всех возможных вариантов во многих случаях оказывается неосуществимым.

Согласно Пойя, человеку удается в какой-то мере преодолевать данную проблему, используя эвристики — приемы, облегчающие решение задач. Но можно ли эвристики запрограммировать? А если можно, в каком виде это следует делать? Попытка ученых ответить на эти вопросы привела в 1950–60-х годах к возникновению одной из первых парадигм искусственного интеллекта, получившей название «эвристическое программирование». В области ИИ с момента ее возникновения существовало много различных направлений исследований, но именно эвристическое программирование можно охарактеризовать как первую попытку создания действительно общей теории искусственного интеллекта.

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

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

Пусть перед нами стоит задача научить компьютер играть в простейшую интеллектуальную игру — «крестики-нолики» на поле 3×3. Как бы вы стали решать такую задачу?

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

Обозначим клетки доски в «шахматном» стиле: от A1 до C3. Тогда такой алгоритм игры (с использованием синтаксиса языка С++) может выглядеть примерно так

make_move (′X′, ′′B2′′);
if (last_move (′O′) == ′′A1′′) {
   make_move (′X′, ′′C2′′);
   if (last_move (′O′) = = ′′A2′′) {
      make_move (′X′, ′′A3′′);
      if (last_move (′O′) = = ′′C1′′) {
         make_move (′X′, ′′B1′′); //...ничья
      } else {
         make_move (′X′, ′′C1′′); //победа
      }
      } else {
         make_move (′X′, ′′A2′′); //победа
      }
      } else ...

Такой алгоритм сродни системе простейших рефлексов. Однако откуда берутся ходы, записанные в нашей программе? Чтобы убедиться в том, что некоторый наш ход приводит к выигрышу, нужно проверить все возможные ходы противника. Это можно представить в виде дерева игры, также называемого деревом вариантов для неигровых задач. На следующем рисунке показан пример фрагмента дерева игры для «крестиков-ноликов» на поле 3×3. Корень этого дерева представляет собой пустую доску, а выходящие из него ветви соответствуют возможным ходам первого игрока. Эти ветви ведут в новые состояния игрового мира, из каждого из которых также выходят ветви, соответствующие разрешенным ходам второго игрока, и так далее. В случае неигровых задач в корне дерева вариантов может находиться, например, решаемое уравнение, а ветви будут соответствовать допустимым операциям по преобразованию этого выражения.

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

Мы пользуемся этой процедурой, чтобы построить дерево игры и найти на нем такие ответы, которые бы приводили

formula_11

 

к победе или, если это невозможно, к ничьей. Их мы и заносим в нашу программу. А нельзя ли, чтобы компьютерная программа, играющая в «крестики-нолики», сама строила дерево вариантов на основе известной порождающей процедуры? Естественно, более элегантный (чем представленный выше) алгоритм и должен был бы сам строить дерево игры и выбирать наилучший ход, как это делаем мы.

Осуществить такое построение без хранения в памяти дополнительной копии игрового поля (а в более общем случае — модели мира) проблематично. Пусть field[3][3] — вспомогательный массив 3×3, значение в ячейке которого установлено в ′–′, если соответствующая клетка не занята, и в ′X′ и ′O′, если там «крестик» и «нолик» соответственно. Тогда порождающая процедура может быть записана в следующей форме:

char field[3][3];
void tree_search( char player ){
   for( int i = 0; i < 3; i++ ) {
      for( int j = 0; j < 3; j++ ) {
         if( field[i][j] = = ′–′) {
            field[i][j] = player;
               if( player = = ′X′)
                  tree_search( ′O′ );
               else
                  tree_search( ′X′ );
               field[i][j] = ′-′;
               }
         }
      }
   }

Если предварительно установить все значения массива field как пустые (′–′), а потом запустить эту процедуру tree_ search(′X′), то в процессе ее работы в массиве field поочередно окажутся все возможные комбинации расположения крестиков и ноликов.

Пусть имеется процедура check_game, которая оценивает ситуацию на доске, возвращая ′X′ или ′O′, если у соответствующего игрока поставлено 3 в ряд, либо ′–′, если такого нет. Для листьев нашего дерева мы можем установить их статус (чей-то выигрыш либо ничья).

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

Удобнее представить выигрыш компьютера как «+1», ничью как «0», а проигрыш компьютера как «–1». Тогда для определения статуса узла, соответствующего ходу компьютера, нужно будет брать максимум, а для хода противника — минимум по всем дочерним узлам. Такая процедура оценки статуса узлов, показанная на следующем рисунке, называется процедурой минимакса. Встроить процедуру минимакса в порождающую процедуру не представляет трудности.

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

formula_12

 

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

Если порождающая процедура известна и с помощью процедуры минимакса можно определить оптимальный ход, в чем же тогда проблема? Как уже не один раз отмечалось выше, проблема — в NP-полноте. Иными словами, полное дерево вариантов может получиться чрезвычайно больших размеров: зачастую число узлов растет экспоненциально с глубиной дерева, поскольку каждый узел ведет к некоторому числу новых узлов, каждый из которых, в свою очередь, опять ведет к некоторому числу новых узлов. К примеру, размер дерева для шашек составляет 10^40, для шахмат — 10^120, а для го и совсем невообразимое число — 10^400. Забавно, что часто, чтобы подчеркнуть величину этих чисел, говорят об их существенном превосходстве количества атомов или элементарных частиц во Вселенной, не вполне правомерно сравнивая число объектов и число комбинаций состояний объектов. Однако это сравнение становится оправданным, если говорить о классических системах с массовой параллельностью: даже если каждый атом во Вселенной будет являться отдельным процессором, перебирающим 10100 комбинаций в секунду, работы всей Вселенной на протяжении всего времени, прошедшего с момента Большого взрыва, не хватит, чтобы сыграть идеальную партию в го.

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

Несмотря на кажущуюся элементарность, игра в «крестики-нолики» даже на поле 3×3 для ребенка, не знакомого с ней, требует заметных умственных усилий. Эта игра требует перебора вариантов на глубину 4–5, что близко к сложности задачи о нахождении центра отрезка с помощью циркуля и линейки. Однако, «решив» один раз «крестики-нолики» на поле 3×3, мы будем знать это решение (путь в «лабиринте» вариантов), и игра потеряет для нас интерес. Для «взрослых» интеллектуальных игр такая ограниченность не свойственна, поскольку все пространство поиска в них не может быть обследовано в течение всей жизни человека и даже в течение всего времени существования цивилизации.

Что же можно сделать, если все дерево порождено быть не может? Из каких соображений выбирать какой-либо ход? В области эвристического программирования термин «эвристика» уточняется как прием, позволяющий в ходе перебора отсекать неперспективные ветви на дереве вариантов, что является заметно более конкретным определением, чем определение эвристики как приема, облегчающего решение задачи.

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

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

Можно представить и более сложную (и более частную) эвристику: выгоднее тот ход, который потенциально может использоваться в большем числе построений трех в ряд. По этой эвристике исходно для «крестиков» самым выгодным является ход в центр, поскольку он может участвовать в четырех разных построениях. Затем идут ходы в углы — для них число построений равно трем. Для ходов у стенок это число всего лишь два. Понятно, что этой эвристики недостаточно, поскольку она не учитывает возможности противника (например, завершить свою комбинацию).

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