Метод максимина

Суть метода заключается в следующем. Имеется два игрока – A (MAX), задачей которого является максимизация платежа (своего выигрыша), и B (MIN), который, естественно, заинтересован в минимизации этого платежа (своего проигрыша).

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

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

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

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

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

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

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

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

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

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

Рис. 2.3. Дерево игры для метода максимина