Un mastermind en Prolog

Publié le 9 juillet 2012

Version PDF Version hors-ligne Version eBooks

IV. Le solveur de mastermind
IV-A. Un client console
IV-B. L' I.A.
IV-C. Quelques résultats.
IV-C-1. Le module de statistiques
IV-C-2. Les résultats
IV-D. Un client XPCE pour faire jouer l'IA

IV. Le solveur de mastermind

Le principe de résolution est simple : on poste les contraintes sur chaque lettre de la proposition en fonction des réponses précédentes et on demande ensuite à Prolog de fournir une proposition cohérente, la première réponse fournie est utilisée.
Dans cet article, le solveur se connecte au serveur.

IV-A. Un client console

Le premier fichier est le fichier gérant la connexion avec le serveur 'mastermind-client.pl' :

Fichier 'mastermind-client.pl'

:- use_module(library(lambda)).
% module de l'IA du mastermind
:- use_module('ia - version 3.0.pl').

% module de calcul des stats lors de test.
:- use_module('mastermind_stats.pl').

% mémorise le numéro de partie
:- dynamic numero/1.

% mémorise le numéro du coup joué
:- dynamic coups/1.

% le prédicat de lancement 
client_mastermind :-
	% on nettoie la base de données
	retractall('ia.pl':guess(_,_)),
	retractall('ia.pl':parametres(_,_,_)),

	retractall(numero(_)),
	retractall(coups(_)),
	assert(coups(0)),
	init_connexion(Len_Proposition) ,
	repeat,
	    % appel de l'IA	
	    bulls_and_cows(Suggestion),
	    % conversion de la suggestion en proposition pour le serveur
	    % [0,1,2,3,4] ==> [97,98,99,100,101] s
	    maplist(\X^Y^(Y is X+97), Suggestion, Ms),
	    
	    % conversion de [97,98,99,100,101] en abcde
	    atom_codes(Guess, Ms),

	    % envoi de la propositon
	    numero(Num),
	    tcp_socket(Socket),
	    Host='localhost', Port=5000,
	    tcp_connect(Socket, Host:Port),
	    tcp_open_socket(Socket, ReadFd, WriteFd),
	    format(WriteFd, '[~w,~w]~n', [Num, Guess]),
	    flush_output(WriteFd),

	    % récupération de la réponse
	    read_line_to_codes(ReadFd, Lst),
	    close(ReadFd),
	    close(WriteFd),
	    atom_codes(Atom, Lst),
	    term_to_atom(Term, Atom),
	    study_answer(Len_Proposition, Term, Guess, Suggestion, Bulls),
	Bulls = Len_Proposition.

% study_answer(+,+)
% on a gagné !
study_answer(Len_Proposition, [-1, [Len_Proposition, Cows]], Guess, _Prop, _Bulls):-
	retract(coups(Coups)),
	Coups1 is Coups + 1,
	assert(coups(Coups1)),
	format('~w Proposition : ~s Bulls= ~w Cows = ~w~n',
	       [Coups1, Guess, Len_Proposition, Cows]),
	writeln('J''ai trouvé !!!').

% cas général
study_answer(_Len_Proposition, [-1, [Bulls, Cows]], Guess, Prop, Bulls):-
	retract(coups(Coups)),
	Coups1 is Coups + 1,
	assert(coups(Coups1)),
	format('~w Proposition : ~s Bulls= ~w Cows = ~w~n', [Coups1, Guess, Bulls, Cows]),
	assert('ia.pl':guess(Prop, [Bulls, Cows])).

% erreur de proposition
% en principe n'arrive jamais !
study_answer(_Len_Proposition, [-2, Mess], _Prop, 0):-
	writeln(Mess).

% init_connexion(-)
% pas de changements importants par rapport au code donné pour le client XPCE
init_connexion(Len_Proposition) :-
	tcp_socket(Socket),
	Host='localhost', Port=5000,
	tcp_connect(Socket, Host:Port),
	tcp_open_socket(Socket, ReadFd, WriteFd),
	
	format(WriteFd, '~w~n', [init_connexion]),
	flush_output(WriteFd),
	read_line_to_codes(ReadFd, Lst),
	close(ReadFd),
	close(WriteFd),
	
	atom_codes(Atom, Lst),
	term_to_atom(Term, Atom),
	Term = [Num, [Len_Proposition, Lettres, Doubles]],
	
	assert('ia.pl':parametres(Len_Proposition, Lettres, Doubles)),
	assert(numero(Num)),
	
	Max is 0'a +Lettres - 1,
	atom_codes(A, [Max]),
	(   Doubles = non
	->  sformat(Str, '\'La proposition est composée de ~w lettres de a à ~w, sans doublons.\'',
		[Len_Proposition, A])
	;   sformat(Str, '\'La proposition est composée de ~w lettres de a à ~w, avec doublons.\'',
		[Len_Proposition, A])),
	writeln(Str).

% pour mémoriser les résultats en cas de test de l'IA
:- dynamic resultat/1.

% test pour étudier l'efficacité de l'IA
test_IA :-
	retractall(resultat(_)),
	assert(resultat([])),

	forall(between(1,50000, _),
	       (   client_mastermind,
	           retract(resultat(Lst)),
	           coups(Coups),
	           assert(resultat([Coups | Lst])))),

	% pour sortir des statistiques
	etudie(resultat).

IV-B. L' I.A.

L'I.A. travaille sur une liste de nombres de 0 à N-1, N étant le nombre de lettres autorisées.
On crée une liste de la bonne longueur, on indique que les éléments de cette liste sont des nombres respectant la consigne précédente.
Ensuite, on poste les contraintes sur chaque élément de la liste en fonction des réponses précédentes puis on demande à Prolog de nous doner une combinaison possible.

Fichier 'ia - version 3.0.pl'

:- module('ia.pl', [bulls_and_cows/1]).
:- use_module(library(clpfd)).
:- use_module(library(lambda)).

% pour mémoriser les propositions et réponses précédentes
:- dynamic guess/2.

% Parametres du moteur de creation / evaluation
% parametre(proposition, Chiffres, Doubles)
:- dynamic parametres/3.

/******************************************************
% exemple
%
% (parametres(5, 8, non)
%
% longueur de la proposition 5
%
% 8 chiffres autorisés 1 ==> 8
%
% Tous les chiffres sont différents
%
*******************************************************/

bulls_and_cows(Guess) :-
	(   tirage(Ms)
	->  Guess = Ms
	;   Guess = 'Désolé, je ne trouve pas de solution !').


% tirage(-)
tirage(Ms) :-
        % On charge les propositions dejà faites
        % La première est tirée au sort
        % les suivantes dépendent des résultats des tirages précédents
        (  bagof([P, R], guess(P,R), Propositions)
        ->  tirage(Propositions, Ms)
        ;   % Pas de solution existante
            tirage_1(Ms)),
        !.

% le premier tirage
% tirage_1(-)
tirage_1(Solution):-
	parametres(Len, Digits, Doubles),
	length(Solution, Len),
	Max is Digits,
	repeat,
		maplist(\X^(X is random(Max)), Solution),
	(   Doubles = non -> all_distinct(Solution); true).


% tirage(+,-)
tirage(L, Ms) :-
	parametres(Len_Proposition, Lettres, Doubles),
	length(Ms, Len_Proposition),

	% la proposition Lettres lettres,
	% donc contient les nombres 0 -> Lettres - 1
	Lettres_1 is Lettres - 1,
	Ms ins 0..Lettres_1,
	(   Doubles = non -> all_distinct(Ms); true),

	% poste les constraintes
	maplist(placees(Ms), L),

	% calcule une solution acceptable
	% la première est retenue
	labeling([ff], Ms).



% placees(+, +])
placees(Sol, [Prop, [BP, MP]]) :-
	V #= 0,

	% calcule les nombres bien placés
	compte_bien_placees(Sol, Prop, V, BP1),
	BP1 #= BP,

	% calcule les nombres mal placés
	compte_mal_placees(Sol, Prop, 0, V, MP1),
	MP1 #= MP .


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% compte_mal_placees(+, +, +, +, -).
% @arg1 : la solution à créer
% @arg2 : Proposition déjà faite
% @arg3 : numéro du premier nombre de la proposition précédente
% @arg4 : compteur courant de nombres mal placés
% @arg5 : compteur fianl de nombres mal placés
%
%
compte_mal_placees(_, [], _, MP, MP).

compte_mal_placees(Sol, [H | T], N, MPC, MPF) :-
	compte_une_mal_placee(H, N, Sol, 0,  0, VF),
	MPC1 #= MPC + VF,
	N1 is N+1,
	compte_mal_placees(Sol, T, N1, MPC1, MPF).


% Ici on travaille sur un nombre d'une proposition déjà faite
% on passe en revue la proposition à créer
% compte_une_mal_placee(+, +, +, +, -).
% @arg1 : le nombre
% @arg2 : le rang de ce nombre
% @arg3 : la proposition à créer
%         on travaille sur chaque nombre de cette proposition
% @arg4 : rang du premier nombre de cette proposition
% @arg5 : compteur courant du nombre mal placé
% @arg6 : compteur final du nombre mal placé
%
compte_une_mal_placee(_H, _N, [], _, TT, TT).

% nombre au même endroit, on continue
compte_une_mal_placee(H, NH, [_H1 | T], NH, TTC, TTF) :-
	NH1 is NH + 1, !,
	compte_une_mal_placee(H, NH, T, NH1, TTC, TTF).

% même nombre à deux endroits différents
% on augmente le compteur et on continue
compte_une_mal_placee(H, NH, [H1 | T], NH1, TTC, TTF) :-
	H #= H1,
	NH \= NH1,
	NH2 is NH1 + 1,
	TTC1 #= TTC + 1,
	compte_une_mal_placee(H, NH, T, NH2, TTC1, TTF).

% nombres différents on continue
compte_une_mal_placee(H, NH, [H1 | T], NH1, TTC, TTF) :-
	H #\= H1,
	NH2 is NH1 + 1,
	compte_une_mal_placee(H, NH, T, NH2, TTC, TTF).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% compte_bien_placees(+, +, +, -)
% @arg1 : proposition à créer
% @arg2 : proposition déjà faite
% @arg3 : compteur courant du nombre bien placé
% @arg4 : compteur final du nombre bien placé
%
compte_bien_placees([], [], MP, MP).

compte_bien_placees([H | T], [H1 | T1], MPC, MPF) :-
	H #= H1,
	MPC1 #= MPC + 1,
	compte_bien_placees(T, T1, MPC1, MPF).

compte_bien_placees([H | T], [H1 | T1], MPC, MPF) :-
	H #\= H1,
	compte_bien_placees(T, T1, MPC, MPF).

IV-C. Quelques résultats.

IV-C-1. Le module de statistiques

Il permet à la suite d'une série de parties de regrouper les résultats et de calculer la moyenne. Par exemple sur 50 parties :

Exemple de résultats statistiques

?- etudie(resultat).
resultat : Min 2, Max 7, Moyenne 5.38
[[1,2],[3,3],[5,4],[15,5],[19,6],[7,7]]

Le code du module :

Fichier 'mastermind_stats.pl'

:- module('mastermind_stats.pl', [etudie/1]).

etudie(Resultat) :-
	call(Resultat, Scores),
	min_list(Scores, Min),
	max_list(Scores, Max),
	sum_list(Scores, Sum),
	length(Scores, Len),
	Moyenne is Sum/Len,
	format('~w : Min ~w, Max ~w, Moyenne ~w~n', [Resultat, Min, Max, Moyenne]),
	msort(Scores, S_Scores),
	packList(S_Scores, P_Scores),
	writeln(P_Scores), nl.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ?- packList([a,a,a,b,c,c,c,d,d,e], L).
%  L = [[3,a],[1,b],[3,c],[2,d],[1,e]] .
%
% ?- packList(R,  [[3,a],[1,b],[3,c],[2,d],[1,e]]).
% R = [a,a,a,b,c,c,c,d,d,e] .
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- use_module(library(clpfd)).

packList([],[]).

packList([X],[[1,X]]) :- !.


packList([X|Rest],[XRun|Packed]):-
    run(X,Rest, XRun,RRest),
    packList(RRest,Packed).


run(Var,[],[1,Var],[]).

run(Var,[Var|LRest],[N1, Var],RRest):-
    N #> 0,
    N1 #= N + 1,
    run(Var,LRest,[N, Var],RRest).


run(Var,[Other|RRest], [1,Var],[Other|RRest]):-
    dif(Var,Other).

IV-C-2. Les résultats

Pour des parties de 5 lettres de a à h sans doublons, des tests ont été effectués en faisant varier la nature des premiers et deuxièmes coups.

Mastermind 5 lettres entre a et h sans doublons

sur 50 000 parties Premier coup aléatoire
resultat : Min 1, Max 9, Moyenne 5.43364
[[3,1],[119,2],[1135,3],[6667,4],[17994,5],[17669,6],[5930,7],[473,8],[10,9]]

sur 50 000 parties premier coup a b c d e, deuxième coup aléatoire
resultat : Min 1, Max 9, Moyenne 5.43594
[[6,1],[114,2],[1141,3],[6674,4],[18017,5],[17560,6],[5922,7],[549,8],[17,9]]

sur 50 000 parties premier coup a b c d e deuxième de e f g h
resultat : Min 1, Max 8, Moyenne 5.48188
[[11,1],[8,2],[865,3],[5741,4],[17864,5],[19736,6],[5428,7],[347,8]]

On peut en conclure que choisir un premier coup aléatoire ou non change peu de choses. Par contre pour le second, il vaut mieux tenir compte du premier coup.
A noter que le temps d'exécution des 50 000 parties tourne autour de 55 minutes.
Pour des parties de 5 lettres de a à h avec doublons, on obtient :

Mastermind 5 lettres entre a et h avec doublons

resultat : Min 1, Max 11, Moyenne 5.59726
[[1,1],[55,2],[750,3],[5491,4],[16750,5],[18468,6],[7061,7],[1274,8],[141,9],[7,10],[2,11]]

On constate qu'il est un peu plus difficile de trouver les solutions lorsqu'il y a des doublons mais ça reste dans le même ordre de nombre de coups.

IV-D. Un client XPCE pour faire jouer l'IA

Pour pouvoir tester l'IA.

fichier 'xpce-local.pl'

:- use_module('ia - version 3.0.pl').
:- use_module(library(lambda)).
:- use_module(library(clpfd)).

:- dynamic proposition/1.
:- dynamic coups/1.


dialog('Mastermind XPCE',
       [ object        :=
	   Client_d,
	 parts         :=
	   [ Client_d  := dialog('Client de mastermind'),
	     GroupBox := dialog_group(paramètres, box),
	     Longueur_item := int_item(longueur),
	     Lettres_item := int_item(lettres),
	     Doubles_item := menu(doubles),
	     Affiche := label(affiche),
	     Combinaison := text_item(combinaison),
	     Button5   := button(ok),
	     Proposition := text_item('proposition   '),
	     BP_item := int_item('bien placées'),
	     MP_item := int_item('mal placées'),
	     Liste :=  browser(resultats),
	     Button2   := button('Recommence'),
	     Button3   := button('Terminé'),
	     Button4   := button('Envoi')
	   ],
	 modifications :=
	   [ GroupBox := [radius := 25,
			  label_font := font(times, bold, 14)],
	     Affiche := [font := font(times, bold, 14)],
	     Combinaison := [value_font := font(times, bold, 15)],
	     Proposition := [value_font := font(times, bold, 15)],
	     Longueur_item := [selection := 5,
			       range := [low := 3,    high := 26]],
	     Lettres_item := [selection := 8,
			      range := [low := 3,    high := 26]],
	     Doubles_item := [append := [non,oui]]
	   ],
	 layout        :=
	   [ area(GroupBox,
		  area(5, 10, 470, 150)),
	     area(Longueur_item,
		  area(15, 40, 120, 60)),
	     area(Lettres_item,
		  area(150, 40, 100, 60)),
	     area(Doubles_item,
		  area(280, 40, 100, 60)),
	     area(Affiche,
		  area(15, 80, 300, 25)),
	     area(Combinaison,
		  area(15, 115, 300, 25)),
	     area(Button5,
		  area(350, 120, 80, 24)),
	     area(Proposition,
		  area(15, 180, 300, 25)),
	     area(BP_item,
		  area(15, 230, 150, 60)),
	     area(MP_item,
		  area(190, 230, 150, 60)),
	     area(Button2,
		  area(500, 16, 80, 24)),
	     area(Button3,
		  area(500, 62, 80, 24)),
	     area(Button4,
		  area(350, 190, 80, 24)),
	     area(Liste,
		  area(15, 270, 450, 200))
	   ],
	 behaviour     :=
	   [
	    Button2 := [message := message(@prolog, recommence,
					   Combinaison, Proposition, BP_item, MP_item, Liste)],
	    Button3 := [message := message(Client_d, destroy)],
	    Button4 := [message := message(@prolog, joue, Proposition, BP_item, MP_item, Liste)],
	    Button5 :=  [message := message(@prolog, test_combinaison,
					    Combinaison, Proposition, BP_item, MP_item)],
	     Longueur_item := [message := message(@prolog, affiche_parametres,
						 Longueur_item?selection,
						 Lettres_item?selection,
						 Doubles_item?selection,
						 Affiche,
						 Combinaison,
						 Liste,
						 BP_item,
						 MP_item)
		       ],
	     Lettres_item := [message := message(@prolog, affiche_parametres,
						 Longueur_item?selection,
						 Lettres_item?selection,
						 Doubles_item?selection,
						 Affiche,
						 Combinaison,
						 Liste,
						 BP_item,
						 MP_item
						)
		       ],
	     Doubles_item := [message := message(@prolog, affiche_parametres,
						 Longueur_item?selection,
						 Lettres_item?selection,
						 Doubles_item?selection,
						 Affiche,
						 Combinaison,
						 Liste,
						 BP_item,
						 MP_item)
		       ]
	   ],

	 initialise :=
	 [
	    Longueur_item := message(Longueur_item, execute)
	 ]

       ]).


xpce_test_IA :-
	make_dialog(D, 'Mastermind XPCE'),
	get(D, member, browser, Liste),
	get(Liste, list_browser, LB),
	send(LB, font,  font(screen, bold, 15)),
	get(@display, size, S),
	send(D,open_centered,  point(S?width/2, S?height/2)).

% affiche_parametres(+, +, +, +, +, +, +, +) :-
% affichage/memorisation des paramètres de jeu
% remise à zéro des affichage des scores
affiche_parametres(Longueur, Lettres, Doubles, Affiche, Combinaison, Liste, BP_item, MP_item) :-
	retractall('ia.pl':guess(_,_)),
	retractall('ia.pl':parametres(_,_,_)),
	assert('ia.pl':parametres(Longueur, Lettres, Doubles)),

	Max is 0'a +Lettres - 1,
	atom_codes(A, [Max]),
	(   Doubles = non
	->  sformat(Str, 'La combinaison est composée de ~w lettres de a à ~w, sans doublons.',
		[Longueur, A])
	;   sformat(Str, 'La combinaison est composée de ~w lettres de a à ~w, avec doublons.',
		[Longueur, A])),
	send(BP_item, range, low := 0, high := Longueur),
	send(MP_item, range, low := 0, high := Longueur),
	send(BP_item, selection, 0),
	send(MP_item, selection, 0),
	send(Combinaison, clear),
	send(Liste, clear),
	send(Affiche, selection, Str).


% lance_IA(+, +, +) :-
% Affiche la proposition de l'IA sous forme correcte
% remet à zéro les compteur de positionnement de lettes
lance_IA(Proposition, BP_item, MP_item) :-
	bulls_and_cows(Suggestion),
	retractall(proposition(_)),
	assert(proposition(Suggestion)),
	maplist(\X^Y^(Y is X+97), Suggestion, Ms),
	atom_codes(Guess, Ms),
	send(Proposition, selection, Guess),
	send(BP_item, selection, 0),
	send(MP_item, selection, 0).


% joue(+, +, +, +)
% enregistre les résultats de la proposition
% Affiche un message de vixtoie ou rejoue un autre coup
joue(Proposition, BP_item, MP_item, Liste) :-

	get(Proposition, selection, Combi),
	retract(proposition(Suggestion)),
	get(BP_item, selection, BP),
	get(MP_item, selection, MP),
	retract(coups(Coups)),
	Coups1 is Coups + 1,
	assert(coups(Coups1)),

	% affichage dans la liste des résultats du coup joué
	sformat(A, '~w : ~w Bulls ~w Cows ~w', [Coups1, Combi, BP, MP]),
	send(Liste, append, A),
	assert('ia.pl':guess(Suggestion, [BP, MP])),

	length(Suggestion, Len),
	% a-t-on trouvé ?
	(BP = Len
	 -> bravo
	 ; % sinon on rejoue
	   lance_IA(Proposition, BP_item, MP_item)).


% test_combinaison(+, +, +, +)
% Si la combinaison choisie est correcte remet à zéro les différents affichage
% sinon affiche un message d'erreur.
test_combinaison(Combinaison, Proposition, BP_item, MP_item) :-
	retractall(coups(_)),
	assert(coups(0)),
	get(Combinaison, selection, Combi),

	(bonne_combinaison(Combi)
	 -> lance_IA(Proposition, BP_item, MP_item)
	 ; send(@display, inform, 'La combinaison proposée est incorrecte'),
	   send(Combinaison, clear)
	).

% bonne_combinaison(+)
% réussi si la combinaison choisie est correcte
bonne_combinaison(Combinaison) :-
	'ia.pl':parametres(Longueur, Lettres, Doubles),
	% effectue la  transformation 1234 => [1,2,3,4]
	atom_codes(Combinaison,Ms),
	% writeln(Ms),
	%vérification de la correction de la proposition
	length(Ms, Longueur),
	maplist(\X^(X >= 0'a, X < Lettres + 0'a), Ms),
	(Doubles = non -> all_distinct(Ms); true).

% recommence(+, +, +, +, +)
% on relance une nouvelle partie
recommence(Combinaison, Proposition, BP_item, MP_item, Liste) :-
	retractall('ia.pl':guess(_,_)),
	send(Combinaison, clear),
	send(Proposition, clear),
	send(BP_item, selection, 0),
	send(MP_item, selection, 0),
	send(Liste, clear).

% boîte d'affichage d'un "modeste" message de victoire !
bravo :-
	new(D, dialog('Mastermind')),
	new(L, label(name,'J''ai trouvé !!!')),
	send(L, size, size(100, 40)),
	send(L, font, font(times, bold, 75)),
	send(L, label_format, center),
	send(D, append, L),
	new(L1, label(name1, image('happy.bm'))),
	send(D, append, L1, right),
	new(B, button(ok, message(D, destroy))),
	send(B, font, font(times, normal, 20)),
	send(D, append, B),
	get(@display, size, S),
	send(D, open_centered, point(S?width/2, S?height/2)).

Précédent Sommaire

Version PDF Version hors-ligne Version eBooks

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2012 Joël Foutelet. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.