Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 63
Текст из файла (страница 63)
Следовательно, зарезервированным значением Х является этот вектор. Вообще говоря, зарезервированное значение узла п представляет собой вектор полезности такого узла-преемника, который имеет наивысшее значение для игрока, выбирающего ход в узле п. Любой, кто играет в игры с несколькими игроками, такие как Е1!р!отасу™ ("Дипломатия"), быстро узнает, что в них происходит гораздо больше событий, чем в играх с двумя игроками. В играх с несколькими игроками обычно создаются Ъ. альянсы между игроками, либо формальные, либо неформальные. К тому же иногда по мере развития игры альянсы то формируются, то разрушаются. Как можно понять такое поведение? Являются ли альянсы естественным следствием выбора оптимальных стратегий для каждого игрока в игре с несколькими игроками? Как оказалось, они действительно могут стать таким следствием.
Например, предположим, что игроки л и в имеют слабые позиции, а игрок с — более сильную позицию. В таком случае и для д, и для в часто бывает оптимальным решение атаковать с, а не друг друга, поскольку иначе с уничтожит каждого из них по отдельности. Таким образом, сотрудничество становится следствием чисто эгоистичного поведения. Безусловно, как только игрок с ослабнет под совместным натиском, альянс потеряет свой Глава 6. Поиск в условиях противодействия 247 смысл и соглашение может нарушить либо игрок л, либо игрок в.
В некоторых случаях явно выраженные альянсы просто становятся конкретным выражением того, что и так произошло бы. А в других случаях попытка нарушить альянс вызывает общественное осулщение, поэтому игроки должны класть на весы немедленно достигаемую выгоду от нарушения альянса и долговременный убыток, возникающий изза того, что их не будут считать заслуживающими доверия.
Дополнительная информация об этих сложностях в игре приведена в разделе 17.6. Ход игрока А с А (1, 2, 6) (4, 2, 3) (6, 1, 2) (7, 4, 1) (5, 1, 1) (1, 5, 2) (7, 7, 1) (5, 4, 5) Рис. бык Первые три налухада игры с тремя игроками ГА, в, о). Каждый узел обозначен значениями, достигаемыми с тачки зрения каждого участника. Наилучший ход обозначен стрелкой, исиздятей из карня Если игра не имеет нулевую сумму, то сотрудничество может также возникать даже при наличии всего двух игроков.
Допустим, что имеется терминальное состояние с полезностями <ага=1000, гга=1000~ и что 1000 — максимальная возможная полезность для каждого игрока. В таком случае оптимальная стратегия для обоих игроков заключается в том, чтобы делать все возможное для достижения этого состояния; это означает, что игроки автоматически вступают в сотрудничество для достижения обоюдно желаемой цели. 6.3. АЛЬФА-БЕТА-ОТСЕЧЕНИЕ При минимаксном поиске проблема состоит в том, что количество состояний игры, которые должны быль исследованы в процессе поиска, зависит экспоненциально от количества ходов.
К сожалению, такую экспоненциальную зависимость устранить невозможно, но Фактически существует возможность сократить ее наполовину. Весь секрет состоит в том, что вычисление правильного минимаксного решения возможно без проверки каждого узла в дереве игры. Зто означает, что можно позаимствовать идею втсечевия, описанную в главе 4, чтобы исключить из рассмотрения большие части дерева.
Конкретный метод, рассматриваемый в данной главе, называется гак альфа-бета-отсечением. Будучи применен к стандартному минимаксному дереву, этот метод возвращает такие же ходы, которые вернул бы минимаксный метод, но отсекает ветви, по всей вероятности, не способные повлиять на окончательное решение. Снова рассмотрим дерево игры с двумя полуходами (см.
рис. 6.2) и еще раз проведем расчет оптимального решения, на сей раз обращая особое внимание на то, чта известно на каждом этапе этого процесса. Пояснения к данным этапам вычисления 249 Глава 6. Поиск в условиях противодействия два преемника узла с на рис.6.4, еще не обработанные в процессе вычисления, имеют значения х и у, и предположим, что я — минимальное значение среди х и у.
В таком случае значение корневого узла можно найти следующим образом: М1п1огах-гга1ие(ссоо) = агах(пьп(3, 12, вг, воп(2, х, у(, ог1п(14, 5, 2г ) = агах(3, вип(2, х, у), 2) = агах(3, г, 2) тае к<2 —. 3 Иными словами, значение корневого узла, а следовательно, и минимаксное решение не зависит от значений отсеченных листовых узлов хи у. Альфа-бета-отсечение может применяться к деревьям любой глубины; к тому же часто возникает возможность отсекать целые поддеревья, а не просто листья.
Об(ций принцип состоит в следующем: рассмотрим узел и, находящийся где-либо в дереве (рис. 6.5), такой, что участник игры со стороны наблюдателя (назовем его Игрок) имеет возможность выбрать ход, ведущий к этому узлу. Но если Игрок имеет лучший выбор ш либо в родительском узле узла и, либо в любой другой точке выбора, находящейся еще выше в дереве, то гв- узел п никогда не будет достигнут в игре, происходящей в действительности.
Поэтому после получения достаточной информации об узле п (путем исследования некоторых из его потомков) для того, чтобы с полной уверенностью прийти к этому заключению, можно выполнить его отсечение. Игрок Противник Игрок Противник Рис. 6.5. Альфа-бета-отсечение: общий случай. Если для Игрока узел вг лучше чеи и, то узел и никогда не встретится в игре Напомним, что минимаксный поиск осуществляется в глубину, поэтому в любой момент времени достаточно рассматривать узлы вдоль единственного пути в дереве.
Алгоритм альфа-бета-отсечения получил свое название по следующим двум параметрам, которые представляют пределы в зарезервированных значениях, присутствующих во всех узлах вдоль этого пути: ° а = значение наилучшего варианта (т.е. варианта с самым высоким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока млх; 250 Часть П.
Решение проблем ° )3 = значение наилучшего варианта (т.с. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока МТМ. Алгоритм альфа-бета-поиска в процессе своей работы обновляет значения а н )3, а также отсекает оставшиеся ветви в узле (т.е. прекращает рекурсивные вызовы), как только становится известно, что значение текущего узла хуже по сравнению с текушим значением а нли (3 для игрока мАХ нлн М1М соответственно. Полный алгоритм приведен в листинге 6.2.
Рекомендуем читателю проследить за его поведением применительно к дереву, показанному на рис. 6.4. Листинг 6.2. Алгоритм альфа-бета-поиска. Обратите внимание на то, что применяемые здесь процедуры остаются такими же, как н процедуры алгоритма м1п1шах, приведенного в листинге 6.1, за исключением двух строк, введенных как в процедуру м1п-ча1ие, так н в Мах-чатие, которые сопровождают значения а н б (а также выполняют соответствующие действия по дальнейшей передаче этих параметров) Еипосзоп А1р)за-Веса-яеагс)з(ясасе) гесигпв действие ассзол 1присв: ясасе, текущее состояние в игре у < — мах-уа1ие(ясасе, — , + ) гееитзз действие ассдоп из множества яиссеязогз(яеаее) со значением у еипсс1оп мах-уа1ие(ясасе, а, )3) гесигпв значение полезности 1приев: ясасе, текущее состояние в игре а, значение наилучшей альтернативы для игрока МАХ вдоль пути к состоянию ясасе значение наилучшей альтернативы для игрока М1Н вдоль пути к состоянию ясаее 1Е Тетщ1па1-Тевс(ясасе) сиоп гесигп цс111су(ясасе) и ь— еог а, я Еп яиссезвотв(ясасе) цо у ь- мах(у, мап-уа1ие(я, а, )3)) 1Е у > )3 Сиоп гееигп а <†мах(а, у) гееитп Еипосаоп мтп-уа1ие(ясасе, а, )3) тесигпв значение полезности 1приев: ягаее, текущее состояние в игре а, значение наилучшей альтернативы для игрока МАХ вдоль пути к состоянию ягасе значение наилучшей альтернативы для игрока М1И вдоль пути к состоянию ясасе 1е тетщ1па1-тезс(ясасе) с)зеп гееигп Вс11зсу(ясасе) и (- Еог а, я 1п Яиссевяотв(ятаСе) (Го и (- М1п(у, Мах-уа1ие(я, а, )3) ) 1Е у < а сноп теситп (3 < — Мьп((3, у) тесигп Глава 6.
Поиск в условиях противодействия 251 Эффективность алгоритма альфа-бета-отсечения в высшей степени зависит от того, в каком порядке происходит проверка преемников. Например, на рис. 6.4, д, е невозможно было бы вообще выполнить отсечение каких-либо преемников узла и, поскольку в первую очередь были бы сформированы наихудшие преемники (с точки зрения игрокам?)ч).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
