Назад | Содержание| Вперёд 15. 2. Минимаксный принцип Для игр, пр...

Назад | Содержание| Вперёд

15. 2.    Минимаксный принцип

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

Обратите внимание на то, что мы здесь делаемопределенное различие между "деревом игры"и "деревом поиска". Дерево поиска - этотолько часть дерева игры (его верхняя часть), т. е.та его часть, которая была явным образомпорождена в процессе поиска. Таким образом,терминальные поисковые позиции совсем необязательно должны совпадать с терминальнымипозициями самой игры.

Очень многое зависит от оценочной функции,которая для большинства игр, представляющихинтерес, является приближенной эвристическойоценкой шансов на выигрыш одного из участниковигры. Чем выше оценка, тем больше у него шансоввыиграть и чем ниже оценка, тем больше шансов навыигрыш у его противника. Поскольку один изучастников игры всегда стремится к высокимоценкам, а другой - к низким, мы дадим им именаМАКС и МИН соответственно. МАКС всегда выбираетход с максимальной оценкой; в противоположностьему МИН всегда выбирает ход с минимальнойоценкой. Пользуясь этим принципом (минимакснымпринципом) и зная значения оценок для всех вершин"подножья" дерева поиска, можно определитьоценки всех остальных вершин дерева. На рис. 15.2показано, как это делается. На этом рисунке видно,что уровни позиций с ходом МАКС'а чередуются суровнями позиций с ходом МИН'а. Оценки вершиннижнего уровня определяются при помощиоценочной функции. Оценки всех внутренних вершинможно определить, двигаясь снизу вверх от уровняк уровню, пока мы не достигнем корневой вершины. Врезультате, как видно из рис. 15.2, оценка корняоказывается равной 4, и, соответственно, лучшимходом МАКС'а из позиции  а  -  a-b

. Лучший ответ МИН'а на этот ход  -

b-d

,и т.д. Эту последовательность ходов называюттакже

основным вариантом

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

Рис. 15. 2.  Статические(нижний уровень) и минимаксные рабочие