Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 66
Текст из файла (страница 66)
К таким играм относятся бридж, вист, "Червы" и некоторые виды покера. На первый взгляд может показаться, что карточные игры полностью аналогичны играм с жеребьевкой: раздача карт происходит случайным образом, а сами карты определяют, какие ходы могут быть сделаны каждым игроком. Однако в картах вся жеребьевка происходит с самого начала! Это замечание будет обсуждаться ниже более подробно и будет показано, что такая особенность рассматриваемых карточных игр весьма полезна на практике. Вместе с тем, это замечание одновременно является совершенно неправильным по очень интересным причинам.
Представьте себе, что два игрока, мАх и м1м, разыгрывают какую-то реальную раздачу по четыре карты в бридже с двумя игроками, в котором открыты все карты. На руках находятся следующие карты, и игрок млх лолжен ходить первым: МАХ: Ю б + б Ф 9 8 мтм: ю 4 4 2 Ф 10 5 Предположим, что игрок мдх ходит с карты 4 9. Теперь должен ходить игрок мтм, который может выбросить карту ь 10 или 4 5. Игрок мгм кладет карту ь !О и забирает взятку. Затем очередь хода переходит к игроку м1м, который ходит картой 4 2. У игрока млх масти пика нет (и поэтому он не может забрать эту взятку), следовательно, он обязан выбросить какую-то другую карту. Очевидным вариантом является карта + 6, поскольку две другие оставшиеся карты являются старшими. Теперь, какой бы картой не ходил игрок м1м во время следующего розыгрыша, игрок МАХ возьмет две оставшиеся взятки и игра окончится ничьей, при двух взятках у каждого игрока. С использованием подходящего варианта минимаксного поиска (см.
упр. 6.12) можно легко показать, что фактически ход картой 4 9, сделанный игроком МАХ, был оптимальным. Теперь заменим карты на руках игрока М1М и вместо карты м 4 введем карту 4 4: МАХ: Ч б Ф б Ф 9 8 Мтн: Ф 4 4 2 Ф 10 5 Рассматриваемые два случая являются полностью симметричными: ход игры будет одинаковым, за исключением того, что при розыгрыше второй взятки игрок млх выбросит карту е 6. Игра снова окончится ничьей при двух взятках у каждого игрока, и ход картой ь 9 является оптимальным.
До сих пор все шло хорошо. А теперь скроем одну из карт игрока М1М и допустим, что игрок мдх знает, что у игрока м1м на руках либо первая раздача (с картой ч 4), либо вторая раздача (с картой 4 4), но он не знает, какая именно из них. Игрок млх рассуждает следующим образом. Глава 6.
Поиск в условиях противодействия 263 Ход картой 4 9 является оптимальным решением в игре против первой и второй раздачи на руках игрока мтн, поэтому теперь этот ход должен быть оптимальным, поскольку известно, что на руках у игрока нтн имеется один из этих двух вариантов раздачи. На более обобщенном уровне можно сказать, что игрок Млх использует подход, который может быть назван "усреднением по прогнозам". Идея его состоит в том, чтобы при наличии карт на руках у противника, которые не видны игроку, оценивать каждый возможный вариант действий, вначале вычисляя минимаксное значение этого действия применительно к каждой возможной раздаче карт, а затем вычисляя ожидаемое значение по всем раздачам с использованием вероятности каждой раздачи.
Если читатель посчитает такой подход разумным (или если он не может судить о нем, поскольку не знаком с бриджем), то ему следует поразмыслить над приведенным ниже рассказом. Первый день. Дорога л ведет к куче золотых слитков; дорога в ведет к развилке. Если вы от развилки пойдете налево, то найдете гору драгоценностей, а если пойдете направо, то попадете под автобус. Второй день. Дорога л ведет к куче золотых слитков; дорога в ведет к развилке. Если вы от развилки пойдете направо, то найдете гору драгоценностей, а если пойдете налево, то попадете под автобус.
Третий день. Дорога л ведет к куче золотых слитков; дорога в ведет к развилке. Если вы от развилки выберете правильное направление, то найдете гору драгоценностей, а если неправильное, то попадете под автобус. Очевидно, что в первые два дня решение выбрать дорогу В не лишено смысла, но в третий день ни один человек в здравом уме не выберет дорогу в. Однако именно такой вариант подсказывает метод усреднения по прогнозам; дорога В является оптимальной в ситуациях, возникающих в первый и второй дни, поэтому она оптимальна и в третий день, поскольку должна иметь место одна из двух предьщущих ситуаций.
Вернемся к карточной игре: после того как игрок МАХ пойдет картой Ь 9, игрок МТМ заберет взятку картой ь 10. Как и прежде, мтм пойдет с карты 4 2, но теперь игрок млх окажется перед развилкой на дороге без каких-либо указаний. Если игрок млх выбросит карту зг 6, а у игрока мтм все еще будет оставаться карта зг 4, то эта карта ч 4 станет козырной и игрок МЛХ проиграет игру. Аналогичным образом, если игрок млх выбросит карту + 6, а у игрока МПЯ все Еще будет оставаться карта + 4, игрок млх также проиграет. Поэтому игра с первым ходом картой ь 9 ведет к ситуации, в которой игрок млх имеет 50%- ную вероятность проигрыша.
(Для него было бы гораздо лучше вначале сыграть картами ч 6 и + 6, гарантируя для себя ничейную игру.) Из всего этого можно извлечь урок, что при недостатке информации игрок должен учитывать, какую информацию он будет иметь в каждый момент игры. Недостаток алгоритма, применяемого игроком МАХ, состоит в том, что в нем предполагается, будто при каждой возможной раздаче игра будет развиваться так, как если бы все карты оставались видимыми. Как показывает данный пример, зто вынуждает игрока млх действовать таким образом, как будто неопределенность разрешится, когда настанет время.
Кроме того, в алгоритме игрока МЛХ никогда не принимается решение, что нужно собирать информацию (или предоставлять информацию партнеру), поскольку этого не требуется делать в рамках каждой отдельной раздачи; тем не менее в таких играх, как бридж, часто бывает целесообразно сыграть такой кар- 264 Часть П, Решение проблем той, которая помогла бы кое-что узнать о картах противника или сообщить партнеру о своих собственных картах. Такие стереотипы поведения формируются автоматически оптимальным алгоритмом ведения игр с неполной информацией. Подобный алгоритм выполняет поиск не в пространстве состояний мира (под этим подразумеваются карты, находящиеся на руках у игроков), а в пространстве доверительных состояний (представлений о том, кто какие карты имеет и с какими вероятностями). Авторы смогут объяснить этот алгоритм должным образом в главе 17 после разработки всего необходимого вероятностного инструментария.
А в данной главе необходимо также остановиться на одном заключительном и очень важном замечании: в играх с неполной информацией лучше всего выдавать противнику как можно меньше информации, а наилучший способ сделать это чаще всего состоит в том, чтобы действовать непредсказуемо. Вот почему санитарные врачи, посещая для проверки предприятия общественного питания, не сообщают заранее о своих визитах.
6.6. СРВРЕМЕИИЫЕ ИГРРВЫЕ ПРРГРАММЫ Публичная демонстрация программ ведения игр представляет собой для искусственного интеллекта примерно то же, что и участие в автогонках международного масштаба для автомобильной промышленности — суперсовременные игровые программы действуют поразительно быстро, чрезвычайно тщательно настроенные компьютеры воплощают в себе наиболее качественные инженерные решения, но это все не предназначено для рядового покупателя. А некоторые исследователи даже считают, что ведение игр представляет собой нечто, не имеющее отношения к основному направлению развития искусственного интеллекта.
Тем не менее эта область продолжает порождать не только всеобщее восхищение, но и постоянный поток инноваций, которые затем усваиваются более широким сообществом разработчиков. э. Шахматы. В 1957 году Герберт Саймон предсказал, что через 1О лет компьютеры победят человека — чемпиона мира по шахматам. Через сорок лет программа Реер В1це победила Гарри Каспарова в показательном матче из шести игр.
Саймон ошибся, но лишь с коэффициентом 4. Каспаров писал: Решающей игрой в этом матче была вторая партия, которая оставила глубокий след в моей памяти... Мы наблюдали события, которые намного превосходили самые невероятные ожидания в отношении того, насколько хорошо компьютер будет способен предвидеть долговременные позиционные последствия своих решений. Машина отказалась перейти в позицию, имеющую явное, но кратковременное преимущество, продемонстрировав вполне человеческое ощущение опасности 1774!.
Программа Реер В1це была создана Мьюрреем Кэмпбеллом, Фенгсюнг Су и Джозефом Хоаном из компании 1ВМ [216] на основе проекта Реер Т11оц8Ы, разработанного ранее Кэмпбеллом и Су в университете Карнеги — Меллона (Сагпей(е — Ме!1оп Пп(чегзйу — СМ()). Компьютер-победитель представлял собой параллельный компьютер с 30 процессорами 1ВМ В8/6000. На этом компьютере эксплуатировались средства "программного поиска'" и 480 специализированных СВИС шахматных процессоров, которые осуществляли выработку ходов (включая упорядочение ходов), "аппаратного поиска" для последних нескольких уровней дерева и проводилась оценка листовых узлов. В программе Реер В!це в среднем осуществлялся поиск 126 миллионов узлов в секунду, а пиковая скорость достигала 330 миллионов узлов в Глава 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
