Романтика искусственного интеллекта - стр. 22

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

Но идеальная оценка невозможна, невозможно и полное или даже очень глубокое дерево перебора. Это означает, что вывод о качестве выбранного хода всегда может быть ошибочен, что создает возможность для так называемого комбинационного удара, выполнение которого выходит за рамки минимакса. В чем суть комбинации (тактического приема)? А суть в следующем: игрок допускает резкое ухудшение своей позиции в анализе дерева перебора на глубину в N ходов, но на большей глубине он получает значительно большую компенсацию. Например, можно отдать ферзя, если в результате противник получит мат, можно отдать легкую фигуру, если за этим последует взятие тяжелой фигуры противника. А иногда в шахматах отдают материал за позиционный выигрыш.

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

В этом параграфе мы обсудим два момента: как увеличить глубину дерева перебора и как без полного перебора обнаружить комбинационный удар. Начнем с метода, позволяющего более глубоко копнуть дерево перебора. Заметим, для начала, что более глубокое дерево без увеличения вычислительных ресурсов возможно только за счет отсечения некоторых его не очень значимых ветвей. Только это дает возможность другие, более важные ветки просмотреть глубже. А процедура отсечения ветки нуждается в критерии, позволяющем оценить ветвь игры до ее анализа.

Интуитивный критерий лежит на поверхности. Предположим, следующим ходом (напомню, мы в качестве базовой игры рассматриваем шахматы) игрок теряет ферзя. С точки зрения простой оценочной функции, это очень плохо, и такой ход разумно исключить из рассмотрения. Предположим далее, что следующим ходом противник теряет ферзя. Обычный здравый смысл говорит, что на этом варианте следует сосредоточиться. Но мы сделаем несколько парадоксальный вывод, что этого хода также следует избегать. Дело в том, что, выстраивая теорию, мы исходили из предположения, что силы игроков равны. Из чего следует, что ни один из игроков выиграть слишком много не может. И следовательно, как выигрыш ферзя, так и его проигрыш необходимо признать делом нереальным. Математически расчетная схема выглядит так: определим для оценочной функции пределы значений, для которых ни одному из игроков не гарантирована победа. Эти два уровня опять-таки можно определить экспертной оценкой. Назовем нижний уровень уровнем альфа, а верхний – уровнем бета. Далее все очень просто. Идя по дереву перебора, будем выполнять оценку промежуточных ситуаций (в чистом минимаксе интересны только конечные позиции), и если эта оценка ниже уровня альфа или выше уровня бета, то такую игровую ветку отсекаем. На вопрос, как все же решиться взять ферзя противника, ответим немного позже.