Bonjour à tous, 

je réalise en ce moment mon projet d'ISN de fin d'année et je bloque sur la partie où il faut programmer l'IA du mastermind, c'est à dire que l'ordinateur retrouve la bonne combinaison de couleur (il y a 6 couleurs disponibles et le code est fait de 4 couleurs), comme il y a 1296 possibilités, le simple hasard ne permettra pas de retrouver le code en 10 coups maximums. J'aimerai donc des pistes de recherche où des idées afin que je puisse venir à bout de ce projet. J'ai lu quelques trucs à propos de la théorie de l'information mais j'ai pas trop compris..

Cordialement,

Salut

Heureusement que ma chaise n'est pas bancale parce qu'à la lecture c'était la chute assurée.

Désolé mais tu as les yeux plus gros que le ventre. Si tu as du mal à comprendre la théorie de l'info, d'ailleurs, je sais même pas ce que c'est, tu peux oublier ton objectif.

Ou alors, tu te fais un algorithme très précis, mais qui sera très long. Tu peux commencer par 2 couleurs dispo et le code fait de 2 couleurs.

Sinon, mais, ça marche surtout pour les objets triés, il y a la recherche dichotomique, c'est un algo utilisé dans la recherche du nombre secret de + ou - :

On prend le nombre médian, si c'est -, on élimine directement ceux qui lui sont supérieurs. Là, avec des couleurs, ça va pas être pareil

Merci de ta réponse mais je ne comprends pas..

les profs d'ISN nous demanderaient de réaliser cela alors que tu me dis que c'est impossible ?
Effectivement, la théorie de l'information est assez complexe pour un terminale mais si il n'y a aucun moyen de réaliser le projet, c'est idiot de le proposer en ISN. J'ai déjà réussi à faire une base qui élimine à 90% de fiabilité une des couleurs qu'il n'y a pas dans le code à trouver. Je connais le principe de la dichotomie mais je ne vois pas comment l'appliquer à un mastermind en revanche.

Cordialement,

Il faut d'abord écrire une fonction score(correct, guess) qui te renvoie le score (a, b) où a est le nombre de noirs et b le nombre de blancs

Ensuite, tu peux essayer l'IA suivante

• génère les 1296 possibilités sous forme d'une liste de listes d'entiers dans range(6)
• fais un choix au hasard dans la liste précédente
• l'ordi te donne ton score (a, b) où a est le nombre de noirs et b le nombre de blancs
• tu génères tous les candidats possibles en testant chacune des 1296 possibilités en ne sélectionnant que celles qui ont un score valant (a, b) et tu rassembles tes candidats dans une liste
• tu choisis au hasard un candidat, tu le soumets à l'ordi qui te renvoie un score 
• et tu recommences (-> une boucle) ce que j'ai montré à l'avant dernier point sauf que tu en as cette fois beaucoup moins que 1296

D'étapes en étapes, le nombre de candidats va se réduire. Je viens de faire quelques essais (1000 parties) et la réponse est toujours trouvée en au plus 6 étapes.

-
Edité par PascalOrtiz 24 mai 2019 à 22:19:05

Merci de ta réponse ! J'ai bien compris ta méthode sauf le quatrième point, cela veut dire que l'on va tester chacune des 1296 possibilités en les comparant au code à trouver ou par rapport au premier code qu'on a pris au hasard ?

ex: si on a au hasard au 1er tour [0,5,2,4] et qu'on nous renvoie qu'il y en a 2 de bien et 1 de mauvais, on va donc comparer les 1295 possibilités restantes à [0,5,2,4] et voir si il y a le même a et b ou alors on les comparent au code à trouver ?

-
Edité par CodingFR 24 mai 2019 à 22:28:28

djanou76 a écrit:

Merci de ta réponse ! J'ai bien compris ta méthode sauf le quatrième point, cela veut dire que l'on va tester chacune des 1296 possibilités en les comparant au code à trouver ou par rapport au premier code qu'on a pris au hasard ?

Oui, forcément puisqu'on ne connait pas le code à trouver.

djanou76 a écrit:

ex: si on a au hasard au 1er tour [0,5,2,4] et qu'on nous renvoie qu'il y en a 2 de bien et 1 de mauvais, on va donc comparer les 1295 possibilités restantes à [0,5,2,4] et voir si il y a le même a et b ou alors on les comparent au code à trouver ?

Oui. Tu peux même laisser [0,5,2,4]  puisque son score avec lui-même sera de (4, 0) qui est différent de (a,b) sinon tu aurais la réponse.

D'accord, merci beaucoup, j'ai une dernière question, pour générer toutes les possibilités, quelles sont les méthodes en python qui permettent de le faire, j'ai trouvé itertools mais sa méthode permutations() ne prend pas en compte 1,1,1,1 par exemple.

Edit: j'ai trouvé avec product('123456', repeat=4)

-
Edité par CodingFR 24 mai 2019 à 22:51:42

djanou76 a écrit:

D'accord, merci beaucoup, j'ai une dernière question, pour générer toutes les possibilités, quelles sont les méthodes en python qui permettent de le faire, j'ai trouvé itertools mais sa méthode permutations() ne prend pas en compte 1,1,1,1 par exemple.

Edit: j'ai trouvé avec product('123456', repeat=4)

-
Edité par djanou76 il y a 5 minutes

Oui effectivement, c'est product qu'il faut utiliser.

J'aurais plutôt écrit :

from itertools import product
r=range(6)
guesses = list(product(r, r, r, r))
print(len(guesses))

mais ton repeat est très bien.

Tu as plus basique ici :

guesses=[[a, b, c, d] for a in range(6) for b in range(6)for c in range(6)for d in range(6) ]
print(len(guesses))

-
Edité par PascalOrtiz 24 mai 2019 à 23:11:09

Au niveau de l'algo, cela ne me semble pas extrêmement complexe.

1. Tu places [0, 0, 0, 0] -> ca te donne le nombre de 0 (=k)

2. Tu places k * 0 et le reste en 1 soit [0, 0, 1, 1] si k=2. -> ca te donne le nombre de 1 et le nombre de 0 bien place (car noir + blanc = k + nb de 1)

3. Tu itère de la même façon avec 2, 3, 4, 5 en alternant la position du 0 jusqu'a avoir le bon placement.

Le truc c'est que plus tu va avoir de pions bien placés, plus tu va réduire ton espace de recherche et ca devient plus simple.

 Par contre, ca demande biensur un code bien organiser pour arriver à le faire proprement et ca ne depend que de tes connaissances et du temps que tu peux y mettre. Je doute que ce soit faisable en 30 min quand meme

Alors, j'ai réalisé la méthode de PascalOrtiz mais je crois que je me suis trompé..

Voici mon code:

COULEURS = {"jaune": (219, 208, 32), "vert": (84, 179, 111), "orange": (226, 128, 0), "bleu": (81, 143, 193), "rouge": (230, 76, 55), "rose": (168, 77, 154)}

r = range(6)
all_possibilities = list(product(r, r, r, r))

first_one = all_possibilities[random.randint(0, len(all_possibilities))]

code_choisi = [list(COULEURS.keys())[int(first_one[0])], list(COULEURS.keys())[int(first_one[1])], list(COULEURS.keys())[int(first_one[2])], list(COULEURS.keys())[int(first_one[3])]]

ca c'est pour choisir la première combinaison au hasard, voici ma fonction qui fait le tri à chaque fois:

def adjust_ia_placement():
    """
    improve the IA at each round
    """
    global code_choisi

    adjust_list = []

    for combi in all_possibilities:
        if compte_placement(code_choisi, [list(COULEURS.keys())[combi[0]],
                                          list(COULEURS.keys())[combi[1]],
                                          list(COULEURS.keys())[combi[2]],
                                          list(COULEURS.keys())[combi[3]]]) == compte_placement(code_a_trouver, code_choisi):
            adjust_list.append(combi)
            adjust_list_2 = adjust_list.copy()

    r_combi = adjust_list_2[random.randint(0, len(adjust_list))]
    code_choisi = [list(COULEURS.keys())[int(r_combi[0])], list(COULEURS.keys())[int(r_combi[1])], list(COULEURS.keys())[int(r_combi[2])], list(COULEURS.keys())[int(r_combi[3])]]

    adjust_list.clear()

et la fonction qui détermine les couleurs bien et mal placées:

good_place = 0
    bad_place = 0

    for i in range(4):
        if chose[i] == find[i]:
            good_place += 1
        else:
            if chose[0] == find[i]:
                bad_place += 1
            elif chose[1] == find[i]:
                bad_place += 1
            elif chose[2] == find[i]:
                bad_place += 1
            elif chose[3] == find[i]:
                bad_place += 1

    return good_place, bad_place

Je ne comprends où ça ne marche pas, j'ai essayé de suivre au mieux tes indications !

Cordialement,