minimax

#!/usr/bin/swipl

% Game interface

membre(X,[X|_]).
membre(X,[_|L]) :- membre(X,L).

% Permet de reperer s'il y a trois piont alignés
gagne(Jeux,P):-
((Piece1 is P),
(Piece2 is (P + 10)),
(Piece3 is (P + 20)),
(Piece4 is (P + 30)),
(Piece5 is (P + 40)),
(Piece6 is (P + 50)),
(Piece7 is (P + 60)),
(Piece8 is (P + 70)),
(Piece9 is (P + 80))),

(
  % ligne horizontale
  (membre(Piece1,Jeux),membre(Piece2,Jeux),membre(Piece3,Jeux));
  (membre(Piece4,Jeux),membre(Piece5,Jeux),membre(Piece6,Jeux));
  (membre(Piece7,Jeux),membre(Piece8,Jeux),membre(Piece9,Jeux));

  % ligne verticale
  (membre(Piece1,Jeux),membre(Piece4,Jeux),membre(Piece7,Jeux));
  (membre(Piece2,Jeux),membre(Piece5,Jeux),membre(Piece8,Jeux));
  (membre(Piece3,Jeux),membre(Piece6,Jeux),membre(Piece9,Jeux));

  % diagonale
  (membre(Piece1,Jeux),membre(Piece5,Jeux),membre(Piece9,Jeux));
  (membre(Piece3,Jeux),membre(Piece5,Jeux),membre(Piece7,Jeux))
).

selectCase([G1,G2,G3,G4,G5],Cb):-
write('\r\nSelect a square : '),read(Ca),

(
  (
    not(G1 == 0),
    R1 is ((G1 // 10) + 1)
  );
  (
    (G1 == 0),
    R1 is 3540
  )
),
(
  (
    not(G1 == 0),
    R1 is ((G1 // 10) + 1)
  );
  (
    (G1 == 0),
    R1 is 3540
  )
),
(
  (
    not(G1 == 0),
    R1 is ((G1 // 10) + 1)
  );
  (
    (G1 == 0),
    R1 is 3540
  )
),
(
  (
    not(G1 == 0),
    R1 is ((G1 // 10) + 1)
  );
  (
    (G1 == 0),
    R1 is 3540
  )
),
(
  (
    not(G1 == 0),
    R1 is ((G1 // 10) + 1)
  );
  (
    (G1 == 0),
    R1 is 3540
  )
),
(
  (
    not(R1 == Ca),
    not(R2 == Ca),
    not(R3 == Ca),
    not(R4 == Ca),
    not(R5 == Ca),
    (
      (Ca == 1);
      (Ca == 2);
      (Ca == 3);
      (Ca == 4);
      (Ca == 5);
      (Ca == 6);
      (Ca == 7);
      (Ca == 8);
      (Ca == 9)
    ),
    (Cb is Ca)
  );
  (
    (
      (
        (R1 == Ca);
        (R2 == Ca);
        (R3 == Ca);
        (R4 == Ca);
        (R5 == Ca)
      ),
      (
        (Ca == 1);
        (Ca == 2);
        (Ca == 3);
        (Ca == 4);
        (Ca == 5);
        (Ca == 6);
        (Ca == 7);
        (Ca == 8);
        (Ca == 9)
      )
    ),
    write('\r\nThere is already something on the square '),
    write(Ca),
    write(', please choose another one'),
    selectCase([G1,G2,G3,G4,G5],Cb)
  );
  (
    write('\r\nIncorect square '),
    write(Ca),
    write(', please choose another one'),
    selectCase([G1,G2,G3,G4,G5],Cb)
  )
)
,!
.

selectPlayer(Player):-
write('Select your player (x or o) : '),read(Pl),
(
  (
    not(Pl == x),not(Pl == o),
    write('Please enter x or o\r\n'),
    selectPlayer(Player)
  )
  ;
  (
    ((Pl == x);(Pl == o)),(Player == Pl)
  )
)
.

playerTurn([GB1,GB2,GB3,GB4,GB5], [GA1,GA2,GA3,GA4,GA5], Position, Player):-

selectCase([GB1,GB2,GB3,GB4,GB5],Ca), % enlever position

(
  (Position < 6);
  (
    (
      (Position == 6), (Position is 1) 
    );
    (
      (Position == 7), (Position is 2) 
    );
    (
      (Position == 8), (Position is 3) 
    )
  )
),
Player2 is (Player mod 2) + 1,

(
  (
    (Position < 5),(NewPosition is Position + 1)
  );
  (
    (
      (Position == 5), (NewPosition is 1) 
    );
    (
      (Position == 6), (NewPosition is 2) 
    );
    (
      (Position == 7), (NewPosition is 3) 
    )
  )
),

(
  (
    (Position < 4),(NewPosition2 is Position + 2)
  );
  (
    (
      (Position == 4), (NewPosition2 is 1) 
    );
    (
      (Position == 5), (NewPosition2 is 2) 
    );
    (
      (Position == 6), (NewPosition2 is 3) 
    )
  )
),

(((Position == 1),(GA1 is Player+((Ca-1)*10)));(not(Position == 1),(GA1 is GB1))),
(((Position == 2),(GA2 is Player+((Ca-1)*10)));(not(Position == 2),(GA2 is GB2))),
(((Position == 3),(GA3 is Player+((Ca-1)*10)));(not(Position == 3),(GA3 is GB3))),
(((Position == 4),(GA4 is Player+((Ca-1)*10)));(not(Position == 4),(GA4 is GB4))),
(((Position == 5),(GA5 is Player+((Ca-1)*10)));(not(Position == 5),(GA5 is GB5))),

affichage([GA1,GA2,GA3,GA4,GA5,1,1]),

(
  (
    gagne([GA1,GA2,GA3,GA4,GA5],Player),write('\r\nYou are the winner !!\r\n\r\n'),game
  );
  not(gagne([GA1,GA2,GA3,GA4,GA5],Player))
),


write('\r\nComputer is playing'),

choice([GA1,GA2,GA3,GA4,GA5,Player2,NewPosition],[S1,S2,S3,S4,S5,S6,S7],4),affichage([S1,S2,S3,S4,S5,S6,S7]),

(
  (
    gagne([S1,S2,S3,S4,S5,S6,S7],Player2),write('\r\nThe computer is the winner !!\r\n\r\n'),game
  );
  not(gagne([S1,S2,S3,S4,S5,S6,S7],Player2))
),

playerTurn([S1,S2,S3,S4,S5],[G1,G2,G3,G4,G5],NewPosition2,Player).


game:-write('Hello !\r\nWelcome at Morpion !\r\n'),
(
 % (selectPlayer(x),write('You are player X'),(Player is 1));
  (write('You are player O'),(Player is 2))
),
write('\r\nGrid : \r\n1|2|3\r\n- - -\r\n4|5|6\r\n- - -\r\n7|8|9'),
playerTurn([0,0,0,0,0],[GA1,GA2,GA3,GA4,GA5],1,Player),!.

%------------------------------------------------------------------------------------
%Rules defining minimum/maximum of a number-list :
min([A],A).
min([A|B],R):-min(B,S),R is min(A,S).

max([A],A).
max([A|B],R):-max(B,S),R is max(A,S).

%Rules defining min/max of a list of sublists, each one formed by two elements, the first being a number :
%Those are used in the first minmax iteration (choice), where we wanna discover the best move, and not
%the best score.
minM([A,B],[C,_],[A,B]):-A<C.
minM([A,_],[C,D],[C,D]):-A>=C.
minM([[A,B]],[A,B]).
minM([[A,B]|C],[RA,RB]):-minM(C,S),minM([A,B],S,[RA,RB]).

maxM([A,B],[C,_],[A,B]):-A>=C.
maxM([A,_],[C,D],[C,D]):-A<C.
maxM([[A,B]],[A,B]).
maxM([[A,B]|C],[RA,RB]):-maxM(C,S),maxM([A,B],S,[RA,RB]).

%By encapsulating branch(),minimax() with evalChild(), we can use setof to create list of scores of all
%children verifying minmax(). We will then be able to find the minimum score amongst it, using the rule min()
%previously defined.
evalChild(Node,Score,Level):-desc(Node,Child),minimax(Child,Score,Level).

%Once the maximum recursion level is reached we evaluate the the leaves.
minimax(Leaf,Score,0):-eval(Score,Leaf).

%While the recursion level has not been reached, keep on building the tree. The min/max alternance is acheived
%by switching the Score sign at each iteration and always calculating the maximum.
minimax(Node,Score,Level):-Level>0,NewLev is Level-1,setof(A,evalChild(Node,A,NewLev),ScoreList),
min(ScoreList,NewScore),Score is -NewScore.

%First predicate to evaluate, this is cut from the algorithm body to allow us to get the best move, and not
%its score as we would have obtained by calling directly minimax().
evalMove(Game,Move,MoveScore,Level):-desc(Game,Move),minimax(Move,MoveScore,Level).

choice(Game,Move,Level):-NewLev is Level-1,setof([MoveScore,Move],evalMove(Game,Move,MoveScore,NewLev),List),
%write(List),
put(10),minM(List,[Score,Move]),NewScore is Score.
%write(NewScore).

%This algorithm may prove wrong when used with a odd heuristic (in this case we can only test 2).

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

%Modelisation of a game state and of an eval function for a game :

%Regarde si la grille S peut être le tour suivant de la grille L avec l’ajout de P (rond ou croix). C est le
%compteur qui correspond à la dernière pièce ajoutée (va de 1 à 5)

% Fonction outils

% nieme(N,X,Y) est vrai si Y est le nième element de la liste X
nieme(1, [H|_], H).
nieme(N, [_|T], Z) :-
N > 0,
N1 is N - 1,
nieme(N1, T, Z).
%rang(N,Y,X) est vrai si N est le rang de l'élément X dans la liste Y
rang(0,X,[X|_]).
rang(N,X,[_|LB]) :- var(N),rang(M,X,LB),N is M+1.
rang(N,X,[_|LB]) :- nonvar(N),M is N-1,rang(M,X,LB).

% On encapsule nieme pour corriger le fait que C soit < 0
niemec(N,X,Y):-N == 0,nieme(5,X,Y).
niemec(N,X,Y):-N == -1,nieme(4,X,Y).
niemec(N,X,Y):-N == -2,nieme(3,X,Y).
niemec(N,X,Y):-N == -3,nieme(2,X,Y).
niemec(N,X,Y):-(N > 0),nieme(N,X,Y).
% pour rang on aura :
rangc(N,Y,X):-N=<0,-N=<5,M is 5+N,rang(M,Y,X).
rangc(N,Y,X):-N>0,rang(N,Y,X).
% Jeux = [11,22,32,51,92].

%desc([L1,L2,L3,L4,L5,LP,C],[S1,S2,S3,S4,S5,SP,SC]):-
%SC is (C+1) mod 5,
%(LP == 2, SP is 1);(LP == 1, SP is 2),
%R1 is C - 1, niemec(R1,[L1,L2,L3,L4,L5],A1),niemec(R1,[S1,S2,S3,S4,S5],A1),
%R2 is C - 2, niemec(R2,[L1,L2,L3,L4,L5],A2),niemec(R2,[S1,S2,S3,S4,S5],A2),
%R3 is C - 3, niemec(R3,[L1,L2,L3,L4,L5],A3),niemec(R3,[S1,S2,S3,S4,S5],A3),
%R4 is C - 4, niemec(R4,[L1,L2,L3,L4,L5],A4),niemec(R4,[S1,S2,S3,S4,S5],A4),
%niemec(C,[S1,S2,S3,S4,S5],V), between(0,90,V), SP is V mod 10.

desc(P,E):-eval(Score,P),(Score==100;Score==(-100)),E = P,!. %There is no descendent for a game that's been won by any of the players.
desc([L1,L2,L3,L4,L5,P,C],[S1,S2,S3,S4,S5,SP,SC]):-
SC is (C mod 5)+1,
((P == 2, SP is 1);(P == 1, SP is 2)),
R1 is C - 1, niemec(R1,[L1,L2,L3,L4,L5],A1),!,niemec(R1,[S1,S2,S3,S4,S5],A1),!,
R2 is C - 2, niemec(R2,[L1,L2,L3,L4,L5],A2),!,niemec(R2,[S1,S2,S3,S4,S5],A2),!,
R3 is C - 3, niemec(R3,[L1,L2,L3,L4,L5],A3),!,niemec(R3,[S1,S2,S3,S4,S5],A3),!,
R4 is C - 4, niemec(R4,[L1,L2,L3,L4,L5],A4),!,niemec(R4,[S1,S2,S3,S4,S5],A4),!,
nieme(C,[S1,S2,S3,S4,S5],V),!, between(0,90,V), P is V mod 10,
((S1 == 0,V1 is 100);(S1 > 0,V1 is S1 // 10)),
((S2 == 0,V2 is 100);(S2 > 0,V2 is S2 // 10)),
((S3 == 0,V3 is 100);(S3 > 0,V3 is S3 // 10)),
((S4 == 0,V4 is 100);(S4 > 0,V4 is S4 // 10)),
((S5 == 0,V5 is 100);(S5 > 0,V5 is S5 // 10)),
%write([V1,V2,V3,V4,V5]),
((not(V1 == V2),not(V1 == V3),not(V1 == V4),not(V1 == V5));V1==100),
((not(V2 == V3),not(V2 == V4),not(V2 == V5));V2==100),
((not(V3 == V4),not(V3 == V5));V3==100),
(not(V4 == V5);V4==100).

%Evaluation function:
%Let 0 stand for an unused area
%Let 1 stand for the computer symbol
%Let 2 stand for the user symbol

eval(Score,[A1,A2,A3,A4,A5,_,_]):-win([A1,A2,A3,A4,A5]),Score is 100,!. %If "Game" is a winning move, Score is maximum
eval(Score,[A1,A2,A3,A4,A5,_,_]):-lose([A1,A2,A3,A4,A5]),Score is -100,!. %If "Game" is a losing move, Score is minimum
eval(Score,[A1,A2,A3,A4,A5,_,_]):-win([A1,A2,A3,A4,A5]),Score is 100,!. %If "Game" is a winning move, Score is maximum
eval(Score,[A1,A2,A3,A4,A5,_,_]):-lose([A1,A2,A3,A4,A5]),Score is -100,!. %If "Game" is a losing move, Score is minimum
eval(Score,[A1,A2,A3,A4,A5,_,_]):-count([A1,A2,A3,A4,A5],MT,1,2),count([A1,A2,A3,A4,A5],HT,2,2),Score is MT*10-HT*10.

win(Game):-count(Game,NT,1,3),NT>0.
lose(Game):-count(Game,NT,2,3),NT>0.

%count(Game,NT,Player,N) is true when NT is the number of lines/columns/diags where player "Player" has N marks
count(Game,NT,Player,N):- (setof(X,line(Game,Player,X,N),NbL),length(NbL,L);L is 0),!,
(setof(Y,column(Game,Player,Y,N),NbC),length(NbC,C);C is 0),!,
(setof(Z,diag(Game,Player,Z,N),NbD),length(NbD,D);D is 0),!,
NT is (L+C+D).
%line(Game,Player,X,N) is true if the player has N marks on line X
%same for column and diag
line([],_,_,N):-N is 0.
line([First|Game],Player,X,N):-between(0,2,X),A is First mod 10, B is First//30,
A==Player, B==X, line(Game,Player,X,M),N is M+1.
line([First|Game],Player,X,N):-between(0,2,X),A is First mod 10,not(A==Player),line(Game,Player,X,N).
line([First|Game],Player,X,N):-between(0,2,X),B is First//30,not(B==X),line(Game,Player,X,N).

column([],_,_,N):-N is 0.
column([First|Game],Player,Y,N):-between(0,2,Y),A is First mod 10, B is (First//10) mod 3,
A==Player, B==Y, column(Game,Player,Y,M),N is M+1.
column([First|Game],Player,Y,N):-between(0,2,Y),A is First mod 10,not(A==Player),column(Game,Player,Y,N).
column([First|Game],Player,Y,N):-between(0,2,Y),B is (First//10) mod 3,not(B==Y),column(Game,Player,Y,N).

diag([],_,_,N):-N is 0.
diag([First|Game],Player,Z,N):-Z = 0, A is First mod 10, B is First//30 , C is (First//10) mod 3,
A==Player, B==C, diag(Game,Player,Z,M), N is M+1.
diag([First|Game],Player,Z,N):-Z = 0, A is First mod 10, not(A==Player), diag(Game,Player,Z,N).
diag([First|Game],Player,Z,N):-Z = 0, B is First//3, C is First mod 3, not(B==C), diag(Game,Player,Z,N).

diag([First|Game],Player,Z,N):-Z = 1, A is First mod 10, B is First//30 , C is 2-(First//10) mod 3,
A==Player, B==C, diag(Game,Player,Z,M), N is M+1.
diag([First|Game],Player,Z,N):-Z = 1, A is First mod 10, not(A==Player), diag(Game,Player,Z,N).
diag([First|Game],Player,Z,N):-Z = 1, B is First//3, C is First mod 3, not(B==C), diag(Game,Player,Z,N).

%------------------------------------------Display function------------------------------------------

piece(R,A):-R = 1, A = "X".
piece(R,A):-R = 2, A = "O".

position(Pos,V,A1,A2,A3,A4,A5,A6,A7,A8,A9):-
((Pos = 0, A1 = V);
(Pos = 1, A2 = V);
(Pos = 2, A3 = V);
(Pos = 3, A4 = V);
(Pos = 4, A5 = V);
(Pos = 5, A6 = V);
(Pos = 6, A7 = V);
(Pos = 7, A8 = V);
(Pos = 8, A9 = V)),
(A1 = " "; A1 = "X"; A1 = "O"),
(A2 = " "; A2 = "X"; A2 = "O"),
(A3 = " "; A3 = "X"; A3 = "O"),
(A4 = " "; A4 = "X"; A4 = "O"),
(A5 = " "; A5 = "X"; A5 = "O"),
(A6 = " "; A6 = "X"; A6 = "O"),
(A7 = " "; A7 = "X"; A7 = "O"),
(A8 = " "; A8 = "X"; A8 = "O"),
(A9 = " "; A9 = "X"; A9 = "O").

affichage([L1,L2,L3,L4,L5,_,_]):-

P1 is L1 // 10,
P2 is L2 // 10,
P3 is L3 // 10,
P4 is L4 // 10,
P5 is L5 // 10,

R1 is L1 mod 10,
R2 is L2 mod 10,
R3 is L3 mod 10,
R4 is L4 mod 10,
R5 is L5 mod 10,

((piece(R1,Piece1), position(P1,Piece1,A1,A2,A3,A4,A5,A6,A7,A8,A9));(L1 == 0)),
((piece(R2,Piece2), position(P2,Piece2,A1,A2,A3,A4,A5,A6,A7,A8,A9));(L2 == 0)),
((piece(R3,Piece3), position(P3,Piece3,A1,A2,A3,A4,A5,A6,A7,A8,A9));(L3 == 0)),
((piece(R4,Piece4), position(P4,Piece4,A1,A2,A3,A4,A5,A6,A7,A8,A9));(L4 == 0)),
((piece(R5,Piece5), position(P5,Piece5,A1,A2,A3,A4,A5,A6,A7,A8,A9));(L5 == 0)),

write('\r\n'),
put(A1), write('|'), put(A2), write('|'), put(A3), write('\r\n- - -\r\n'), put(A4),
write('|'), put(A5), write('|'),
put(A6), write('\r\n- - -\r\n'), put(A7), write('|'), put(A8), write('|'), put(A9),
write('\r\n'),!.