Que
Le vent eclectique
Par Legolas
Mais encore ?
Musique, informatique, divers
Depuis le 12-11-2004
Monde extérieur
Vefblog.net
Vef Blog accueilgribouillé 08-03-2005 à 23:58:05
Mastermind : algorithme génétique
Voici comment je ferais personnellement pour écrire un programme d'AI qui essaierait de trouver la combinaison du mastermind. J'ecrirais un petit algo génétique, dont un individu serait une combinaison possible. Chaque combinaison serait notée en fonction de sa compatibilité aux réponses précédentes ; quand au moins une répondant complètement (100%) à ce critère serait trouvée, elle serait proposée à l'interface.
Au premier tour, une combinaison est tirée au hasard mais sans redondance de couleur pour obtenir d'emblée le maximum d'information (sauf si n>m). Une réponse sera donnée à cette premiere proposition.
Au tour suivant, on initie une population avec nb combinaisons tirées au hasard pour commencer la population de l'algo génétique. On décide que la population aura un nombre d'individu de nb , que on fera des crossover (reproduction) jusqu'à obtenir une population de max, et que on selectionnera les meilleurs pour revenir à une population de nb.
Au premier tour, une combinaison est tirée au hasard mais sans redondance de couleur pour obtenir d'emblée le maximum d'information (sauf si n>m). Une réponse sera donnée à cette premiere proposition.
Au tour suivant, on initie une population avec nb combinaisons tirées au hasard pour commencer la population de l'algo génétique. On décide que la population aura un nombre d'individu de nb , que on fera des crossover (reproduction) jusqu'à obtenir une population de max, et que on selectionnera les meilleurs pour revenir à une population de nb.
Valeurs de bases possibles :nb=20à60, max=2*n
Crossover ou reproduction
La population ayant nb individus, on va l'ammener à max individus par la reproduction ou crossover.
On tire au hasard deux individus (on vérifie qu'ils soient différents), et on prend une partie de l'un et une partie de l'autre pour former un nouvel individu.
Pour cela, on peut dcider d'un point de départ a, et un point d'arrivée b,
0 <= a < b < n
entre 0 et a, on prend le code du premier individu,
entre a+1 et b on prend le code du 2ème,
entre b+1 et n on prend le code du 1er.
On répète l'oprération jusqu'à obtenir une population de max. On va noter ensuite chaque individu.
On peut décider que la note maximum est 1, la note minimum est 0. Chaque tentative précédente compte pour une part égale, donc pour t tentatives, chaque concordance de tentative équivaudra à 1/t de la note.
Pour une tentative : on fait passer la combinaison à juger pour le résultat final, et on regarde la différence de résultat bien placés/mal placés par rapport à celui obtenu par l'interface.
Si on avait obtenu 1 point noir (bien placé) et 2 points blancs(mal placés), et que avec la combinaison à tester on obtient 0 points noirs et 1 point blanc, on peut considérer que la note pour cette tentative est de 1/3 : 1 bons et 2 mauvais, donc que l'ajout à la note finale est 1/t*1/3
Si on a obtenu 2noirs et 0 blancs, et que ca donne 1 noir et 3 blancs, on a 4 mauvais et 1 bon, donc 1/4*1/t
Pour une tentative : on fait passer la combinaison à juger pour le résultat final, et on regarde la différence de résultat bien placés/mal placés par rapport à celui obtenu par l'interface.
Si on avait obtenu 1 point noir (bien placé) et 2 points blancs(mal placés), et que avec la combinaison à tester on obtient 0 points noirs et 1 point blanc, on peut considérer que la note pour cette tentative est de 1/3 : 1 bons et 2 mauvais, donc que l'ajout à la note finale est 1/t*1/3
Si on a obtenu 2noirs et 0 blancs, et que ca donne 1 noir et 3 blancs, on a 4 mauvais et 1 bon, donc 1/4*1/t
Selection
La nature étant sans pitié, il faut retirer les moins bons et garders les meilleurs. Mais pas en un coup : on a besoin de la diversité. On organise alors un tournoi :
A chaque tour on prend deux individus au hasard, et on décide par exemple que le meilleur a 80% de chance de gagner contre 20% pour le moins bon : g=0.8 par exemple. Le perdant est éliminé, le gagnant est laissé dans la population.
On recommence l'opération jusqu'à retrouver un nombre nb d'individus.
A ce niveau là, on peut éventuellement regarder si un individu a comme note 1, auquel cas on peut le proposer à l'interface. Sinon, on recommence un cycle de reproduction, éventuellement après avoir ajouté un mutant.
Mutants
A chaque tour de population, on peut avoir mut chance d'avoir un individu en plus, retiré au hasard, pour réintroduire de la diversité avant la phase de crossover.
Une bonne valeur de mut : 0.2 par exemple (pas trop).
Apres un nouveau résultat de l'interface, ca peut valoir le coup de reprendre une population constituée pour un part de la population précédente. On peut par exemple garder nb/2 individus, en refaire autant au hasard et entamer de nouveau une phase de crossover.
Voilà, en deux mots, comment moi je ferais. Je pense que bien réglé, cette algorithme peut être rapide et extrèmenent efficace. Il faut touver les bonnes valeurs de nb,max,g et mut. Il faut aussi eventuellement limiter le nombre d'individus semblables pour éviter une convergence qui deviendrait blocage.
J'ai fait mon propore algo génétique pour participer à un concours de voyageur du commerce, dont le résultat est visible en lien : le concours PVC des 250 villes de Alex.
A chaque tour on prend deux individus au hasard, et on décide par exemple que le meilleur a 80% de chance de gagner contre 20% pour le moins bon : g=0.8 par exemple. Le perdant est éliminé, le gagnant est laissé dans la population.
On recommence l'opération jusqu'à retrouver un nombre nb d'individus.
A ce niveau là, on peut éventuellement regarder si un individu a comme note 1, auquel cas on peut le proposer à l'interface. Sinon, on recommence un cycle de reproduction, éventuellement après avoir ajouté un mutant.
Mutants
A chaque tour de population, on peut avoir mut chance d'avoir un individu en plus, retiré au hasard, pour réintroduire de la diversité avant la phase de crossover.
Une bonne valeur de mut : 0.2 par exemple (pas trop).
Apres un nouveau résultat de l'interface, ca peut valoir le coup de reprendre une population constituée pour un part de la population précédente. On peut par exemple garder nb/2 individus, en refaire autant au hasard et entamer de nouveau une phase de crossover.
Voilà, en deux mots, comment moi je ferais. Je pense que bien réglé, cette algorithme peut être rapide et extrèmenent efficace. Il faut touver les bonnes valeurs de nb,max,g et mut. Il faut aussi eventuellement limiter le nombre d'individus semblables pour éviter une convergence qui deviendrait blocage.
J'ai fait mon propore algo génétique pour participer à un concours de voyageur du commerce, dont le résultat est visible en lien : le concours PVC des 250 villes de Alex.
Rappel article
Un blog comme les autres..
Réactions
1. Marielle le 09-03-2005 à 08:52:53
Merci beaucoup ! Je n'ai pas tout saisi mais je relirai ça à tête reposée ce soir (là, en TP, je ne suis pas dans des conditions idéales de réflexion).
2. Legolas le 09-03-2005 à 21:16:56
en fait, c'est un peu bourrin le coup de l'algo génétique pour le mastermind. Disons que c'est un peu lourd à programmer ; par contre ca évite de réfléchir à la spécificité du problème de trouver une solution au mastermind. avantages - très générique, quand tyu l'auras fait pour ce problème là tu sauras le faire pour d'autres, - normalement efficace, surtout que le problème n'est pas très complexe inconvéniants - ne fait rien de plus que trouver une solution valable à chaque fois : pas d'optimisation de la propositoin (du moins dans la version que j'ai décrite), - c'est un peu prendre un char pour pas grand chose
3. brubru le 09-03-2005 à 21:20:45
Tu veux dire : "c'est goret ?"
4. Legolas le 09-03-2005 à 21:23:29
oui, un algo génétique pour résoudre un mastermind, je pense que c'est goret : ca fait le mec qui s'y connait mais qui ne veut pas trop réfléchir à la spécificité du jeu. Cela dit, quand n et m augmentent, il se peut que ce soi une très très bonne solution, parce que il me semble que le problème doit devenir bien bien complexe.
5. Marielle le 09-03-2005 à 21:25:07
Si je réussis grâce à toi, je chargerai Elo de te faire un énoooooooorme bisou. :-)
6. brubru le 09-03-2005 à 21:26:01
Jusqu'à quelles valeurs de m et n le cerveau humain peut-il jouer au mastermind (j'ai bien dit jouer)
7. Legolas le 09-03-2005 à 21:28:11
la difficulté, c'est surtout de mettre en place les piles d'emplacement mémoire pour les populations, et de passer de la pile des emplacements libres à la pile des emplacements occupés en comblant les trous à chaque fois par le dernier emplacement de la pile. Pusi ensuite de travailler sur ca. A mon avis, c'est long à programmer quand même tout ça ....
8. Brubru le 10-03-2005 à 00:00:31
Pour le Mastermind de Marielle le critère "nb de coups" est assez important, or avec ton truc Légo tu testes toutes les possibilités ?
9. legolas le 10-03-2005 à 00:04:09
non non au contraire, un AG justement permet de converger vers une solution sans tester toutes les possibilités. Par contre, pa rapport au mastermind, il se contente à chaque tour de trouver une solution possible, il n'optimise pas en fonctions de la probabilité d'informations intéressantes qu'il pourrait avoir. Mais ce n'est déjà pas mal, j'ai réfléchi pour faire un algo dédié qui trouve une solution posible à chaque coup, c'est chaud.