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

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

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

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

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

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

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

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

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