% 5x5 tic-tac-toe by Remigiusz 'lRem' Modrzejewski <http://lrem.net>
% % Distributed under the GPL, for more details see:  
% % http://lrem.net/pages/view/prolog_tic_tac_toe

domains
	s=symbol
	i=integer
	ls=s*
	li=i*
	
predicates
	boardsize(i)
	opponent(s,s)
	unfold(i, i, i)
	board(ls)
	board(ls, i)
	show(ls)
	showloop(ls, i)
	get(ls, i, s)
	get(ls, i, i, s)
	set(ls, i, s, ls)
	set(ls, i, i, s, ls)
	points(ls, i, i, s, i)
	points(ls, i, i, s, i, i, i)
	points(ls, i, i, s, i, i, i, i)
	points(i, i)
	nonblocking(s, s)
	open(ls, i, i, s, i)
	open(ls, i, i, s, i, i, i)
	open(ls, i, i, s, i, i, i, i)
	open(i, i)
	value(ls, s, i, i)
	nice(ls, s, i)
	isfree(ls, i)
	genmoves(ls, s, li)
	genmoves(ls, s, i, li, i)
	findisfree(ls, i, li)
	minimax(ls, s, i, i, i)
	choose(ls, s, i, li, i, i)
	max(i, i, i, i, i, i)
	turn(ls, s, i, i)
	main

clauses

boardsize(3).
opponent(o,x).
opponent(x,o).
unfold(M, X, Y) :-
	boardsize(S),
    X = M mod S,
    Y = (M-X)/S.
% Initialize the board% {{{
/*board([".", ".", ".", ".", ".", ".",
       ".", ".", ".", ".", ".", ".",
       ".", ".", ".", ".", ".", ".",
       ".", ".", ".", ".", ".", ".",
       ".", ".", ".", ".", ".", ".",
       ".", ".", ".", ".", ".", "." ]).*/
board(B) :- 
	boardsize(S),
	F = S*S,
	board(B, F).
board([], 0) :- !.
board(["."|T], N) :-
	N1 = N-1,
	board(T, N1).
% }}}
% Show the board% {{{
show(B) :- write(" 0123456"), nl, write("0"), showloop(B, 0), write("0123456"), nl.
showloop([], _).
showloop([H|T], I) :-
	boardsize(S),
    I mod S = S-1,
    L = (I-S+1)/S, 
    NL = (I+1)/S,
    write(H), write(L), nl, write(NL),
    I1 = I + 1,
    showloop(T, I1), !.
showloop([H|T], I) :-
    write(H),
    I1 = I + 1,
    showloop(T, I1).

% }}}
% Gets an index of array% {{{
get([H|_], 0, H) :- !.
get([_|T], N, R) :- 
    N1 = N-1, 
    get(T, N1, R).
% }}}
% Gets a position on board% {{{
get(B, X, Y, R) :- 
	boardsize(S),
    -1 < X, X < S, % Check whether inside the board
    -1 < Y, Y < S,
    N = X + S*Y,
    get(B, N, R).
% }}}
% Sets an index of array% {{{
set([_|T], 0, X, [X|T]) :- !.
set([H|T], N, X, [H|R]) :- 
    N1 = N-1, 
    set(T, N1, X, R).
% }}}
% Sets a position on board% {{{
set(B, X, Y, M, NB) :- 
	boardsize(S),
    N = X + S*Y,
    set(B, N, M, NB).
% }}}
% Counts how much points player P gets for the mark% {{{
points(B, X, Y, P, R) :-
    get(B, X, Y, M), M = ".", % Asserting it"s legal to put it there
    points(B, X, Y, P, 1, 0, R1),
    points(B, X, Y, P, 0, 1, R2),
    points(B, X, Y, P, 1, 1, R3),
    points(B, X, Y, P, 1, -1, R4),
    %write([R1, R2, R3, R4]), nl,
    R = R1 + R2 + R3 + R4.
points(B, X, Y, P, DX, DY, R) :-
    points(B, X, Y, P, DX, DY, 1, R1),
    MDX = -DX, MDY = -DY,
    points(B, X, Y, P, MDX, MDY, 1, R2),
    %write([inside, DX, DY, R1, R2]), nl,
    RS = R1 + R2 + 1,
    points(RS, R).
points(_, _, _, _, _,  _,  3, 0) :- !. % Search for half-lines no longer than 2
points(B, X, Y, P, DX, DY, D, R) :-
    X1 = X + DX*D,
    Y1 = Y + DY*D,
    get(B, X1, Y1, M),
    M = P,
    D1 = D+1,
    points(B, X, Y, P, DX, DY, D1, R1),
    R = R1 + 1, !.
points(_, _, _, _, _,  _,  _, 0).
points(1, 0) :- !.
points(N, R) :- R = N-2.
% }}}
%Counts open lines in  the neighbourhood{{{
nonblocking(".", _).
nonblocking(A, A).
open(B, X, Y, P, R) :-
    get(B, X, Y, M), M = ".", % Asserting starting point = open
    open(B, X, Y, P, 1, 0, R1),
    open(B, X, Y, P, 0, 1, R2),
    open(B, X, Y, P, 1, 1, R3),
    open(B, X, Y, P, 1, -1, R4),
    %write([R1, R2, R3, R4]), nl,
    R = R1 + R2 + R3 + R4.
open(B, X, Y, P, DX, DY, R) :-
    open(B, X, Y, P, DX, DY, 1, R1),
    MDX = -DX, MDY = -DY,
    open(B, X, Y, P, MDX, MDY, 1, R2),
    %write([inside, DX, DY, R1, R2]), nl,
    RS = R1 + R2 + 1,
    open(RS, R).
open(_, _, _, _, _,  _,  3, 0) :- !. % Search for half-lines no longer than 2
open(B, X, Y, P, DX, DY, D, R) :-
    X1 = X + DX*D,
    Y1 = Y + DY*D,
    get(B, X1, Y1, M),
    nonblocking(M, P),
    D1 = D+1,
    open(B, X, Y, P, DX, DY, D1, R1),
    R = R1 + 1, !.
open(_, _, _, _, _,  _,  _, 0).
open(1, 0) :- !.
open(N, R) :- R = N-2.
%}}}
%The value function {{{
value(B, P, M, R) :-
    unfold(M, X, Y),
    points(B, X, Y, P, RPM),
    open(B, X, Y, P, ROM),
    %opponent(P, O),
    %points(B, X, Y, O, RPO),
    %open(B, X, Y, O, ROO),
    R = 10*RPM + 3*ROM. % + 8*RPO + 3*ROM + 1*ROO.
nice(B, P, M) :-
    value(B, P, M, R),
    R > 10.
%}}}
%Moves generator{{{
isfree(B, M) :- 
    get(B, M, R), 
    R = ".".
genmoves(B, P, ML) :- 
    genmoves(B, P, 0, ML, MC),
    %write([MC, "nice moves"]), nl,
    MC > 0, !.
genmoves(B, _, ML) :- 
    %write("finding all isfree"), nl,
    findisfree(B, 0, ML).
%genmoves(_, _, 36, [], 0) :- !.
genmoves(_, _, N, [], 0) :- 
	boardsize(S),
	N = S*S, !.
genmoves(B, P, N, [N|T], MC) :-
    nice(B, P, N),
    N1 = N+1,
    genmoves(B, P, N1, T, MC1),
    MC = MC1+1, !.
genmoves(B, P, N, T, MC) :-
    N1 = N+1,
    genmoves(B, P, N1, T, MC).
findisfree([], _, []).
findisfree([H|T], N, [N|RT]) :-
    H = ".",
    N1 = N+1,
    findisfree(T, N1, RT), !.
findisfree([_|T], N, RT) :-
    N1 = N+1,
    findisfree(T, N1, RT).
%}}}
%The minimax search {{{
%Board, player, depth, next best move, value
minimax(_, _, 0, -1, 0) :- !.
minimax(B, P, D, M, V) :-
    genmoves(B, P, ML),
    %write(" in minimax "), nl, 
    choose(B, P, D, ML, M, V).
choose(_, _, _, [], -1, -999).
choose(B, P, D, [H|T], M, V) :-
    %write(" in choose "),
    value(B, P, H, V1),
    set(B, H, P, NB),
    opponent(P, O),
    D1 = D-1,
    minimax(NB, O, D1, _, V2),
    VH = V1 - V2,
    %write([D, P, H, VH]), nl,
    choose(B, P, D, T, MT, VT),
    max(VH, H, VT, MT, V, M).
max(VH, H, VT, _, VH, H) :-
    VH > VT, !.
max(_, _, VT, MT, VT, MT).
%}}}
%/*{{{*/
turn(B, x, RX, RO) :-
    show(B),
    write("x coord:"), readterm(i, X),
    write("y coord:"), readterm(i, Y),
    points(B, X, Y, x, RX1),
    set(B, X, Y, x, NB),
    turn(NB, o, RX2, RO),
    RX = RX1 + RX2, !.

turn(B, o, RX, RO) :-
    show(B),
    %write("x coord:"), read(X),
    %write("y coord:"), read(Y),
    minimax(B, o, 2, M, _),
    unfold(M, X, Y),
    points(B, X, Y, o, RO1),
    set(B, X, Y, o, NB),
    turn(NB, x, RX, RO2),
    RO = RO1 + RO2, !.

turn(_, _, 0, 0).
%/*}}}*/
main :- 
    board(B),
    turn(B, x, RX, RO),
    write(x, RX, points, o, RO, points), nl.
main :- 
    write(nowai)%, 
    %halt.
    .