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

1.  Цель работы:

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

2.  Анализ задачи

Для реализации игрового алгоритма для крестиков-ноликов на бесконечном поле на языке Пролог можно использовать следующие предложения:

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

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

·  Наиболее сложная и интересная задача – выбор функции оценивания позиции. Можно использовать разные принципы оценивания игровой позиции и получать разные функции оценивания. В приведенном алгоритме использовалась следующая функция оценивания: 2*X²+3*Y², где X – это самая длинная линяя ноликов (то есть игрока-компьютера) в данной позиции, а  Y – это самая длинная линяя крестиков, которая прерывается после сделанного ноликом хода.

3.  Текст программы

domains

trinity=t(integer,integer,char)

pair = p(integer,integer)

xos = trinity*

pol = pair*

database

xs(pair)

os(pair)

%longest(char,trinity)

predicates

play(pol,pol,integer,integer,integer,integer,pair)

getLegalMoves(pol,pair,pol)

occupied(pair)

occ(pair,char)

valid(integer,integer)

addRight(pair,pol,pol)

addLeft(pair,pol,pol)

addUp(pair,pol,pol)

addDown(pair,pol,pol)

addUpRight(pair,pol,pol)

addUpLeft(pair,pol,pol)

addDownRight(pair,pol,pol)

addDownLeft(pair,pol,pol)

bounds(char)

moved(char)

coout(integer,integer)

insert(pair,pol,pol)

delete(pair,pol,pol)

belong(pair,pol)

razn(pair,pair)

add(pair,char)

erase(pair,char)

gl(pair,char,integer,integer)

horiz(integer,pair,char)

horizr(integer,pair,char)

horizl(integer,pair,char)

vert(integer,pair,char)

vertu(integer,pair,char)

vertd(integer,pair,char)

diag1(integer,pair,char)

diag1r(integer,pair,char)

diag1l(integer,pair,char)

diag2(integer,pair,char)

diag2r(integer,pair,char)

diag2l(integer,pair,char)

maxi(integer,integer,integer)

newABs(integer,integer,integer,integer,integer,char)

BestMove(integer,pol,integer,integer,pair,integer,integer,integer,char)

vspom(integer,pol,integer,integer,pair,pair,integer,integer,integer,integer,char)

Oze(integer,pair,pol,integer,integer,integer,integer,integer,char)

value(pair,integer,integer,integer,char)

check(integer)

dbgout(pair,integer,integer)

%========================================================================

repeat

run(Pol,integer,integer)

max(integer,pair,integer,pair,integer,pair)

min(integer,pair,integer,pair,integer,pair)

%=========================================================================

clauses

% Dvizhenie po polyu

bounds(Z):- Z='\72', cursor(Y,X),  Y>0, A=Y-1, coout(X,A).

bounds(Z):- Z='\75', cursor(Y,X),  X>0, A=X-1, coout(A,Y).

bounds(Z):- Z='\80', cursor(Y,X), Y<18, A=Y+1, coout(X,A).

bounds(Z):- Z='\77', cursor(Y,X), X<79, A=X+1, coout(A,Y).

bounds(Z):- Z='\13', cursor(Y,X), valid(X,Y), write('X'), cursor(Y,X).

bounds(Z):- Z='\27',exit(0).

% cycle

repeat.

repeat:-repeat.

% play

moved('\13').

%==========================================================================

occupied(P):-xs(P).

occupied(P):-os(P).

occ(P,'X'):-xs(P).

occ(P,'O'):-os(P).

valid(X,Y):-not(occupied(p(X,Y))).

getLegalMoves(Old,p(P,Q),Legals):delete(p(P,Q),Old,L0),!,

addUpRight(p(P,Q),L0,L1),

addUpLeft(p(P,Q),L1,L2),

addDownRight(p(P,Q),L2,L3),

addDownLeft(p(P,Q),L3,L4),

addRight(p(P,Q),L4,L5),

addLeft(p(P,Q),L5,L6),

addUp(p(P,Q),L6,L7),

addDown(p(P,Q),L7,Legals),

!.

% Adding legal fields

addRight(p(X,Y),L,Legals):- X1=X+1, X1<=79,

not(occupied(p(X1,Y))),

insert(p(X1,Y),L,Legals).

addRight(p(X,Y),L,L).

addLeft(p(X,Y),L,Legals):- X1=X-1, X1>=0,

not(occupied(p(X1,Y))),

insert(p(X1,Y),L,Legals).

addLeft(p(X,Y),L,L).

addUp(p(X,Y),L,Legals):- Y1=Y-1, Y1>=0,

not(occupied(p(X,Y1))),

insert(p(X,Y1),L,Legals).

addUp(p(X,Y),L,L).

addDown(p(X,Y),L,Legals):- Y1=Y+1, Y1<=18,

not(occupied(p(X,Y1))),

insert(p(X,Y1),L,Legals).

addDown(p(X,Y),L,L).

addUpRight(p(X,Y),L,Legals):- Y1=Y-1, X1=X+1, Y1>=0, X1<=79,

not(occupied(p(X1,Y1))),

insert(p(X1,Y1),L,Legals).

addUpRight(p(X,Y),L,L).

addUpLeft(p(X,Y),L,Legals):- Y1=Y-1, X1=X-1, Y1>=0, X1>=0,

not(occupied(p(X1,Y1))),

insert(p(X1,Y1),L,Legals).

addUpLeft(p(X,Y),L,L).

addDownLeft(p(X,Y),L,Legals):- Y1=Y+1, X1=X-1, Y1<=18, X1>=0,

not(occupied(p(X1,Y1))),

insert(p(X1,Y1),L,Legals).

addDownLeft(p(X,Y),L,L).

addDownRight(p(X,Y),L,Legals):- Y1=Y+1, X1=X+1, Y1<=18, X1<=79,

not(occupied(p(X1,Y1))),

insert(p(X1,Y1),L,Legals).

addDownRight(p(X,Y),L,L).

razn(p(X,Y),p(U,V)):-X<>U.

razn(p(X,Y),p(U,V)):-Y<>V.

belong(X,[X]).

belong(X,[X|List]):-!.

belong(X,[Y|List]):-belong(X,List).

insert(X,List,List):-belong(X,List),!.

insert(X,List,[X|List]).

delete(_,[],[]).

delete(p(X,Y),[p(X,Y)|L],L).

delete(P,[Q|List],[Q|List1]):-razn(P,Q),delete(P,List,List1).

gl(p(A,B),C,Mold,Mnew):-horiz(N1,p(A,B),C),

vert(N2,p(A,B),C),

diag1(N3,p(A,B),C),                           

diag2(N4,p(A,B),C),

maxi(N1,N2,N6),

maxi(N3,N4,N7),

maxi(N6,N7,N8),

maxi(N8,Mold,Mnew),

%                                           readchar(T),