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

Рис. 2.4. Пример минимакса

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

Принцип основан на предположении, что игроки имеют равную силу. Действительно, преуменьшать возможности оппонента нет смысла. Если окажется, что он играет сильнее, чем предполагалось, – это может иметь плохие последствия. Исходить из того соображения, что соперник играет лучше, – заведомо проигрышная психология. Оптимальная точка зрения заключается в том, что я играю так хорошо, как могу, и мой соперник играет не хуже. В терминах мини-макса это означает следующее. Если выбор хода за мной, то я выберу ход с наилучшей оценкой для себя и наихудшей для противника, он, в свою очередь, сделает то же самое.

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

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

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

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

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

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

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