УПРАЖНЕНИЯ
6.1. В этой задаче рассматриваются основные концепции ведения игр с использо-
ванием в качестве примера игры в крестики-нолики. Определим Хп как коли-
чество строк, столбцов или диагоналей, в которых находится точно п значков
X и ни одного значка О. Аналогичным образом, Оп — это количество строк,
столбцов или диагоналей, в которых находятся только п значков о. Функция
полезности присваивает +1 любой позиции с х3 = 1 и -1 любой позиции с
03 = 1. Все остальные терминальные позиции имеют полезность 0. Для нетер-
минальных позиций используется линейная функция оценки, определенная
какEval (s) =ЗХ2 (s) +X1(s) - (302 (s) +01 (s) ).
а) Сколько приблизительно существует возможных вариантов игры в кре-
стики-нолики?
б) Покажите полное дерево игры, начиная от пустой доски вплоть до глуби-
ны 2 (т.е. глубины, на которой на доске имеется один значок х и один
значок О), учитывая симметрию позиций.
в) Проставьте в этом дереве оценки всех позиций на глубине 2.
г) С использованием алгоритма минимаксного поиска проставьте в дереве
зарезервированные значения для позиций на глубине 1 и 0 и воспользуй-
тесь этими значениями для выбора наилучшего начального хода.
д) Обведите кружками узлы на глубине 2, которые не оценивались бы в случае
применения альфа-бета-отсечения, исходя из предположения, что эти узлы
вырабатываются в порядке, оптимальном для альфа-бета-отсечения.
6.2. Докажите следующее утверждение: для каждого дерева игры значение полезности, полученное игроком МАХ с использованием минимаксных решений в игре против неоптимально действующего игрока MIN, никогда не будет ниже значений полезности, полученных в игре против оптимально действующего игрока MIN. Можете ли вы показать дерево игры, в котором игрок МАХ может действовать еще лучше, используя неоптимальную стратегию против неоптимально действующего игрока MIN?
6.3. Рассмотрим игру с двумя игроками, показанную на рис. 6.12.
Начальная позиция простой игры. Игрок А ходит первым. Два игрока ходят по очереди, и каждый игрок должен переместить свою фишку в открытый смежный квадрат в любом направлении. Если противник занимает смежный квадрат, то игрок может перенести свою фишку через фишку противника на следующий открытый квадрат, если он имеется. (Например, если фишка А стоит в квадрате 3, а фишка В — в квадрате 2, то А снова может перейти в квадрат 1.) Игра заканчивается после того, как один из игроков достигает противоположного конца доски. Если игрок А достигает квадрата 4 первым, то значение этой игры для А равно +1; если игрок В достигает квадрата 1 первым, то значение этой игры для игрока А равно -1.
а) Нарисуйте полное дерево игры с использованием следующих соглашений:
• записывайте каждое состояние как (sA,sB), где sA и sB обозначают местонахождения фишек;
• обводите квадратом каждое терминальное состояние и записывайте для него значение игры в кружке;
• обводите двойными квадратами циклические состояния (состояния, которые уже появлялись на пути к корню). Поскольку не ясно, как присваивать значения циклическим состояниям, обозначайте каждое из них знаком ? в кружке.
б) Обозначьте каждый узел его зарезервированным минимаксным значени-
ем (также в кружке). Объясните, как вы учитывали значения ? и почему.
в) Объясните, почему стандартный алгоритм минимаксного поиска в этом
дереве игры потерпит неудачу, и вкратце опишите, каким образом вы
могли бы его исправить, опираясь на ваш ответ на пункт б). Приведет ли
модифицированный вами алгоритм к получению оптимальных решений
для всех игр с циклами?
г) Эту игру с четырьмя клетками можно обобщить до п клеток для любого
п>2. Докажите, что игрок А побеждает, если число п — четное, и проиг-
рывает, если число п — нечетное.
6.4. S) Реализуйте генераторы хода и функции оценки для одной или нескольких из следующих игр: калах, "Отелло", шашки и шахматы. Сконструируйте агента общего назначения для ведения игры на основе альфа-бета-поиска, в котором используется ваша реализация. Сравните эффективность увеличения глубины поиска, усовершенствования способа упорядочения ходов и улучшения функции оценки. Насколько близко приближается полученный вами эффективный коэффициент ветвления к идеальному случаю самого совершенного упорядочения ходов?
6.5. Разработайте формальное доказательство правильности алгоритма альфа-бета-отсечения. Для этого рассмотрите ситуацию, показанную на рис. 6.13. Вопрос заключается в том, следует ли выполнять отсечение в узле щ, который представляет собой узел МАХ и является одним из потомков узла п1. Основная идея такова, что отсечение должно выполняться тогда и только тогда, когда можно показать, что минимаксное значение п± не зависимо от значения щ.
а) Значение узла л2 определяется с помощью выражения
Найдите аналогичное выражение для узла п2, а следовательно, выражение для узла п.1 в терминах значений узла щ.
б) Допустим, что li — минимальное (или максимальное) значение узлов
слева от узла п± на глубине i, минимаксное значение которого уже из-
вестно. Аналогичным образом, допустим, что rL — минимальное (или
максимальное) значение неисследованных узлов справа от rii на глубине
i. Перепишите ваше выражение для узла пг в терминах значений li и rL.
в) Теперь переформулируйте это выражение для того, чтобы показать,
что значение узла щ не должно превышать некоторый предел, полу-
ченный на основе значений li, для того, чтобы оно могло повлиять на
значение узла
г) Повторите этот процесс для того случая, когда щ является узлом MIN.
6.6. SFE Ш Реализуйте алгоритм поиска по ожидаемому минимаксному значению и алгоритм *-альфа-бета-поиска, который описан Баллардом [65], для отсечения деревьев игры с узлами жеребьевки. Испытайте эти алгоритмы в такой игре, как нарды, и проведите измерения эффективности отсечения в *-альфа-бета-поиске.
6.7. Докажите, что после положительной линейной трансформации листовых значений (т.е. трансформации значения х в ах+Ь, где а>0) выбор хода в дереве игры остается неизменным, даже если в нем имеются узлы жеребьевки.
6.8. Рассмотрите описанную ниже процедуру выбора ходов в играх с узлами жеребьевки:
• Сформируйте некоторые последовательности метания жребия (скажем, 50) вплоть до подходящей глубины (скажем, 8).
• После того как результаты метания жребия становятся известными, дерево игры преобразуется в детерминированное. Для каждой последовательности метания жребия найдите решение результирующего детерминированного дерева игры с помощью альфа-бета-поиска.
• С использованием этих результатов оцените значение каждого хода и выберите наилучший.
Будет ли эта процедура действовать успешно? Почему да (или почему нет)?
6.9. Опишите и реализуйте среду ведения игры в реальном времени с несколькими игроками, где время образует часть состояния среды, а игрокам выделяются фиксированные промежутки времени.
6.10. Опишите или реализуйте описания состояний, генераторы ходов, проверки терминальных состояний, функции полезности и функции оценки для одной или нескольких из следующих игр: монополия, Scrabble ("Эрудит"), бридж
(под этим подразумевается вариант бриджа с заключением соглашения) и покер (выберите свой любимый вариант).
6.11. Тщательно изучите, как взаимодействуют события жеребьевки и частичная
информация в каждой из игр, упомянутых в упр. 6.10.
а) Для какой из них подходит стандартная модель на основе ожидаемых ми-
нимаксных значений? Реализуйте этот алгоритм и примените его в вашем
агенте для ведения игры после внесения соответствующих изменений в
среду ведения игры.
б) Для какой из этих игр подходит схема, описанная в упр. 6.8?
в) Обсудите вопрос о том, как можно было бы воспользоваться фактом, что в
некоторых играх игроки не имеют одинаковые знания о текущем состоянии.
6.12. В алгоритме минимаксного поиска принято предположение, что игроки де-
лают ходы по очереди, но в таких карточных играх, как вист и бридж, следую-
щую взятку разыгрывает первым тот, кто взял предыдущую взятку.
а) Модифицируйте алгоритм таким образом, чтобы он правильно действо-
вал в этих играх. Для этого можно принять предположение, что имеется
функция Winner (s), которая сообщает, какой игрок взял только что ра-
зыгранную взятку (если она имеется).
б) Нарисуйте дерево игры для первой пары карт, имеющихся на руках, по-
казанной на с. 262.
6.13. В программе игры в шашки Chinook широко используются базы данных с эндшпилями, которые предоставляют точные значения для каждой позиции с восемью или меньшим количеством шашек. Каким образом можно обеспечить эффективное формирование таких баз данных?
6.14. Обсудите вопрос о том, насколько успешно может применяться стандартный подход к ведению игры в таких играх, как теннис, пул (род игры на бильярде) и крокет, которые происходят в непрерывном физическом пространстве состояний.
6.15. Опишите, как изменятся алгоритмы минимаксного поиска и альфа-бета-поиска для случая игр с ненулевой суммой с двумя игроками, в которых каждый игрок имеет собственную функцию полезности. Может быть принято предположение, что каждый игрок знает функцию полезности другого игрока. Если в этих двух функциях нет ограничений полезности терминальных состояний, возможно ли отсечение какого-либо узла с помощью альфа-бета-поиска?
6.16. Предположим, что имеется шахматная программа, способная оценивать 1 миллион узлов в секунду. Выберите компактное представление состояния игры для хранения в таблице транспозиций. Сколько примерно записей удастся вам поместить в таблицу на 500 Мбайт, находящуюся в памяти? Будет ли этого достаточно для поиска в течение трех минут, отведенных на один ход? Сколько операций поиска в таблице вы сможете выполнить за время, которое потребуется для одной оценки? Теперь предположим, что таблица транспозиций больше, чем для нее отведено оперативной памяти. Сколько узлов вы сможете оценить за время, которое требуется для выполнения одного поиска на диске с использованием стандартного аппаратного обеспечения жесткого диска?