Поиск в условиях противодействия

В предыдущих задачах сложность нахождения решения определялась только размерностью пространства состояний. Существует класс задач, в которых присутствует элемент неопределенности. К ним относятся все игровые задачи. Мы не будем рассматривать шахматы (оцените сами комбинаторную сложность на первые 40 ходов, коэффициент ветвления па первом ходе — 20), а вернемся к игре в спички.

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

Так, показанная на рис. 2.15 цепочка «5 — 3 — 0» спичек нас устраивает (узлы отображают число спичек, остающееся после сделанного хода), но противник так никогда не будет ходить, а возьмет вместо трех спичек две, что приведет к нашему проигрышу.

Рис. 2.15. Фрагмент дерева решений в игре «23 спички».

Чтобы оценить целесообразность того или иного хода, присвоим нашей победе значение 1, а победе противника — значение 0. В таком случае наша стратегия заключается в том, чтобы максимизировать результат, а стратегия противника — его минимизировать. Назовем для ясности противника — МИН, а себя — МАКС. Спускаясь, но дереву решений, мы можем дать оценку каждому узлу на самом нижнем уровне (рис. 2.16).

Предполагая, что оба игрока действуют в своих интересах разумно, мы можем дать оценку каждому ходу игроков на каждый уровень выше, а именно: из всех вариантов ходов МИН предпочтет те, которые дадут оценку 0, а МАКС — ходы, дающие оценку 1. Таким образом, оценка каждого хода МАКСа будет равна минимуму оценок ответных ходов МИ На и, наоборот, оценка каждого хода МИ На будет равна максимуму оценок ответных ходов МАКСА.

мин.

Рис. 2.16. Фрагмент дерева решений в игре «23 спички» (алгоритм минимакса):

 — выигрыш МАКСа;  — выигрыш МИНа Данный алгоритм получил название алгоритма минимакса, или минимаксный алгоритм. Легко видеть, что оценки по минимаксу являются пессимистическими для каждого из игроков и, следовательно, гарантируют успешный результат.

В общем случае минимаксный алгоритм состоит из следующих шагов:

• 1) выбор шкалы оценок исходов игры;
• 2) спуск по дереву и присвоение оценок конечным состояниям;
• 3) последовательное присвоение оценок родительским узлам: для МИНа — максимальной из дочерних, для МАКСа — минимальной;
• 4) после присвоения значения начальной позиции можно начинать делать ходы.

Очевидным недостатком минимаксного алгоритма является его трудоемкость, поскольку необходимо выполнить обход всего дерева. Модификацией данного алгоритма, существенно укорачивающей его сложность, является альфа-бета отсечение. Рассмотрим еще раз тот же фрагмент, теперь уже с позиции МАКСа, цель которого максимизировать результат. Спускаясь, но дереву вглубь по левым ветвям, мы можем убедиться, что ход МАКСа «7—6» (взятие одной спички при семи в наличии) дает возможность МИНу выиграть ходом «6—5». А поскольку оценка хода МАКСа определяется минимумом оценок возможных ответов МИНа, спускаться по соседним ветвям «6—4» и «6—3» нет необходимости и можно сразу переходить к спуску по ветви «7—5».

Рис. 2.17. Алгоритм минимакса с альфа-бета отсечением.

И наоборот, если мы видим, что ход МАКСа «7—5» имеет оценку 1, нам нет необходимости проверять ветвь «7—4».

Эффективность альфа-бета отсечения существенно зависит от порядка проверки узлов. Если бы мы вначале проверили ход «7—5», то нам бы не пришлось проверять ход «7—6». Это означает, что спуск, но дереву целесообразно начинать с наиболее перспективных ходов. Разумеется, это возможно, только если мы располагаем подходящей информацией.