Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 68
Текст из файла (страница 68)
Решение проблем жений. Во-вторых, в программе 01В используется обобщение на основе обаяснеиия для вычисления и кэширования общих правил оптимальной игры в виде определений различных стандартных классов ситуаций. Это позволяет данной программе принимать точное решение в отношении каждой раздачи. Тактическая точность программы О1В компенсирует ее неспособность формировать рассуждения в отношении имеющейся информации. Она финишировала на 12-м месте среди 35 участников в парных соревнованиях (в которых предусматривался только розыгрыш карт, имеющихся на руках) в чемпионате мира среди людей в!998 году, значительно превзойдя ожилания многих специалистов в этой области.
6.7. ОБСУЖДЕНИЕ ИЗЛОЖЕННЫХ СВЕДЕНИЙ Поскольку вычисление оптимальных решений в играх чаще всего является неосуществимым, во всех алгоритмах необходимо использовать некоторые предположения и допущения. Стандартный подход, основанный на использовании минимаксных значений, функций оценки и альфа-бета-отсечения, представляет собой лишь один из способов достижения этой цели. По-видимому, из-за того, что он был предложен уже давно, этот стандартный подход интенсивно развивался и стал доминировать над другими методами, участвующими в борьбе за право на существование. Некоторые специалисты в этой области считают, что такое состояние дел стало причиной отделения проблематики ведения игр от основного направления развития исследований по искусственному интеллекту„поскольку этот стандартный подход больше не предоставляет большого простора для новых открытий, позволяющих найти ответы на общие вопросы в области принятия решений.
В настоящем разделе описаны некоторые альтернативные варианты. Вначале рассмотрим минимаксный поиск. Алгоритмы минимаксного поиска позволяют выбрать оптимальный ход в данном конкретном дереве поиска, при условии, что оценки листовых узлов являются абсолютно правильными. Но в действительности оценки обычно представляют собой грубые прогнозы стоимости той или иной позиции, поэтому можно считать, что с ними связаны существенные ошибки. На рис. 6.11 показано дерево игры с двумя полуходами, для которого минимаксный поиск представляется неподходящим.
Минимаксный поиск подсказывает, что должна быть выбрана правая ветвь, тогда как весьма вероятно„что истинное значение левой ветви должно быть выше. Минимаксный выбор основывается на предположении, что все узлы, отмеченные значениями 100, 1О1, 102 и 100, действительно лучше, чем узел, отмеченный значением 99. Однако тот факт, что узел с отметкой 99 имеет сестринские узлы с отметками 1000, наводит на мысль, что фактически он может иметь более высокое истинное значение. Один из способов справиться с этой проблемой состоит в том, чтобы использовать какую-то оценку, которая возвращает распределение вероятностей среди возможных значений. В таком случае появляется возможность вычислить распределение вероятностей для значения родительского узла с использованием стандартных статистических методов.
К сожалению, обычно значения сестринских узлов являются в высшей степени коррелированными, поэтому такое вычисление может оказаться дорогостоящим и требующим больших усилий для получения информации. Затем рассмотрим алгоритм поиска, в котором формируется дерево. Каждый проектировщик алгоритмов стремится создать такой способ вычислений, который 1 1 ~на 6 Иж1."к н ~г"!Лвни~ по ~ига 'и~"п~р~ ') 270 Часть 11.
Решение проблем Наконец, еше раз рассмотрим природу самого поиска. Алгоритмы эвристического поиска и ведения игр действуют путем выработки последовательностей конкретных состояний (начиная от начального состояния), а затем применения функции оценки. Безусловно, люли играют в игры иначе. В шахматах игрок часто руководствуется конкретной целью (например, поймать ферзя противника) и может использовать эту цель для избирательной выработки осуществимых планов ее достижения.
Иногда такого рода подход на основе рассуждений, управляемых целью, или планирования, позволяет полностью устранить комбинаторный поиск (см. часть 1Ъ). Программа Рагагйзе Дэвида Уилкинса 11592) — это единственная программа, в которой с успехом использовались рассуждения, управляемые целью, для игры в шахматы; она оказалась способной решать некоторые шахматные задачи, для которых требовались комбинации из 18 ходов. Тем не менее еще нет полного понимания того, как объединить эти два типа алгоритмов в надежную и эффективную систему, хотя программа Впг)йе Вагоп может рассматриваться как шаг в правильном направлении. Полностью интегрированная система стала бы значительным достижением не только в области исследований ведения игр, но и для всех исследований по искусственному интеллекту в целом, поскольку послужила бы хорошей основой для создания интеллектуального агента общего назначения.
РЕЗЮМЕ В этой главе были проанализированы самые разные игры с тем, чтобы можно бьио понять, что означают слова "оптимальная игра", а также узнать, как научиться хорошо играть на практике. Ниже изложены наиболее важные идеи, которые рассматривались в данной главе. ° Любая игра может быть определена с помощью начального состояния (которое показывает, как осуществляется подготовка доски к игре), допустимых действий в каждом состоянии, проверки терминального состояния (позволяющей определить, когда игра окончена) и функции полезности, которая применяется к терминальным состояниям. ° В играх с двумя игроками и нулевой суммой, характеризующихся полной информацией, для выбора оптимальных ходов с помощью перебора узлов в глубину в дереве игры может использоваться алгоритм минимаксного поиска.
° Алгоритм альфа-бета-поиска вычисляет такие же оптимальные ходы, как и алгоритм минимаксного поиска, но позволяет достичь гораздо большей эффективности, удаляя поддеревья, которые, по всей вероятности, не нужны для поиска решения. ° Обычно не представляется возможным рассматривать все дерево игры (даже с помощью альфа-бета-поиска), поэтому необходимо в какой-то точке останавливать поиск и применять функцию оценки, позволяющую определить приближенное значение полезности некоторого состояния.
° Ведение игр с элементами случайности можно осуществить с помощью расширения алгоритма минимаксного поиска, в котором оцениваются узлы же- Глава 6. Поиск в условиях противодействия 271 ребьевки путем опрелеления средней полезности всех их дочерних узлов с учетом вероятности каждого дочернего узла. ° Для определения оптимальных ходов в играх с неполной информацией, таких как бридж, необходимо формировать рассуждения о текущем и будущем доверительных состояниях для каждого игрока. Одна из простых аппроксимаций может быть получена путем усреднения значения данного действия по всем возможным конфигурациям недостаюшей информации.
° Программы способны соревноваться на равных или побеждать лучших игроков-людей в шашках, игре "Отелло" и в нардах, а также вплотную приблизились к ним в бридже. Программа победила чемпиона мира по шахматам в одном показательном матче. В игре го программы до сих пор остаются на любительском уровне. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Ранняя история развития механических средств ведения игр была запятнана многочисленными случаями мошенничества. Наиболее известным из них был "Турок" барона Вольфганга фон Кем пелена (1734 — 1804).
Это устройство выдавали за автомат для игры в шахматы и смогли с его помощью обмануть очень многих, в том числе Наполеона. Лишь в дальнейшем выяснилось, что это устройство представляет собой хитроумный ящик фокусника, в котором сидит человек, хорошо играющий в шахматы ]919]. Игры с участием этого устройства проводились с 1769 по 1854 годы. В ! 846 году Чарльз Бэббидж (который был в восторге от "Турка" ) участвовал в одной из первых серьезных дискуссий на тему осуществимости задачи ведения игр в шахматы и шашки с помощью вычислительного устройства ]1089].
Он также спроектировал, но не построил машину специального назначения для игры в крестики-нолики. Первая настоящая машина для ведения игры была построена примерно в 1890 году испанским инженером Леонардо Торресом и Кеведо. Она была специально предназначена для ведения шахматного эндшпиля "КВК" (К]п8 апд Коок чз. К)п8 — король и ладья против короля) и гарантировала победу из любой позиции в игре с этими тремя фигурами.
В качестве первоисточника идеи алгоритма минимаксного поиска часто называют статью, опубликованную в 1912 году Эрнстом Цермело, основоположником современной теории множеств ]1642]. К сожалению, эта статья содержала несколько ошибок, а алгоритм минимаксного поиска не был в ней описан правильно. Солидный фундамент теории игр был создан в оригинальной работе ТЬеогу оГ батез аМ Есолоиис Вейаиог ]1546], которая содержала анализ, показывающий, что для некоторых игр требуются стратегии, которые являются рандомизированными (или становятся непредсказуемыми для противников по каким-то иным причинам).
Дополнительная информация на эту тему приведена в главе 17. На заре компьютерной эры возможность создания компьютерных шахмат интересовала многих важных деятелей в этой области. Конрад Цузе ]1651] (первый, кто спроектировал программируемый компьютер) разработал довольно подробные предложения, касаюшиеся того, как может быть решена эта задача. Во влиятельной книге СуЬетег)сз (Кибернетика) Норберта Винера [1589] обсуждался один возможный 272 Часть П.
Решение проблем проект создания шахматной программы и были высказаны идеи минимаксного поиска, останова на заданной глубине и применения функций оценки. Клод Шеннон [1395] изложил основные принципы создания современных программ ведения игр гораздо более подробно, чем Винер. Он ввел понятие поиска спокойной позиции, а также высказал некоторые идеи в отношении избирательного (неисчерпывающего) поиска в дереве игры. Слейтор [1430) и комментаторы его статьи также рассматривали возможности ведения игры в шахматы с помощью компьютера. В частности, Гуд ) 574) разработал понятие спокойной позиции независимо от Шеннона. В 1951 году Алан Тьюринг написал первую компьютерную программу, способную вести полную игру в шахматы [1521).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
