Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 231
Текст из файла (страница 231)
онаточно равна -1712! (Общий выводсостоитвтом, что в эту игрулучше играть от имени игрока О, а не Е.) Кроме того, истинная полезность достигается при исПОЛЬЗОВаинн СМЕШаННОЙ СтратЕГИИ [7 /12 г ОПЕ; 5 /12: СЫО), КОтОрОй дОЛжНЫ ПрндЕрживаться оба игрока. Такая стратегия называется 'а. максиминным равновесием игры и соответствует равновесию Нэша. Обратите внимание на то, что каждая составляющая стратегия в равновесной смешанной стратегии имеет одну и ту же ожидаемую полезность.
В данном случае и ход опе, и ход саго имеют ту же ожидаемую полезность, -1 7 12, что и сама смешанная стратегия. Приведенный выше результат для игры в чет и нечет на двух пальцах представляет собой пример общего результата, полученною фон Нейманом: ср «алсдая игра с нулевой суммой с двумя игроками имеет максиминное равновесие, если разрешены смешанные стратегии. Кроме того, каждое равновесие Нэша в игре с нулевой суммой представляет собой максиминное равновесие для обоих игроков.
Но общий алгоритм поиска максиминных равновесий в играх с нулевой суммой немного сложнее по сравнению с тем, что показано в виде схем на рис. 17.9, д и е. Если количество возможных действий равно п, то смешанная стратегия представляет собой точку в и-мерном пространстве и прямые линии становятся гиперплоскостями. Возможно также, что над некоторыми чистыми стратегиями для второго игрока будут доминировать другие стратегии, так что они перестанут быть оптимальными по отношению к любой стратегии для первого игрока.
После удаления всех подобных стратегий (а эту операцию может потребоваться выполнить неоднократно) оптимальным вариантом хода из корневой позиции становится самая высокая (или самая низкая) точка пересечения оставшихся гиперплоскостей. Поиск этого варианта представляет собой пример задачи линейного программирования — максимизации целевой функции с учетом линейных ограничений. Такие задачи могут быть решены с помощью стандартных методов за время, полиномиально зависящее от количества действий (а также формально и от количества битов, используемых для определения функции вознаграждения).
а То, что зги уравнения являются такими же, как и для р, обусловлено лишь совпадением; сов- ПадЕНИЕ ВОЗНИКЛО, ПОСКОЛЬКУ П (ОПЕ, ЬНО) = цг(СМО,ОПЕ) = -3. Эта СОВПадЕНИЕ таКжЕ Обьясняст, почему оптимальная стратегия является одинаковой для обоих игроков. 848 Часть У. Неопределенные знания и рассуждения в условиях неопределенности Остается нерешенным следующий вопрос: как фактически должен действовать рациональный агент при ведении такой одноходовой игры, как игра в чет и нечет? Рациональный агент пришел логическим путем к выводу, что ~7?12: спец 5 ? 12: Сьо] представляет собой максиминную равновесную стратегию, и исходит из предположения, что знаниями об этом обладает и его рациональный противник.
Агент может использовать игральную кость с ! 2 сторонами или генератор случайных чисел для выбора случайным образом хода, соответствуюшего этой смешанной стратегии, и в этом случае ожидаемое вознаграждение для игрока Е будет равно -1 ?12. В ином случае агент может просто решить сделать ход опе или сьго.
В любом случае для игрока и ожидаемое вознаграждение остается равным -1?12, Удивительно то, что односторонний выбор конкретного действия не уменьшает ожидаемое вознаграждение для данного игрока, но если другой агент будет иметь возможность узнать, что данный игрок принял такое одностороннее решение, то ожидаемое вознаграждение изменится, поскольку противник сможет откорректировать свою стратегию соответствующим образом.
Поиск решений для конечных игр с ненулевой суммой (т.е. равновесий Нэша) немного сложнее. Общий подход заключается в использовании двух этапов. Во-первых, необходимо составить список из всех возможных последовательностей действий, которые могут образовывать смешанные стратегии. Например, вначале следует проверить все профили стратегий, в которых каждый игрок выполняет одно действие, затем те, в которых каждый игрок выполняет либо одно, либо два действия, и т.д. Количество таких проверок экспоненциально зависит от количества действий, поэтому может применяться только в относительно простых играх.
Во-вторых, для каждого профиля стратегий, включенного в список на первом этапе, необходимо провести проверку для определения того, представляет ли он некоторое равновесие. Такая задача выполняется путем решения ряда уравнений и неравенств, аналогичных используемым в случае с нулевой суммой. В игре с двумя игроками эти уравнения являются линейными и могут быть решены с помощью основных методов линейного программирования, но в случае трех или большего количества игроков они являются нелинейными и задача поиска их решения может оказаться очень сложной.
До сих пор мы рассматривали только такие игры, которые состоят из одного хода. Простейшей разновидностью игры, состоящей из нескольких ходов, является Ж повторяющаяся игра, в которой игроки снова и снова сталкиваются с одним и тем же выбором, но каждый раз пользуются знаниями истории всех предыдущих выборов всех игроков. Профиль стратегий для повторяющейся игры определяет выбор действия для каждого игрока на каждом временном интервале для всех возможных историй предыдуших выборов. Как и в случае задач МОР, вознаграждения определяются аддитивной функцией от времени. Рассмотрим повторяющуюся версию поиска решения дилеммы заключенного.
Будут ли Алиса и Боб действовать совместно и откажутся свидетельствовать друг против друга, зная о том, что им придется снова встретиться? Ответ зависит от деталей их соглашения. Например, предположим, Алиса и Боб знают, что им придется провести ровно 100 раундов игры в дилемму заключенного. В таком случае оба они знают, что 100-й раунд не будет повторяющейся игрой, т.е. что ее результат не сможет оказать влияния на будущие раунды, и поэтому оба они выберут в этом раунде доминантную стратегию сеэсдГу.
Но как только булет определен результат 100-го 849 Глава 17. Принятие сложных решений раунда, 99-й раунд перестанет оказывать влияние на последующие раунды, поэтому в нем также будет достигаться равновесие доминантной стратегии в случае выбора действий ( севсзЕу, сезсзЕу). По индукции оба игрока даажны выбирать действие сев сз Еу в каждом раунде, заработав общий срок по 500 лет тюремного заключения на каждого. Изменяя правила взаимодействия, можно получить другие решения.
Например, предположим, что после каждого раунда существует 99% шансов, что игроки снова встретятся. В таком случае ожидаемое число раундов все еще остается равным 100, но ни один из игроков не знает точно, какой раунд будет последним. При таких условиях возможно поведение, характеризующееся большей степенью сотрудничества.
Например, одной из стратегий равновесия для каждого игрока является выбор действия ~-еГиэе, если другой игрок никогда не выбирал действие геэсугу. Такую стратегию можно назвать 'а. вечным наказанием. Предположим, что оба игрока приняли данную стратегию и это известно им обоим. В таком случае, при условии, что ни один из игрок не выберет действие сезсзЕу, в любой момент времени ожидаемое суммарное вознаграждение в будущем для каждого игрока составляет следующее: Х 0.99~(-1) = -100 с=о Игрок, который выберет сеэсуЕу, получит 0 очков вместо -1 в каждом следующем ходе, но его суммарное ожидаемое будущее вознаграждение становится равным: 0 ь ~ 0.99~ (-10) = -99 с=о Поэтому на каждом этапе игроки не имеют стимула, который заставил бы их отказаться от стратегии (кеГизе, хе~иве) .
Вечное наказание — это стратегия "взаимно гарантированного уничтожения" в рамках дилеммы заключенного: как только один из игроков решит выполнить действие сезсу бу, он обеспечит получение обоими игроками больших неприятностей. Но такая перспектива развития событий может стать предостережением, только если другой игрок знает, что вы приняли эту стратегию или по меньшей мере что вы могли ее принять.
Существуют и другие стратегии в этой игре, которые являются не такими бескомпромиссными. Наиболее известная из них, называемая 'в. отплатой "зуб за зуб", предусматривает, что игрок начинает с действия кеЕизе, а затем повторяет предыдущий ход другого игрока во всех последующих ходах. Поэтому Алиса должна отказываться свидетельствовать против Боба до тех пор, пока Боб отказывается свидетельствовать против нее, затем должна выбирать в своем ходе дачу показаний против Боба, как только Боб даст показания против нее, но должна возвращаться к отказу от дачи показаний, после того как это сделает Боб. Хотя эта стратегия очень проста, оказалось, что она является в высшей степени надежной и эффективной в противодействии самым разнообразным стратегиям.
Кроме того, другие решения могут быть получены в результате модификации самих агентов, а не изменения правил их взаимодействия. Предположим, что агенты представляют собой конечные автоматы с п состояниями и играют в игру с общим 850 Часть х'. Неопределенные знания и рассуждения в условиях неопределенности количество ходов шэп. Поэтому агенты в какой-то момент становятся неспособными представить целый ряд оставшихся ходов и должны рассматривать их как неизвестные. Это означает, что они не могут выполнять логический вывод по индукции и вправе переходить к наиболее благоприятному равновесию (гейиэе,хедиве).
В таком случае глупость идет на пользу или, скорее, идет на пользу мнение противника о том, что вы глупы. Ваш успех в таких повторяющихся играх зависит от мнения о вас другого игрока как о тупице или простаке, а не от ваших фактических характеристик. Полное описание повторяющихся игр, которые представляют собой большую и важную научную область, выходит за рамки данной книги, но они возникают во многих ситуациях.
Например, последовательную игру можно организовать, поместив двух агентов в мир 4хЗ, показанный на рис. 17.1. Если будет определено, что не должно происходить никакого движения, если два агента пытаются одновременно перейти в один и тот же квадрат (эта проблема часто возникает на многих пересечениях разных направлений дорожного движения), то некоторые чистые стратегии могут привести к бесконечному тупику. Одно из решений состоит в том, чтобы для каждого агента был рандомизирован выбор между движением вперед и остановкой на месте; патовая ситуация будет быстро разрешена и оба агента смогут продолжить свое движение. Именно такой подход применяется при разрешении коллизий между пакетами в сетях Ег)зегпеь Известные в настоящее время методы выработки решений для повторяющихся игр напоминают методы, применяемые в играх с поочередными ходами, описанных в главе 6, в том, что дерево игры может быть сформировано от корня вниз и решено от листьев вверх.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
