Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 61
Текст из файла (страница 61)
(Подсказка. Предусмотрите использование новой переменной, которая принимает значения, являющиеся парами других значений, и примените такие ограничения, как "Х является первым элементом пары у".) Затем покажите, как можно трактовать аналогичным образом ограничения больше чем с тремя переменными. Наконец, покажите, как можно устранить унарные ограничения, модифицируя области определения переменных. На этом завершается демонстрация того, что любую задачу СБР можно преобразовать в задачу СВР только с бинарными ограничениями.
5.12. ()=(я Предположим, что известно, будто граф имеет множество разрыва цикла, содержащее не больше )г узлов. Опишите простой алгоритм поиска минимального множества разрыва цикла, время прогона которого не намного превышает о(п') для задачи СВР с и переменными. Найдите в литературе методы обнаружения приближенно минимальных множеств разрыва цикла за время, которое полиномиально зависит от размера множества разрыва. Обеспечивает ли наличие таких алгоритмов практическую применимость метода поиска на основе множества разрыва цикла? 5.13. Рассмотрите приведенную ниже логическую головоломку. В пяти домах, имеющих разный цвет, живут лица пяти национальностей, которые предпочитают разные сорта сигарет, пьют разные напитки и держат разных домашних питомцев.
На основе следующих фактов найдите ответ на вопрос: "В каком доме держат зебру и в каком доме пьют воду?" ° Англичанин живет в доме красного цвета. ° Испанец держит собаку. ° Норвежец живет в первом доме слева. ° Сигареты "Куле" курят в доме желтого цвета. е Человек, курящий "Честерфилд", живет рядом с домом человека, который держит лису. ° Норвежец живет рядом с домом синего цвета. ° Человек, курящий "Уинстон", держит улиток. 5.11. Покажите, как можно преобразовать одно тернарное ограничение, такое как Глава 5. Задачи удовлетворения ограничений 239 ° Человек, курящий "Лаки Страйк*', пьет апельсиновый сок.
° Украинец пьет чай. ° Японец курит "Парламент". ° Сигареты "Куле'" курят в доме, находящемся рядом с домом, где держат лошадь. ° Кофе пьют в доме зеленого цвета. ° Дом зеленого цвета находится непосредственно справа (с точки зрения того, кто решает эту задачу) от дома цвета слоновой кости. ° Молоко пьют в среднем доме. Обсудите различные представления этой задачи в виде задачи СБР. По каким причинам следовало бы предпочесть одно представление другому? В этой главе рассматриваются проблемы, возникающие при попытке агента планировать наперед в мире, где другие агенты составляют планы, направленные против нега. 6.1. ИГРЫ В главе 2 представлены мультиагеитиые варианты среды, в которых каждый конкретный агент вынужден принимать во внимание действия других агентов и устанавливать, как они повлияют на его собственное благополучие.
Непредсказуемость действий этих прочих агентов может потребовать в процессе решения задачи агентом учета многих возможных непредвиденных ситуаций, как было описано в главе 3. Различие между кооперативными и конкурентными мультиагентными вариантами среды также было показано в главе 2. Наличие конкурентных вариантов среды, в которых цели агентов конфликтуют, приводит к возникновению задач поиска в условиях противодействия, часто называемых 'пк играми.
В математической теории игр, одной из ветвей экономики, любые мультиагентные варианты среды рассматриваются как игры, при условии, что влияние каждого агента на других является "значительным", независимо от того, являются ли агенты кооперативными или конкурентными'. В искусственном интеллекте "играми" обычно называют довольно специфические формы взаимодействия агентов, которые теоретиками игр именуются как детерминированные, поочередные, охватываюшие двух игроков сю.
игры с нулевой суммой и с полной информацией. В терминологии, принятой в данной книге, это соответствует детерминированным, полностью наблюдаемым вариантам среды, в которых имеются два агента, обязанных чередовать свои действия, и в которых значения полезности в конце игры всегда равны и противоположны. Например, если один игрок выигрывает игру в шахматы (+1), другой игрок обязательно проигрывает (-1). В подобной ситуации условия противо- ' Варианты среды с очень большим количеством агентов лучше рассматривать как экономики, а не как игры. Глава 6. Поиск в условиях противодействия 24! действия возникают именно из-за такого противопоставления функций полезности агентов. В данной главе будут кратко рассматриваться игры с несколькими игроками, игры с ненулевой суммой и стохастические игры, но надлежащее обсуждение теории игр откладывается до главы 17.
Игры заставляли людей напрягать свои интеллектуальные способности (иногда до угрожающей степени) на протяжении всего существования цивилизации. В силу своего абстрактного характера игры являются привлекательным объектом исследований и в области искусственного интеллекта. Состояние игры можно легко представить, а поведение агентов обычно ограничено небольшим количеством действий, результаты которых определяются с помощью точных правил. Спортивные игры, такие как крокет и хоккей с шайбой, имеют гораздо более сложные описания, значительно больший диапазон возможных действий и довольно неточные правила, определяющие допустимость действий. За исключением проблематики создания робота-футболиста эти спортивные игры не привлекают значительного интереса в сообществе специалистов по искусственному интеллекту.
Ведение игр было одной из первых задач, рассматриваемых в области искусственного интеллекта. К 1950 году, почти сразу же после того, как компьютеры стали программируемыми, шахматами уже интересовались Конрад Цузе (изобретатель первого программируемого компьютера и разработчик первого языка программирования), Клод Шеннон (основоположник теории информации), Норберт Винер (создатель современной теории управления) и Алан Тьюринг. С тех пор уровень игры с применением компьютеров неуклонно повышался и достиг того, что компьютеры превзошли людей в шашках и игре "Отелло" ("реверси"), побеждали чемпионов (но не всегда) в шахматах и нардах, а также стали конкурентоспособными во многих других играх.
Основным исключением остается игра го, в которой компьютеры пока еще выступают на любительском уровне. Игры, в отличие от большинства учебных задач, которые рассматривались в главе 3, интересны тем, что в них очень трудно найти решение. Например, шахматы характеризуются в среднем коэффициентом ветвления, примерно равным 35, а игра часто продолжается до 50 ходов со стороны каждого игрока, поэтому дерево поиска имеет приблизительно 35"' или 10"4 узлов (хотя граф поиска включает "всего лишь" около 104' различных узлов). Поэтому игры, как и реальная жизнь, требуют способности принимать хоть какие-то решения, даже если вычисление оптимального решения неосуществимо. Кроме того, игры сурово наказывают за неэффективность.
Притом что реализация поиска А*, в два раза менее эффективная по сравнению с другой реализацией, просто потребует вдвое больше времени для получения окончательного решения, шахматная программа, вдвое менее эффективно использующая отведенное ей время, по-видимому, потерпит поражение на самых ранних этапах игры, даже при всех прочих равных условиях. Поэтому исследователи, работающие в области ведения игр, стали авторами многих интересных идей, касающихся того, как обеспечить наилучшее возможное использование времени.
Начнем описание данной темы с определения понятий оптимального хода игры и алгоритма его поиска. Затем рассмотрим методы выбора хорошего хода в условиях ограниченного времени. Отсечение позволяет игнорировать те части дерева поиска, которые не оказывают влияния на окончательный выбор, а эвристические функции оценки позволяют приближенно рассчитывать истинную полезность состояния без проведения полного поиска.
В разделе 6.5 рассматриваются такие игры, включающие элемент случайности, как нарды; кроме того, в данной главе рассматривается 242 Часть П. Решение проблем бридж, который включает элементы ох неполной информации, поскольку не все карты видны каждому игроку. Наконец, в этой главе будет описано, как новейшие программы ведения игр постепенно преодолевают сопротивление людей в борьбе с этими программами и каковы направления будущих разработок.
6.2. ПРИНЯТИЕ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ИГРАХ В данной главе речь идет об играх с двумя игроками, которые будут именоваться млх и м1м по причинам, которые вскоре станут очевидными. Игрок млх ходит первым, после чего игроки делают ходы по очереди до тех пор, пока игра не закончится. В конце игры игроку-победителю присваиваются очки, а на побежденного налагается штраф. Игра может быть формально определена как своего рода задача поиска с описанными ниже компонентами. ° Начальное состояние, которое включает позицию на доске и определяет игрока, который должен ходить. ° Функция определения преемника, возврагдающая список пар (тоие, в сисе), каждая из которых указывает допустимый ход и результирующее состояние.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
