|
|
Теоретико-игровые методы принятия решений (Еремеев А. П.). Теоретико-игровые методы принятия решений (Еремеев А. П. Учебное пособие по курсам Теория игр и исследование операций, Теория принятия решений
2.1.Представление антагонистической игры
Рассмотрим антагонистическую игру G(mn),где у первого игрокаA имеется множество стратегий {Ai},i=1, …, m, а у второго игрока B – множество стратегий {Bj},j=1, …, n.
Игра G(mn)может быть представлена в виде дерева игры и в виде матрицы (матрицы платежей).
Представление игры в виде дерева является универсальным, т.е. любая игра может быть представлена в виде дерева, матричное представление не является универсальным – не любая игра может быть приведена к матричной форме.
Рассмотрим представление антагонистической игры G(mn) в виде дерева.
Корневая вершина дерева представляет начальную ситуацию (состояние), промежуточные вершины – промежуточные ситуации, возможные в игре, концевые вершины – все возможные исходы игры, взвешенные платежами – выигрышами игрока A (соответственно, проигрышами игрока B). Дуги – представляют возможные переходы, возникающие в результате личных или случайных ходов, причем личные ходы выполняются игроками согласно выбранных ими стратегий.
Проиллюстрируем процесс построения дерева игры на следующем примере.
Имеется два игрока – A,B.
1 ход (личный): игрок А выбирает одну из двух цифр – 1 или 2;
2 ход (случайный): бросается монета и если выпадает «герб» (Г), то игроку В сообщается о выборе игрока А, если выпадает «решетка» (Р), то не сообщается;
3 ход (личный): игрок В выбирает одну из двух цифр – 3 или 4.
Платеж определяется следующим образом. Суммируются выборы игроков А и В, и если сумма чётная, то она выплачивается игроком В игроку А, если сумма нечетная, то игрок А платит игроку В. Соответствующее дерево игры представлено на рис. 2.1.
Определение 2.1. Классом информации S называется множество вершин дерева, в которых игроку, делающему личный ход, доступна одна и та же информация.
Для рассматриваемого примера имеется четыре класса информации (см. рис. 2.1): S1,S2 и S4, содержащие по одной вершине, и S3, который содержит две вершины.
Нетрудно доказать следующую лемму.
Лемма 2.1. Для игры с неполной информацией имеется хотя бы один класс информации, содержащий две или более вершин. Соответственно для игры с полной информацией все классы информации содержат по одной вершине.
Рис. 2.2. Дерево игры
Так как класс S3включает две вершины, то, следовательно, в общем случае имеем игру с неполной информацией. Отметим, что в частном случае, когда выпадает «герб» и игроку В сообщается о выборе игрока А, данная игра становится игрой с полной информацией.
Определим множества стратегий игроков.
Очевидно, что у игрока А имеется всего две стратегии (для класса информации S1): A1– выбор 1,A2 – выбор 2.У игрока В стратегией Biявляется правило (, ,), определяющее выбор игрока в классах информации S2(), S3()и S4().Следовательно, у игрока В имеется восемь стратегий: B1=(3; 3; 3),B2=(3; 3; 4), …, B8=(4; 4; 4).
2.2.Поиск решения на дереве игры 2.2.1.Общие замечания
Дерево игры может быть построено, используя известные методы полного перебора («в глубину», «в ширину», комбинированный) или сокращенного перебора, выполняемого с использованием некоторой оценочной функции (точной или приближенной, эвристической) [7, 8].
Определение 2.2. Алгоритм поиска решения называется допустимым, если он оканчивает свою работу построением оптимального решения (оптимального пути к цели).
Определение 2.3. Допустимый алгоритм поиска решения называется оптимальным, если он при поиске решения анализирует (раскрывает) минимальное число вершин.
Примером допустимого (но, конечно, не оптимального) алгоритма является алгоритм, построенный на основе полного перебора. Эвристические алгоритмы, использующие при поиске решения методы сокращенного перебора на основе эвристических функций, как правило, не являются допустимыми, т.е. эти алгоритмы не гарантируют в общем случае нахождение оптимального решения. Преимуществом эвристических алгоритмов являются существенно меньшие затраты вычислительных ресурсов (времени вычислений и памяти) по сравнению с алгоритмами, основанными на полном переборе.
Нильсон Н. (Nilsson N.) в своей классической работе по искусственному интеллекту [7] доказал теорему, определяющую требования к эвристической функции, чтобы алгоритм поиска решения, построенный на ее основе, был допустимым. К сожалению, проверка выполнимости этого требования, в свою очередь, является сложной и обычно практически нереализуемой задачей.
Рассмотрим два универсальных метода сокращенного перебора на дереве игры – метод максимина (максиминный метод) и метод - отсечений.
2.2.2.Метод максимина
Суть метода заключается в следующем. Имеется два игрока – A(MAX), задачей которого является максимизация платежа (своего выигрыша), иB(MIN), который, естественно, заинтересован в минимизации этого платежа (своего проигрыша).
Реализуется процедура, результатом выполнения которой является определение наилучшего относительно оценочной функции первого хода игрока A.
Процедура включает следующие шаги.
Строится полное поисковое дерево на максимально возможную с учетом вычислительных ресурсов (времени счета и памяти) глубину, при условии равенства числа ходов у обоих игроков.
Концевые вершины дерева взвешиваются значениями оценочной функции.
Совершается обратное движение по дереву от концевой к начальной вершине с пересчетом значений оценочной функции и итоговым выбором первого хода игрока A, максимизирующего это значение.
Далее осуществляется переход в вершину, соответствующую выбранному ходу, и вся процедура повторяется уже для игрока B, с тем только отличием, что игрок B заинтересован в минимизации значения оценочной функции.
Описанная процедура поочередно применяется для игроков A и B до завершения игры (партии).
Алгоритм поиска на основе метода максимина будет допустимым, если используется точная оценочная функция, и эвристическим, если оценочная функция является эвристической.
Рис. 2.2 иллюстрирует данный метод. Цифры у промежуточных вершин являются пересчитанными для этих вершин значениями оценочной функции. В результате выполнения процедуры будет рекомендовано игроку A в качестве первого хода выбрать переход к вершине S1 с максимальным значением оценки.
Существенный недостаток метода максимина, следствием которого являются чрезмерно большие затраты вычислительных ресурсов, что, в свою очередь, сокращает глубину построения дерева, заключается в разделении этапов построения дерева и оценки вершин. Усовершенствованием данного метода является метод - отсечений, согласно которому отсечение неперспективных вершин производится непосредственно в процессе построения дерева игры.
Рис. 2.3. Дерево игры для метода максимина
2.2.3.Метод - отсечений
Идея улучшения метода максимина за счет совмещения этапов построения дерева и отсечения неперспективных продолжений была предложено Дж. Маккарти (J. McCarthy) в 1961 г.
Существуют два вида - отсечения:
неглубокое - отсечение;
глубокое - отсечение.
Неглубокое - отсечение
Рассмотрим дерево игры на рис. 2.3.
 Рис. 2.4. Неглубокое - отсечение
Пусть известны оценки f(X) = и f(C) = z.. Справедлива следующая лемма.
Лемма 2.2. Если f(C) , то ветви, исходящие из вершины Y и обозначенные штриховой линией, можно отсечь.
Доказательство. Так как игрок Bстремится минимизировать оценочную функцию, то оценка вершины Yбудет не больше z, т.е. f(Y) f(C) . Следовательно, вершина Yне будетконкурировать с вершиной X при выборе игрока A, так как f(Y) f(X), что и означает неперспективность ветвей, исходящих из вершины Y.
Мы рассмотрели отсечение, соответствующее выбору игрока A. Аналогичные рассуждения справедливы и для отсечения в ситуации, когда выбор делает игрок B при справедливости следующих оценок: f(X)=,f(C)=w.
Глубокое - отсечение
Рассмотрим дерево игры на рис. 2.4. Пусть известны оценки f(X) = и f(E) = z ..
Докажем следующую лемму.
Лемма 2.3. Если f(E) , то ветви, исходящие из вершины D и помеченные штриховой линией, можно отсечь.
Доказательство. Так как игрок Bстремится минимизировать оценочную функцию, то для вершины Dбудет справедлива следующая оценка f(D)f(E), а для вершины C, ход из которой делает игрок A, стремящийся максимизировать оценочную функцию, соответственно f(C)f(D).
Рассмотрим две возможности:
f(C) = f(D), что означает f(C)f(E), т.е. имеем согласно лемме 2.2 неглубокое отсечение, означающее неперспективность для игрока A вообще всех продолжений из вершины Y.
f(C)f(D), что означает неучастие (неперспективность) вершины Dдля получения оценки f(C).
Лемма доказана.
Рис. 2.5 иллюстрирует применение метода -отсечений.
Рис. 2.5. Глубокое - отсечение
Из рис. 2.5 видно, что игроку A рекомендуется в качестве первого хода выбрать продолжение, ведущее к вершине X.
Рис. 2.6. Применение метода - отсечений
Табл. 2.1 иллюстрирует процедуру -отсечения.
Таблица 2.1
Ход
|
Наилучшая оценка
|
Позиция на глубину
|
Оценка позиции
|
Условие отсечения
|
Действие
|
A (max)
|
|
Своя
|
z
|
z
|
отсечение
|
B (min)
|
|
Противника
|
w
|
w
|
отсечение
|
Заметим, что оценка возрастает при движении по дереву снизу вверх, а оценка , наоборот, убывает.
Приведем сравнительные оценки методов максимина и отсечений. Пусть оценивается дерево на глубину ходов (уровней) n (для равенства ходов игроков nдолжно быть четным) и на каждом уровне имеется m вариантов выбора. Тогда сложность вычислений равна:
Таким образом, метод - отсечений позволяет при тех же затратах памяти, что и метод максимина, построить дерево в среднем на глубину, в два раза большую, а значит, найти более качественное решение. Эффективность метод - отсечений возрастает, если удается предварительно упорядочить оцениваемые вершины по убыванию оценки и возрастанию оценки .
К недостаткам рассмотренных методов относятся:
по сути оба метода не являются стратегиями и базируются на классических переборных алгоритмах с использованием оценочной функции;
наличие эффекта горизонта, т.е. методы «не видят» выигрыша, который находится за горизонтом (ниже по дереву) оцениваемых вершин.
|
|
|
Скачать 1.18 Mb.