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

Лабораторная работа 3

Тема: Программирование игр

Цель работы: Применение базовых стратегий решения задач для программирования игр двух лиц с полной информацией.

Задание

1.  Рассмотреть класс игр двух лиц с полной информацией. На примере нескольких игр (шахматы, шашки, го.)  дать интерпретацию следующим понятиям:

-  полная информация о текущей игровой позиции;

-  правила игры и возможные ходы;

-  условия окончания игры и возможные окончания (выигрыш, ничья);

-  дерево игры;

-  позиция игры, полу ход, позиция игрока, позиция противника, терминальная позиция;

2.  Для простой игры “крестики-нолики” на поле 3 на 3 нарисовать дерево игры и оценить сложность этой игры.

3.  Рассмотреть минимаксный принцип и алфа-бета-принцип для программирования игры.

4.  Реализовать эти принципы в виде программ на Прологе в общем виде.

5.  Для игры “крестики-нолики” выбрать подходящую структуру данных для представления позиции игры и реализовать до конца программу.

6.  Обобщить полученные результаты для игры “крестики нолики” на “бесконечном поле” с использованием алфа-бета-принципа.

7.  Устроить между бригадами турнир и выявить победителя.

Методические указания

Предметом рассмотрения в данной лабораторной работе являются так называемые игры двух лиц с полной информацией. Примерами таких игр могут быть шахматы, шашки, го и пр. В игре принимают участия два игрока, производящие ходы по очереди. Игрокам полностью доступна текущая игровая ситуация. Отсюда название данного класса игр. Игра может быть представлена древовидным графом. Начальная ситуация игры – корень дерева, листья дерева – возможные терминальные ситуации игры. Прочие узлы дерева соответствуют текущим позициям. Выходящие из узла ветви дерева – возможные ходы противника. Путь на графе от корневой вершины к некоторой терминальной вершине определяет конкретную партию в данной игре. Сложность игры характеризуется количеством терминальных вершин. Если дерево игры поддается полному просмотру, то такая игра не представляет интереса. Шахматы интересны в силу своей сложности.

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

Поскольку для реальных игр полный просмотр дерева игры невозможен, то был предложен принцип неполного просмотра и оценки перспективности хода, известный как минимаксный принцип. Просмотр дерево ведется только на фиксированную глубину, например на пять ходов.  Для всех вершин на этой глубине вычисляется некоторая количественная оценка. Основываясь на этих оценках, вычисляются оценки на более высоком уровне (обратный ход) и т. д. Из данной позиции выбирается ход, соответствующий максимальной оценке. Этот принцип называется минимаксным, в силу того, что для одного игрока, назовем его MIN, следует выбирать ходы с минимальными оценками, а для другого, назовем его MAX - с максимальными. На рис. 1 дана иллюстрация вычисления оценок при просмотре дерева на два полухода.

                                                             4  b

ход MIN

                                                 4    d             6   e               

                                                                                   ход MAX

                                       1          4                5          6

Рис.1

Дальнейшим развитием этого принципа является так называемый алфа-бета-принцип. Суть его сводится к следующему. На рис.1 можно заметить, что для вычисления оценки в вершине b не обязательно знать  точное значение оценки в вершине e. Достаточно знать лишь его нижнюю оценку. С другой стороны, для вычисления нижней оценки можно использовать значение 5 вместо 6. Это не изменит результата вычисления  оценки в вершине b, но не потребует вычисления оценки в закрашенной серым цветом вершине, что существенно сокращает варианты перебора вершин.

Получить достаточно полное представление по данной теме можно в [3, гл.6], [4, гл.15].        

Вопросы для самопроверки

1.  Можно ли игру в карты (покер, преферанс, бридж и пр.) рассматривать как игру с полной информацией?

2.  Как И-ИЛИ дерево можно использовать для представления дерева игры?

3.  Сформулируйте принцип минимакса.

4.  В чем состоит суть алфа-бета алгоритма?

5.  Отчего зависит эффективность алфа-бета алгоритма?

6.  Какие пути совершенствования своей программы Вы могли бы указать?