%       Tictactoe
% Ricus Smid                    9660208
% Andreas van Cranenburgh       0440949

% =========================================
% Facts
% =========================================
initial(state(_, [], [])).

%values for 4x4.
posval([[1,1],[1,4],[4,1],[4,4],[2,2],[2,3],[3,2],[3,3]], 3) :-
        dimensions(2), size(4).
posval([_], 2) :-
        dimensions(2), size(4).

%values for 3x3x3
posval([[1,1,1],[1,3,1],[3,1,1],[3,3,1],[1,1,3],[1,3,3],[3,1,3],[3,3,3]], 5) :-
        dimensions(3), size(3).
posval([[1,2,2], [3,2,2], [2,1,2], [2,3,2], [2,2,1], [2,2,3]], 5) :-
        dimensions(3), size(3).
posval([[2,2,2]], 11) :- dimensions(3), size(3).
posval(_, 4) :- dimensions(3), size(3).

%values for 3x3
posval([[1,1],[1,3],[3,1],[3,3]],3) :- dimensions(2), size(3).
posval([[2,2]], 4) :- dimensions(2), size(3).
posval(_,2) :- dimensions(2), size(3).

% switch(+Player, -Player2)
% Gives other player
switch(x, o).
switch(o, x).


%Dynamic facts
:- dynamic turn/1, num_moves/2, h/2, size/1, dimensions/1, gravity/1.

dimensions(3).
size(3).

%turn says whose move it is, regardless of what state minimax is considering.
turn(x).
h(x, 1).
h(o, 1).

% num_moves/2 counts number of states a player has considered.
num_moves(o,0).
num_moves(x,0).

% =========================================
% Gameplay
% =========================================

% Wrapper for computer vs. computer matches.

go :-
    writeln('Dimensions(2 or 3):'), read(Dim),
    retractall(dimensions(_)), assert(dimensions(Dim)),
    writeln('Size(3 or 4):'), read(Size),
    retractall(size(_)), assert(size(Size)),
    
    retractall(gravity(_)),
    (dimensions(3) ->
    (writeln('Simulate gravity (true or false):'),
    read(Gravity),
    assert(gravity(Gravity)))
    ;
    assert(gravity(false))),
    
    dimensions(3), size(4),
    writeln('How many games to play:'),
    read(RepeatN),
    writeln('Depth of O:'),
    read(Depth1),
    writeln('Depth of X'),
    read(Depth2),
    test(RepeatN, Depth1, Depth2, 0, 0, NNO, NNX, ND, NMovesO, NMovesX),
    nl, writeln('Results:'),
    write('Wins O: '), write(NNO),nl,
    write('Wins X: '), write(NNX),nl,
    write('Draws: '), write(ND),nl,
    write('States made by O: '), write(NMovesO),nl,
    write('States made by X: '), write(NMovesX).

go :-
    writeln('How many games to play:'),
    read(RepeatN),
    writeln('Depth of O:'),
    read(Depth1),
    ((size(3), writeln('heuristic O(0,1,2 or 3):'),read(HeurO));
    (writeln('heuristic O(0,1 or 2):'),
    read(HeurO))),
    writeln('Depth of X'),
    read(Depth2),
    ((size(3), writeln('heuristic O(0,1,2 or 3):'),read(HeurX));
    (writeln('heuristic O(0,1 or 2):'),
    read(HeurX))),
    test(RepeatN, Depth1, Depth2, HeurO, HeurX, NNO, NNX, ND, NMovesO, NMovesX),
    nl, writeln('Results:'),
    write('Wins O: '), write(NNO),nl,
    write('Wins X: '), write(NNX),nl,
    write('Draws: '), write(ND),nl,
    write('States made by O: '), write(NMovesO),nl,
    write('States made by X: '), write(NMovesX).

/*
go3:-   retractall(dimensions(_)),
        retractall(size(_)),
        retractall(gravity(_)),
        assert(dimensions(2)),
        %assert(dimensions(3)),
        assert(size(4)),
        %assert(size(4)),
        assert(gravity(false)),
        %assert(gravity(true)),
        %writeln('Depth of O/X:'),
        %read(Depth1/Depth2),
        %writeln('heuristic O/X(0,1,2 or 3):'),
        %read(HeurO/HeurX),
        test(5, 4,1, 1,2, NNO, NNX, ND, NMovesO, NMovesX),
        nl, writeln('Results:'),
        write('Wins O: '), write(NNO),nl,
        write('Wins X: '), write(NNX),nl,
        write('Draws: '), write(ND),nl,
        write('States made by O: '), write(NMovesO),nl,
        write('States made by X: '), write(NMovesX),nl,nl,
        X is NNO + NNX + ND,
        StatO is NMovesO//X,
        StatX is NMovesX//X,
        write('States/game O: '), write(StatO),nl,
        write('States/game X: '), write(StatX),nl,
        WinO is NNO * (100/X), write('Win O/100: '), write(WinO),nl,
        WinX is NNX * (100/X), write('Win X/100: '), write(WinX),nl,
        Dr is ND * (100/X), write('Draws/100: '), write(Dr),nl.
*/

go2 :-
        writeln('Search depth of computer: '),
        read(XDepth),
        initial(State),
        retractall(turn(_)),
        assert(turn(o)),
        retractall(h(_,_)),
        assert(h(x, 1)),
        against_comp(State, XDepth).

against_comp(State, _XDepth) :-
        winnaar(State, X),
        write(X), writeln(' wins the match').

against_comp(state(o, XPos, OPos), XDepth) :-
        retract(turn(_)),
        assert(turn(x)), !,
        (dimensions(3),
        write('Give [X,Y,Z]: '),
        read([X,Y,Z]),
        against_comp(state(x, XPos, [[X,Y,Z]|OPos]), XDepth)
        ;
        dimensions(2),
        write('Give [X,Y]: '),
        read([X,Y]),
        against_comp(state(x, XPos, [[X,Y]|OPos]), XDepth)
        ).

against_comp(state(x, XPos, OPos), XDepth) :-
        zet_x(XDepth, state(x, XPos, OPos), NewState),
        against_comp(NewState, XDepth).

% test(+RepeatN, +DepthO, +DepthX, +HeurO, +HeurX, -WinsO, -WinsX, -Draws, -MovesO,-MovesN)
% test/8 wordt gebruikt om experimenten uit te voeren.
% Je geeft in RepeatN aan hoeveel spellen er gespeeld meoten worden, en
% vervolgens houdt test bij wie er hoeveel spellen gewonnen heeft.
% Daarnaast houdt het ook bij hoeveel zetten een Player in al die
% spellen heeft gedaan. (je moet dit zelf dus nog middelen).
test(0,_, _, _, _, 0,0,0,0,0).

test(RepeatN, Depth1, Depth2, HeurO, HeurX, NNO, NNX, ND, NMovesO, NMovesX) :-
    NRepeat is RepeatN - 1,
    test(NRepeat, Depth1, Depth2, HeurO, HeurX, NumO, NumX, D,MO,MX),
    % Printen om welk spel het gaat
    nl, writeln('-----------------------------------'),
    write('Game '),write(RepeatN), write(': O ('), write(Depth1),
    write(') vs. X ('), write(Depth2), writeln(')'),
    writeln('-----------------------------------'),
    speel(Depth1, Depth2, HeurO, HeurX, R, MovesO, MovesX),
    NMovesO is MO + MovesO,    % Het bijhouden van de gemaakte
    NMovesX is MX + MovesX,    % states.
    update_val(NumO, NumX, D, R, NNO, NNX, ND), !.

% update_val(+WinsO, +WinsX, +Draws, +Winner, -NWinsO, -NWinsX, -NDraws)
% Verhoogt de waarden van het aantal winsten en gelijk spel.
update_val(NO, NX, D, o, NNO, NX, D) :- NNO is NO + 1.
%,write(' - o'),nl.
update_val(NO, NX, D, x, NO, NNX, D) :- NNX is NX + 1.
%write(' - x'),nl.
update_val(NO, NX, D, draw, NO, NX, ND) :- ND is D + 1.
% write(' - d'),nl.


% speel(+DiepteO, +DiepteX, -Resultaat)
% speel/3 is een wrapper predicaat voor speel/4
% Hier wordt het starten van het spel voorbereid
speel(DiepteO, DiepteX, HeurO, HeurX, Resultaat, MovesO, MovesX) :-
    retractall(turn(_)),
    assert(turn(o)),
    initial(State),!,
    retractall(h(_,_)),
    assert(h(o, HeurO)),
    assert(h(x, HeurX)),

    speel(DiepteO, DiepteX, State, Resultaat),

    % Het aantal gemaakte states op 0 stellen aan het einde van het spel.
    num_moves(o, MovesO),
    num_moves(x, MovesX),
    retractall(num_moves(_,_)),
    assert(num_moves(x, 0)),
    assert(num_moves(o, 0)).


% speel(+DiepteO, +DiepteX, +State, -Resultaat)
% Hier wordt het spel gespeeld.
speel(_, _, State, Resultaat) :-
    winnaar(State, Resultaat).

speel(DiepteO, DiepteX, state(o, XPos, OPos), Resultaat) :-
    zet_o(DiepteO, state(o, XPos, OPos), NewState),
    speel(DiepteO,DiepteX, NewState, Resultaat),!.

speel(DiepteO, DiepteX, state(x, XPos, OPos), Resultaat) :-
    zet_x(DiepteX, state(x, XPos, OPos), NewState),
    speel(DiepteO, DiepteX, NewState, Resultaat),!.

% zet_o(+DiepteO, +State, -NewState)
% Het genereren van een zet voor o.
zet_o(DiepteO, State, state(x, XPos, OPos)) :-
    minimax(State, state(x, XPos, OPos), _, DiepteO),
    %alphabeta(State, -1001, 1001, state(x, XPos, OPos),  _, DiepteO),
    % Output van de nieuwe stelling:
    pretty_print(state(x, XPos, OPos)),
    % Wisseling van de turn
    retractall(turn(_)),
    assert(turn(x)), !.

% zet_x(+DiepteX, +State, -NewState)
% Het genereren van een zet voor x.
zet_x(DiepteX, State, state(o, XPos, OPos)) :-
    minimax(State, state(o, XPos, OPos), _, DiepteX),
    %alphabeta(State, -1001, 1001, state(o, XPos, OPos),  _, DiepteX),
    % Output van de nieuwe stelling:
    pretty_print(state(o, XPos, OPos)),
    % Wisseling van de turn
    retractall(turn(_)),
    assert(turn(o)), !.

% pretty_print(+Stand)
% Zorgt voor een mooie output van een bordopstelling

% pretty_print voor drie_bij_drie spel

pretty_print(Stand):-
  dimensions(2), size(3),
  bord_three_in_a_row(Bord),
  invullen(Stand, Bord, [P1,P2,P3,P4,P5,P6,P7,P8,P9]),
  nl,
  write(P1),write('|'),write(P2),write('|'),write(P3),nl,
  write('-+-+-'),nl,
  write(P4),write('|'),write(P5),write('|'),write(P6),nl,
  write('-+-+-'),nl,
  write(P7),write('|'),write(P8),write('|'),write(P9),nl.
% writeln(Stand).

% pretty_print voor vier_bij_vier spel

pretty_print(Stand):-
  dimensions(2), size(4),
  bord_four_in_a_row(Bord),
  invullen(Stand, Bord,
[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13,P14,P15,P16]),
  nl,
  write(P1),write('|'),write(P2),write('|'),write(P3), write('|'),
write(P4),nl,
  write('-+-+-+-'), nl,
  write(P5),write('|'),write(P6), write('|'), write(P7),
write('|'),write(P8),nl,
  write('-+-+-+-'),nl,
  write(P9), write('|'),
  write(P10),write('|'),write(P11),write('|'),write(P12),nl,
  write('-+-+-+-'),nl,
  write(P13), write('|'),
  write(P14),write('|'),write(P15),write('|'),write(P16),nl.

pretty_print(Stand):-
  dimensions(3), size(3),
  bord_three_dimension(Bord),
  invullen(Stand, Bord, [P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13,P14,P15,P16,P17,P18,P19,P20,P21,P22,P23,P24,P25,P26,P27]),
  nl,
  write(P1),write('|'),write(P2),write('|'),write(P3),
  tab(3),write(P4),write('|'),write(P5),write('|'),write(P6),
  tab(3),write(P7),write('|'),write(P8),write('|'),write(P9),nl,
  write('-+-+-   -+-+-   -+-+-'),nl,
  write(P10),write('|'),write(P11),write('|'),write(P12),
  tab(3),write(P13), write('|'),
  write(P14),write('|'),write(P15),tab(3),write(P16),write('|'),write(P17),write('|'),write(P18),nl,
  write('-+-+-   -+-+-   -+-+-'),nl,
  write(P19),write('|'),write(P20),write('|'),write(P21),
  tab(3),write(P22),write('|'),write(P23),write('|'),write(P24),
  tab(3),write(P25),write('|'),write(P26),write('|'),write(P27),nl.


pretty_print(Stand):-
  dimensions(3), size(4),
  bord_four_dimension(Bord),
  invullen(Stand, Bord,
[P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11,P12,P13,P14,P15,P16,P17,P18,P19,P20,
P21,P22,P23,P24,P25,P26,P27,P28,P29,P30,P31,P32,P33,P34,P35,P36,P37,P38,P39,P40,
P41,P42,P43,P44,P45,P46,P47,P48,P49,P50,P51,P52,P53,P54,P55,P56,P57,P58,P59,P60,P61,P62,P63,P64]),
  nl,
  write(P1),write('|'),write(P2),write('|'),write(P3), write('|'),write(P4), tab(3), write(P5),write('|'),write(P6), write('|'), write(P7),
  write('|'),write(P8), tab(3), write(P9), write('|'), write(P10),write('|'),write(P11),write('|'),write(P12), tab(3),  write(P13), write('|'),
  write(P14),write('|'),write(P15),write('|'),write(P16),nl,
  write('-+-+-+-   -+-+-+-   -+-+-+-   -+-+-+-'), nl,
  write(P17),write('|'),write(P18),write('|'),write(P19), write('|'),write(P20), tab(3), write(P21),write('|'),write(P22), write('|'), write(P23),
  write('|'),write(P24), tab(3), write(P25), write('|'), write(P26),write('|'),write(P27),write('|'),write(P28), tab(3),  write(P29), write('|'),
  write(P30),write('|'),write(P31),write('|'),write(P32),nl,
  write('-+-+-+-   -+-+-+-   -+-+-+-   -+-+-+-'), nl,
  write(P33),write('|'),write(P34),write('|'),write(P35), write('|'),write(P36), tab(3), write(P37),write('|'),write(P38), write('|'), write(P39),
  write('|'),write(P40), tab(3), write(P41), write('|'), write(P42),write('|'),write(P43),write('|'),write(P44), tab(3),  write(P45), write('|'),
  write(P46),write('|'),write(P47),write('|'),write(P48),nl,
  write('-+-+-+-   -+-+-+-   -+-+-+-   -+-+-+-'), nl,
  write(P49),write('|'),write(P50), write('|'),write(P51),write('|'), write(P52),tab(3),write(P53), write('|'), write(P54),
  write('|'),write(P55),write('|'),  write(P56),tab(3),  write(P57),write('|'),write(P58),write('|'),write(P59), write('|'),  write(P60),tab(3),
  write(P61),write('|'),write(P62),write('|'),write(P63),write('|'),write(P64),nl.

% pretty_print(+State)
% when all else fails, print raw output
pretty_print(State) :-
    write('State: '), writeln(State).


invullen(state(_, _, _), [],[]).

invullen(state(_, XPos, OPos), [H|T],['x'|Rest]):-
  member(H, XPos),
  invullen(state(_, XPos, OPos), T, Rest).

invullen(state(_, XPos, OPos), [H|T],['o'|Rest]):-
  member(H, OPos),
  invullen(state(_, XPos, OPos), T, Rest).

invullen(state(_, XPos, OPos), [_|T], [' '|Rest]):-
  invullen(state(_, XPos, OPos), T, Rest).


% alle bordcoordinaten van drie_bij_drie, vier_bij_vier en drie_dimensie
bord_three_in_a_row([[1,3],[2,3],[3,3],[1,2],[2,2],[3,2],[1,1],[2,1],[3,1]]).

bord_four_in_a_row([[1,4],[2,4],[3,4],[4,4],[1,3],[2,3],[3,3],[4,3],
[1,2],[2,2],[3,2],[4,2],[1,1],[2,1],[3,1],[4,1]]).

bord_three_dimension([[1,3,1],[2,3,1],[3,3,1], [1,3,2],[2,3,2],[3,3,2],
[1,3,3],[2,3,3],[3,3,3], [1,2,1],[2,2,1],[3,2,1], [1,2,2],[2,2,2],[3,2,2],
[1,2,3],[2,2,3],[3,2,3], [1,1,1],[2,1,1],[3,1,1], [1,1,2],[2,1,2],[3,1,2],
[1,1,3],[2,1,3],[3,1,3]]).

bord_four_dimension([[1,4,1],[2,4,1],[3,4,1],[4,4,1], [1,4,2],[2,4,2],[3,4,2],[4,4,2],
[1,4,3],[2,4,3],[3,4,3],[4,4,3],  [1,4,4],[2,4,4],[3,4,4],[4,4,4],
[1,3,1],[2,3,1],[3,3,1],[4,3,1],  [1,3,2],[2,3,2],[3,3,2],[4,3,2],
[1,3,3],[2,3,3],[3,3,3],[4,3,3],  [1,3,4],[2,3,4],[3,3,4],[4,3,4],
[1,2,1],[2,2,1],[3,2,1],[4,2,1],  [1,2,2],[2,2,2],[3,2,2],[4,2,2],
[1,2,3],[2,2,3],[3,2,3],[4,2,3],  [1,2,4],[2,2,4],[3,2,4],[4,2,4],
[1,1,1],[2,1,1],[3,1,1],[4,1,1],  [1,1,2],[2,1,2],[3,1,2],[4,1,2],
[1,1,3],[2,1,3],[3,1,3],[4,1,3],  [1,1,4],[2,1,4],[3,1,4],[4,1,4]]).

% =========================================
% Minimax implementatie (Vanuit BRATKO)
% =========================================
minimax(State, _, Val, 0):-
    staticval(State, Val),!.

minimax(State, _, Val,_):-
    winnaar(State, _),
    staticval(State, Val),!.

minimax(State, BestSucc, Val, ZoekDiepte) :-
    NZoekDiepte is ZoekDiepte - 1,
    moves(State, StateList),
    !,
    best(StateList, BestSucc, Val, NZoekDiepte).

best([State], State, Val, ZoekDiepte):-
    minimax(State, _, Val, ZoekDiepte),!.

best([State1 | StateList], BestState, BestVal, ZoekDiepte):-
    minimax(State1, _, Val1, ZoekDiepte),
    best(StateList, State2, Val2, ZoekDiepte),
    betterOf(State1, Val1, State2, Val2, BestState, BestVal).


% Als MIN aan zet is prefereert MAX de hoogste
betterOf(State0, Val0, _State1, Val1, State0, Val0):-
    min_to_move(State0), Val0 > Val1, !;
    max_to_move(State0), Val0 < Val1, !.

betterOf(State0, Val0, State1, Val1, State1, Val1):-
    min_to_move(State0), Val0 < Val1, !;
    max_to_move(State0), Val0 > Val1, !.

% Anders wordt er random gekozen
betterOf(_, _, State1, Val1, State1, Val1) :-
    random(0,2,C), C=0, !.

betterOf(State0, Val0, _, _, State0, Val0).

% max_to_move(State)
% kijkt of MAX in een stelling aan de turn is
max_to_move(state(A, _, _)) :-
    turn(A).

% min_to_move(State)
% true if it's MIN's turn
min_to_move(state(A, _, _)) :-
    turn(X),
    X \= A.

%---------------------------------------------------------------
% Bratko Alpha-beta implementation (page 589, prolog programming for AI)
%---------------------------------------------------------------
alphabeta(State, _, _, _, Val, 0) :-
        staticval(State, Val).

alphabeta(State, _, _, _, Val, _) :-
        winnaar(State, _),
        staticval(State, Val), !.

alphabeta(State, Alpha, Beta, GoodState, Val, Depth) :-
        NewDepth is Depth - 1,
        moves(State, List), !,
        boundedbest(List, Alpha, Beta, GoodState, Val, NewDepth);
        staticval(State, Val).

boundedbest([State | List], Alpha, Beta, GoodState, GoodVal, Depth) :-
        alphabeta(State, Alpha, Beta, _, Val, Depth),
        goodenough(List, Alpha, Beta, State, Val, GoodState, GoodVal, Depth).

goodenough([], _, _, State, Val, State, Val, _Depth) :- !.

goodenough(_, Alpha, Beta, State, Val, State, Val, _Depth) :-
        min_to_move(State), Val > Beta, !;
        max_to_move(State), Val < Alpha, !.

goodenough(List, Alpha, Beta, State, Val, GoodState, GoodVal, Depth) :-
        newbounds(Alpha, Beta, State, Val, NewAlpha, NewBeta),
        boundedbest(List, NewAlpha, NewBeta, State1, Val1, Depth),
        betterOf(State, Val, State1, Val1, GoodState, GoodVal).

newbounds(Alpha, Beta, State, Val, Val, Beta) :-
        min_to_move(State), Val > Alpha, !.

newbounds(Alpha, Beta, State, Val, Alpha, Val) :-
        max_to_move(State), Val < Beta, !.

newbounds(Alpha, Beta, _State, _Val, Alpha, Beta).

%---------------------------------------------------------------

moves(Pos, PosList) :-
    findall(X, move(Pos, X), PosList),

    % Bijhouden gemaakte states
    turn(Player),
    length(PosList, NumMoves),
    num_moves(Player, Moves),
    NMoves is NumMoves + Moves,
    retract(num_moves(Player, _)),
    assert(num_moves(Player, NMoves)).

%generate a legal move
move(state(A, XPos, OPos), NewState) :-
    try(Piece),
    not(member(Piece, XPos)),
    not(member(Piece, OPos)),
    (
        dimensions(3),
        gravity(true),
        (
                Piece = [_ , _, 1]
        ;
                Piece = [X, Y, 2],
                (member([X, Y, 1], XPos) ; member([X, Y, 1], OPos))
        ;
                Piece = [X, Y, 3],
                (member([X, Y, 2], XPos) ; member([X, Y, 2], OPos))
        ;
                Piece = [X, Y, 4],
                (member([X, Y, 3], XPos) ; member([X, Y, 3], OPos))
        )
   ;
        gravity(false)
   ),
   (
        A = x,
        NewState = state(o, [Piece|XPos], OPos)
    ;
        A = o,
        NewState = state(x, XPos, [Piece|OPos])
    ).

%generate a legal coordinate in the playing field/cube/space
try([X,Y]) :-
    dimensions(2), size(A),
    inc(1, X, A),
    inc(1, Y, A).

try([X,Y,Z]) :-
    dimensions(3), size(A),
    inc(1, X, A),
    inc(1, Y, A),
    inc(1, Z, A).

try([X,Y,Z,W]) :-
    dimensions(4), size(A),
    inc(1, X, A),
    inc(1, Y, A),
    inc(1, Z, A),
    inc(1, W, A).

%predicate to count from Start to Max
%inc(Start, Next, Max)
inc(X, X, _).

inc(X, Xnew, Max) :-
  X < Max,
  Xtemp is X + 1,
  inc(Xtemp, Xnew, Max).

winnaar(state(_A, Xpos, _Opos), x) :-
    hasWon(Xpos).

winnaar(state(_A, _Xpos, Opos), o) :-
    hasWon(Opos).

winnaar(state(_A, Xpos, Opos), draw) :-
    full(Xpos, Opos).

hasWon(APos) :-
    (
        size(3),
        bagof([P1, P2, P3], getCombination(APos, [P1, P2, P3]), Comb)
    ;
        size(4),
        bagof([P1, P2, P3, P4], getCombination(APos, [P1, P2, P3, P4]), Comb)
    ),
    checkCombinations(Comb).

%predicate to generate a combination from a list
%getCombination(+List, -Comb)
getCombination(_, []).

getCombination([H|Apos], [H|Comb]) :-
    getCombination(Apos, Comb).

getCombination([_|Apos], [H|Comb]) :-
    getCombination(Apos, [H|Comb]).

%H is a list of three/four coordinates.
%each coordinate will be a list with 2/3 elements.
%here it should be checked if they are a sequence
%or on the same row/column etc.
checkCombinations([H|Comb]) :-
        %transpose the list of lists so that each X coordinate
        %is in one list, each Y coordinate, etc.
        insert_sort(H, I),
        transpose(I, J),
        (
            testComb(J) %found a winning combination
        ;
            checkCombinations(Comb)
        ).


%insert sort
insert_sort(List,Sorted) :- i_sort(List,[],Sorted).
i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted) :- insert(H,Acc,NAcc),i_sort(T,NAcc,Sorted).

insert(X,[Y|T],[Y|NT]) :- comp(X, Y), insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]) :- not(comp(X, Y)).
insert(X,[],[X]).

%compare two lists with numbers, first element is most significant
comp([A|X], [B|Y]) :-
        A > B
        ;
        (A = B, comp(X, Y)).

testComb([]).
testComb([H|Tail]) :-
    (allEqual(H)
    ;
    downSequence(H)
    ;
    upSequence(H)
    ),
    testComb(Tail).

%test if elements in a list are all equal
allEqual([]).
allEqual([_]).
allEqual([X, X | T]) :-
    allEqual([X|T]).

downSequence([1]).
downSequence([H1, H2|T]) :-
        H1 is H2 + 1,
        downSequence([H2|T]).

upSequence([A]) :- size(A).
upSequence([H1, H2|T]) :-
        H1 is H2 - 1,
        upSequence([H2|T]).

%test if elements in a list are all different
allDifferent([_]).
allDifferent([H|T]) :-
    not(member(H, T)),
    allDifferent(T).

%transpose a matrix
transpose([Word], Cs) :- !,
/*  reverse(Word, R), */
    R = Word,
    list2columns(R, Cs).

transpose([Word|Words], Cs) :- !,
    transpose(Words, Cs0),
/*  reverse(Word, R), */
    R = Word,
    put_columns(R, Cs0, Cs).

list2columns([], []).
list2columns([X|Xs], [[X]|Zs]) :-
    list2columns(Xs, Zs).

put_columns([], Cs, Cs).
put_columns([X|Xs], [C|Cs0], [[X|C]|Cs]) :-
    put_columns(Xs, Cs0, Cs).

%check arithmetically if playing field/space is full
full(XPos, OPos) :-
    length(XPos, X),
    length(OPos, O),
    size(S), dimensions(D),
    Places is S ^ D,
    Places =:= X + O.

% =========================================
% Statische evaluation function
% =========================================

% staticval(+State, -Val)
% Geeft de waarde van een bepaalde Stateopstelling
staticval(state(_, XPos, OPos), Val) :-
    turn(Player),
    h(Player, Heur),
    heuristic(Heur, state(_, XPos, OPos), Val).

% check_winval(+State, +Player, -Val)
% Waarde is bij verlies -1000
% bij winst +1000 en bij draw of anders 0
check_winval(State, Player, 1000) :-
    winnaar(State, Player).

check_winval(State, Player, -1000) :-
    switch(Player, S2),
    winnaar(State, S2).

check_winval(State, _, 0) :- 
        winnaar(State, draw).

check_winval(State, _, 0) :- 
        not(winnaar(State, _Player)).

check_posval(state(_A, Xpos, _Opos), x, Value) :-
    getposval(Xpos, 0, Value).

check_posval(state(_A, _Xpos, Opos), o, Value) :-
    getposval(Opos, 0, Value).

getposval([], Result, Result).
getposval([H|Apos], Val, Result) :-
    posval(X, PosVal),
    member(H, X),
    NVal is PosVal + Val,
    getposval(Apos, NVal, Result).

heuristic(1, state(_, XPos, OPos), Val) :-
    turn(Player),
    % Berekent de waarde van de opstelling van beide Players op grond
    % van de waarden van de vakjes die ze hebben
    check_posval(state(_, XPos, OPos), Player, Val1),
    switch(Player, Player2),
    check_posval(state(_, XPos, OPos), Player2, Val2),

    % Berekent de toegevoegdewaarde van een State op grond van winnaars of verliezers
    check_winval(state(_, XPos, OPos), Player, WinVal),

    % Totale waarde is Waarde Player 1 - Waarde Player 2
    % met eventuele optelling of aftrekking van punten vanwege
    % een winnend of verliezend State.
    Val is Val1 - Val2 + WinVal.

% heuristiek 3
% berekent het aantal rijen met 1 symbool van de player en geen symbolen van de ander (waarde 1)
% en de rijen met 2 symbolen van de player en zonder symbolen van de ander( waarde 8)

heuristic(3, state(_, XPos, OPos), Val):-
      turn(Player),
      check_rows(state(_,XPos,OPos), Player, Val1),
      switch(Player, Player2),
      check_rows(state(_,XPos,OPos), Player2, Val2),
      check_winval(state(_, XPos, OPos), Player, WinVal),
      Val is Val1 - Val2 + WinVal,!.

% dummy heuristic (random)

heuristic(0, State, Val) :-
        turn(Player),
        check_winval(State, Player, Val).

% heuristiek 2

heuristic(2, state(_, XPos, OPos), Val) :-
        count_freedoms(XPos, state(x, XPos, OPos), ValX),
        count_freedoms(OPos, state(o, XPos, OPos), ValO),
        (turn(x) ->
                check_winval(state(_, XPos, OPos), x, WinVal),
                Val is ValX - ValO + WinVal
        ;
                check_winval(state(_, XPos, OPos), o, WinVal),
                Val is ValO - ValX + WinVal
        ).

count_freedoms(A, B, Val) :- count_freedoms(A, B, 0, Val).

count_freedoms([], _, Result, Result).
count_freedoms([H|PosTail], state(A, XPos, OPos), OldVal, Result) :- 
        findall(X, neighbor(H, X), List),
        check_freedoms(List, state(A, XPos, OPos), 0, NewVal),
        Val is OldVal + NewVal,
        count_freedoms(PosTail, state(A, XPos, OPos), Val, Result).

check_freedoms([], _, Result, Result).
check_freedoms([H|T], state(A, XPos, OPos), OldVal, Result) :-
        % if neighbor square is occupied by opposing player, a point is substracted
        % otherwise, empty or occupied by ourselves, a point is added
        ( A = o ->
                ( member(H, XPos) ->
                        Val is OldVal - 1
                ;
                        ( member(H, OPos) -> 
                                Val is 1 + OldVal ;
                                Val is 1 + OldVal ) )
        ;
                ( member(H, OPos) ->
                        Val is OldVal - 1
                ;
                        ( member(H, XPos) -> 
                                Val is 1 + OldVal ;
                                Val is 1 + OldVal ) ) ),
        check_freedoms(T, state(A, XPos, OPos), Val, Result).

neighbor([], []).
neighbor([HA|A], [HB|B]) :-
        (HA = HB;
        %HB is HA + 2;
        %HB is HA - 2;                  
        HB is HA - 1;                   
        HB is HA + 1),
        HB > 0, size(Size), HB =< Size,
        neighbor(A, B).
        



check_rows(state(_A, XPos,OPos), x, Value) :-
      get_rows_one(XPos, OPos, [], Val1),
      get_rows_two(XPos, OPos, [], Val2),
      Value is Val1 + Val2.

check_rows(state(_A, XPos,OPos), o, Value) :-
      get_rows_one(OPos, XPos, [], Val1),
      get_rows_two(OPos, XPos, [], Val2),
      Value is Val1 + Val2.



get_rows_one([H|APos], BPos, Acc , Value):-
      \+ member(H,Acc),
      append(APos, BPos, List),
      rows_one(H, List, Val1),
      append(APos,[H],APosNew),
      get_rows_one(APosNew, BPos, [H|Acc], Val2),
      Value is Val1 + Val2.

get_rows_one(_, _, _,0).


get_rows_two([H|APos], BPos, Acc , Value):-
      \+ member(H, Acc),
      rows_two([H|APos], BPos, Val1),
      append(APos,[H],APosNew),
      get_rows_two(APosNew, BPos,[H|Acc], Val2),
      Value is Val1 + Val2.

get_rows_two(_, _, _,0).

rows_one(H, List, Value):-
     bagof(Val, row_one(H, List, Val), Value1),
     bagof(Val2, row_one_diag(H, List, Val2), Value2),
     append(Value1, Value2, ValList),
     sumlist(ValList, Value).

rows_two(APos, BPos, Value):-
      bagof(Val1, row_two(APos, BPos, Val1), Value1),
      bagof(Val2, row_two_diag(APos, BPos, Val2), Value2),
      append(Value1, Value2, ValList),
      sumlist(ValList, Value).

%Search for horizontal and vertical rows with 1 of the players symbol and none of the other player.

% for 2 dimensions

row_one([X,Y],List,1):-
      \+ inlistx(X, List);
      \+ inlisty(Y,List).

% for three dimensions

row_one([X,Y,Z],List,1):-
      \+ inlist3dx([X,Y,Z], List);
      \+ inlist3dy([X,Y,Z],List);
      \+ inlist3dz([X,Y,Z],List).

row_one(_,_,0).

%search for diagonal rows with 1 symbol of player and none of the other player

row_one_diag([X,Y], List,1):-
      not_diag1([X,Y], List);
      not_diag2([X,Y], List).


% 3 dimensions

row_one_diag([X,Y,Z], B, 1):-
      not_diag1x([X,Y,Z],B);
      not_diag1y([X,Y,Z],B);
      not_diag1z([X,Y,Z],B);
      not_diag2x([X,Y,Z],B);
      not_diag2y([X,Y,Z],B);
      not_diag2z([X,Y,Z],B);
      not_diag_3d1([X,Y,Z],B);
      not_diag_3d2([X,Y,Z],B);
      not_diag_3d3([X,Y,Z],B);
      not_diag_3d4([X,Y,Z],B).

row_one_diag(_,_,0).

% Search for rows with 2 symbols of the player and none of the other player.

% for 2 dimensions:

row_two([[X,_]|APos], BPos, 4):-
      \+ inlistx(X, BPos),
      inlistx(X, APos),
      select([X,_],APos, APosNew),!,
      \+ inlistx(X ,APosNew).

row_two([[_,Y]|APos], BPos, 4):-
      \+ inlisty(Y, BPos),
      inlisty(Y, APos),
      select([_,Y],APos, APosNew),!,
      \+ inlisty(Y ,APosNew).

% for 3 dimensions

row_two([[X,Y,Z]|APos], BPos, 4):-
      \+ inlist3dx([X,Y,Z], BPos),
      inlist3dx([X,Y,Z], APos),
      select([_,Y,Z],APos, APosNew),!,
      \+ inlist3dx([X,Y,Z] ,APosNew).

row_two([[X,Y,Z]|APos], BPos, 4):-
      \+ inlist3dy([X,Y,Z], BPos),
      inlist3dy([X,Y,Z], APos),
      select([X,_,Z],APos, APosNew),!,
      \+ inlist3dy([X,Y,Z] ,APosNew).

row_two([[X,Y,Z]|APos], BPos, 4):-
      \+ inlist3dz([X,Y,Z], BPos),
      inlist3dz([X,Y,Z], APos),
      select([X,Y,_],APos, APosNew),!,
      \+ inlist3dz([X,Y,Z] ,APosNew).

row_two(_,_, 0).

% search for diagonal rows with 2 symbols of player and none of the other.

row_two_diag([[X1,Y1]|APos], BPos, 4):-
      check_diag1([X1,Y1],APos),
      not_diag1([X1,Y1],BPos).

row_two_diag([[X1,Y1]|APos], BPos, 4):-
      check_diag2([X1,Y1],APos),
      not_diag2([X1,Y1],BPos).

% 3 dimensions

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag1x([X,Y,Z],APos),
      not_diag1x([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag1y([X,Y,Z],APos),
      not_diag1y([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag1z([X,Y,Z],APos),
      not_diag1z([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag2x([X,Y,Z],APos),
      not_diag2x([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag2y([X,Y,Z],APos),
      not_diag2y([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag2z([X,Y,Z],APos),
      not_diag2z([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag_3d1([X,Y,Z],APos),
      not_diag_3d1([X,Y,Z],BPos).

row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag_3d2([X,Y,Z],APos),
      not_diag_3d2([X,Y,Z],BPos).
      
row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag_3d3([X,Y,Z],APos),
      not_diag_3d3([X,Y,Z],BPos).
      
row_two_diag([[X,Y,Z]|APos], BPos, 4):-
      check_diag_3d4([X,Y,Z],APos),
      not_diag_3d4([X,Y,Z],BPos).

row_two_diag(_, _, 0).


inlistx(X, [[X|_]|_]).

inlistx(X, [_|T]):-
      inlistx(X,T).


inlisty(Y, [[_,Y|_]|_]).

inlisty(Y, [_|T]):-
      inlisty(Y, T).

inlistz(Z, [[_,_,Z]|_]).

inlistz(Z, [_|T]):-
      inlistz(Z,T).

inlist3dx([_,Y,Z], [[_,Y,Z]|_]).
inlist3dx([X,Y,Z], [_|T]):-
     inlist3dx([X,Y,Z], T).

inlist3dy([X,_,Z], [[X,_,Z]|_]).
inlist3dy([X,Y,Z], [_|T]):-
     inlist3dy([X,Y,Z], T).


inlist3dz([X,Y,_], [[X,Y,_]|_]).
inlist3dz([X,Y,Z], [_|T]):-
     inlist3dz([X,Y,Z], T).


% 2 dimensions

check_diag1([A,A],APos):-
      member([B,B], APos),
      select([B,B],APos,APosNew), !,
      not_diag1([A,A],APosNew).

check_diag2([X1,Y1],APos):-
      diag2(D),
      member([X1,Y1], D),
      member([X2,Y2], APos),
      Y2 - Y1 =:= X1 - X2,
      select([X2,Y2],APos,APosNew), !,
      not_diag2([X1,Y1],APosNew).

% 3 dimensions

check_diag1x([X,A,A],APos):-
      member([X,B,B], APos),
      select([X,B,B],APos,APosNew), !,
      not_diag1x([X,A,A],APosNew).

check_diag1y([A,Y,A],APos):-
      member([B,Y,B], APos),
      select([B,Y,B],APos,APosNew),!,
      not_diag1y([A,Y,A],APosNew).

check_diag1z([A,A,Z],APos):-
      member([B,B,Z], APos),
      select([B,B,Z],APos,APosNew),!,
      not_diag1z([A,A,Z],APosNew).

check_diag2x([X,Y,Z],APos):-
      diag2(D),
      member([Y,Z], D),
      member([X,Y2,Z2], APos),
      Y2 - Y =:= Z - Z2,
      select([X,Y2,Z2],APos,APosNew),!,
      not_diag2x([X,Y,Z],APosNew).

check_diag2y([X,Y,Z],APos):-
      diag2(D),
      member([X,Z], D),
      member([X2,Y,Z2], APos),
      X2 - X =:= Z - Z2,
      select([X2,Y,Z2],APos,APosNew),!,
      not_diag2y([X,Y,Z],APosNew).

check_diag2z([X,Y,Z],APos):-
      diag2(D),
      member([X,Y], D),
      member([X2,Y2,Z], APos),
      X2 - X =:= Y - Y2,
      select([X2,Y2,Z],APos,APosNew),!,
      not_diag2z([X,Y,Z],APosNew).

check_diag_3d1(A,APos):-
      diag_3d1(D),
      member(A,D),
      member(B,APos),
      member(B,D),
      select(B,APos, APosNew),!,
      not_diag_3d1(A,APosNew).

check_diag_3d2(A,APos):-
      diag_3d2(D),
      member(A,D),
      member(B,APos),
      member(B,D),
      select(B,APos, APosNew),!,
      not_diag_3d2(A,APosNew).

check_diag_3d3(A,APos):-
      diag_3d3(D),
      member(A,D),
      member(B,APos),
      member(B,D),
      select(B,APos, APosNew),!,
      not_diag_3d3(A,APosNew).

check_diag_3d4(A,APos):-
      diag_3d4(D),
      member(A,D),
      member(B,APos),
      member(B,D),
      select(B,APos, APosNew), !,
      not_diag_3d4(A,APosNew).

diag2([[1,3],[2,2],[3,1]]).

not_diag1(_,[]).

not_diag1([X,X], [[X2,Y2]|APos]):-
      Y2 =\= X2,
      not_diag1([X,X],APos).

not_diag2(_,[]).

not_diag2([X1,Y1], [[X2,Y2]|APos]):-
      diag2(D),
      member([X1,Y1], D),
      Y2 - Y1 =\= X1 - X2,
      not_diag2([X1,Y1],APos).


not_diag1x([X,A,A], [[X,Y2,Z2]|APos]):-
      Y2 =\= Z2,
      not_diag1x([X,A,A], APos).

not_diag1x([X,A,A], [[X2,_,_]|APos]):-
      X2 =\= X,
      not_diag1x([X,A,A], APos).

not_diag1x(_,[]).

not_diag1y([A,Y,A], [[X2, Y, Z2]|APos]):-
      X2 =\= Z2,
      not_diag1y([A,Y,A],APos).

not_diag1y([A,Y,A], [[_, Y2, _]|APos]):-
      Y2 =\= Y,
      not_diag1y([A,Y,A],APos).
      
not_diag1y(_,[]).

not_diag1z([A,A,Z], [[X2, Y2, Z]|APos]):-
      X2 =\= Y2,
      not_diag1z([A,A,Z],APos).

not_diag1z([A,A,Z], [[_, _,Z2]|APos]):-
      Z2 =\= Z,
      not_diag1z([A,A,Z],APos).

not_diag1z(_,[]).

not_diag2x([X,Y,Z], [[X, Y2, Z2]|APos]):-
      diag2(D),
      member([Y,Z], D),
      Y2 - Y =\= Z - Z2,
      not_diag2x([X,Y,Z], APos).

not_diag2x([X,Y,Z], [[X2, _, _]|APos]):-
      diag2(D),
      member([Y,Z], D),
      X =\= X2,
      not_diag2x([X,Y,Z], APos).

not_diag2x(_,[]).

not_diag2y([X,Y,Z], [[X2, Y, Z2]|APos]):-
      diag2(D),
      member([X,Z], D),
      X2 - X =\= Z - Z2,
      not_diag2y([X,Y,Z], APos).

not_diag2y([X,Y,Z], [[_, Y2, _]|APos]):-
      diag2(D),
      member([X,Z], D),
      Y =\= Y2,
      not_diag2y([X,Y,Z], APos).

not_diag2y(_,[]).

not_diag2z([X,Y,Z], [[X2, Y2, Z]|APos]):-
      diag2(D),
      member([X,Y], D),
      X2 - X =\= Y - Y2,
      not_diag2z([X,Y,Z], APos).

not_diag2z([X,Y,Z], [[_, _, Z2]|APos]):-
      diag2(D),
      member([X,Y], D),
      Z =\= Z2,
      not_diag2z([X,Y,Z], APos).

not_diag2z(_,[]).

diag_3d1([[1,1,1],[2,2,2],[3,3,3]]).
diag_3d2([[1,1,3],[2,2,2],[3,3,1]]).
diag_3d3([[1,3,1],[2,2,2],[3,1,3]]).
diag_3d4([[1,3,3],[2,2,2],[3,1,1]]).

not_diag_3d1(A,[H|T]):-
      diag_3d1(D),
      member(A,D),
      \+ member(H, D),
      not_diag_3d1(A,T).

not_diag_3d1(_,[]).

not_diag_3d2(A,[H|T]):-
      diag_3d2(D),
      member(A,D),
      \+ member(H, D),
      not_diag_3d2(A,T).

not_diag_3d2(_,[]).

not_diag_3d3(A,[H|T]):-
      diag_3d3(D),
      member(A,D),
      \+ member(H, D),
      not_diag_3d3(A,T).

not_diag_3d3(_,[]).

not_diag_3d4(A,[H|T]):-
      diag_3d4(D),
      member(A,D),
      \+ member(H, D),
      not_diag_3d4(A,T).

not_diag_3d4(_,[]).
