% 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)).