!.
add(P,'X'):-assertz(xs(P)).
add(P,'O'):-assertz(os(P)).
erase(P,'X'):-retract(xs(P)).
erase(P,'O'):-retract(os(P)).
horiz(N,Hod,C):-horizr(N1,Hod,C),horizl(N2,Hod,C),N=N1+N2-1.
vert(N,Hod,C):-vertu(N1,Hod,C),vertd(N2,Hod,C),N=N1+N2-1.
diag1(N,Hod,C):-diag1l(N1,Hod,C),diag1r(N2,Hod,C),N=N1+N2-1.
diag2(N,Hod,C):-diag2l(N1,Hod,C),diag2r(N2,Hod,C),N=N1+N2-1.
horizr(N,p(A,B),C):-occ(p(A,B),C),A1=A+1,horizr(N1,p(A1,B),C),N=N1+1,!.
horizr(0,p(A,B),C).
horizl(N,p(A,B),C):-occ(p(A,B),C),A1=A-1,horizl(N1,p(A1,B),C),N=N1+1,!.
horizl(0,p(A,B),C).
vertd(N,p(A,B),C):-occ(p(A,B),C),B1=B+1, vertd(N1,p(A,B1),C),N=N1+1,!.
vertd(0,p(A,B),C).
vertu(N,p(A,B),C):-occ(p(A,B),C),B1=B-1, vertu(N1,p(A,B1),C),N=N1+1,!.
vertu(0,p(A,B),C).
diag1l(N,p(A,B),C):-occ(p(A,B),C),A1=A-1,B1=B-1, diag1l(N1,p(A1,B1),C),N=N1+1,!.
diag1l(0,p(A,B),C).
diag1r(N,p(A,B),C):-occ(p(A,B),C),A1=A+1,B1=B+1, diag1r(N1,p(A1,B1),C),N=N1+1,!.
diag1r(0,p(A,B),C).
diag2l(N,p(A,B),C):-occ(p(A,B),C),A1=A-1,B1=B+1, diag2l(N1,p(A1,B1),C),N=N1+1,!.
diag2l(0,p(A,B),C).
diag2r(N,p(A,B),C):-occ(p(A,B),C),A1=A+1,B1=B-1, diag2r(N1,p(A1,B1),C),N=N1+1,!.
diag2r(0,p(A,B),C).
maxi(A,B,A):-A>B.
maxi(A,B,B).
%===========================================================================
play(OldLegals,NewLegals,OldLx,OldLo,NewLx,NewLo,p(P,Q)):-
cursor(Y,X),
not(occupied(p(X,Y))),
assertz(xs(p(X,Y))),
%readchar(T0),
getLegalMoves(OldLegals,p(X,Y),CurLegal),
%readchar(T1),
gl(p(X,Y),'X',OldLx,NewLx),
%readchar(T11),
check(NewLx),
%readchar(T2),
BestMove(0,CurLegal,NewLx,OldLo,p(P,Q),_,-500,500,'O'),
%readchar(T3),
assertz(os(p(P,Q))),
getLegalMoves(CurLegal,p(P,Q),NewLegals),
gl(p(P,Q),'O',OldLo,NewLo),
!.
%===============================================================================
dbgout(p(X,Y),I,2):gotowindow(2),
cursor(0,0),
write(" ( ",X," , ",Y," ) "," : ",I," "),
readchar(T),
gotowindow(1).
dbgout(_,_,N).
min(V1,H1,V2,H2,V1,H1):-V1<V2.
min(V1,H1,V2,H2,V2,H2).
max(V1,H1,V2,H2,V1,H1):-V1>V2.
max(V1,H1,V2,H2,V2,H2).
newABs(A,B,V,V,B,'O'):-V>A.
newABs(A,B,V,A,B,'O').
newABs(A,B,V,A,V,'X'):-V<B.
newABs(A,B,V,A,B,'X').
vspom(_,_,_,_,H1,H1,V1,V1,_,Beta,'O'):V1>=Beta,
!.
vspom(N,[H1|List],Lx,Lo,H1,Hod,V1,Val,Alfa,Beta,'O'):V1<Beta,
newABs(Alfa,Beta,V1,NewAlfa,NewBeta,'O'),
BestMove(N,List,Lx,Lo,H2,V2,NewAlfa,NewBeta,'O'),!,
max(V1,H1,V2,H2,Val,Hod).
vspom(_,_,_,_,H1,H1,V1,V1,Alfa,_,'X'):V1<=Alfa,
!.
vspom(N,[H1|List],Lx,Lo,H1,Hod,V1,Val,Alfa,Beta,'X'):V1>Alfa,
newABs(Alfa,Beta,V1,NewAlfa,NewBeta,'X'),
BestMove(N,List,Lx,Lo,H2,V2,NewAlfa,NewBeta,'X'),!,
min(V1,H1,V2,H2,Val,Hod).
BestMove(N,[Hod],Lx,Lo,Hod,Val,Alfa,Beta,C):Oze(N,Hod,[Hod],Lx,Lo,Val,Alfa,Beta,C),
dbgout(Hod,Val,N),
!.
BestMove(N,[H1|List],Lx,Lo,Hod,Val,Alfa,Beta,'O'):%readchar(T),
Oze(N,H1,[H1|List],Lx,Lo,V1,Alfa,Beta,'O'),
dbgout(H1,V1,N),
vspom(N,[H1|List],Lx,Lo,H1,Hod,V1,Val,Alfa,Beta,'O'),
!.
BestMove(N,[H1|List],Lx,Lo,Hod,Val,Alfa,Beta,'X'):%readchar(T),
Oze(N,H1,[H1|List],Lx,Lo,V1,Alfa,Beta,'X'),
vspom(N,[H1|List],Lx,Lo,H1,Hod,V1,Val,Alfa,Beta,'X'),
!.
Oze(0,p(A,B),_,Lx,Lo,Val,_,_,C):value(p(A,B),Lx,Lo,Val,C),
%readchar(T),
!.
Oze(N,p(A,B),List,Lx,Lo,Val,Alfa,Beta,'X'):-
N>0, N1=N-1,
assertz(xs(p(A,B))),
getLegalMoves(List,p(A,B),Spisok),
gl(p(A,B),'X',Lx,NewLx),
BestMove(N1,Spisok,NewLx,Lo,H,Val,Alfa,Beta,'O'),
retract(xs(p(A,B))),
!.
Oze(N,p(A,B),List,Lx,Lo,Val,Alfa,Beta,'O'):-
N>0, N1=N-1,
assertz(os(p(A,B))),
getLegalMoves(List,p(A,B),Spisok),
gl(p(A,B),'O',Lo,NewLo),
BestMove(N1,Spisok,Lx,NewLo,H,Val,Alfa,Beta,'X'),
retract(os(p(A,B))),
!.
value(p(A,B),Lx,Lo,Val,'O'):add(p(A,B),'X'),
gl(p(A,B),'X',Lx,V1),
erase(p(A,B),'X'),
add(p(A,B),'O'),
gl(p(A,B),'O',Lo,V2),
erase(p(A,B),'O'),
Val=V2*V2+2*V1*V1.
value(p(A,B),Lx,Lo,Val,'X'):add(p(A,B),'X'),
gl(p(A,B),'X',Lx,V1),
erase(p(A,B),'X'),
add(p(A,B),'O'),
gl(p(A,B),'O',Lo,V2),
erase(p(A,B),'O'),
Val=-2*V2*V2+V1*V1.
%================================================================================
check(M):-M<5.
check(_):-gotowindow(2),
cursor(0,34),
write(" "),
cursor(0,34),
write("Game Over!"),
readchar(C),
exit(0).
run(Olds,OLx,OLo) :repeat,
readchar(Z),
bounds(Z),
moved(Z),
play(Olds,News,OLx,OLo,NLx,NLo,p(X,Y)),!,
cursor(Y,X),
write('O'),
check(NLo),!,
run(News,NLx,NLo).
coout(X,Y):gotowindow(2),
cursor(0,30),
write(" "),
write("(",X,",",Y,")"),
gotowindow(1),
cursor(Y,X).
goal
retractall(_),
makewindow(1,31,31,"XOS!",0,0,21,80),
makewindow(2,31,31,"info",21,0,3,80),
coout(0,0),
run([],0,0).
%============================================================================
4. Тестирование
· Реализованный алгоритм при установке глубины анализа равной 0 может играть в крестики-нолики на не очень высоком уровне. Алгоритм отслеживает попытки противника построить 5 крестиков в ряд и пресекает их. Однако «склонность к обороне» алгоритма иногда мешает ему находить правильный ход из выигрышных позиций. Кроме того, алгоритм пресекает только явные попытки нападений и обмануть его не составляет особой сложности.
· Если параметр глубин анализа увеличить, то программа играет несколько лучше, однако провести тестирование до конца не удалось, вследствие постоянно возникающих ошибок нехватки памяти (“term too big” или “heap overflow or endless loop”).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.