Допустим, что некоторая вершина дерева соответствует ходу игрока ПЛЮС. Оценка для нее вычисляется как

Отсечение

A(2) B(2) C(2) D(2) E(1)

Позиция E имеет самую низкую оценку, но она выигрышная (как и D), а позиции A, B и C – ничейные, хотя и имеют более высокие оценки.

Для отсечения бесперспективных вариантов в игровых программах используется процедура α – β отсечения, использующая идеи метода ветвей и границ. Пусть имеется дерево игры и построена функция оценки, наибольшие значения которой определяют ход игрока ПЛЮС.

a = MAX (a₁, a₂, …, a_n),

где a₁, a₂, …, a_n – значения функции оценки в сыновьях этой вершины. Пусть нашли некоторое значение a_i. Тогда a ≥ a_i, то есть величина a_i определяет нижнюю границу для a, называемую α – значением. Эту границу можно использовать для отсечения некоторых ветвей дерева игры.

Аналогично для вершины, соответствующей ходу игрока МИНУС, оценка вычисляется как

b = MIN (b₁, b₂, …, b_m),

где b₁, b₂, …, b_m – значения функции оценки в сыновьях. После нахождения любого значения b_j получаем, что b≤ b_j, то есть величина b_j определяет верхнюю границу для b или β – значение.

Рассмотрим процедуру α – β отсечения на примере. На рисунке показан фрагмент дерева игры. Как и раньше, приведены оценки с точки зрения игрока ПЛЮС. Вершины дерева, соответствующие ходу игрока ПЛЮС, показаны квадратиками, а игрока МИНУС – кружками. Для игрока ПЛЮС оценка вершины определяется как максимум оценок сыновей, а для игрока МИНУС – как минимум. Корню соответствует текущая позиция. В листьях указаны статические оценки соответствующих позиций.

R

Оценка MAX: ≥3

Оценка MIN: ≤3 =3 после β – отсечения ≤2

MAX

=3 ≥

Lg

Tb

S

B

D

Hhb

5 ≥4

1 3 0 2 5 3 4 2 2 1 0 2 0 2 0 1 1 0

β – отсечение α - отсечение

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

1. После получения показанных на рисунке оценок в листовых вершинах a, b и c получаем в вершине D оценку 3. Значит, в вершину p поднимется оценка ≤3.

2. Оцениваем вершины d и e. После получения оценки 5 в вершине f можно заключить, что в вершине H будет оценка ≥5, то есть вершина H не сможет оказать влияние на оценку вершины p. Отсюда других сыновей вершины H (на рисунке f) можно не рассматривать. Значит, имеет смысл строить дерево в процессе оценок, а не заранее.

3. Аналогично получив в вершине h оценку 4, заключаем, что в вершине L будет оценка ≥4, поэтому вершины k и l можно не рассматривать. Это примеры β – отсечения, так как рассматривались сыновья вершины p, в которой оценка находится по минимуму оценок сыновей. Таким образом, в вершине p устанавливается окончательная оценка 3.

4. Оцениваем вершины n, o и p, получая оценку 2 в вершине B. Значит, в вершине q оценка ≤2.

5. Нас интересует оценка в корне. Для него определяется максимум из оценок сыновей, но в вершине p уже достигнуто значение 3. Значит, вершина q с оценкой ≤2 не может оказать влияние на оценку корня, поэтому в корень поднимается оценка 3. Вершины S и T со всеми своими сыновьями можно не рассматривать, а соответствующие части дерева игры не строить вообще. Это примеры α - отсечения.

Оценки вершин a, b и c сказались на 2 уровня выше, как и оценка q. Процедура α – β отсечения позволяет, например, в шашках сократить объем вычислений в 4-6 раз.

Эффективность процедуры зависит от порядка перебора вершин. Например, перебирая вершины в порядке d, e, f, h, k, l, a, b, c, для вершины p получали бы последовательно ограничения ≤5, ≤4, ≤3, то есть β – отсечения не было бы совсем. Поэтому важно как можно раньше получать удовлетворительный ход, что возможно на основе дополнительной информации об игре. Опытный игрок вообще не рассматривает бесперспективные варианты.

Методы теории вероятности позволяют распространить описанные подходы и на недетерминированные игры.

Не стоит думать, что подобные игровые модели имеют значение только в развлекательных целях. Существует, например, класс так называемых “игр с природой”, когда необходимо принимать решения, позволяющие добиться наибольшей выгоды, избегая риска катастрофических последствий. Другой вид игр – противодействие (ответные ходы) попыткам доступа к конфиденциальной информации.

Дата добавления: 2014-01-11