# [TGG et QBO] Projet IAT
###### tags: `IAT`, `Projet 1`, `TGG ET QBO`
[Le sujet](https://moodle.insa-lyon.fr/pluginfile.php/280283/mod_resource/content/1/Projet-IAT-MasterMind-2021.pdf)

## Résolution du Mastermind par méta-heuristiques
### Etape 1 : Modélisation du problème
#### Question 1
Chaque combinaison de pions sera représentée par un tableau de 4 chiffres allant de 1 à 8 où chaque chiffre correspond à une couleur (ex : 1 = rouge, 2 = bleu, 3 = vert, etc…)

Exemple de représentation de combinaison: [1,6,3,8]

#### Question 2
Pour une combinaison de N pions avec k couleurs, il existe $k^N$ solutions. Pour 4 pions de 8 couleurs on a donc $8^4=4096$ solutions

#### Question 3.1
Soit X le rapport entre le poid des éléments placés correctement et mal placés. Différentes valeurs de ce rapport seront testés pour voir quel est le rapport le plus optimal

int X
def score (p, m):
     if (p<0 or m<0):
         exit(1)
     elif (p==0 and m==0):
         return 0
     else:
         return (p*X + m)

#### Question 3.2

**Fonction compare**

def compare(c,j):
    m,p = 0,0 
    c_b = []
    j_b = []
    for i in range(len(c)):
        if c[i]==j[i]:
            p=p+1
        else:
            c_b.append(c[i]) 
            j_b.append(j[i])

    for j in range(len(c_b)):
        for k in range(len(j_b)):
            if j_b[k]==c_b[j]:
                m+=1
                c_b[j]=0
    return m,p

**Fonction eval**

def eval(c, j):  
    j_p, j_m = compare(j,A_DEVINER)
    v_p, v_m = compare (c,j)
    j_score=score(j_p, j_m)
    v_score=score(v_p,v_m)
    return abs(j_score-v_score)

#### Question 3.3

**Fonction fitness**

def fitness(c):
    fitness = 0
    for j in range (len(historique)):
        fitness = fitness + eval(c, historique[j])
    return fitness / len(historique)

### Etape 2 : Résolution par algorithme génétique

#### Question 1

Pour sélectionner les m "meilleurs" candidats pour la nouvelle génération, nous pouvons calculer la "Fitness" de tous les candidats d'une génération puis les normaliser. On peut ensuite les ordonner en fonction de leur Fitness et l'on gardera les m candidats avec la Fitness la plus faible.
On pourrait aussi faire un tirage au sort biaisé par la fitness où les éléments avec la probabilité d'être tiré au sort est proportionelle à 1/Fitness.

**Fonction meilleur_candiat**

def meilleur_candidat(generation):

    liste_candidat = []

    for i in range(TAILLE_POPULATION):
        valeur_fitness = fitness(generation[i])
        liste_candidat.append((valeur_fitness, generation[i]))

    # on trie la liste et on extrait la fitness dans une nouvelle liste
    liste_candidat = sorted(liste_candidat, key=lambda element: element[0])
    return liste_candidat[0][1]

#### Question 2

Une opération simple de mutation pourrait être de choisir aléatoirement un des 4 pions de la solution, puis de tirer au sort une nouvelle couleur et de lui affecter.
On peut également interchanger aléatoirement deux pions d'une même solution.

**Fonction mutation**

def mutation(c): 
    
    index_aleatoire = random.randint(0,3)
    couleur_aleatoire = random.randint(1,8)
    
    #tant que la couleur n'est pas différente de la précédente on retire au sort
    while couleur_aleatoire==c[index_aleatoire]:
        couleur_aleatoire = random.randint(1,8)
    
    c[index_aleatoire] = couleur_aleatoire
    
    return c

**Fonction croisement**

def croisement(parent1, parent2):

    enfant = [-1, -1, -1, -1]
    index_aleatoire = random.randint(0,3)

    for i in range (2):
        enfant[(index_aleatoire+i)%4]=parent1[(index_aleatoire+i)%4]
        enfant[(index_aleatoire+i+2)%4]=parent2[(index_aleatoire+i+2)%4]
    
    return enfant

#### Question 3

Une opération de croisement pourrait être de garder 2 pions de la première solution et deux de la deuxième afin de constituer une nouvelle solution candidate valide.

0) Générer 1 première solution aléatoire que l'on joue
1) Générer une populations de 100 solutions aléatoires
2) Selectionner les 50 meilleures (celles avec la fitness la plus faible)
3) Les faire muter et croiser pour recréer une génération de 100 solutions
4) Chosir le meilleur individu et le jouer
5) Recommencer à l'étape 2 a partir des 100 solutions de la nouvelle génération et ce jusqu'a obtenir le bon code

**Fonction nouvelle_generation**

def nouvelle_generation(generation):

    liste_candidat = []
    new_generation = []

    # On trie les la génération de candidats
    for i in range(TAILLE_POPULATION):
        valeur_fitness = fitness(generation[i])
        liste_candidat.append((valeur_fitness, generation[i]))
    liste_candidat = sorted(liste_candidat, key=lambda element: element[0])

    #On garde la première moitié des meilleurs candidats
    for i in range (0,50):
        new_generation.append(liste_candidat[i][1])
        new_generation[i]=mutation(new_generation[i])     #On mute chacun des candidats

    #On croise pour former les candidats restant de la nouvelle generation
    for i in range (0,25):
        parent1 = new_generation[i]
        parent2 = new_generation[i+24]
        parent3 = new_generation[49-i]
        new_generation.append(croisement(parent1,parent2))
        new_generation.append(croisement(parent1,parent3))

    return new_generation

#### Implémentation

Notre code est disponible dans l'archive déposée

**Fonction Main**

if __name__ == '__main__':

    print("Tirage du code à trouver effectué -> c'est parti !")
    A_DEVINER= initialisation_code() # Tirage au sort du code a déviner
    premier_candidat = initialisation_code() # Tirage au sort du premier candidat

    nombre_iteration=1  # Définition du compteur d'itérations
    candidats=[]        # Définition d'une liste pour stocker les candidats

    m,p = compare(premier_candidat,A_DEVINER) #On test le premier candidat
    historique.append(premier_candidat) #On l'ajoute à l'historique
    generation=initialisation_population(100) #Tirage aléatoire de la première génération
    print("coup n°:", nombre_iteration, " : " , premier_candidat, " -> ", p , "bien placés et ", m , " mal placés")

    while p !=4: # tant que le code n'est pas le même
        nombre_iteration = nombre_iteration+1
        generation = nouvelle_generation(generation) 
        solution_retenue = meilleur_candidat(generation)
        m,p = compare(solution_retenue, A_DEVINER) #on joue le candidat retenu
        historique.append(solution_retenue) #On ajoute le candidat joué à l'historique
        print("coup n°",nombre_iteration, ":" , solution_retenue, " -> ", p , "bien placés et ", m , " mal placés")
        

    print("=============")
    print("Code trouvé en ", nombre_iteration ," itérations")
    print("La solution était ", A_DEVINER)
    print("====================")

#### Résultats

Après des tests sur plusieurs centaines de codes différents notre algorithme génétique résout le Mastermind en environ 7 coups en moyenne (6.88 pour être exact)