Имеется два игрока – A, B.

• 1 ход (личный): игрок А выбирает одну из двух цифр – 1 или 2;

• 2 ход (случайный): бросается монета и если выпадает «герб» (Г), то игроку В сообщается о выборе игрока А, если выпадает «решетка» (Р), то не сообщается;

• 3 ход (личный): игрок В выбирает одну из двух цифр – 3 или 4.

Платеж определяется следующим образом. Суммируются выборы игроков А и В, и если сумма чётная, то она выплачивается игроком В игроку А, если сумма нечетная, то игрок А платит игроку В. Соответствующее дерево игры представлено на рис. 2.1.

Определение 2.1. Классом информации S называется множество вершин дерева, в которых игроку, делающему личный ход, доступна одна и та же информация.

Для рассматриваемого примера имеется четыре класса информации (см. рис. 2.1): S₁, S₂ и S₄, содержащие по одной вершине, и S₃, который содержит две вершины.

Нетрудно доказать следующую лемму.

Лемма 2.1. Для игры с неполной информацией имеется хотя бы один класс информации, содержащий две или более вершин. Соответственно для игры с полной информацией все классы информации содержат по одной вершине.

Рис. 2.2. Дерево игры

Так как класс S₃ включает две вершины, то, следовательно, в общем случае имеем игру с неполной информацией. Отметим, что в частном случае, когда выпадает «герб» и игроку В сообщается о выборе игрока А, данная игра становится игрой с полной информацией.

Определим множества стратегий игроков.

Очевидно, что у игрока А имеется всего две стратегии (для класса информации S₁): A₁ – выбор 1, A₂ – выбор 2. У игрока В стратегией B_i является правило (, , ), определяющее выбор игрока в классах информации S₂(), S₃() и S₄(). Следовательно, у игрока В имеется восемь стратегий: B₁ = (3; 3; 3), B₂ = (3; 3; 4), …, B₈ = (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.

Процедура включает следующие шаги.

1. Строится полное поисковое дерево на максимально возможную с учетом вычислительных ресурсов (времени счета и памяти) глубину, при условии равенства числа ходов у обоих игроков.

2. Концевые вершины дерева взвешиваются значениями оценочной функции.

3. Совершается обратное движение по дереву от концевой к начальной вершине с пересчетом значений оценочной функции и итоговым выбором первого хода игрока A, максимизирующего это значение.

Далее осуществляется переход в вершину, соответствующую выбранному ходу, и вся процедура повторяется уже для игрока B, с тем только отличием, что игрок B заинтересован в минимизации значения оценочной функции.

Описанная процедура поочередно применяется для игроков A и B до завершения игры (партии).

Алгоритм поиска на основе метода максимина будет допустимым, если используется точная оценочная функция, и эвристическим, если оценочная функция является эвристической.

Рис. 2.2 иллюстрирует данный метод. Цифры у промежуточных вершин являются пересчитанными для этих вершин значениями оценочной функции. В результате выполнения процедуры будет рекомендовано игроку A в качестве первого хода выбрать переход к вершине S₁ с максимальным значением оценки.

Существенный недостаток метода максимина, следствием которого являются чрезмерно большие затраты вычислительных ресурсов, что, в свою очередь, сокращает глубину построения дерева, заключается в разделении этапов построения дерева и оценки вершин. Усовершенствованием данного метода является метод - отсечений, согласно которому отсечение неперспективных вершин производится непосредственно в процессе построения дерева игры.

Рис. 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).

Рассмотрим две возможности:

1. f(C) = f(D), что означает f(C)  f(E)  , т.е. имеем согласно лемме 2.2 неглубокое  отсечение, означающее неперспективность для игрока A вообще всех продолжений из вершины Y.

2. 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 вариантов выбора. Тогда сложность вычислений равна:

• mⁿ для метода максимина;

• 2m^n/2 для метода - отсечения.

Таким образом, метод - отсечений позволяет при тех же затратах памяти, что и метод максимина, построить дерево в среднем на глубину, в два раза большую, а значит, найти более качественное решение. Эффективность метод - отсечений возрастает, если удается предварительно упорядочить оцениваемые вершины по убыванию оценки  и возрастанию оценки .

К недостаткам рассмотренных методов относятся:

• по сути оба метода не являются стратегиями и базируются на классических переборных алгоритмах с использованием оценочной функции;

• наличие эффекта горизонта, т.е. методы «не видят» выигрыша, который находится за горизонтом (ниже по дереву) оцениваемых вершин.

2.3.Контрольные вопросы к разделу 2

1. Перечислите возможные виды представления антагонистической игры.

2. Дайте определение класса информации.

3. Сформулируйте лемму 2.1.

4. Приведите пример представления антагонистической игры в виде дерева.

5. Назовите возможные методы поиска решений на дереве игры.

6. Дайте определения допустимого и оптимального алгоритмов поиска.

7. Поясните максиминный метод поиска решения.

8. Поясните неглубокое - отсечение.

9. Сформулируйте лемму 2.2.

10. Дайте доказательство леммы 2.2.

11. Поясните глубокое - отсечение.

12. Сформулируйте лемму 2.3.

13. Дайте доказательство леммы 2.3.

14. Приведите сравнительные оценки методов максимина и  отсечений.

15. Перечислите основные недостатки методов максимина и  отсечений.

3.МЕТОДЫ РЕШЕНИЯ АНТАГОНИСТИЧЕСКИХ ИГР, ПРЕДСТАВЛЕННЫХ В МАТРИЧНОЙ ФОРМЕ

3.1.Матричное представление антагонистической игры

Пусть заданы множества стратегий {A_i}, i = 1,… m, и {B_j}, j = 1,…,n, игроков A и B соответственно, а также матрица выигрышей A = ||a_ij||, i = 1, …, m, j = 1, …, n, где элемент a_ij – выигрыш игрока A в ситуации, когда он выбирает стратегию A_i, а игрок B – стратегию B_j. Такая игра G(mn) может быть представлена в матричной форме (и называется матричной игрой) в виде таблицы (табл. 3.1).

Таблица 3.2

B j Ai	B1		Bj		Bn
A1	a11		a1j		a1n
Ai	ai1		aij		ain
Am	am1		amj		amn

В качестве иллюстрации снова рассмотрим игру из примера 1 п. 2.1 для случая неполной информации, т.е. когда игроку B не сообщается о выборе игрока A. У игроков A и B имеется по две стратегии: A₁ и A₂ – выбрать 1 или 2 соответственно, B₁ и B₂ – выбрать 2 или 3 соответственно. Данная игра G(22) в матричной форме представлена табл. 3.2.