/* Ce programme met en oeuvre l'algorithme Minmax (avec convention negamax) et l'illustre sur le jeu du TicTacToe (morpion 3x3) */ :- [tictactoe]. /**************************************************** ALGORITHME MINMAX avec convention NEGAMAX : negamax/5 *****************************************************/ /* negamax(+J, +Etat, +P, +Pmax, [?Coup, ?Val]) SPECIFICATIONS : retourne pour un joueur J donne, devant jouer dans une situation donnee Etat, de profondeur donnee P, le meilleur couple [Coup, Valeur] apres une analyse pouvant aller jusqu'a la profondeur Pmax. Il y a 3 cas a decrire (donc 3 clauses pour negamax/5) 1/ la profondeur maximale est atteinte : on ne peut pas developper cet Etat ; il n'y a donc pas de coup possible a jouer (Coup = rien) et l'evaluation de Etat est faite par l'heuristique. 2/ la profondeur maximale n'est pas atteinte mais J ne peut pas jouer ; au TicTacToe un joueur ne peut pas jouer quand le tableau est complet (totalement instancie) ; il n'y a pas de coup a jouer (Coup = rien) et l'evaluation de Etat est faite par l'heuristique. 3/ la profondeur maxi n'est pas atteinte et J peut encore jouer. Il faut evaluer le sous-arbre complet issu de Etat ; - on determine d'abord la liste de tous les couples [Coup_possible, Situation_suivante] via le predicat successeurs/3 (deja fourni, voir plus bas). - cette liste est passee a un predicat intermediaire : loop_negamax/5, charge d'appliquer negamax sur chaque Situation_suivante ; loop_negamax/5 retourne une liste de couples [Coup_possible, Valeur] - parmi cette liste, on garde le meilleur couple, c-a-d celui qui a la plus petite valeur (cf. predicat meilleur/2); soit [C1,V1] ce couple optimal. Le predicat meilleur/2 effectue cette selection. - finalement le couple retourne par negamax est [Coup, V2] avec : V2 is -V1 (cf. convention negamax vue en cours). A FAIRE : ECRIRE ici les clauses de negamax/5 ..................................... */ % cas 1 negamax(J, Etat, Pmax, Pmax, [[], Val]) :- heuristique(J, Etat, Val), !. % cas 2 negamax(J, Etat, _, _, [[], Val]):- ground(Etat), heuristique(J, Etat, Val), !. % cas 3 negamax(J, Etat, P, Pmax, [Coup, Val]):- successeurs(J,Etat,Succ), loop_negamax(J,P,Pmax,Succ, List), meilleur(List, [Coup,MVal]), Val is MVal*(-1). /******************************************* DEVELOPPEMENT D'UNE SITUATION NON TERMINALE successeurs/3 *******************************************/ /* successeurs(+J,+Etat, ?Succ) retourne la liste des couples [Coup, Etat_Suivant] pour un joueur donne dans une situation donnee */ successeurs(J,Etat,Succ) :- copy_term(Etat, Etat_Suiv), findall([Coup,Etat_Suiv], successeur(J,Etat_Suiv,Coup), Succ). /************************************* Boucle permettant d'appliquer negamax a chaque situation suivante : *************************************/ /* loop_negamax(+J,+P,+Pmax,+Successeurs,?Liste_Couples) retourne la liste des couples [Coup, Valeur_Situation_Suivante] a partir de la liste des couples [Coup, Situation_Suivante] */ loop_negamax(_,_,_,[],[]). loop_negamax(J,P,Pmax,[[Coup,Suiv]|Succ], [[Coup,Vsuiv]|Reste_Couples]) :- loop_negamax(J,P,Pmax,Succ,Reste_Couples), adversaire(J,A), Pnew is P+1, negamax(A,Suiv,Pnew,Pmax, [_,Vsuiv]). /* A FAIRE : commenter chaque litteral de la 2eme clause de loop_negamax/5, en particulier la forme du terme [_,Vsuiv] dans le dernier litteral ? */ /* J --> Symbole du joueur P --> profondeur actuelle Pmax --> profondeur maximale [[Coup, Suiv] | Succ] --> Itération sur la liste de couple (Coup avec l'état Suiv où on arrive) puis le reste de la liste Succ [[Coup,Vsuiv] | Reste_Couples] --> Liste de couple (Coup, VSuiv). VSuiv indique si c'est un bon ou mauvais coup à jouer */ /********************************* Selection du couple qui a la plus petite valeur V *********************************/ /* meilleur(+Liste_de_Couples, ?Meilleur_Couple)*/ /* SPECIFICATIONS : On suppose que chaque element de la liste est du type [C,V] - le meilleur dans une liste a un seul element est cet element - le meilleur dans une liste [X|L] avec L \= [], est obtenu en comparant X et Y,le meilleur couple de L Entre X et Y on garde celui qui a la petite valeur de V. A FAIRE : ECRIRE ici les clauses de meilleur/2 */ meilleur([[Coup, Valeur]], [Coup, Valeur]). meilleur([[Coup, Valeur]|Succ], [MCoup,MValeur]):- meilleur(Succ, [CX, VX]), (Valeur < VX -> MCoup = Coup, MValeur = Valeur ; MCoup = CX, MValeur = VX ). % Tests du prédicat meilleur :- meilleur([[[3,4], 6]],[[3,4], 6]). :- meilleur([[[1,2],7],[[1,4],8],[[2,2],2]],[[2,2],2]). /****************** PROGRAMME PRINCIPAL *******************/ % ?B --> meilleur coup / ?V --> valeur du meilleur coup % Prédicat main main(B,V,Pmax) :- situation_initiale(SI), negamax(x,SI,0,Pmax,[B,V]). % Deuxieme predicat main avec posibilite de choisir le joueur J et la situation S main2(J,S,B,V,Pmax):- negamax(J,S,0,Pmax,[B,V]). /* A FAIRE : Completer puis tester le programme principal pour plusieurs valeurs de la profondeur maximale. Pmax = 1, 2, 3, 4 ... Commentez les resultats obtenus. */ % Q1 % Tests sur la profondeur de Pmax :- main([],0,0). % avec Pmax = 0 --> on ne lance pas la recherche de meilleur coup :- main([2,2],4,1). :- main([2,2], 1, 2). :- main([2,2],3,5). % main(B,V,9). --> débordement de pile % Pour l'état initial, peu importe le nombre Pmax on obtient toujours la case du milieu en coup à jouer. % Cependant, la valeur V change,on effet elle est plus petite quand P est pair (prise en compte plus forte du coup de l'adversaire) % De plus la valeur V diminue également au fur et à mesure quand on se rapproche de la grille finale (9 coups joués) car si tous les jouoeurs jouent bien, il n'y a aucun gagnants. % Exemple d'une partie ou les 2 joueurs jouent les coups optimaux --> pas de gagnants :- A=[[_,_,_],[_,_,_],[_,_,_]], main2(x,A,[2,2],3,3). :- A=[[_,_,_],[_,x,_],[_,_,_]], main2(o,A,[3,3],-1,3). :- A=[[_,_,_],[_,x,_],[_,_,o]], main2(x,A,[2,1],3,3). :- A=[[_,_,_],[x,x,_],[_,_,o]], main2(o,A,[2,3],-1,3). :- A=[[_,_,_],[x,x,o],[_,_,o]], main2(x,A,[1,3],2,3). :- A=[[_,_,x],[x,x,o],[_,_,o]], main2(o,A,[3,1],0,3). :- A=[[_,_,x],[x,x,o],[o,_,o]], main2(x,A,[3,2],0,3). :- A=[[_,_,x],[x,x,o],[o,x,o]], main2(o,A,[1,2],0,3). :- A=[[_,o,x],[x,x,o],[o,x,o]], main2(x,A,[1,1],0,3). :- A=[[x,o,x],[x,x,o],[o,x,o]], main2(x,A,[],0,3). %Q2 en utilisant des rotations comme pour le jeu de bois du S1. On pourrait voir ainsi si la situation n'a pas deja ete % calculee % Q3 Que le coup gagnant soit quand on a 4 symboles identiques allignes. Il faudra aussi changer le predicat successeur % (en effet on ne peut mettre des jetons que sur d'autres jetons ou sur le sol) % Q4 // Insert alpha beta