Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

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

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

На рисунке показано дерево игры с двумя полуходами, для которого минимаксный поиск представляется неподходящим. Минимаксный поиск подсказывает, что должна быть выбрана правая ветвь, тогда как весьма вероятно, что истинное значение левой ветви должно быть выше. Минимаксный выбор основывается на предположении, что все узлы, отмеченные значениями 100, 101, 102 и 100, действительно лучше, чем узел, отмеченный значением 99. Однако тот факт, что узел с отметкой 99 имеет сестринские узлы с отметками 1000, наводит на мысль, что фактически он может иметь более высокое истинное значение.

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

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

Image
Дерево игры с двумя полуходами, для которого минимаксный поиск может оказаться неподходящим

 

 

 

 

 

 

 

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

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

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

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

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

Программа Paradise Дэвида Уилкинса — это единственная программа, в которой с успехом использовались рассуждения, управляемые целью, для игры в шахматы; она оказалась способной решать некоторые шахматные задачи, для которых требовались комбинации из 18 ходов. Тем не менее еще нет полного понимания того, как объединить эти два типа алгоритмов в надежную и эффективную систему, хотя программа Bridge Baron может рассматриваться как шаг в правильном направлении.

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