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

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

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

2. Задание

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

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

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

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

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

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

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

constants

xowindow = 2

swindow  = 1

domains

row,col= integer

player = user; computer

pos    = ps( row, col)

moves  = pos*

database

x( pos )

o( pos )

database - cells

cell( pos )

predicates

play( player )

init( player )

move( player, pos )

member( pos, moves )

opponent( player, player )

yes( char, player )

valid( pos )

showpos( player, pos )

draw( pos, char )

alpha_beta( pos, integer )

weight( pos, integer )

make_moves()

max( integer, integer, integer )

add_beyong_X( moves )

add_beyong_O( moves )

addcell( pos )

beyong( pos )

best_move( pos, integer, pos, integer, pos, integer )

snX( pos, integer )

neX( pos, integer )

weX( pos, integer )

seX( pos, integer )

nsX( pos, integer )

nwX( pos, integer )

ewX( pos, integer )

swX( pos, integer )

snO( pos, integer )

neO( pos, integer )

weO( pos, integer )

seO( pos, integer )

nsO( pos, integer )

nwO( pos, integer )

ewO( pos, integer )

swO( pos, integer )

fiveX

fiveO

bounds(char)

repeat

getMove(integer,integer)    

goal

retractall(_),

retractall(_, Cells ),

init( Player ),

play( Player ).

clauses

opponent( user, computer ).

opponent( computer, user ):-!.

init( X ) :makewindow( xowindow, $31, $3F, "Окно игры", 0, 0, 18, 78 ),

makewindow( swindow,  $1F, $1F, "Окно диалога", 18, 0, 6, 78 ),

write( "" ), nl,

write( "Будете ходить первым(y/n):" ),

readchar( Y ), nl,

yes( Y, X ).

yes( 'y', user ) :- !,

write( "Ваш ход..." ), nl.

yes( 'Y', user ) :- !,

write( "Ваш ход..." ), nl.

yes( _, computer ) :write(""), nl.

play( _ ) :-   % Имеется 5 крестиков в ряд

fiveX,

write( "Вы выиграли...!" ), nl.

play( _ ) :- % Имеется 5 ноликов в ряд

fiveO,

write( " Я выиграл!!!" ), nl.

play( Player ) :move( Player, Pos ),

showpos( Player, Pos ),

opponent( Player, Player1 ),

play( Player1).

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

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

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

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

bounds(Z):- Z='\13'.

repeat.

repeat:-repeat.

getMove(X,Y):gotoWindow(2),

repeat,

readchar(Z),

bounds(Z),

cursor(X1,Y1),

Y=Y1-39,

X=8-X1.

move( user, ps( X, Y ) ) :getMove(Y,X),

valid( ps( X, Y ) ),

assertz( x( ps( X, Y ) ) ).

move( computer, ps( 0, 0 ) ) :not ( x( _ ) ),

assertz( o( ps( 0, 0 ) ) ).

move( computer, Best ) :write( ""),

make_moves(),

alpha_beta( Best, _ ),

assertz( o( Best ) ).

valid( Pos ) :x( Pos ), !, fail.

valid( Pos ) :o( Pos ), !, fail.

valid( Pos ) :cell( Pos ), !, fail.

valid( _ ).

make_moves() :retractall( cell( _ ), Cells ),

add_beyong_X( [] ),

add_beyong_O( [] ).

addcell( Pos ) :valid( Pos ),

assertz( cell( Pos ) ).

addcell( _ ).

beyong( ps( X, Y ) ) :Xm1 = X-1,

Xp1 = X+1,

Ym1 = Y-1,

Yp1 = Y+1,

addcell( ps( Xm1, Ym1 ) ),

addcell( ps( Xm1, Y   ) ),

addcell( ps( Xm1, Yp1 ) ),

addcell( ps( X,   Ym1 ) ),

addcell( ps( X,   Yp1 ) ),

addcell( ps( Xp1, Ym1 ) ),

addcell( ps( Xp1, Y   ) ),

addcell( ps( Xp1, Yp1 ) ).

add_beyong_X( Used ) :x( Pos ),

not( member( Pos, Used ) ),

beyong( Pos ),

add_beyong_X( [Pos|Used] ).

add_beyong_X( _ ).

add_beyong_O( Used ) :o( Pos ),

not( member( Pos, Used ) ),

beyong( Pos ),