Оценочная функция
Прежде всего, нам необходимо дать точные определения, что такое хорошая позиция игрока и что такое плохая позиция. Ясно, что выбор стратегии должен производиться таким образом, чтобы реализация этой стратегии приводила к хорошей позиции.
Любой игрок, владея даже только основами игры, принимает решение о своем ходе не случайным образом. Он знает некоторые правила позволяющие ему оценивать качество позиции. Например, русские шашки, если в результате хода отдав одну шашку можно взять две шашки противника, то это хорошо, а если будут потери и ничего взамен, то это плохо. Таким образом, количество шашек на доске это фактор качества позиции. Чем своих шашек больше, тем лучше, а чем больше шашек у противника, тем хуже.
Конечно, это не единственный фактор. Например, важное значение имеет количество дамок. Можно разработать и другие факторы качества игры. Чем игрок опытнее, тем большее количество факторов качества ему известно.
Из этого же примера видно, что факторы по своей значимости неодинаковы. Одна единственная дамка может полностью компенсировать недостаток в обычных шашках. Поэтому для каждого фактора необходимо ещё установить его важность в виде числа которое называют весом. Вес не единственная характеристика фактора качества. Существует ещё величина фактора. Например, пусть мы выделили в качестве фактора наличие дамки. Дамок может быть несколько а следовательно вес фактора необходимо умножить на их количество, чтобы оценить влияние данного фактора на игру.
Важное замечание. Необходимо очень хорошо понять, что не существует общего способа выявить все факторы, влияющие на игру и определить их веса. Это определяется только опытом игрока и его личными знаниями о данной игре.
Более того, любая система факторов будет только приблизительно правильной, так как она не учитывает взаимного влияния факторов и их зависимости от хода игры. Например, пешка в шахматах имеет различный вес в зависимости от того, стоит она на второй горизонтали (то есть на своём месте) или на предпоследней (то есть может следующим ходом превратиться в ферзя) и т.д.
Но все эти вопросы мы сейчас рассматривать не будем. Мы займемся ими позже.
Пусть у нас есть система факторов, определены их веса и количества, как вычислить качество позиции? Таким образом, мы приходим к понятию оценочной функции. Введём обозначения. Пусть ai - это фактор с номером i pi – вес данного фактора. Тогда величина P называется оценочной функцией, и она равна следующему выражению
P = p1a1 + p2a2 +…..+pnan
Чем значение этой функции больше, тем позиция соответствующая данной функции лучше. Все, что теперь должен сделать игрок, – это просчитать оценочную функцию для всех возможных ходов и выяснить, который из них даёт наилучший результат.
Дерево перебора.
Правда необходимо заметить, что перебор всех возможных вариантов только на один ход вперёд даёт не слишком много информации. Ход выгодный сейчас, может привести к невыгодной позиции в некотором будущем. Любой игрок знает, что считать варианты игры надо на несколько ходов вперёд, чем глубже, тем лучше, конечно с учетом личных способностей к таким расчётам. Для просчёта различных вариантов игры строится специальная структура называемая деревом вариантов или деревом перебора. Построим пример и рассмотрим, как связываются понятия дерева перебора и оценочная функция.
Пусть дана двоичная игра. Неважно в чём заключаются её правила, важно только то, что в каждой ситуации любой игрок, чья очередь хода имеет только два варианта ответа. Тогда, любую часть игры, начиная с некоторой позиции можно представить в виде дерева, вершины которого это игровые ситуации, а дуги соединяющие вершины это варианты хода. Вот как это выглядит:
|
Это дерево перебора вариантов на два хода вперёд, один свой и один ход противника. Числа, подписанные под кружками на самом нижнем уровне, – это значения оценочной функции в этих позициях. Заметим, что значения оценочной функции в промежуточной позиции нас не интересуют. Это от того, что цель анализа - поиск хорошей конечной позиции.
Первый игрок может принять решение выбрать ход А и он может принять решение выбрать ход В. Если он выберет ход А, то он может надеется получить в качестве выигрыша 15 очков. Если же он выберет ход В, то его надежда составит 18 очков. Это предварительное рассуждение говорит о том, что первый игрок, тот который ведёт анализ должен выбрать ход В. Однако необходимо посмотреть, насколько оправданы его надежды.
Метод минимакса
Проблема первого игрока в том, что он не один, ему противостоит второй игрок и не учитывать его возможные действия нельзя. Надо что-то предположить о действиях второго игрока и мы предположим, что он будет играть наиболее сильным образом. Другими словами, можно сказать, что второй игрок будет стремиться не дать первому игроку максимального выигрыша.
Вернемся к дереву нашей двоичной игры. Предположим, первый игрок выбрал вариант А. Теперь очередь выбора за вторым. Так как он не должен давать первому сильнейшей позиции, то его ход будет в позицию с оценочной функцией = 5. В случае же выбора первым игроком хода В, второй игрок должен выбрать ход ведущий в позицию с оценочной функцией 3.
Из этих рассуждений ясно, что на самом деле второй игрок может рассчитывать только на два варианта 3 или 5. Это худшие из возможных, и из них он может выбрать лучший. Поэтому метод такого выбора и называется минимаксом (из минимальных максимальные). Наилучший вариант 5, поэтому первый игрок должен выбрать ход А, что противоречит предыдущему простейшему рассуждению.
Заключение. Таким образом, построение алгоритма игры заключается в решении двух проблем: как построить оценочную функцию, правильно описывающую игру и как построить и просмотреть дерево вариантов.