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