Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 70
Текст из файла (страница 70)
Бил [89] и Дана Нау ]! 113], [11!4] изучали недостатки минимаксного поиска, касаюгциеся приближенных оценок. Они показали, что при некоторых предположениях о независимости распределения листовых значений в дереве применение минимаксного поиска может привести к получению таких значений для корня, которые фактически являются менее надежными, чем полученные с помощью непосредственного использования самой функции оценки.
В книге Перла НеипЯез [!188] дано частичное объяснение этого кажущегося парадокса и приведен анализ многих алгоритмов ведения игр. Баум и Смит [83] предложили заменить алгоритм минимаксного поиска алгоритмом, основанном на учете вероятностей, и показали, что он приводит к осуществлению лучших вариантов выбора в некоторых играх. Глава 6. Поиск в условиях противодействия 275 Но объем теоретических результатов исследования влияния останова поиска на разных уровнях и применения функций оценки все еще остается недостаточным. Алгоритм поиска на основе ожидаемого минимаксного значения был предложен Дональдом Мичи [1043], хотя, безусловно, он непосредственно следует из принципов оценки дерева игры, выдвинутых фон Нейманом и Моргенштерном. Брюс Боллард [65] распространил метод альфа-бета-отсечения на деревья с узлами жеребьевки.
Первый успешно действующей программой игры в нарды была разработанная Берлинером программа ВКО [104], [107]; в ней использовалась сложная, сконструированная вручную функция оценки, а поиск осуществлялся только на глубину 1. Это была первая программа, которая смогла победить чемпиона мира — человека в одной из основных классических игр [106]. По завершении соревнований Берлинер сразу же объявил, что это был очень короткий показательный матч (а не матч чемпионата мира) и что программе ВКО очень повезло со жребием. Работа Герри Тесауро, приведшая вначале к созданию программы Хецго8апипоп [1498], а затем ТР-Оагпгпоп [1500], показала, что гораздо лучшие результаты могут быть достигнуты с помощью обучения с подкреплением. Эта тема будет рассматриваться более подробно в главе 21. Первой из классических игр, полное решение которой было найдено компьютером, оказались не шахматы, а шашки.
Кристофер Стрейчи [1469] написал первую работоспособную программу игры в шашки. Шеффер [1357] составил очень доступный отчет о разработке программы СЫпоо[~, ставшей чемпионом мира по шашкам, в котором все факты изложены "без прикрас". Первые программы для игры го были разработаны немного позднее по сравнению с программами для шашек и шахмат [906], [1281], а их развитие происходило более медленно.
Райдер [1334] использовал подход, основанный исключительно на использовании поиска в сочетании с всевозможными методами избирательного отсечения для преодоления колоссального коэффициента ветвления, характерного для этой игры. Зобрист [1650] применил правила "условие — действие", которые способны предложить приемлемые ходы при обнаружении известных шаблонов. Рейтман и Уилкокс [1280] добились хороших результатов, сочетая применение правил и поиска, поэтому большинство современных программ было разработано на основе этого гибридного подхода. Мюллер [1103] подытожил современное состояние работы в области компьютеризации игры го и привел в своей книге много ссылок.
Аншелевич [33] использовал подобные методы для создания программы для игры геке. Описания современных разработок можно найти в журнале Сотригег 6о 14еъю(ег(ег, который публикует организация Сотри(ег Оо Аззос!айоп. Работы по компьютерному ведению игры появляются во многих разных источниках. В трудах конференции Неиг(з((с Рпзлгапит(пл (и Агв((с(а! Ьиейдепсе, имеющей довольно дезориентирующее название, публикуются отчеты о компьютерных олимпиадах, в рамках которых проводятся весьма разнообразные игры. Имеется также несколько отредактированных сборников важных статей об исследованиях в области ведения игр [920], [921], [988]. Международная ассоциация компьютерных шахмат (1пзегпайопа! Сотри(ег СЬезз Аззос!агюп — 1ССА), основанная в 1977 году, публикует ежеквартальный журнал (ССА .(оигпа( (который раньше носил название (ССА ЮоигпаЬ. В серийно выпускаемой антологии Ай апсез ьп Сотригег Спезз публикуются важные статьи, начиная со статьи Кларке [268]. В томе 134 журнала Ага((с(а( 7п(е(((лепсе (2002) содержатся описания современных программ для шахмат, "Отелло", гекса, сеги (японские шахматы), го, нард, покера, БсгаЬБ!е™ (" Эрудит" ) и др.
Часть !!. Решение проблем 276 УПРАЖНЕНИЯ 1 2 3 4 6.1. 6.2. 6.3. В этой задаче рассматриваются основные концепции ведения игр с использованием в качестве примера игры в крестики-нолики. Определим х„как количество строк, столбцов или диагоналей, в которых находится точно и значков х и ни одного значка О. Аналогичным образом„о„— это количество строк, столбцов или диагоналей, в которых находятся только и значков О. Функция полезности присваивает +1 любой позиции с х,=1 и -1 любой позиции с 0,=1.
Все остальные терминальные позиции имеют полезность О. Для нетерминальных позиций используется линейная функция оценки, определенная какрчв1(э) =ЗХ,(э)+Х,(э) — (30,(о) ь0, (э) ) . а) Сколько приблизительно существует возможных вариантов игры в крестики-нолики? б) Покажите полное дерево игры, начиная от пустой доски вплоть до глубины 2 (т.е. глубины, на которой на доске имеется один значок х и один значок 0), учитывая симметрию позиций. в) Проставьте в этом дереве оценки всех позиций на глубине 2. г) С использованием алгоритма минимаксного поиска проставьте в дереве зарезервированные значения для позиций на глубине ! и 0 и воспользуйтесь этими значениями для выбора наилучшего начального хода. д) Обведите кружками узлы на глубине 2, которые не оценивались бы в случае применения альфа-бета-отсечения, исходя из предположения, что эти узлы вырабатываются в порядке, оптимальном для альфа-бета-отсечения.
Докажите следующее утверждение: для каждого лерева игры значение полезности, полученное игроком МАХ с использованием минимаксных решений в игре против неоптимально действующего игрока мты, никогда не будет ниже значений полезности, полученных в игре против оптимально действующего игрока м12(.
Можете ли вы показать дерево игры, в котором игрок млх может действовать еще лучше, используя неоптимальную стратегию против неоптимально действуюгдего игрока М12(? Рассмотрим игру с двумя игроками, показанную на рис. 6.12. Рис. б. 12 Начальная позиция простой игры. Игрок л ходит первым. Два игрока ходят по очереди, и каждый игрок должен переместить свою фишку в открытый смежный квадрат в любом направлении. 1сли противник занимает смежный квадрат, то игрок может перенести свою фишку через фишку противника на следующий открытый квадрат, если он имеется.
(Наприиер, если фишка л стоит в квадрате 3, и фишка в — в квадрате 2, то л снова маясет перейти в квадрат 1.) Игра заканчивается после того, как один из игроков достигает противопалозкного конца доски. Если игрок л достигает квадрата 4 первым, то значение этой игры для Л равно ь 2; если игрок В достигает квадрата 1 первым, то значение этой игры для игрока Л равно -2. а) Нарисуйте полное дерево и2ры с использованием следующих соглашений: Глава 6. Поиск в условиях противодействия 277 ° записывайте каждое состояние как (я„, я,), где вх и аа обозначают местонахождения фишек; ° обводите квадратом каждое терминальное состояние и записывайте для него значение игры в кружке; ° обводите двойными квадратами циклические состояния (состояния, которые уже появлялись на пути к корню).
Поскольку не ясно, как присваивать значения циклическим состояниям, обозначайте каждое из них знаком 7 в кружке. 6) Обозначьте каждый узел его зарезервированным минимаксным значением (также в кружке). Объясните, как вы учитывали значения 7 и почему. в) Объясните, почему стандартный алгоритм минимаксного поиска в этом дереве игры потерпит неудачу, и вкратце опишите, каким образом вы могли бы его исправить, опираясь на ваш ответ на пункт б). Приведет ли модифицированный вами алгоритм к получению оптимальных решений для всех игр с циклами? г) Эту игру с четырьмя клетками можно обобщить до л клеток для любого п>2.
Докажите, что игрок л побеждает, если число и — четное, и проигрывает, если число л — нечетное. 6.4. Ф Реализуйте генераторы хода и функции оценки для одной или нескольких из следующих игр: калах, "Отелло", шашки и шахматы. Сконструируйте агента обшего назначения для ведения игры на основе альфа-бета-поиска, в котором используется ваша реализация. Сравните эффективность увеличения глубины поиска, усовершенствования способа упорядочения ходов и улучшения функции оценки.
Насколько близко приближается полученный вами эффективный коэффициент ветвления к идеальному случаю самого совершенного упорядочения ходов? 6.5. Разработайте формальное доказательство правильности алгоритма альфа- бета-отсечения, Для этого рассмотрите ситуацию, показанную на рис. 6Д3. Вопрос заключается в том, следует ли выполнять отсечение в узле п„который представляет собой узел мдх и является одним из потомков узла лц Основная идея такова, что отсечение должно выполняться тогда и только тогда, когда можно показать, что минимаксное значение пз не зависимо от значения и, а) Значение узла и, определяется с помощью выражения и = мал (п2, п21, ° », п2ь ) 2 Найдите аналогичное выражение для узла п„а следовательно, выражение для узла и, в терминах значений узла и,.
6) Допустим, что 1г — минимальное (или максимальное) значение узлов слева от узла пз на глубине З, минимаксное значение которого уже известно. Аналогичным образом, допустим, что тз — минимальное (или максимальное) значение неисследованных узлов справа от пз на глубине З.
Перепишите ваше выражение для узла и, в терминах значений 2, и гз. в) Теперь переформулируйте это выражение для того, чтобы показать, что значение узла и, не должно превышать некоторый предел, полученный на основе значений 2,, для того, чтобы оно могло повлиять на значение узла и,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
