Решение игровых задач в терминах И/ИЛИ- графа

И/ИЛИ- граф- это направленный граф, вершины которого соответствуют задачам, а дуги – отношениям между задачами.

Между дугами также существуют свои отношения – это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них. В принципе из вершины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, будем предполагать, что каждая вершина имеет либо только И-преемников, либо только ИЛИ-преемников, так как в такую форму можно преобразовать любой И/ИЛИ- граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И- дуги называются И- вершиной; вершину, из которой выходят только ИЛИ- дуги,- ИЛИ- вершиной.

Решением задачи, представленной в виде И/ИЛИ- графа является решающее дерево, так как решение должно включать в себя все подзадачи И-вершин.

Решающее дерево T определяется следующим образом:

· исходная задача P – это корень дерева T;

· если P является ИЛИ-вершиной, то в T содержится только один из ее преемников (из И/ИЛИ-графа) вместе со своим собственным решающим деревом;

· если P – это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в T.

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И/ИЛИ- графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры:

· выигрыш;

· проигрыш.

Игры с тремя возможными исходами можно свести к играм с двумя исходами, считая, что есть: выигрыш и невыигрыш.

Так как участники игры ходят по очереди, то выделим два вида позиций, в зависимости от того, чей ход:

· позиция игрока;

· позиция противника.

Допустим, что начальная позиция P – это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника G₁, G₂, G₃ и так далее. Каждый вариант хода противника в позиции G_i приводит к одной из позиций игрока P_ij.

В И/ИЛИ- дереве, показанном на рисунке, вершины соответствуют позициям, а дуги – возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Игрок выигрывает в позиции P, если он выигрывает в G₁, G₂, G₃ и так далее. Следовательно, P – это ИЛИ-вершина. Позиции G_i – это позиции противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника, то есть игрок выигрывает в G_i, если он выигрывает во всех позициях P_ij. Таким образом, все позиции противника – это И-вершины. Целевые позиции – это позиции, выигранные согласно правилам игры. Для того, чтобы решить игровую задачу, мы должны построить решающее дерево, гарантирующее победу игрока независимо от ответов противника. Такое дерево задает полную стратегию достижения выигрыша: для каждого возможного продолжения, выбранного противником, в дереве стратегии есть ответный ход, приводящий к победе.

…. ….

Рассмотрим решение подобных задач на примере игры в «2 лунки».

Игрок или его противник может взять из одной любой лунки любое количество камешков. Проигрывает тот, кто берет последний камешек.

Дерево решений этой игры представлено на рисунке.

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