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