% All valid positions
pos(1). pos(2). pos(3). pos(4). pos(5). pos(6). pos(7). pos(8). pos(9).
% That is:
% 1 2 3
% 4 5 6
% 7 8 9
% Computer moves
:-dynamic(computer/1).
% Human moves
:-dynamic(human/1).
% Winning triples
winning([1,2,3]).
winning([4,5,6]).
winning([7,8,9]).
winning([1,4,7]).
winning([2,5,8]).
winning([3,6,9]).
winning([1,5,9]).
winning([7,5,3]).
% The computer wins if it has moved
% on three positions which belong
% to winning triple.
win(computer):-
winning(W),
computer(X),
computer(Y),
computer(Z),
X \= Y,
Y \= Z,
Z \= X,
member(X, W),
member(Y, W),
member(Z, W).
% Same as up for the human.
win(human):-
winning(W),
human(X),
human(Y),
human(Z),
X \= Y,
Y \= Z,
Z \= X,
member(X, W),
member(Y, W),
member(Z, W).
% Position is free if neither computer or
% human has moved there.
free_pos(X):- pos(X), \+computer(X), \+human(X).
% The game is draw if all positions has taken.
% In other words: no free posittion exists.
draw:- \+free_pos(_).
% The list of free positions.
% If there are no free positions this will
% be an empty list.
free_list(F):- findall(X, free_pos(X), F).
% Finding minimum and maximum from the list of elements.
max([], M, M).
max([X|Xs], MaxSoFar, Max):- X > MaxSoFar, max(Xs, X, Max).
max([X|Xs], MaxSoFar, Max):- X =< MaxSoFar, max(Xs, MaxSoFar, Max).
min([], M, M).
min([X|Xs], MinSoFar, Min):- X < MinSoFar, min(Xs, X, Min).
min([X|Xs], MinSoFar, Min):- X >= MinSoFar, min(Xs, MinSoFar, Min).
% Calculate minimax on current node.
% This depends on which player makes
% current move.
minimax(computer, Costs, Cost):- max(Costs, 0, Cost).
minimax(human, Costs, Cost):- min(Costs, 0, Cost).
% Now comes critical part.
% Yes, we are building a tree.
build_tree(computer):-
free_list(F),!,
build_node(computer, F).
build_tree(human):-
free_list(F),!,
build_node(human, F).
build_node(_, []).
build_node(computer, [F|Fs]):-
assert(computer(F)),
(win(computer) ->
retract(computer(F))
;
build_tree(human),!, retract(computer(F))
),
build_node(computer, Fs).
build_node(human, [F|Fs]):-
assert(human(F)),
(win(human) ->
retract(human(F))
;
build_tree(human),!, retract(human(F))
),
build_node(human, Fs).
% Clear up procedure.
clearup:- retractall(computer(_)), retractall(human(_)).