ОБСУЖДЕНИЕ ИЗЛОЖЕННЫХ СВЕДЕНИЙ

Поскольку вычисление оптимальных решений в играх чаще всего является неосуществимым, во всех алгоритмах необходимо использовать некоторые предположения и допущения. Стандартный подход, основанный на использовании минимаксных значений, функций оценки и альфа-бета-отсечения, представляет собой лишь один из способов достижения этой цели. По-видимому, из-за того, что он был предложен уже давно, этот стандартный подход интенсивно развивался и стал доминировать над другими методами, участвующими в борьбе за право на существование. Некоторые специалисты в этой области считают, что такое состояние дел стало причиной отделения проблематики ведения игр от основного направления развития исследований по искусственному интеллекту, поскольку этот стандартный подход больше не предоставляет большого простора для новых открытий, позволяющих найти ответы на общие вопросы в области принятия решений. В настоящем разделе описаны некоторые альтернативные варианты.
Вначале рассмотрим минимаксный поиск. Алгоритмы минимаксного поиска позволяют выбрать оптимальный ход в данном конкретном дереве поиска, при условии, что оценки листовых узлов являются абсолютно правильными. Но в действительности оценки обычно представляют собой грубые прогнозы стоимости той или иной позиции, поэтому можно считать, что с ними связаны существенные ошибки. На рис. 6.11 показано дерево игры с двумя полуходами, для которого минимаксный поиск представляется неподходящим. Минимаксный поиск подсказывает, что должна быть выбрана правая ветвь, тогда как весьма вероятно, что истинное значение левой ветви должно быть выше. Минимаксный выбор основывается на предположении, что все узлы, отмеченные значениями 100, 101, 102 и 100, действительно лучше, чем узел, отмеченный значением 99. Однако тот факт, что узел с отметкой 99 имеет сестринские узлы с отметками 1000, наводит на мысль, что фактически он может иметь более высокое истинное значение. Один из способов справиться с этой проблемой состоит в том, чтобы использовать какую-то оценку, которая возвращает распределение вероятностей среди возможных значений. В таком случае появляется возможность вычислить распределение вероятностей для значения родительского узла с использованием стандартных статистических методов. К сожалению, обычно значения сестринских узлов являются в высшей степени коррелированными, поэтому такое вычисление может оказаться дорогостоящим и требующим больших усилий для получения информации.
Затем рассмотрим алгоритм поиска, в котором формируется дерево. Каждый проектировщик алгоритмов стремится создать такой способ вычислений, который действует быстро и позволяет определить хороший ход. Наиболее очевидным недостатком альфа-бета-алгоритма является то, что он предназначен не только для выбора хорошего хода, но и для расчета пределов значений всех допустимых ходов Чтобы понять, почему эта лишняя информация часто не нужна, рассмотрим позицию, в которой имеется только один допустимый ход.
Альфа-бета-поиск все еще вырабатывает и оценивает большое и полностью бесполезное дерево поиска. Безусловно, можно предусмотреть в этом алгоритме какую-то проверку подобной ситуации, но она просто замаскирует основную проблему: многие вычисления, выполняемые в альфа-бета-алгоритме, практически ничего не дают для решения задачи. Ситуация, в которой имеется только один допустимый ход, ненамного отличается от той, где имеется несколько допустимых ходов, притом что один из них является правильным, а остальные — явно катастрофическими. В подобной ситуации наличия "четко выраженного фаворита" было бы желательно быстро достигать решения после проведения небольшого объема поиска, чем терять время, которое можно было бы использовать продуктивнее в дальнейшем, в более проблематичной позиции. Это ведет к идее полезности развертывания узла. Хороший алгоритм поиска должен выбирать варианты развертывания узлов с высокой полезностью, т.е. те варианты, которые, со всей вероятностью, приведут к обнаружению гораздо лучшего хода. Если же отсутствуют варианты развертывания узлов, полезность которых превышает их стоимость (измеряемую в затратах времени), то алгоритм должен прекратить поиск и выбрать ход. Следует отметить, что такое усовершенствование касается не только ситуаций с явными фаворитами, но и тех случаев, когда имеются симметричные ходы, для которых сколь угодно большой объем поиска не позволит показать, что один ход лучше другого.
Рассуждения о том, какие вычисления следует выполнять, а какие нет, называются метарассуждениями (рассуждениями о рассуждениях). Этот подход распространяется не только на ведение игр, но и в целом на рассуждения любого рода. Все вычисления выполняются для того, чтобы выработать лучшие решения, все они имеют стоимость и характеризуются определенной вероятностью достижения конкретного улучшения качества решения. Альфа-бета-поиск представляет собой реализацию метарассуждений простейшего вида, а именно теоремы о том, что некоторые ветви дерева можно игнорировать без ущерба для всей игры. Но такие метарас-суждения могут проводиться гораздо лучше. В главе 16 будет показано, как сделать изложенные идеи более точными и реализуемыми.
Наконец, еще раз рассмотрим природу самого поиска. Алгоритмы эвристического поиска и ведения игр действуют путем выработки последовательностей конкретных состояний (начиная от начального состояния), а затем применения функции оценки. Безусловно, люди играют в игры иначе. В шахматах игрок часто руководствуется конкретной целью (например, поймать ферзя противника) и может использовать эту цель для избирательной выработки осуществимых планов ее достижения. Иногда такого рода подход на основе рассуждений, управляемых целью, или планирования, позволяет полностью устранить комбинаторный поиск (см. часть IV). Программа Paradise Дэвида Уилкинса [1592] — это единственная программа, в которой с успехом использовались рассуждения, управляемые целью, для игры в шахматы; она оказалась способной решать некоторые шахматные задачи, для которых требовались комбинации из 18 ходов. Тем не менее еще нет полного понимания того, как объединить эти два типа алгоритмов в надежную и эффективную систему, хотя программа Bridge Baron может рассматриваться как шаг в правильном направлении. Полностью интегрированная система стала бы значительным достижением не только в области исследований ведения игр, но и для всех исследований по искусственному интеллекту в целом, поскольку послужила бы хорошей основой для создания интеллектуального агента общего назначения.
В этой главе были проанализированы самые разные игры с тем, чтобы можно было понять, что означают слова "оптимальная игра", а также узнать, как научиться хорошо играть на практике. Ниже изложены наиболее важные идеи, которые рассматривались в данной главе.
• Любая игра может быть определена с помощью начального состояния (которое показывает, как осуществляется подготовка доски к игре), допустимых действий в каждом состоянии, проверки терминального состояния (позволяющей определить, когда игра окончена) и функции полезности, которая применяется к терминальным состояниям.
• В играх с двумя игроками и нулевой суммой, характеризующихся полной информацией, для выбора оптимальных ходов с помощью перебора узлов в глубину в дереве игры может использоваться алгоритм минимаксного поиска.
• Алгоритм альфа-бета-поиска вычисляет такие же оптимальные ходы, как и алгоритм минимаксного поиска, но позволяет достичь гораздо большей эффективности, удаляя поддеревья, которые, по всей вероятности, не нужны для поиска решения.
• Обычно не представляется возможным рассматривать все дерево игры (даже с помощью альфа-бета-поиска), поэтому необходимо в какой-то точке останавливать поиск и применять функцию оценки, позволяющую определить приближенное значение полезности некоторого состояния.
• Ведение игр с элементами случайности можно осуществить с помощью расширения алгоритма минимаксного поиска, в котором оцениваются узлы жеребьевки путем определения средней полезности всех их дочерних узлов с учетом вероятности каждого дочернего узла.
• Для определения оптимальных ходов в играх с неполной информацией, таких как бридж, необходимо формировать рассуждения о текущем и будущем доверительных состояниях для каждого игрока. Одна из простых аппроксимаций может быть получена путем усреднения значения данного действия по всем возможным конфигурациям недостающей информации.
• Программы способны соревноваться на равных или побеждать лучших игроков-людей в шашках, игре "Отелло" и в нардах, а также вплотную приблизились к ним в бридже. Программа победила чемпиона мира по шахматам в одном показательном матче. В игре го программы до сих пор остаются на любительском уровне.







Материалы

Яндекс.Метрика