Лекция: Минимаксный алгоритм.
Пространство поиска астрономических размеров в дереве игры в шахматы включает приблизительно 10120 позиций. Иногда можно услышать такие возражения, что в различных местах дерева, показанного на рис. 10.23, встречаются одинаковые позиции. Тем не менее доказано, что количество различных позиций на шахматной доске намного превосходит возможности любых компьютеров, которые могут быть созданы в обозримом будущем.
Начальная позиция
… ≈ 30 позиций
продолжения
30х30≈ 1000 позиций
≈ 100040 позиций
..............................................................
Рис. 10.23. Сложность деревьев игр в шахматах. Приведенные здесь оценки основаны на предположении, что из любой шахматной позиции может быть сделано приблизительно 30 допустимых ходов, а заключительные позиции возникают на глубине 40 ходов. Каждый ход состоит из 2 полуходов (по 1 полуходу от каждого участника) .
Поскольку длясоздания программ ведения таких интересных игр как шахматы невозможно применить исчерпывающий поиск в деревьях игры, разработаны другие методы, которые основаны на поиске только в некоторой части дерева игры. К ним относится стандартный метод, применяемый при ведении на компьютере игр (таких как шахматы), который основан на принципе минимакса.
Поиск в дереве игры осуществляется только до определенной глубины, как правило, на несколько ходов, а затем осуществляется оценка концевых узлов этого дерева поиска с помощью некоторой функции оценки. Идея состоит в том, что оценка этих заключительных позиций поиска происходит без выполнения поиска за их пределами, что позволяет сэкономить время. После этого оценки заключительных позиций распространяются вверх по дереву поиска в соответствии с принципом минимакса. Это позволяет определить оценки позиций для всех позиций в дереве поиска. Затем в игре фактически выполняется ход, который ведет от первоначальной, корневой позиции к ее наиболее перспективному преемнику (согласно этим оценкам).
Обратите внимание на то, что в приведенном выше описании проводится различие между понятиями "дерево игры" и "дерево поиска". Дерево поискаобычно представляет собой лишь (верхнюю) часть дерева игры, иными словами, часть, явно формируемую в процессе поиска. Поэтому заключительные позиции поиска не обязательно должны быть заключительными позициями игры.
При этом многое зависит от функции оценки. Такая функция в большинстве интересных игр должна представлять собой эвристическую функцию, позволяющую оценить шансы на выигрыш с точки зрения одного из игроков. Чем выше эта оценка, тем больше шансов на выигрыш имеет игрок, а чем меньше это значение, тем выше шансы на выигрыш у его противника. Поскольку один из игроков получает возможность достичь позиции с высокой оценкой, а другой вынужден довольствоваться низкой оценкой, эти два игрока соответственно именуются как МАХ и MIN. Каждый раз, когда ход должен сделать игрок МАХ, он выбирает ход, который в максимальной степени увеличивает оценку своей позиции. В противоположность этому игрок MIN должен выбрать ход, который сводит к минимуму оценку позиции своего противника. Если известны значения позиций низкого уровня в дереве поиска, то такой принцип (называемый минимаксом) позволяет определить значения всех других позиций в дереве поиска, как показано на рис. 10.24. На этом рисунке уровни позиций, в которых должен ходить игрок МАХ, чередуются с позициями, в которых право сделать ход передается игроку MIN. Значения позиций нижнего уровня определяются с помощью функции оценки. Стоимости внутренних узлов можно рассчитать, поднимаясь снизу вверх, от одного уровня к другому до тех пор, пока не будет достигнут корневой узел. На рис. 10.24. результирующая стоимость корневого узла равна 4, поэтому наилучшим ходом для игрока МАХ в позиции а является а -b. Наилучшим ответом для игрока MIN является b-d и т.д. Такая последовательность позиций в игре называется также основным вариантом. Основной вариант определяет для обоих участников игру, оптимальную в соответствии с принципом минимакса. Обратите внимание на то, что стоимость позиций вдоль основного варианта не изменяется. В соответствии с этим правильнымиявляются те ходы, которые позволяют сохранить стоимость игры.
аХод игрока МАХ
b cХод игрока MIN
d e f gХод игрока
МАХ
Статические оценки
Рис. 10.24. Статические значения (нижний уровень) и зафиксированные минимаксные значения в дереве поиска. Ходы, обозначенные жирными стрелками, составляют основной вариант, т.е. игру обеих сторон, оптимальную в соответствии с принципом минимакса.