Искусственный интеллект. Современный подход

Оптимальные решения в играх с несколькими игроками

Многие популярные игры допускают наличие больше чем двух игроков. Рассмотрим, как можно распространить идею минимаксного алгоритма на игры с несколькими игроками. С точки зрения технической реализации это сделать несложно, но при этом возникают некоторые новые и интересные концептуальные проблемы.
Вначале необходимо заменить единственное значение для каждого узла вектором значений. Например, в игре с тремя игроками, в которой участвуют игроки А, В и С, с каждым узлом ассоциируется вектор . Для терминальных состояний этот вектор задает полезность данного состояния с точки зрения каждого игрока. (В играх с двумя игроками и нулевой суммой двухэлементный вектор может быть сокращен до единственного значения, поскольку значения в нем всегда противоположны.) Простейшим способом реализации такого подхода является применение функции Utility, которая возвращает вектор значений полезности.
Теперь необходимо рассмотреть нетерминальные состояния. Рассмотрим узел в дереве игры, показанном на рис. 6.3, который обозначен как X. В этом состоянии игрок С выбирает, что делать. Два варианта ведут к терминальным состояниям с векторами полезности и . Поскольку 6 больше чем 3, игрок С должен выбрать первый ход. Это означает, что если достигнуто состояние X, то дальнейшая игра приведет к терминальному состоянию с полезностя-ми . Следовательно, зарезервированным значением X является этот вектор. Вообще говоря, зарезервированное значение узла п представляет собой вектор полезности такого узла-преемника, который имеет наивысшее значение для игрока, выбирающего ход в узле п.
Любой, кто играет в игры с несколькими игроками, такие как Diplomacy™ ("Дипломатия"), быстро узнает, что в них происходит гораздо больше событий, чем в играх с двумя игроками. В играх с несколькими игроками обычно создаются альянсы между игроками, либо формальные, либо неформальные. К тому же иногда по мере развития игры альянсы то формируются, то разрушаются. Как можно понять такое поведение? Являются ли альянсы естественным следствием выбора оптимальных стратегий для каждого игрока в игре с несколькими игроками? Как оказалось, они действительно могут стать таким следствием. Например, предположим, что игроки А и В имеют слабые позиции, а игрок С— более сильную позицию. В таком случае и для А, и для В часто бывает оптимальным решение атаковать С, а не друг друга, поскольку иначе С уничтожит каждого из них по отдельности. Таким образом, сотрудничество становится следствием чисто эгоистичного поведения. Безусловно, как только игрок С ослабнет под совместным натиском, альянс потеряет свой смысл и соглашение может нарушить либо игрок А, либо игрок В. В некоторых случаях явно выраженные альянсы просто становятся конкретным выражением того, что и так произошло бы. А в других случаях попытка нарушить альянс вызывает общественное осуждение, поэтому игроки должны класть на весы немедленно достигаемую выгоду от нарушения альянса и долговременный убыток, возникающий из-за того, что их не будут считать заслуживающими доверия. Дополнительная информация об этих сложностях в игре приведена в разделе 17.6.
Если игра не имеет нулевую сумму, то сотрудничество может также возникать даже при наличии всего двух игроков. Допустим, что имеется терминальное состояние с полезностями и что 100 0 — максимальная возможная полезность для каждого игрока. В таком случае оптимальная стратегия для обоих игроков заключается в том, чтобы делать все возможное для достижения этого состояния; это означает, что игроки автоматически вступают в сотрудничество для достижения обоюдно желаемой цели.