Формулировка игровых задач в терминах И/ИЛИ-графов
Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И/ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами - ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция P - это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника Q1, Q2, Q3, … (рис. 2.10).
Рис. 2.10. Формулировка игровой задачи для игры двух лиц
в форме И/ИЛИ-дерева; участники игры: "игрок" и "противник"
Далее, каждый вариант хода противника в позиции Q1 приводит к одной из позиций игрока R11, R12, … . В И/ИЛИ-дереве, показанном на рис. 2.10, вершины соответствуют позициям, а дуги - возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того чтобы выиграть в позиции P, нужно найти ход, переводящий позицию P в выигранную позицию Qi (при некотором i). Таким образом, игрок выигрывает в позиции P, если он выигрывает в Q1 или Q2, или Q3, или … . Следовательно, P - это ИЛИ-вершина. Для любого i, позиция Qi - это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Qi, если он выигрывает во всех позициях Ri1 и Ri2 и … . Таким образом, все позиции противника - это И-вершины. Целевые вершины - это терминальные (окончательные) позиции, выигранные согласно правилам игры, например, позиции, в которых король противника получает мат.
Позициям проигранным соответствуют задачи, не имеющие решения. Для того чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.
Ниже приводится простая программа, которая определяет, является ли некоторая позиция игрока выигранной.
'выигранная'(P):-
'терм_выигранная'(P). % терминальная выигранная позиция
'выигранная'(P):-
not 'терм_проигранная'(P), % не терминальная проигранная
% позиция
'ход'(P,P1), % разрешенный ход из позиции P в позицию P1
% ни один из ходов противника не ведет к не-выигрышу
not('ход'(P1,P2),
not 'выигранная'(P2)).
Здесь правила игры встроены в предикат 'ход'(P,P1), который порождает все разрешенные ходы, а также в предикаты 'терм_выигранная'(P) и 'терм_проигранная'(P), которые распознают терминальные позиции, являющиеся, согласно правилам игры, выигранными или проигранными. В последнем из правил программы, содержащем двойное отрицание, говорится: не существует хода противника, ведущего к не выигранной позиции. Другими словами, все ходы противника приводят к позициям, выигранным с точки зрения игрока.
Программа, которую мы составили, демонстрирует основные принципы программирования игр. Но практически приемлемая реализация таких сложных игр, как шахматы или го, потребовала бы привлечения значительно более мощных методов. Огромная комбинаторная сложность этих игр делает наш наивный переборный алгоритм, просматривающий дерево вплоть до терминальных игровых позиций, абсолютно непригодным. Для шахмат, например, пространство поиска имеет астрономические размеры - около 10120
позиций.