% 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, Ss, S):- max(Ss, -100, S).
minimax(human, Ss, S):- min(Ss, 100, S).
% Now comes critical part.
% Yes, we are building a tree.
build_tree(computer, Ns, S):-
free_list(F),!,
length(F, N),
((N > 0) ->
build_nodes(computer, F, Ns),!, minimax(computer, Ns, S)
;
S is 0, Ns = []
).
build_tree(human, Ns, S):-
free_list(F),!,
length(F, N),
((N > 0) ->
build_nodes(human, F, Ns),!, minimax(human, Ns, S)
;
S is 0, Ns = []
).
build_nodes(_, [], []).
build_nodes(computer, [F|Fs], [(S,F,T)|Ns]):-
assert(computer(F)),
(win(computer) ->
retract(computer(F)), T = [], S is 1
;
build_tree(human, T, S),!, retract(computer(F))
),
build_nodes(computer, Fs, Ns).
build_nodes(human, [F|Fs], [(S,F,T)|Ns]):-
assert(human(F)),
(win(human) ->
retract(human(F)), T = [], S is -1
;
build_tree(computer, T, S),!, retract(human(F))
),
build_nodes(human, Fs, Ns).
% Take the top node of the tree (with score 1).
% We get the position from here.
% If we won't find winning node, take node
% that leads to draw.
top(Ns, P):- top1(Ns, P).
top(Ns, P):- top2(Ns, P).
top1([(1,P,_)|_], P).
top1([_|Ns], P):- top1(Ns, P).
top2([(0,P,_)|_], P).
top2([_|Ns], P):- top2(Ns, P).
top2([], 'loser :(').
move(P):- build_tree(computer, T, _), top(T, P).
traverse_node([(S,_,T)|Ns]):-
write(S), nl,
traverse_node(T),!,
traverse_node(Ns).
traverse_node([]).
% Clear up procedure.
clearup:- retractall(computer(_)), retractall(human(_)).
% Simple base case with three moves done.
%
% X X O
% X O
% O
%
% X - computer
base:-
assert(human(3)),
assert(human(5)),
assert(human(8)),
assert(computer(1)),
assert(computer(2)),
assert(computer(4)).