Материал: Волченков Логическое программирование язык пролог 2015

шинство же известных нетривиальных игр этого типа (шашки, шахматы, рэндзю и т.п.) не допускают полного перебора за реальное (неастрономическое) время, разве что, когда речь идёт о решении шахматных задач типа «Белые начинают и дают мат в 3 хода».

В таких «реальных» играх при поиске лучшего хода из некоторой позиции приходится просчитывать игру лишь на некоторую глубину, оценивать возникающие при этом позиции и выбирать ход, который наиболее выгоден игроку, делающему этот ход, с точки зрения указанного оценивания.

Вся интеллектуальность здесь как раз и проявляется в выборе удачной оценочной функции. Аргументом её служит описание позиции игры, а значением – число, которое чем больше, тем выгоднее позиция для игрока по имени МАКСИМУМ, и которое чем меньше, тем выгоднее позиция для игрока по имени МИНИМУМ. Функцию эту называют эвристической, а поиск решающего подграфа на игровом дереве – эвристическим поиском. (Отметим, что задачу эвристического поиска традиционно относят к задачам искусственного интеллекта.)

Пример 9.3.

Всем с детства хорошо известна игра «крестики-нолики», в которую играют на поле 3 х 3. Неплохой оценочной функцией для

оценки произвольной позиции этой игры может быть такая: z = y – x,

где y – это число строк, столбцов и диагоналей, на которых нет «нолика», x – число строк, столбцов и диагоналей, на которых нет «крестика».

131

На рис. 9.4 показаны 5 позиций, в которые может перейти игрок МИНИМУМ («нолик») после своего ответа на ход «крестика» в угловую клетку.

Рис. 9.4. Примеры позиций игры «крестики-нолики» и вычисления их оценок

Самой лучшей в смысле значения эвристической функции (-1) для игрока МИНИМУМ является последняя в этом ряду позиция.

И действительно, всем хорошо известно, что только эта позиция из пяти представленных на рис. 9.4 не приводит «нолика» к проигрышу.

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

Простейшим является так называемый минимаксный алгоритм. Следующий пример демонстрирует его суть.

Пример 9.4.

На рис. 9.5,а показано дерево абстрактной игры, когда из исходной позиции M1 ход делает игрок МИНИМУМ.

Возле каждой «висячей» вершины дерева игры, имеющего глубину 3, представлено численное значение эвристической оценки этой вершины. С помощью минимаксного алгоритма все вершины, не являющиеся «висячими», получают так называемые возвращённые оценки путём движения по дереву снизу-вверх. Если родительская вершина является позицией игрока МИНИМУМ, то значение её возвращённой оценки равно минимальному значению оценок её дочерних вершин. Если родительская вершина является позицией игрока МАКСИМУМ, то значение её возвращённой оценки равно максимальному значению оценок её дочерних вершин. На рис. 9.5,б показаны значения возвращённых оценок всех родительских вершин и выделен решающий путь, состоящий из наилучших ходов как игрока МИНИМУМ, так и игрока МАКСИМУМ.

132

б)

P7

1

Рис. 9.5. Демонстрация работы минимаксного алгоритма на абстрактном примере

Следующая программа на Прологе (код 9.7) демонстрирует процедуру поиска последовательности наилучших ходов по методу «минимакса» для уже имеющегося дерева игры.

133

Код 9.7

%Процедура поиска оптимальной стратегии игры

%по методу минимакса. Автор Н.Волченков. 2003 г.

%Сначала необходимо загрузить данные из двух файлов:

minmax(A, N, P) :- eval(A, N), path(A, N, P), !.

%Сначала, двигаясь от листьев к корню,

%программа оценивает все нелистовые вершины

%дерева (eval/2), затем строится оптимальный путь

%из корня к листу дерева – по вершинам, имеющим

%одинаковое значение оценки (path/3).

eval(A, N) :- m(A, N, L), !, eval(min, A, N, L). eval(A, N) :- p(A, N, L), !, eval(max, A, N, L).

eval(_, _, N, []) :- !.

eval(min, A, N, [B|L]) :- retract(m(A, N, [B|L])), eval(B, M),

eval1(min, N, M, L), assert(m(A, N, [B|L])).

eval(max, A, N, [B|L]) :- retract(p(A, N, [B|L])), eval(B, M),

eval1(max, N, M, L), assert(p(A, N, [B|L])).

eval1(_, N, N, []) :- !.

eval1(S, N, K, [A|L]) :- eval(A, K1), eval2(S, N, K, K1, L).

eval2(min, N, K, K1, L) :- K1 < K, !, eval1(min, N, K1, L). eval2(max, N, K, K1, L) :- K1 > K, !, eval1(max, N, K1, L). eval2(S, N, K, K1, L) :- !, eval1(S, N, K, L).

134

path(A, N, [A]) :- (m(A, N, []) ; p(A, N, [])), !. path(A, N, [A|P]) :- (m(A, N, L) ; p(A, N, L)), !,

path(B, N, L, P). path(A, N, L, P) :- member(A, L),

(m(A, N, _) ; p(A, N, _)), path(A, N, P).

% Извлечение данных из двух файлов: izvp :- see(ppp), read(T), cys(T), seen.

izvm :- see(mmm), read(T), cys(T), seen. cys(end_of_file) :- !.

cys(T) :- assert(T), read(TN), cys(TN).

Вреальных играх деревья, в отличие от дерева, представленного

впримере 9.4, бывают значительно более ветвистыми. И глубина их, как правило, бывает значительно большей. Поэтому становится актуальным повышение эффективности поиска решающего пути. С

этой целью часто используют улучшенный минимаксный метод – так называемую стратегию АЛЬФА/БЕТА-отсечений.

Стратегия АЛЬФА/БЕТА-отсечений предполагает совмещение процесса построения дерева игры с процессом вычисления верхних и нижних границ значений оценок его вершин: нижних границ для позиций игрока МАКСИМУМ и верхних границ для позиций игрока МИНИМУМ (так называемых АЛЬФА-ограничений и БЕТАограничений соответственно). Знание этих границ позволяет «отсекать» «бесперспективные» вершины при построении дерева игры.

Пример 9.5. Продемонстрируем процесс АЛЬФА/БЕТАотсечения на примере фрагментов дерева игры, показанного на рис. 9.5. Используем следующие обозначения: α(Pi) – АЛЬФАограничение вершины Pi; β(Mj) – БЕТА-ограничение вершины Mj.

На рис. 9.6,а показан фрагмент дерева игры после построения вершины P3. Её оценка -2. Следовательно, β(M3) = -2. При этом ранее установлено, что α(P1) = 5. Так как α(P1) > β(M3), то строить другие дочерние вершины для вершины M3 не имеет смысла. Вершина M3 бесперспективна и отсекается.

После построения вершины P6, имеющей оценку 4, выясняется, что α(P2) = -3, а β(M5) = 4. Так как α(P2) не превышает β(M5), то

генерация дочерних вершин (P7, P8) должна быть продолжена. На рис. 9.6,б представлен фрагмент дерева игры после этой генерации.

135