Posté le 14/03/2008 à 18:52 Membre depuis le 09/07/2003, 21783 messages
( non j'ai jamais dit que je participais à qqch )
Posté le 14/03/2008 à 19:00 Membre depuis le 11/04/2007, 1076 messages
Ok
Posté le 14/03/2008 à 19:46 Membre depuis le 01/12/2005, 413 messages
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.

Posté le 16/03/2008 à 20:57 Membre depuis le 25/12/2006, 499 messages
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...
Posté le 17/03/2008 à 18:32 Membre depuis le 01/12/2005, 413 messages
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?
Posté le 17/03/2008 à 19:49 Membre depuis le 11/04/2007, 1076 messages
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...
Posté le 17/03/2008 à 20:24 Membre depuis le 06/02/2006, 349 messages
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
Posté le 18/03/2008 à 09:50 Membre depuis le 11/04/2007, 1076 messages
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...
Posté le 18/03/2008 à 15:54 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 18/03/2008 à 17:58 Membre depuis le 06/02/2006, 349 messages
gon33>ok, mais d'toute façon j'pense qu'il a compris ^^
et puis si y a de la place, tant mieux smile
Posté le 24/03/2008 à 18:41 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 24/03/2008 à 19:34 Membre depuis le 01/12/2005, 413 messages
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
Posté le 26/03/2008 à 20:28 Membre depuis le 01/12/2005, 413 messages
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.
Posté le 27/03/2008 à 19:06 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 27/03/2008 à 19:48 Membre depuis le 01/12/2005, 413 messages
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.
Posté le 27/03/2008 à 22:27 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 28/03/2008 à 04:51 Membre depuis le 13/03/2008, 2 messages
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
Posté le 28/03/2008 à 12:23 Membre depuis le 01/12/2005, 413 messages
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).

Posté le 31/03/2008 à 17:30 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 08/04/2008 à 20:36 Membre depuis le 11/04/2007, 1076 messages
Y'a qqun qui est actif en ce moment pr le mastermind?
Ce serait pas mal de le finir...
Posté le 08/04/2008 à 22:21 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 08/04/2008 à 22:45 Membre depuis le 11/04/2007, 1076 messages
Tu veux pas le coder?? ^^
Histoire que je serve à qque chose en temps que juge...
Posté le 08/04/2008 à 22:47 Membre depuis le 25/12/2006, 499 messages
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 ?
Posté le 09/04/2008 à 14:49 Membre depuis le 11/04/2007, 1076 messages
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)
Posté le 09/04/2008 à 15:56 Membre depuis le 09/07/2003, 21783 messages
( 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. )
Posté le 09/04/2008 à 16:25 Membre depuis le 01/12/2005, 413 messages
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).
Posté le 09/04/2008 à 17:34 Membre depuis le 25/12/2006, 499 messages
Dsl, je pensais qu'on le faisais en prépa, pas grave. Aufait quelqu'un a testé le prog de nitacku ?
Posté le 09/04/2008 à 17:48 Membre depuis le 25/12/2006, 499 messages
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.
Posté le 09/04/2008 à 17:49 Membre depuis le 25/12/2006, 499 messages
Ah oui j'oubliais, on avait limité le nombre de couleurs à 6 et lui en met 9.
Posté le 10/04/2008 à 14:45 Membre depuis le 11/04/2007, 1076 messages
Ah, lol
La méthode Jordanienne est dans mon programme (de fac).
J'ai un DS dessus samedi^^
Posté le 10/04/2008 à 18:49 Membre depuis le 25/12/2006, 499 messages
No comment.