Романтика искусственного интеллекта

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

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

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

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

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