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

Министерство образования Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра программных систем и баз данных

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

по дисциплине «Искусственный интеллект»

Факультет:          ПМИ

Группа:                ПМ-13

Студент:              Глухова М.А.

Преподаватель:  Пономаренко В.М.

Новосибирск

2005

Цель работы:

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

Задание

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

Рассмотрим начальную позицию. Тут у первого игрока (пусть это будут крестики) имеются 9 ходов (симметрию игнорируем). На каждый из них у соперника имеется 8 ответов, в свою очередь на каждый из них - по 7 ответов у крестиков и т.д. Максимальная длина игры - 9 полуходов (т.е. ходов одного из соперников), но она может кончиться и раньше, если игрок выстроит 3 крестика (нолика) по линии.

Дерево игры:  

9!  позиций-приемников

72 позиций-приемников

Анализ

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

В качестве оценочной функции некоторой позиции будем использовать функцию , где  и  - наибольшие длины последовательностей крестиков и ноликов, соответственно.

Позиция, когда игрок следующим ходом может завершить свою последовательность «5 в ряд», а значит программа проиграет, оценивается отдельно, и имеет наибольшую оценку (наивысший приоритет).

Позиция, когда программа следующим ходом может завершить свою последовательность «5 в ряд», а значит программа выиграет, оценивается отдельно, и имеет вторую по величине оценку.
Текст программы

domains

p=p(integer,integer)

list=p*

%----------------------------------------------------------------------- 

predicates

game(list,list)         %главная управляющая программа

member(p,list,list)            %содержится в списке

max(integer,integer,integer)   %функция нахождения максимума

append(list,list,list)  %добавляет элемент в конец списка

h(p,list,integer)       %горизонтальные случаи

hr(p,list,integer)             %горизонтальный правый случай

hl(p,list,integer)             %горизонтальный левый случай

v(p,list,integer)       %вертикальные случаи

vu(p,list,integer)             %вертикальный «вверх» случай

vd(p,list,integer)             %вертикальный «вниз» случай

dr(p,list,integer)             %диагональный правый случай

drf(p,list,integer)           

drb(p,list,integer)

dl(p,list,integer)             %диагональный левый случай

dlf(p,list,integer)

dlb(p,list,integer)

longest(p,list,integer) %длина самого длинного списка

ocenka(p,list,list,integer)

draw(list,char)         %рисует х или о из списка

readpos(list,list,integer,integer,p)%чтение позиции

move(char,integer,integer,list,list,p)      %передвижения курсора

win(p,list,symbol)     

find(list,list,list)           %нахождение всех корректных позиций для «нолика»

best(p,list,list,list,integer) %нахождение лучшей позиции

run

%----------------------------------------------------------------------- 

clauses

run:-      makewindow(1,141,-8,"Игра: крестики-нолики ",0,0,25,80),