:- dynamic board/1. :- retractall(board(_)). :- assert(board([_Z1,_Z2,_Z3,_Z4,_Z5,_Z6,_Z7,_Z8,_Z9])). %%%%% %% Generate possible marks on a free spot on the board. %% Use mark(+,+,-X,-Y) to query/generate possible moves (X,Y). %%%%% mark(Player, [X|_],1,1) :- var(X), X=Player. mark(Player, [_,X|_],2,1) :- var(X), X=Player. mark(Player, [_,_,X|_],3,1) :- var(X), X=Player. mark(Player, [_,_,_,X|_],1,2) :- var(X), X=Player. mark(Player, [_,_,_,_,X|_],2,2) :- var(X), X=Player. mark(Player, [_,_,_,_,_,X|_],3,2) :- var(X), X=Player. mark(Player, [_,_,_,_,_,_,X|_],1,3) :- var(X), X=Player. mark(Player, [_,_,_,_,_,_,_,X|_],2,3) :- var(X), X=Player. mark(Player, [_,_,_,_,_,_,_,_,X|_],3,3) :- var(X), X=Player. %%%%% %% Record a move: record(+,+,+). %%%%% record(Player,X,Y) :- retract(board(B)), mark(Player,B,X,Y), assert(board(B)). %%%%% %% Calculate the value of a position, o maximizes, x minimizes. %%%%% value(Board,100) :- win(Board,o), !. value(Board,-100) :- win(Board,x), !. value(Board,E) :- findall(o,open(Board,o),MAX), length(MAX,Emax), % # lines open to o findall(x,open(Board,x),MIN), length(MIN,Emin), % # lines open to x E is Emax - Emin. %%%%% %% A winning line is ALREADY bound to Player. %% win(+Board,+Player) is true or fail. %% e.g., win([P,P,P|_],P). is NOT correct, because could bind %%%%% win([Z1,Z2,Z3|_],P) :- Z1==P, Z2==P, Z3==P. win([_,_,_,Z1,Z2,Z3|_],P) :- Z1==P, Z2==P, Z3==P. win([_,_,_,_,_,_,Z1,Z2,Z3],P) :- Z1==P, Z2==P, Z3==P. win([Z1,_,_,Z2,_,_,Z3,_,_],P) :- Z1==P, Z2==P, Z3==P. win([_,Z1,_,_,Z2,_,_,Z3,_],P) :- Z1==P, Z2==P, Z3==P. win([_,_,Z1,_,_,Z2,_,_,Z3],P) :- Z1==P, Z2==P, Z3==P. win([Z1,_,_,_,Z2,_,_,_,Z3],P) :- Z1==P, Z2==P, Z3==P. win([_,_,Z1,_,Z2,_,Z3,_,_],P) :- Z1==P, Z2==P, Z3==P. %%%%% %% A line is open if each position is either free or equals the Player %%%%% open([Z1,Z2,Z3|_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([_,_,_,Z1,Z2,Z3|_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([_,_,_,_,_,_,Z1,Z2,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([Z1,_,_,Z2,_,_,Z3,_,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([_,Z1,_,_,Z2,_,_,Z3,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([_,_,Z1,_,_,Z2,_,_,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([Z1,_,_,_,Z2,_,_,_,Z3],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). open([_,_,Z1,_,Z2,_,Z3,_,_],Player) :- (var(Z1) | Z1 == Player),(var(Z2) | Z2 == Player), (var(Z3) | Z3 == Player). %%%%% %% Calculate the value of a position, o maximizes, x minimizes. %%%%% value(Board,100) :- win(Board,o), !. value(Board,-100) :- win(Board,x), !. value(Board,E) :- findall(o,open(Board,o),MAX), length(MAX,Emax), % # lines open to o findall(x,open(Board,x),MIN), length(MIN,Emin), % # lines open to x E is Emax - Emin. alpha_beta(Player,0,Position,_Alpha,_Beta,_NoMove,Value) :- value(Position,Value). alpha_beta(Player,D,Position,Alpha,Beta,Move,Value) :- D > 0, findall((X,Y),mark(Player,Position,X,Y),Moves), Alpha1 is -Beta, % max/min Beta1 is -Alpha, D1 is D-1, evaluate_and_choose(Player,Moves,Position,D1,Alpha1,Beta1,nil,(Move,Value)). evaluate_and_choose(Player,[Move|Moves],Position,D,Alpha,Beta,Record,BestMove) :- move(Player,Move,Position,Position1), other_player(Player,OtherPlayer), alpha_beta(OtherPlayer,D,Position1,Alpha,Beta,_OtherMove,Value), Value1 is -Value, cutoff(Player,Move,Value1,D,Alpha,Beta,Moves,Position,Record,BestMove). evaluate_and_choose(_Player,[],_Position,_D,Alpha,_Beta,Move,(Move,Alpha)). cutoff(_Player,Move,Value,_D,_Alpha,Beta,_Moves,_Position,_Record,(Move,Value)) :- Value >= Beta, !. cutoff(Player,Move,Value,D,Alpha,Beta,Moves,Position,_Record,BestMove) :- Alpha < Value, Value < Beta, !, evaluate_and_choose(Player,Moves,Position,D,Value,Beta,Move,BestMove). cutoff(Player,_Move,Value,D,Alpha,Beta,Moves,Position,Record,BestMove) :- Value =< Alpha, !, evaluate_and_choose(Player,Moves,Position,D,Alpha,Beta,Record,BestMove). other_player(o,x). other_player(x,o). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% For testing, use h(+,+) to record human move, %%% supply coordinates. Then call c (computer plays). %%% Use s to show board. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% h(X,Y) :- record(x,X,Y), showBoard. c :- board(B), alpha_beta(o,2,B,-200,200,(X,Y),_Value), % <=== NOTE record(o,X,Y), showBoard. showBoard :- board([Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9]), write(' '),mark(Z1),write(' '),mark(Z2),write(' '),mark(Z3),nl, write(' '),mark(Z4),write(' '),mark(Z5),write(' '),mark(Z6),nl, write(' '),mark(Z7),write(' '),mark(Z8),write(' '),mark(Z9),nl. s :- showBoard. mark(X) :- var(X), write('#'). mark(X) :- \+var(X),write(X).