Introduction à l'Intelligence Artificielle

L'objectif de cette séance est d'approfondir la connaissance de Prolog par la réalisation d'une application classique : la résolution du jeu Mastermind. L'environnement choisi est toujours celui de SWI-Prolog (http://www.swi-prolog.org/). A l'issue de cette séance vous aurez découvert les prédicats d'entrées/sorties, la négation, et le méta-prédicat findall/3 qui permet d'obtenir la liste de toutes les valeurs que prend une variable pour satisfaire un prédicat donné.

Cette séance est organisée en 3 séquences supposées durer chacune environ 25 minutes : les 3 séquences mises bout à bout tiennent donc probablement en 1h30, mais surveillez l'heure tout de même. En fin de séance, vous devrez envoyer par mél les prédicats que vous avez définis.

Ce T.P. est très largement inspiré d'un exemple donné dans « L'art de Prolog », Leon Sterling & Ehud Shapiro, édition Masson, 1990, pp 332-336.

Le Mastermind est un jeu de réflexion à 2 joueurs. Le joueur 1 choisit secrètement une combinaison de pions : les pions sont identifiés par leur couleur, une combinaison est une liste ordonnée de pions. Le joueur 2 doit deviner cette combinaison : couleur et position des pions. A chaque tour, le joueur 2 propose une combinaison de pions et le joueur 1 indique seulement le nombre de pions bien placés (les pions de la bonne couleur et à la bonne position) et le nombre de pions mal placés (les pions de la bonne couleur mais à une mauvaise position). Le jeu se termine lorsque le joueur 2 devine la combinaison choisie par le joueur 1. Nous prenons une version simple du jeu Mastermind dans laquelle la combinaison à trouver ne comporte aucun trou, et ne comporte pas plusieurs fois un pion d'une même couleur. Nous coderons la couleur des pions par des entiers, et les combinaisons par les listes Prolog.

Le principe de résolution du jeu que vous allez implanter en Prolog est le suivant :

1. générer une combinaison ;
2. vérifier qu'elle est compatible avec toutes les propositions déjà faites, sinon revenir en 1 ;
3. proposer cette combinaison à l'adversaire et enregistrer sa réponse ;
4. recommencer en 1 si l'adversaire ne répond pas que tous les pions sont bien placés.

Avec le prédicat prédéfini select/3, définissez le prédicat tirer/2 qui réussit lorsque la liste passée en 1^er argument ne contient que des éléments de la liste passée en 2^e argument. Le 2^e argument est supposé être une liste instanciée ne contenant aucun doublon. Le 1^er argument est supposé être une liste, et ne doit contenir aucun doublon. Par exemple :

?- tirer([6,2,3],[0,1,2,3,4,5,6]).
true ;
false.

De plus, lorsque le 1^er argument n'est pas instancié mais est une liste d'une certaine longueur, ce prédicat doit, par backtrack, trouver toutes les sous-listes de cette longueur. Le cas où le 1^er argument n'est pas une liste ne nous intéresse pas, et ne sera pas traité.

Vous savez maintenant générer toutes les combinaisons, et tester si une combinaison est compatible avec une combinaison déjà proposée. Avec le prédicat proposer/1 donné ci-dessous, vous pouvez proposer au joueur 1 une combinaison, et l'enregistrer avec la réponse du joueur 1 :

proposer(Proposition) :- 
   write('proposition = '),
   writeln(Proposition),
   write('Combien de pions bien places ?'),
   read(Bp),
   write('Combien de pions mal places ?'),
   read(Mp),
   nl,
   assert(coup_joue(Proposition,Bp,Mp)),
   Bp = 4.

Ce prédicat proposer/1 réussit lorsque la proposition est la combinaison secrète choisie par le joueur 1 (Bp = 4). Ce prédicat enregistre aussi la réponse du joueur 1 sous la forme d'un prédicat coup_joue/3 grâce au prédicat prédéfini assert/1. En invoquant le prédicat coup_joue/3 vous aurez donc accès à tous les coups précédemment joués, et vous pourrez vérifier s'ils sont compatibles.

Voici le prédicat principal du jeu qui vous permettra de tester l'ensemble de votre travail et même de jouer contre l'ordinateur :

mastermind(Sol) :-
   retractall(coup_joue(_,_,_)),
   length(Sol,4),
   tirer(Sol,[1,2,3,4,5,6,7,8,9,0]),
   tenter(Sol).

1. La première ligne « retractall(coup_joue(_,_,_)) » permet de nettoyer le jeu : ce prédicat retire toutes les clauses du prédicat coup_joue/3 éventuellement enregistrées lors d'une partie précédente ;
2. la deuxième ligne « length(Sol,4) » permet de fabriquer une liste de 4 éléments non instanciés. C'est équivalent à « Sol = [_,_,_,_] ». Cela permet de respecter les contraintes indiquées ci-dessus.

Pour terminer, vous devez indiquer à l'interprète Prolog que le prédicat coup_joue/3 est un prédicat dynamique. En effet, en début de partie, aucune clause ne définit le prédicat coup_joue/3. Ce n'est qu'après le 1^er coup qu'on commence à voir apparaître une 1^e clause qui définit ce prédicat dans le programme (cf. proposer/1). Et il ne faut pas que l'interprète indique une erreur lorsque vous chercherez les coups précédemment joués alors qu'il n'y en a pas encore. Pour cela insérez au début de votre fichier « .pl » la ligne suivante :

:- dynamic coup_joue/3.

Cela indique à l'interprète qu'un appel à coup_joue/3 doit échouer si aucune clause ne définit ce prédicat.