Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 71
Текст из файла (страница 71)
Часть 11. Решение проблем 278 г) Повторите этот процесс для того случая, когда пг является узлом мтм. Рис. б. 13. Ситуация, возникающая пра определении того, следует ли отсекать узел ог 6.6. 1Й 1ив Реализуйте алгоритм поиска по ожидаемому минимаксному значению и алгоритм *-альфа-бета-поиска, который описан Баллардом 165], для отсечения деревьев игры с узлами жеребьевки. Испытайте эти алгоритмы в такой игре, как нарды, и проведите измерения эффективности отсечения в "-альфа- бета-поиске.
6.7. Докажите, что после положительной линейной трансформации листовых значений (т.е. трансформации значения х в ах+Ь, где а>0) выбор хода в дереве игры остается неизменным, даже если в нем имеются узлы жеребьевки. 6.8. Рассмотрите описанную ниже процедуру выбора ходов в играх с узлами жеребьевки: ° Сформируйте некоторые последовательности метания жребия (скажем, 50) вплоть до подходящей глубины (скажем, 8).
° После того как результаты метания жребия становятся известными, дерево игры преобразуется в детерминированное. Для каждой последовательности метания жребия найдите решение результирующего детерминированного лерева игры с помощью альфа-бета-поиска. ° С использованием этих результатов оцените значение каждого хода и вы- берите наилучший. Будет ли эта процедура действовать успешно? Почему да (или почему нет)? 6.9. Опишите и реализуйте среду ведения игры в реальном времени с несколькими игроками, где время образует часть состояния среды, а игрокам выделяются фиксированные промежутки времени.
6.10. Опишите или реализуйте описания состояний, генераторы ходов, проверки терминальных состояний, функции полезности и функции оценки для одной или нескольких из следуюших игр: монополия, 8сгаЬЫе (" Эрудит" ), бридж Глава 6. Поиск в условиях противодействия 279 6.11. 6.12. 6.13. 6Л4. 6.15. 6.16. (под этим подразумевается вариант бриджа с заключением соглашения) и покер (выберите свой любимый вариант). Тщательно изучите, как взаимодействуют события жеребьевки и частичная информация в каждой из игр, упомянутых в упр. 6.10. а) Для какой из них подходит стандартная модель на основе ожидаемых минимаксных значений? Реализуйте этот алгоритм и примените его в вашем агенте для ведения игры после внесения соответствующих изменений в среду ведения игры.
6) Для какой из этих игр подходит схема, описанная в упр. 6.8? в) Обсудите вопрос о том, как можно было бы воспользоваться фактом, что в некоторых играх игроки не имеют одинаковые знания о текущем состоянии. В алгоритме минимаксного поиска принято предположение, что игроки делают ходы по очереди, но в таких карточных играх, как вист и бридж, следуюшую взятку разыгрывает первым тот, кто взял предыдущую взятку. а) Модифицируйте алгоритм таким образом, чтобы он правильно действовал в этих играх. Для этого можно принять предположение, что имеется функция у71ппет ( л), которая сообшает, какой игрок взял только что разыгранную взятку (если она имеется).
б) Нарисуйте дерево игры для первой пары карт, имеюшихся на руках, показанной на с. 262. В программе игры в шашки СЫпоок широко используются базы данных с эндшпилями, которые предоставляют точные значения для каждой позиции с восемью или меньшим количеством шашек. Каким образом можно обеспечить эффективное формирование таких баз данных? Обсудите вопрос о том, насколько успешно может применяться стандартный подход к ведению игры в таких играх, как теннис, пул (род игры на бильярде) и крокет, которые происходят в непрерывном физическом пространстве состояний. Опишите, как изменятся алгоритмы минимаксного поиска и альфа-бета-поиска для случая игр с ненулевой суммой с двумя игроками, в которых каждый игрок имеет собственную функцию полезности.
Может быть принято предположение, что каждый игрок знает функцию полезности другого игрока. Если в этих двух функциях нет ограничений полезности терминальных состояний, возможно ли отсечение какого-либо узла с помошью альфа-бета-поиска? Предположим, что имеется шахматная программа, способная оценивать 1 миллион узлов в секунду. Выберите компактное представление состояния игры для хранения в таблице транспозиций. Сколько примерно записей удастся вам поместить в таблицу на 500 Мбайт, находящуюся в памяти? Будет ли этого достаточно для поиска в течение трех минут, отведенных на один ход? Сколько операций поиска в таблице вы сможете выполнить за время, которое потребуется для одной оценки? Теперь предположим, что таблица транспозиций больше, чем для нее отведено оперативной памяти. Сколько узлов вы сможете оценить за время, которое требуется для выполнения одного поиска на диске с использованием стандартного аппаратного обеспечения жесткого диска? Часть? Ц Логические агенты ЗНАНИЯ И РАССУЖДЕНИЯ Логика первого порядка Логический вывод в логике первого порядка Представление знаний 282 341 380 440 В данной главе описано, как проектировать агентов, которые обладают способностью формировать представления о мире, используют процесс логического вывода для получения новых представлений о мире, а такзке применяют эти новые представления для определения того, что следует делать.
В этой главе приведено вводное описание агентов, действующих на основе знаний (или просто агентов на основе знаний). Рассматриваемые здесь понятия (представление знаний и процессы рассуждения, которые связывают знания с действительностью) являются центральными во всей сфере искусственного интеллекта. Вполне очевидно, что люди многое знают и обладают способностью рассуждать. Кроме того, знания и рассуждения очень важны для искусственных агентов, поскольку обеспечивают формирование успешных способов повеления, которых было бы очень трудно добиться иным образом. В этой главе будет показано, что знания о результатах действий позволяют агентам, решающим задачи, успешно действовать в сложных вариантах среды.
В отличие от них рефлексные агенты были способны найти путь от Арада ло Бухареста только благодаря слепой удаче. Однако знания агентов, решающих задачи, являются очень специфичными и недостаточно гибкими. Шахматная программа способна рассчитать допустимые ходы лля короля того цвета, за который она играет, но не обладает многими другими полезными сведениями, например, о том, что ни одна фигура не может стоять одновременно на двух разных клетках. Агенты, основанные на знаниях, способны воспользоваться знаниями, выраженными в очень общих формах, комбинируя и рекомбинируя информацию в соответствии с бесчисленным множеством внешних условий.
Часто этот процесс может быть весьма далеким от потребностей текущего момента; это можно сравнить с тем, как математик доказывает абстрактную теорему или астроном вычисляет ожидаемую продолжительность существования Земли. Кроме того, знания и рассуждения играют решающую роль, когда приходится действовать в частично наблюдаемых вариантах среды.
Агент, основанный на знаниях, способен сочетать общие знания с результатами текущих восприятий, чтобы иметь возможность выявить скрытые аспекты текущего состояния, прежде чем выбирать действия. Например, терапевт диагностирует пациента (т.е. выявляет болезненное состояние, которое недоступно непосредственному наблюдению), прежде чем выбрать способ лечения. Некоторая часть знаний, используемых терапевтом, Глава 7.
Логические агенты 283 находится в форме правил, полученных с помощью учебников и учителей, а еще одна часть представлена в форме ассоциативных образов, которые терапевт не всегда может описать словами. Но если эти ассоциации складываются в уме терапевта, они также относятся к области знаний. Для понимания естественного языка требуется также выявление скрытых аспектов состояния, в частности намерений говорящего. Услышав фразу: "Джон увидел алмаз через окно и страстно пожелал его получить", мы знаем, что слово "его" относится к алмазу, а не к окну; мы рассуждаем, возможно даже подсознательно, с помощью имеющихся у нас знаний об относительной ценности этих предметов.
Аналогичным образом, услышав фразу: "Джон бросил кирпич в окно и разбил его", мы понимаем, что слово "его" относится к окну. Рассуждения позволяют нам справиться практически с бесконечным количеством форм выражения мысли, используя конечный запас обыденных знаний. Сталкиваясь с неоднозначностью подобного рода, агенты, решающие задачи, испытывают затруднения, поскольку применяемый в них способ представления задач с непредвиденными ситуациями обусловливает экспоненциальный рост количества рассматриваемых вариантов.
Не менее важная причина, по которой следует заниматься изучением агентов, основанных на знаниях, состоит в том, что такие агенты характеризуются значительной гибкостью. Они способны принимать к исполнению новые задачи, выраженные в форме явно поставленных целей, они могут быстро достигать компетентности, получая инструкции или усваивая новые знания, полученные из своей среды, кроме того, они способны приспосабливаться к изменениям в своей среде, обновляя соответствующие знания. Изложение темы, рассматриваемой в данной главе, начинается с описания общего проекта агента, приведенного в разделе 7.!. В разделе 7.2 представлена новая простая среда (мир вымышленных существ — вампусов) и показано, как функционирует агент, основанный на знаниях, без углубления в какие-либо техни ~еские подробности.
После этого в разделе 7.3 представлены основные принципы логики. Логика будет служить основным средством представления знаний во всей части !1! данной книги. Знания логических агентов всегда являются опрелеленными — каждое высказывание в этом мире является либо истинным, либо ложным, хотя агент может не знать о существовании некоторых высказываний. С точки зрения изложения учебного материала логика обладает тем преимуществом, что служит простым примером одного из способов представления для агентов, основанных на знаниях, но логика имеет некоторые серьезные ограничения. Очевидно, что значительная часть рассуждений, осуществляемых людьми и другими агентами в частично наблюдаемых вариантах среды, основана на оперировании знаниями, которые являются неопределенными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
