Программирование на языке Пролог для искусственного интеллекта

       

Формулировка игровых задач в терминах И / ИЛИграфов



13. 2. 3.    Формулировка игровых задач в терминах И / ИЛИ-графов

Такие игры, как шахматы или шашки, естественно рассматривать как задачи, представленные И / ИЛИ-графами. Игры такого рода называются играми двух лиц с полной информацией. Будем считать, что существует только два возможных исхода игры: ВЫИГРЫШ и ПРОИГРЫШ. (Об играх с тремя возможными исходами -ВЫИГРЫШ, ПРОИГРЫШ и НИЧЬЯ, можно также говорить, что они имеют только два исхода: ВЫИГРЫШ и НЕВЫИГРЫШ). Так как участники игры ходят по очереди, мы имеем два вида позиций, в зависимости от того, чей ход. Давайте условимся называть участников игры "игрок" и "противник", тогда мы будем иметь следующие два вида позиций: позиция с ходом игрока ("позиция игрока") и позиция с ходом противника ("позиция противника"). Допустим также, что начальная позиция  Р  -   это позиция игрока. Каждый вариант хода игрока в этой позиции приводит к одной из позиций противника  Q1,  Q2,  Q3,   ...  (см. Рисунок 13.7). Далее каждый вариант хода противника в позиции  Q1  приводит к одной из позиций игрока  R11,  R12,   ... .  В  И / ИЛИ-дереве, показанном на Рисунок 13.7, вершины соответствуют позициям, а дуги - возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции   Р,  нужно найти ход, переводящий  Р   в выигранную позицию  Qi.  (при некотором  i).  Таким образом, игрок выигрывает в позиции  Р,  если он выигрывает в  Q1,  или  Q2,   или  Q3,  или ... . Следовательно,  Р  - это ИЛИ-вершина. Для любого  i  позиция  Qi  -   это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого вариан-



Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий