Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 230
Текст из файла (страница 230)
Специалисты в области теории игр соглашаются с тем, что обязательным условием того, чтобы некоторый ход представлял собой решение, является принадлежность его к равновесию Нэша, но еще не достигнуто полное согласие в отношении того, является ли это условие достаточным. Решения 1геэгдбу, Сеэгзбу) можно довольно легко избежать, немного изменив правила игры (или взгляды игроков). Например, можно перейти к итерационной игре, в которой игроки знают, что когда-то обязательно снова встретятся и вспомнят, как действовали при прошлой встрече (но крайне важно то, что они не должны иметь определенной информации о том, через какое время встретятся). Кроме того, если агенты имеют моральные убеждения, которые способствуют сотрудничеству и справедливому отношению друг к другу, то можно изменить матрицу вознаграждения так, чтобы она отражала для каждого агента полезность взаимодействия с другим агентом.
Как будет показано ниже, на результатах может также отразиться такая модификация агентов, чтобы они обладали ограниченной вычислительной мощью, а не способностью рассуждать абсолютно рационально, а также предоставление одному агенту информации о том, что способности другого рассуждать рационально ограничены. Теперь рассмотрим игру, в которой отсутствует доминантная стратегия. Предположим, что компания Асше, изготовитель аппаратных средств для видеоигр, должна решить, будут ли в ее следующей игровой машине использоваться РУР или СР. Между тем компания Вем, производитель программного обеспечения для видеоигр, должна принять решение о том, следует ли выпускать свою очередную игру на РУР или СР.
Для обеих компаний прибыль будет положительной, если они примут согласованные решения, и отрицательной, если решения не будут согласованными, как показывает матрица вознаграждений, приведенная в табл. 17.3. 844 Часть х'. Неопределенные знания и рассуждения в условиях неопределенности том, что оба игрока должны выбрать решение, оптимальное по принципу Парето,— (с)згс), ойле); это означает, что можно ограничить определение понятия "решения" уникальным, оптимальным по принципу Парето равновесием Нэша, при условии, что оно существует. Каждая игра имеет по меньшей мере одно оптимальное по принципу Парето решение, но в любой игре может быть несколько таких решений, или эти решения могут не оказаться точками равновесия. Например, можно было бы установить вознаграждения за решение (Жс), с)ьт)), равные 5, а не 9.
В этом случае имеются две одинаковые точки равновесия, оптимальные по принципу Парето. Чтобы выбрать между ними, агенты должны либо пользоваться догадками, либо прибегать к обшению, что можно сделать, приняв соглашение об упорядочении решений до начала игры, или проводить переговоры, чтобы достичь обоюдно выгодного решения во время игры (это может означать, что в состав многоходовой игры должны быть включены коммуникативные действия). Таким образом, необходимость в обшении возникает в рамках теории игр точно по тем же причинам, что и в мультиагентном планировании, описанном в главе 12. Игры, подобные этой, в которых игроки должны вступать во взаимодействие, называются Ъ.
координационными играми. Выше было показано, что игра может иметь больше одного равновесия Нэша; но на основании чего мы можем утверждать, что каждая игра должна иметь по меньшей мере одно такое равновесие? Может оказаться, что в игре отсутствует равновесие Нэша для чистой (не смешанной) стратегии. Рассмотрим, например, любой профиль чистых стратегий для игры в чет и нечет на двух пальцах (с. 839). Если обшее количество показанных пальцев является четным, то игрок О может захотеть переключиться на другую стратегию, а если это количество нечетно, то будет стремиться переключиться игрок Е.
Поэтому ни один профиль чистых стратегий не может представлять собой равновесие и приходится рассматривать смешанные стратегии. Но какой должна быть смешанная стратегия? В 1928 году фон Нейман разработал метод поиска оптимальной смешанной стратегии для игр с двумя игроками, называемых 'в. играми с нулевой суммой.
Игрой с нулевой суммой называется игра, в которой вознагражления в каждой ячейке матрицы вознаграждения в сумме равны нулю'. Очевидно, что игра в чет и нечет является именно таковой. Известно, что для игр с двумя игроками и нулевой суммой вознаграждения являются равными и противоположными, поэтому достаточно рассмотреть вознаграждения только для одного игрока, который будет считаться максимизируюшим игроком (точно так же, как и в главе 6). Применительно к игре в чет и нечет выберем в качестве максимизируюшего игрока е, который выбрал для себя в качестве выигрышного результата четное количество пальцев, поэтому можно определить матрицу вознаграждений на ОСНОВЕ ЗНаЧЕНИй Ув( Е, О) — ВОЗНаГРажДЕНИЕ, ПОЛУЧаЕМОЕ ИГРОКОМ Е, ЕСЛИ ИГРОК Е выбирает действие е, а Π— действие о. Метол фон Неймана называется методом 'в.
максимина и действует, как описано ниже. ' более обшим является понятие игр с постоянной суммой, в которых сумма в каждой ячейке матрицы вознаграждений игры равна некоторой константе с. Любую игру с постоянной суммой и п участниками можно преобразовать в игру с нулевой суммой, вычтя из каждого вознаграждения значение суп. Таким образом, шахматы, в которых по трааиции применяется вознаграждение 1 за победу, 1/2 — за ничью и Π— за проигрыш, формально представляет собой игру с постоянной суммой, где с=1, носе можно легко преобразовать в игру с нулевой суммой, вычтя 1/2 из каждого вознаграждения.
Глава 17. Принятие сложных решений 845 ° Предположим, что правила игры изменились таким образом, что игрок Е вынужден раскрывать свою стратегию первым, а за ним следует игрок О. В таком случае мы имеем дело с игрой, где ходы выполняются поочередно, к которой можно применить стандартный минимаксный алгоритм из главы 6. Допустим, что такая игра приводит к получению результата ()в о Очевидно, что эта игра окончится в пользу игрока О, поэтому истинная полезность ((данной игры (с точки зрения игрока я) равна по меньшей мере (гв о Например, если рассматриваются только чистые стратегии, то минимаксное дерево игры имеет корневое значение, равное -3 (рис. 17.9, а), поэтому известно, что О>-3.
° Теперь предположим, что правила изменились таким образом, что свою стратегию вынужден раскрывать игрок О, а за ним следует игрок я. В таком случае минимаксное значение этой игры становится равным ()о „а поскольку игра складывается в пользу игрока я, то известно, что полезность ц самое большее Равна Оо в ПРи использовании чистых стРатегий это значение Равно +2 (см. рис.
17.9„б), поэтому известно, что Он+2, Рассматривая эти два предположения совместно, можно прийти к заключению, что истинная полезность (( рассматриваемого решения должна удовлетворять следуюшему неравенству: Уа,о < У Я Уо.а мли в данном случае -3 < У < 2 Чтобы точно определить значение (), необходимо перейти к анализу смешанных стратегий. Вначале отметим следуюшее: ~~ как только первыи игрок раскрыл свою стратегию, второй игрок ие может проиграть, ведя игру согласно чистой стратегии. Причина этого проста — если второй игрок ведет игру на основе смешанной стратегии, [р: опе; (1-р): гыо], то ожидаемая полезность этой игры представляет собой линейную комбинацию (р.и,„,+ (1-р) .и,„,) полезностей чистых стратегий и,„, и и,„,. Эта линейная комбинация ни при каких условиях не будет лучше по сравнению с лучшим из значений и,„, и и,„„поэтому второй игрок вполне может просто выбрать для ведения игры чистую стратегию.
С учетом этого замечания минимаксные деревья можно рассматривать как имеющие бесконечное количество ветвей, исходяших от корня, которые соответствуют бесконечному количеству смешанных стратегий, доступных для выбора первым игроком. Каждая из этих ветвей ведет к узлу с двумя ветвями, соответствующими чистым стратегиям для второго игрока. Эти бесконечные деревья можно изобразить как конечные, предусмотрев один "параметризованный" выбор у корня, как описано ниже. ° Ситуация, возникающая, если игрок я ходит первым, показана на рис.
17.9, в. Игрок еделает из корневой позиции ход [р: опе; (1-р): сьо], а затем игрок О выбирает ход с учетом значения р. Если игрок О выбирает ход опе, то ожидаемое вознаграждение (для я) становится равным 2р-3 (1-р) =5р-3; если игрок О выбирает ход саго, то ожидаемое вознаграждение равно -Зрь4 (1-р) =4-7р. Зависимости, выражаюшие величину этих двух вознаграждений, можно изобразить в внде прямых линий на графике, где р изменяется от О до 1 вдоль оси х, как показано на рис. 17.9, д. Игрок О, минимизируюший стоимость игры, должен всегда выбирать наименьшее значение на двух прямых линиях, как показано на этом рисунке жирными отрезками прямых. Поэтому наилучшее решение, которое может 846 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности принять игрок к, выбирая ход, подлежащий выполнению из корневой позиции, состоит в том, чтобы выбрать значение р, соответствующее точке пересечения и определяемое следующим образом: а) б) О О о о 3 3 4 2 3 3 в) г) о (9: опе; (1- д): (р:опе;(1-р): О 39 ь 4( ! - 9) 2д-3(! -9) )р + 4(! — р) 2р-3(! -р) я) и с) и +4 44 Рис. 17.9. Анализ игры с двумя игроками: минимаксные деревья игры в чет и нечет на двух польник, если игроки ходят по очереди, ведя игру на основе чистых стратегий (а), (б); параметризованные деревья игры, в которой первый игрок использует смешанную стратегию, причем вознаграждения зависят огп параметра вероятности (р или с() в смешанной стратегии (в), (г); для любого конкретного значения параметра вероятности второй игрок выбирает "наилучшее" этих двух действий, поэтому значение для смешанной стратегии первого игрока задается зкирными линиями; первый огрок выбирает параметр вероятности для смешанной стратегии в точке пересечения (д), (е) 847 Глава 17.
Принятие сложных решений бр-3 = 4-7р т р=7г'12 ПОЛЕЗНОСтЬ ДЛЯ ИГРОКа Е В ЭтОт МОМЕНТ ВРЕМЕНИ РаВНа Ув о=-1712. ° А если первым холит игрок О, то складывается ситуация, показанная на рис. 17.9, г. Игрок О из корневой позиции делает ход [с1: опе; (1-д): сьго), после чего игрок е выбирает ход с учетом значения д. При этом вознаграждения определяются соотношениями' 2г7-3 (1-ст) =5гт-3 и -Зд~й (1-гт) =4-7су. Опять-таки на рис. 17.9, е показано, что наилучший ход, который может быть сделан игроком О из корневой позиции, состоит в выборе точки пересечения, следующим образом: 5Ч-3 = 4-7сг ~ Ч=.7/12 Полезность длЯ игРока е в этот момент Равна Оо в=-1/12. Теперь известно, что истинная полезность этой игры находится в пределах от -1 7 12 до -1712, те.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
