Prolog

деревьях.

Ниже приводится простая программа, которая определяет, является ли некоторая позиция игрока выигранной.

        выигр( Поз) :-

                терм_выигр( Поз).

                                          % Терминальная выигранная позиция

        выигр( Поз) :-

                not терм_проигр( Поз),

                ход( Поз, Поз1),                         % Разрешенный ход в Поз1

                not ( ход( Поз1, Поз2),

                         not выигр( Поз2) ).

                  % Ни один из ходов противника не ведет к не-выигрышу

Здесь правила игры встроены в предикат ход( Поз, Поз1), который порождает все разрешенные ходы, а также в предикаты терм_выигр( Поз) и терм_проигр( Поз), которые распознают терминальные позиции, являющиеся, согласно правилам игры, выигранными или проигранными. В последнем из правил программы, содержащем двойное отрицание (not), говорится: не существует хода противника, ведущего к не выигранной позиции. Другими словами: все ходы противника приводят к позициям, выигранным с точки зрения игрока.

Рис. 15. 1.  Сложность игровых деревьев в шахматах. Оценки основаны

на том, что в каждой шахматной позиции существуют приблизительно

30 разрешенных ходов я что терминальные позиции расположены на

глубине 40 ходов. Один ход равен двум полуходам (по одному

полуходу с каждой стороны).

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

Программа, которую мы составили, демонстрирует основные принципы программирования игр. Но практически приемлемая реализация таких сложных игр, как шахматы или го, потребовала бы привлечения значительно более мощных методов. Огромная комбинаторная сложность этих игр делает наш наивный переборный алгоритм, просматривающий дерево вплоть до терминальных игровых позиций, абсолютно непригодным. Этот вывод иллюстрирует (на примере шахмат) рис. 15.1: пространство поиска имеет астрономические размеры - около 10¹²⁰ позиций. Можно возразить, что в дереве на рис. 15.1 встречаются одинаковые позиции. Однако было показано, что число различных позиций дерева поиска находится далеко за пределами возможностей вычислительных машин обозримого будущего.

Проект

Напишите программу для какой-нибудь простой игры (такой, как ним), использующую упрощенный алгоритм войска в И / ИЛИ-дереве.

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

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

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

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