60

( non j'ai jamais dit que je participais à qqch )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

61

Ok

62

Hey Nitacku!

There is not really a Mastermind program. Just make a simply program, and use it to do the AI.

I repeat the rules: the AI can play a variable number of times (just call that by a variable name), there are 4 numbers to find, by 1 to 6, and the 4 numbers cannot be the same (only 4 differents numbers).

My english is very bad, so say it if you didn't understand all xD.

63

Wow, shame on me, I'm really bad in english. Well, I'm gonna try. I'll send to you my prog this evening. The code isn't very good, but it works ^^ (and today I'm better XD).

Ouch, bon je rappelle juste un truc (qqun traduira, moi sa me saoule ^^) : il faut aussi créer un deuxième IA qui donne les indices.

Sinon Syfo t'en es où ? Moi je piétine un peu...

64

Hum j'ai pas avance ce WE, et je n'avancerais pas ce soir. Je pense que je vais finir ma seconde mouture demain ou apres demain, et que je le tenterais sur calc directement (parce que la theorie c'est bien beau, mais ca vaut pas la pratique).

La deuxieme IA qui donne les indices? Ca doit vraiment pas etre dur. Tu veux que chacun fasse la sienne, ou que j'en fasse une qui serve pour tout le monde?

65

Nitacku, Baruch wants to tell you that you must code a piece of program that gives the indications...
Syfo-Dias wonders if he codes it for everybody...

66

gon33>delay = retard
time limit = délai

(j'viens d'me taper toute une liste de faux-amis grin)

Bon sinon ça a l'air de bien avancer par ici, j'participerai bien mais moi-même j'sais pas jouer au mastermind alors pour programmer une AI de mastermind ça va être catastrophique
par contre s'il y a une place de juge c'est sans problème grin
programmeur sur TI ^^

mon blog sur les TI => clic

mon (p'tit) fofo sur les TI => clic

67

Bien sur qu'il y a de la place!!!

Donc je corrige:

The time limit for coding is 2 weeks.

Tu remarqueras que j'ai pas forcément un excellent niveau en anglais, mais bon, comme je discute souvent avec lui...

68

Non, pas la peine de faire l'IA correcteur Syfo, de toute façon le code dépend des objets utilisés dans l'algo de résolution.

69

gon33>ok, mais d'toute façon j'pense qu'il a compris ^^
et puis si y a de la place, tant mieux smile
programmeur sur TI ^^

mon blog sur les TI => clic

mon (p'tit) fofo sur les TI => clic

70

Bon, je sais pas toi Syfo, mais moi j'arrive vraiment pas. Si tu es dans le même cas que moi, ça serait plus intéressant si on mettait nos idées en commun.

71

Hum c'est pas que j'arrive pas, c'est que je n'avance pas. Je vais m'y remettre prochainement.

La pour l'ordi j'ai peu de temps, donc pas le temps meme de te donner les grandes lignes de mon AI. Ca devrait s'arranger au mieux demain, au pire vendredi.

En attendant, resume moi l'algo de ton AI, et dis moi la ou tu bloques smile

72

Bon desole pour le double post, mais j'ai peur que celui ci ne se voit pas si je le rajoutais a la suite du precedent par edit.


Donc voici en gros comment j'ai procede pour mon bot: je ne m'occupe que d'un chiffre a la fois jusqu'a etre sur qu'il est juste, puis j'avance d'un rang. De plus, je garde un historique du nombre de chiffres justes et mauvais pour plus de surete, puisque je fais en sorte de ne jamais sortir deux chiffres pareils en meme temps.
Enfin, j'utilise une liste des nombres dont je ne suis pas sur (au debut, {1,2,3,4,5,6}), et j'elimine dedans un chiffre que je suis sur d'avoir bien place.

-Debut:
--Si premier tour
----Alors je sors {1,2,3,4}   //au hasard, pourquoi pas
--Sinon
----Si second tour
------Je sors {5,2,3,4}
---Sinon
-----Je recopie les nombres sortis au dernier tour dans la liste de ceux que je vais sortir (pour la modifier par la suite)
----Si le nombre de chiffres bien places + celui des mal places au dernier tour = 4 (donc tous bien ou mal places)
------Alors j'elimine de la liste des chiffres dont je ne suis pas sur ceux qui n'ont pas ete tentes au tour precedent
----Si le tour precedent, le nombre de chiffres bien places a monte d'un par rapport au precedent
------Alors j'ai trouve un bon chiffre, je l'elimine de la liste de ceux dont je ne suis pas sur
------Et puis j'avance d'un cran
----Si le tour precedent, le nombre de chiffres bien places a diminue au contraire
------Alors je recupere le chiffre propose a l'avant dernier tour, je le retire de la liste de ceux dont je ne suis pas sur, j'avance le rang recherche d'un cran
----La je change le chiffre du rang dont je m'occupe en ce moment
------Pour cela, je voit tous ceux deja testes precedemment, et je compare avec ceux non testes et non deja places
------Et j'en propose un nouveau
------Si il n'y avait qu'un seul chiffre placable
--------Alors je le retire de la liste de ceux dont je ne suis pas sur, j'avance d'un cran etc.
----Et puis je regarde si je ne propose pas plusieurs chiffres pareils dans les rangs suivants.
------Si c'est le cas, alors je recommence tout le trafic pour en chercher un qui n'ai pas deja ete propose (tant qu'a faire :) )
--Enfin je sors une proposition, et je repart a la case depart (de preference avec les 200 euros)



Voila voila. J'espere que la presentation est suffisamment claire (ou qu'elle n'est pas trop bordelique plutot). Il est possible que j'ai oublie une ou deux partie, puisque je te dis ca de memoire, mais dans l'ensemble ce doit etre complet.
Si quelqu'un voit une grosse connerie, ou une amelioration possible, dites le moi.
J'espere que ca t'aidera a continuer.

73

Bon je crois avoir été un peu trop pessimiste. Je ne vais pas me pencher sur ton code pour l'instant, vu que celui que j'ai commencé à faire est totalement différent. Encore dsl.

74

Po grave. J'y vois plus clair dans le mien maintenant.
Ce pourrait etre interessant de comparer nos manieres de proceder une fois que tu aura bien avance.

75

Oui, ce sera je pense le plus intéressant. Mais bon, pour l'instant je vais éviter de te dévoiler l'outil clé de mon algo ^^. A aufait, selon une étude très précise, il parait que le nombre d'essais minimum pour résoudre un mastermind de ce type est de 4 à 5 essais.

76

Sup everyone!

I have completed an AI for mastermind.
It can solve any combination in 5-6 moves.

I hope I followed the directions accurately.

I have attached the program to this post. You can download it from the link below.
tromb Fichier joint : AMASTER.8xp

Please let me know what you think.
Thanks grin

77

Rah Nitacku, you're too good for us!
(and too fast smile)

I will test in the evening.
Can you write how did you proceed to program it please?

(but not here, in a .txt document, I don't want to read it now).

78

Yiha, bon moi j'avance, contrairement à ce que pouvez constater. Bravo nitacku pour ta rapidité, je suis entrain de jeter un coup d'oeil à ton prog.

79

Y'a qqun qui est actif en ce moment pr le mastermind?
Ce serait pas mal de le finir...

80

Bon, afin d'éviter que mes recherches soient vaines, voilà ce que j'ai pu imaginer.

J'ai scindé le problème en 2 parties.

- le problème d'existence, qui consiste à savoir quelles couleurs sont présentes dans la solution
- le problème de placement, qui lui cherche à placer ces couleurs

L'erreur à ne pas commettre est de résoudre le problème d'existence PUIS celui de placement. Il faut imbriquer les 2 problèmes.

Commençons par le problème d'existence :

Je rappelle que chaque couleur ne peut avoir qu'une seule occurrence.

Il y a 6 couleurs, et 4 emplacements disponibles.

On appelle {A,B,C,D,E,F} les couleurs disponibles, et {a,b,c,d,e,f} leur nombre d'occurrence respectifs.
Or {a,b,c,d,e,f} ont la valeur 0 ou 1, car soit une couleur est dans la solution, soit elle ne l'est pas, et elle ne peut pas apparaître plus d'une fois.

Le problème d'existence consiste donc à trouver la valeur de ces 6 coefficients.

Comment faire ? Prenons un exemple :

On a tenté la combinaison A C F E et après analyse par la machine, il y a 3 pions présents dans la solution finale (ce nombre comprend les indices noirs et blancs)

Puis on fait A F E D -> 2

Eh bien, on peut formaliser le problème par un système d'équations :

a+b+c+d+e+f=4
a+c+e+f=3
a+f+e+d=2

Et on rentre celà dans une matrice en considérant qu'on a :

1a+1b+1c+1d+1e+1f=4
1a+0b+1c+0d+1e+1f=3
1a+0b+0c+1d+1e+1f=2

qui correspond à la matrice :

[[1,1,1,1,1,1,4]
[1,0,1,0,1,1,3]
[1,0,0,1,1,1,2]]


En effet, la première équation correspond au fait qu'il y a 4 pions différents dans la solution.

Et là, à quoi pensent ceux qui connaissent les matrices ? Comment résoudre un système d'équations de sommes ? La méthode de Gauss-Jordan !

Mais là, vous me dites : si on a 6 inconnues, il faut donc nécessairement 6 équations, donc au moins 5 essais.
Mais c'est oublier un caractère essentiel de ce système : toutes les inconnues prennent une valeur binaire, 0 ou 1.

Il faut donc rajouter des contraintes à la méthode de Gauss-Jordan, qui s'applique au moins pour des nombres réels.

Quelles sont ces contraintes ?

- Si une somme est nulle, alors tous les termes sont nuls.

ex : a+b+c+d=0 <=> a=b=c=d=0

- Si une somme de termes est égal au nombre de termes qui la composent, alors tous ces termes valent 1.

ex : a+b+c=3 <=> a=b=c=1

- Les valeurs nulles (les couleurs dont on a trouvé qu'elles n'existent pas) doivent être retenues, bizarrement, si l'on trouve que a=0, la méthode Jordanienne ne le prend pas en compte pour les autres équations.


Je pense que ce sont les seules contraintes.

Si on applique cette méthode, il faut donc faire comme suit :

- Créer une matrice dont le nombre de lignes est le nombre d'équations, avec 7 colonnes, les 6 premières pour chaque inconnue, la dernière pour la somme connue.

- A chaque fois qu'une nouvelle combinaison est tentée et analysée, on l'ajoute à la matrice (avec en dernière colonne la somme du nombre d'indices noirs et blancs)

- A chaque fois, résoudre la matrice grâce à la fonction rref(

- A chaque fois, appliquer les 2 contraintes citées plus haut. La première est simple, l'autre nécessite un comptage.


J'ai fait un prog qui permet de faire tout celà, par contre tout ne se passe pas comme prévu.

En effet, avec la méthode de résolution, on obtient parfois des -1

Que signifient ces -1 ? Comment les manipuler ? Je n'ai pas réussi à trouver.


De plus, pour pouvoir commencer le problème de placement, il ne faut pas attendre de connaître toutes les couleurs présentes dans la solution.
Il faut SUPPOSER.

On crée donc une liste d'existence qui contient les couleurs dont on sait qu'elles existent, mais il faut y rajouter des couleurs supposées.
Mais le problème est qu'il est illogique de mettre des couleurs totalement aléatoires, il faut que les couleurs supposées respectent les contraintes d'existence. Là non plus, je n'ai pas pu trouver.



Essayons d'imaginer le problème de placement, en considérant que tous les problèmes énoncés plus haut ont été résolus (je sais, c'est dur ^^) :


On a donc à l'issu de la résolution partielle du problème d'existence, une liste des 4 couleurs supposées présentes dans la solution.

Essayez d'imaginer une résolution des places en utilisant la méthode jordannienne. Impossible. Il faudrait une matrice 3D.




Voilà, j'imagine qu'il existe bien plus simple que ce que j'ai pu concevoir, mais bon au moins ce que j'ai fait ne tombera pas dans l'inconnu.

81

Tu veux pas le coder?? ^^
Histoire que je serve à qque chose en temps que juge...

82

J'ai déjà commencé, mais bon c'est un peu confus. Par contre, j'ai été étonné par la rapidité de ce que j'ai codé. Toi qui es en prépa, tu veux pas m'éclairer un peu sur la méthode jordanienne ?

83

Euh, c'est à moi que tu parles?

Je suis pas en prépa mais à la fac (enfin, bientôt je serai en école d'ingé), et je ne connais pas la méthode jordanienne... (du moins pas pour son nom)

84

( Cf la réduction de Jordan . en gros c'est un algo pour obtenir une matrice triangulaire-supérieur-qui-va-bien (en un certain sens –le nb de cases non-nulles – minimal ) qui est la matrice initiale à un changement de base près . A noter que c'est pas du tout explicitement dans le programme de prépa, et que selon la niveau de la classe on le voit juste une fois ou deux en exo ou comme une vraie méthode quasi-du-cours. )
«Les gens exigent la liberté d’expression pour compenser la liberté de pensée qu’ils préfèrent éviter.» - Sören Kierkegaard

La République, c’est comme la syphilis : quand on l’a attrapée, soit on se fait sauter le caisson, soit on essaie de vivre avec.

85

Oula bien trop complique pour moi la reduction de Jordan (bon ok j'avoue, la flemme de tout lire).
Pour mon programme, il n'a pas avance, peut etre durant les vacances (la semaine prochaine pour moi).

86

Dsl, je pensais qu'on le faisais en prépa, pas grave. Aufait quelqu'un a testé le prog de nitacku ?

87

Il est clair qu'il sait très bien coder. Par contre il y a des erreurs je pense dans les règles du jeu. La solution ne peut pas avoir une répétition de couleurs, mais lui admis les répétitions dans les combinaisons essais. De plus, il y a une erreur dans la vérification des combinaisons : Il y a toujours des indices noirs, ou blancs, mais jamais des "trous", ce qui fait qu'il y a toujours 4 indices. Exemple :

Solution : 1234

Essai : 1112
Indices : 1 noir, 3 blancs

Or ici il ne devrait y avoir qu'1 noir (le premier 1), et un blanc (le 2).
La raison de cette faute est facile à imaginer.

Enfin bon j'espère que Syfo tu es d'accord avec moi sur les règles.

88

Ah oui j'oubliais, on avait limité le nombre de couleurs à 6 et lui en met 9.

89

Ah, lol
La méthode Jordanienne est dans mon programme (de fac).
J'ai un DS dessus samedi^^

90

No comment.