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,
Développeur python amateur et fan de jeux-vidéos !
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
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,
Développeur python amateur et fan de jeux-vidéos !
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.
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
Développeur python amateur et fan de jeux-vidéos !
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
Développeur python amateur et fan de jeux-vidéos !
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.
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
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,
Développeur python amateur et fan de jeux-vidéos !
Pseudo Intelligence Artificielle Mastermind
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Développeur python amateur et fan de jeux-vidéos !
Développeur python amateur et fan de jeux-vidéos !
Découverte Python Doc Tkinter Les chaînes de caractères
Développeur python amateur et fan de jeux-vidéos !
Découverte Python Doc Tkinter Les chaînes de caractères
Développeur python amateur et fan de jeux-vidéos !
Découverte Python Doc Tkinter Les chaînes de caractères
Développeur python amateur et fan de jeux-vidéos !