# Graphe pour les tests (merci à Serge Haddad pour l'exemple) arene = [(True, [1, 3]), (False, [2]), (True, [0, 1]), (False, [2, 5]), (True, [3, 5]), (False, [4])] # Exercice 1 def inclus(liste1, liste2): """Détermine si la première liste est incluse dans la deuxième. """ for element in liste1: if element not in liste2: return False return True def commun(liste1, liste2): """Détermine si deux listes sont d'intersection non vide. """ for element in liste1: if element in liste2: return True return False def attracteur(arene, objectif): """Calcule l'ensemble gagnant pour Ève dans un jeu d'accessibilité, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Un éventuel sommet d'Adam sans successeur n'est pas déclaré gagnant s'il n'est pas explicitement dans l'objectif (il faut éviter d'avoir de tels sommets en pratique). """ a_n = [] # attracteur au rang n a_np1 = objectif # attracteur au rang n+1 while a_np1 != a_n: a_n = a_np1[:] # Ne pas oublier la copie, car on mute a_np1 for i, (proprietaire, successeurs) in enumerate(arene): if inclus(successeurs, a_n) and proprietaire: # Adam doit aller dans l'attracteur if i not in a_np1 and successeurs != []: # pas de doublons ni de faux positif (sommet d'Adam bloquant, qui devrait être interdit par principe) a_np1.append(i) elif commun(successeurs, a_n) and not proprietaire: # Eve peut y aller if i not in a_np1: a_np1.append(i) return a_n # Après stabilisation def arene_renversee(arene): rep = [[] for _ in range(len(arene))] for sommet in range(len(arene)): for successeur in arene[sommet][1]: rep[successeur].append(sommet) return rep import copy def attracteur_autre_methode(arene, gain_eve): L = copy.deepcopy(arene) # Il y a des mutations en profondeur. L_rev = arene_renversee(arene) attracteur = gain_eve[:] a_traiter = gain_eve[:] # idéalement sous forme de file, mais une pile convient aussi while len(a_traiter) > 0: en_cours = a_traiter.pop() for x in L_rev[en_cours]: if not L[x][0]: if x not in attracteur : attracteur.append(x) a_traiter.append(x) else : L[x][1].remove(en_cours) if L[x][1] == [] : attracteur.append(x) a_traiter.append(x) return(attracteur) def attracteur_autre_methode_bis(arene, gain_eve): # Moins lourd mais mieux vaut commencer par lire ce qui précède pour comprendre cette version L = [len(arene[i][1]) for i in range(len(arene))] # nombre de successeurs par sommet L_rev = arene_renversee(arene) attracteur = { s : 42 for s in gain_eve } a_traiter = gain_eve[:] # file ou pile, peu importe (ici c'est une pile) while len(a_traiter) > 0: en_cours = a_traiter.pop() for x in L_rev[en_cours]: if not arene[x][0]: if x not in attracteur: attracteur[x] = 42 a_traiter.append(x) else: L[x] -= 1 if L[x] == 0: attracteur[x] = 42 a_traiter.append(x) return(list(attracteur.keys())) ## Tests : ### print(attracteur(arene, [0, 5])) # Exercice 2 # On reprend la fonction précédente en mode couper-coller. # Ce n'est donc pas du copier-coller, mais l'idée était de laisser une trace du premier exercice. def attracteur_E_ou_A(arene, objectif, pour_Eve=True): """Calcule l'ensemble gagnant pour le joueur precisé dans un jeu d'accessibilité, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Par défaut, c'est Ève qui est le joueur précisé. Un éventuel sommet sans successeur n'est pas déclaré gagnant pour l'adversaire s'il n'est pas explicitement dans l'objectif (il faut éviter d'avoir de tels sommets en pratique). """ a_n = [] a_np1 = objectif while a_np1 != a_n: a_n = a_np1[:] for i, (proprietaire, successeurs) in enumerate(arene): if inclus(successeurs, a_n) and (proprietaire == pour_Eve): # astuce ! if i not in a_np1 and successeurs != []: a_np1.append(i) elif commun(successeurs, a_n) and (proprietaire != pour_Eve): if i not in a_np1 and successeurs != []: a_np1.append(i) return a_n ## Tests : ### print(attracteur_E_ou_A(arene, [0, 5], False)) # Exercice 3 # Encore une adaptation ! def attracteur_E_et_A(arene, objectifs): """Calcule l'ensemble gagnant pour le joueur precisé dans un jeu d'accessibilité, où chaque joueur a un objectif éventuel (le deuxième argument est une liste de deux listes, une par joueur, une liste vide signifiant que le joueur en question n'a pas d'objectif d'accessibilité, ce qui peut correspondre à un jeu à somme nulle). Chaque objectif est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Un éventuel sommet sans successeur n'est pas déclaré gagnant pour l'adversaire s'il n'est pas explicitement dans l'objectif (il faut éviter d'avoir de tels sommets en pratique). """ if commun(objectifs[0], objectifs[1]): raise ValueError("Les ensembles à atteindre ne sont pas disjoints") les_a_n = [] les_a_np1 = objectifs while les_a_np1 != les_a_n: les_a_n = [les_a_np1[0][:], les_a_np1[1][:]] # copie profonde maison, attention à ne pas se faire avoir comme moi for i, (proprietaire, successeurs) in enumerate(arene): if i in objectifs[0] or i in objectifs[1]: # Déjà gagnant pour quelqu'un et déjà recensé comme tel. pass elif inclus(successeurs, les_a_n[0]) and proprietaire: if i not in les_a_np1[0] and successeurs != []: les_a_np1[0].append(i) # sommet d'Adam, condition d'Ève elif commun(successeurs, les_a_n[0]) and not proprietaire: if i not in les_a_np1[0]: les_a_np1[0].append(i) # sommet d'Ève, condition d'Ève elif inclus(successeurs, les_a_n[1]) and not proprietaire: if i not in les_a_np1[1] and successeurs != []: les_a_np1[1].append(i) # sommet d'Ève, condition d'Adam elif commun(successeurs, les_a_n[1]) and proprietaire: if i not in les_a_np1[1]: les_a_np1[1].append(i) # sommet d'Adam, condition d'Adam return les_a_np1 ## Tests : ### print(attracteur_E_et_A(arene, [[0, 5], [2, 4]])) # Finalement, on observe que attracteur(arene, objectif) peut être obtenu en faisant attracteur_E_et_A(arene, [objectif, []]) et en extrayant le premier élément du résultat, # et attracteur_E_ou_A(arene, objectif, pour_Eve) peut être obtenu en faisant attracteur_E_et_A(arene, [objectif * pour_Eve, objectif * (1 - pour_Eve)]) # et en extrayant l'élément d'indice 1 - pour_Eve du résultat. # Exercice 4 # Soit n le nombre de sommets. # inclus : O(n²) ici, O(n) avec une liste de booléens (l'espace est O(n) de toute manière) # commun : Idem # attracteur : O(n) tours de la boucle for, variant n - len(a_np1) pour la boucle while qui fait donc O(n) tours d'où un O(n⁴) ici pouvant se ramener à O(n³). # Idem pour les deux autres fonctions. # En pratique, l'optimisation permet de ne tenir compte des arcs qu'une seule fois et en gérant bien les tests d'appartenance à l'attracteur (tableau de booléens), on peut avoir une complexité linéaire en la taille du graphe # (ce qui donne du O(n²) vu que le nombre d'arcs peut être le carré du nombre de sommets). # Exercice 5 def strategie(arene, objectif): """Calcule une stratégie pour Ève dans un jeu d'accessibilité, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. La stratégie est gagnante depuis l'attracteur et indéfinie ailleurs : la liste retournée indique quel coup jouer suivant l'indice du sommet, et l'élément à l'indice i est "OK" si le sommet à l'indice i de l'arène est dans la condition de gain, -1 si ce sommet appartient à Adam sans être dans la condition de gain, None si ce sommet appartient à Ève mais n'est pas dans l'attracteur et un certain k sinon, sachant que le sommet k reste dans l'attracteur et rapproche Ève de son objectif. Un éventuel sommet d'Adam sans successeur n'est pas considésé comme gagnant s'il n'est pas explicitement dans l'objectif (il faut éviter d'avoir de tels sommets en pratique). """ rep = [None for _ in arene] # None à la fin : Peu importe le coup, Ève n'a pas de stratégie gagnante. iv = [None for _ in arene] # À quelle itération un sommet est-il mis dans le a_n virtuel ? ("indice de victoire") for i in range(len(arene)): if arene[i][0]: rep[i] = -1 # Sommet d'Adam : stratégie non définie for indice in objectif: rep[indice] = "OK" # Sommet à atteindre : stratégie non définie iv[indice] = 0 changement = True tour = 0 while changement: # Quelque chose s'est passé tour += 1 changement = False for i, (proprietaire, successeurs) in enumerate(arene): if proprietaire and iv[i] is None: # voyons si Adam doit aller dans l'attracteur gagnant = successeurs != [] # Pas gagnant s'il n'y a pas de successeurs et pas dans l'objectif. for indice in successeurs: if iv[indice] is None: gagnant = False if gagnant: iv[i] = tour elif iv[i] is None: # donc not propriétaire, voyons si Eve peut aller dans l'attracteur ou_aller = None for indice in successeurs: if iv[indice] is not None: if (ou_aller is None or iv[indice] < iv[ou_aller]): # pour éviter d'avoir une ligne trop longue, on coupe en deux ou_aller = indice # Meilleur coup a priori if ou_aller is not None: iv[i] = tour rep[i] = ou_aller return rep ## Tests : ### print(strategie(arene, [0, 5])) # Exercice 6 def intersection(liste1, liste2): """Intersection de deux listes. """ return [i for i in liste1 if i in liste2] # Pour cet exercice, on calcule successivement les attracteurs des ensembles en question. # L'ensemble gagnant global est l'ensemble des sommets qui permet d'atteindre # le premier ensemble gagnant tout en permettant de continuer à atteindre les ensembles. # Ainsi, parmi les éléments du premier ensemble gagnant, seuls ceux qui permettent ensuite # d'atteindre le deuxième ensemble gagnant sont à maintenir, et encore, # le deuxième ensemble gagnant est à restreindre selon le même principe, et ainsi de suite. # Par conséquent, on calcule depuis le fond, car le dernier ensemble gagnant n'a pas de restriction # et permet de restreindre les précédents successivement. def attracteur_accessibilite_successive(arene, objectifs): """Calcule l'ensemble gagnant pour Ève dans un jeu d'accessibilité successive, où l'objectif à atteindre est une liste de listes d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Le but pour Ève est d'atteindre successivement (mais pas forcément consécutivement) chacun des ensembles de la liste. """ attracteur_precedent = list(range(len(arene))) # a priori tout est bon for objectif in objectifs[::-1]: # on étudie depuis le fond vrai_objectif = intersection(objectif, attracteur_precedent) # Il faut atteindre l'objectif et pouvoir atteindre les suivants attracteur_precedent = attracteur(arene, vrai_objectif) # On en déduit l'attracteur pour cet objectif return attracteur_precedent # Première version ## Tests : ### print(attracteur_accessibilite_successive(arene, [[0, 5], [2, 5]])) # 0, 3, 4 et 5 ### print(attracteur_accessibilite_successive(arene, [[2, 5], [0, 5]])) # Seulement 3, 4 et 5 ### print(attracteur_accessibilite_successive(arene, [[0], [0]])) # Vérification que tous les objectifs sont remplis en même temps : si on démarre en 0 (autrement inaccessible), c'est gagné def strategie_accessibilite_successive(arene, objectifs): """ Calcule une stratégie pour Ève dans un jeu d'accessibilité successive, où l'objectif à atteindre est une liste de listes d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Le but pour Ève est d'atteindre successivement (mais pas forcément consécutivement) chacun des ensembles de la liste. La stratégie est gagnante depuis l'attracteur et indéfinie ailleurs : la liste de listes retournée indique quel coup jouer suivant le nombre d'objectifs successifs déjà atteints, l'indice du sommet, et l'élément à l'indice i est "OK" si le sommet à l'indice i de l'arène est dans l'objectif actuel, -1 si ce sommet appartient à Adam sans être dans l'objectif actuel, None si ce sommet appartient à Ève mais n'est pas dans l'attracteur actuel et un certain k sinon, sachant que le sommet k reste dans l'attracteur actuel et rapproche Ève de son objectif. """ attracteur_precedent = list(range(len(arene))) strategies = [] for objectif in objectifs[::-1]: vrai_objectif = intersection(objectif, attracteur_precedent) strat = strategie(arene, vrai_objectif) attracteur_precedent = attracteur(arene, vrai_objectif) strategies.append(strat) return strategies[::-1] ## Tests : ### print(strategie_accessibilite_successive(arene, [[0, 5], [2, 5]])) ### print(strategie_accessibilite_successive(arene, [[2, 5], [0, 5]])) # Exercice 7 # L'ensemble gagnant pour un jeu de Büchi est l'attracteur pour le sous-ensemble X de l'objectif # pour lequel chaque élément de X permet d'atteindre un élément de X. # Il se construit alors en intersectant l'objectif avec l'attracteur "strict" jusqu'à atteindre un point fixe. def attracteur_strict(arene, objectif): """Calcule l'ensemble gagnant pour Ève dans un jeu d'accessibilité, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. On impose au moins un déplacement pour qu'un élément soit dans l'attracteur. Un éventuel sommet d'Adam sans successeur n'est pas déclaré gagnant s'il n'est pas explicitement dans l'objectif (il faut éviter d'avoir de tels sommets en pratique). """ a_n = None a_np1 = [] while a_np1 != a_n: a_n = a_np1[:] for i, (proprietaire, successeurs) in enumerate(arene): if inclus(successeurs, a_n + objectif) and proprietaire: # Adam doit aller dans l'attracteur if i not in a_np1 and successeurs != []: # pas de doublons a_np1.append(i) elif commun(successeurs, a_n + objectif) and not proprietaire: # Eve peut y aller if i not in a_np1: a_np1.append(i) return a_n # Après stabilisation ## Tests : ### print(attracteur_strict(arene, [0, 5])) # 0 n'est plus mentionné, car on ne peut pas retourner en 0 ni aller en 5 depuis 0 def vrai_objectif_Buchi(arene, objectif): """Calcule l'objectif d'accessibilité équivalent pour Ève dans un jeu de Büchi, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Le but pour Ève est d'être en mesure d'atteindre une infinité de fois l'objectif de Büchi dans une partie infinie. L'objectif d'accessibilité est le sous-ensemble de l'objectif de Büchi qui permet cette accessibilité répétée une infinité de fois. Attention : il faut adapter le calcul de l'attracteur car on doit quitter un sommet pour considérer qu'on y est retourné. """ attr_actu = objectif # attracteur actuel attr_prec = list(range(len(arene))) # attracteur précédent while attr_actu != attr_prec: attr_prec = attr_actu attr_actu = intersection(attr_prec, attracteur_strict(arene, attr_prec)) return attr_actu ## Tests : ### print(vrai_objectif_Buchi(arene, [0, 5])) # Seulement 5 def attracteur_Buchi(arene, objectif): """Calcule l'ensemble gagnant pour Ève dans un jeu de Büchi, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Le but pour Ève est d'être en mesure d'atteindre une infinité de fois l'objectif dans une partie infinie. """ vrai_objectif = vrai_objectif_Buchi(arene, objectif) return attracteur(arene, vrai_objectif) # Et pour finir on fait l'attracteur (ou strict, car les éléments de l'objectif dans l'attracteur sont dans l'attracteur strict à ce stade) ## Tests : ### print(attracteur_Buchi(arene, [0, 5])) # … donc seulement 3, 4 et 5 def strategie_stricte(arene, objectif): """Calcule une stratégie pour Ève dans un jeu d'accessibilité, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Une modification par rapport à la fonction strategie : Eve ne peut gagner instantanément et doit faire au moins un mouvement. La stratégie est gagnante depuis l'attracteur strict et indéfinie ailleurs : la liste retournée indique quel coup jouer suivant l'indice du sommet, et l'élément à l'indice i est -1 si le sommet à l'indice i appartient à Adam, None si ce sommet appartient à Ève mais n'est pas dans l'attracteur strict et un certain k sinon, sachant que le sommet k reste dans l'attracteur strict et rapproche Ève de son objectif. """ rep = [None for _ in arene] # None à la fin : Peu importe le coup, Ève n'a pas de stratégie gagnante. iv = [None for _ in arene] # À quelle itération un sommet est-il mis dans le a_n virtuel ? ("indice de victoire") for i in range(len(arene)): if arene[i][0]: rep[i] = -1 # Sommet d'Adam : stratégie non définie changement = True tour = 0 while changement: # Quelque chose s'est passé tour += 1 changement = False for i, (proprietaire, successeurs) in enumerate(arene): if proprietaire and iv[i] is None: # voyons si Adam doit aller dans l'attracteur gagnant = successeurs != [] for indice in successeurs: if iv[indice] is None and indice not in objectif: gagnant = False if gagnant: iv[i] = tour elif iv[i] is None: # donc not propriétaire, voyons si Eve peut aller dans l'attracteur ou_aller = None for indice in successeurs: if indice in objectif: ou_aller = indice break # J'ai craqué ! if iv[indice] is not None: if (ou_aller is None or iv[indice] < iv[ou_aller]): # pour éviter d'avoir une ligne trop longue, on coupe en deux ou_aller = indice # Meilleur coup a priori if ou_aller is not None: iv[i] = tour rep[i] = ou_aller return rep ## Tests : ### print(strategie_stricte(arene, [0, 5])) def strategie_Buchi(arene, objectif): """Calcule une stratégie pour Ève dans un jeu de Büchi, où l'objectif à atteindre est une liste d'indices des sommets dans l'arène, elle-même liste de sommets formés d'un booléen indiquant le propriétaire (False pour Ève et True pour Adam) et de la liste des indices dans la liste où se situe un successeur du sommet courant. Le but pour Ève est d'être en mesure d'atteindre une infinité de fois l'objectif dans une partie infinie. La stratégie est gagnante depuis l'attracteur et indéfinie ailleurs : la liste retournée indique quel coup jouer suivant l'indice du sommet, et l'élément à l'indice i est -1 si le sommet à l'indice i appartient à Adam None si ce sommet appartient à Ève mais n'est pas dans l'attracteur final et un certain k sinon de sorte qu'en jouant systématiquement vers le sommet donné par la stratégie, Eve gagne effectivement les parties démarrant dans son ensemble gagnant. Il faut adapter la stratégie comme on a adapté l'attracteur précédemment. """ vrai_objectif = vrai_objectif_Buchi(arene, objectif) return strategie_stricte(arene, vrai_objectif) ## Tests : ### print(strategie_Buchi(arene, [0, 5])) # Exercice 8 def successeurs_morpion(config, joueur): """Détermine les successeurs d'une configuration du morpion, celle-ci étant un triplet de triplets de "X", "O" ou "" avec l'information du joueur dont c'est le tour. La valeur de retour est une liste contenant des listes de taille deux, formées de la nouvelle configuration et de la position où un coup a été joué. """ adversaire = {"X" : "O", "O" : "X"} liste = [] for i in range(3): for j in range(3): if config[i][j] == "": nvconf = () for k in range(3): nvsousconf = () for l in range(3): if (k, l) == (i, j): nvsousconf += (joueur, ) else: nvsousconf += (config[k][l], ) nvconf += (nvsousconf, ) liste.append([(nvconf, adversaire[joueur]), (i, j)]) return liste def victoire(config): """Détermine si un joueur a gagné dans une configuration du morpion, qui est un triplet de triplets de "X", "O" ou "". Si "X" a gagné, retourne -1, si "O" a gagné, retourne 1, sinon retourne 0. """ vainqueur = {"X" : -1, "O" : 1} for i in range(3): if config[i][0] == config[i][1] == config[i][2] != "": return vainqueur[config[i][0]] if config[0][i] == config[1][i] == config[2][i] != "": return vainqueur[config[0][i]] if config[0][0] == config[1][1] == config[2][2] != "": return vainqueur[config[1][1]] if config[0][2] == config[1][1] == config[2][0] != "": return vainqueur[config[1][1]] return 0 def morpion(): """Construit le dictionnaire avec une stratégie optimale pour le morpion. Les clés sont un encodage des configurations possibles avec "X", "O" et "" mis dans des triplets de triplets, avec l'information du joueur dont c'est le tour, et les éléments sont les positions où jouer quand on est O pour garantir la victoire si l'adversaire joue mal ou a minima la nulle. Dans le cas où une position est déjà victorieuse, on met dans le dictionnaire l'information -1 si "X" a gagné et 1 si "O" a gagné. Dans le cas où une position est non victorieuse mais remplie, on met 0. Si c'est au tour de "X", seule l'information -1, 0 ou 1 est donnée. """ configs = {} def mouline(configuration): if configuration in configs: # déjà étudié par ailleurs (confluence) if type(configs[configuration]) == tuple: return configs[configuration][0] # cas spécial si c'est à "O" de jouer, le coup préconisé est-il gagnant ou pour faire un match nul ? return configs[configuration] config = configuration[0] est_on_O = configuration[1] == "O" joueur = victoire(config) suivants = successeurs_morpion(config, configuration[1]) if joueur: configs[config] = joueur return joueur elif suivants == []: configs[config] = 0 return 0 else: resultats = [] for ((config2, adversaire), coup) in suivants: resultat = mouline((config2, adversaire)) resultats.append((resultat, coup)) if est_on_O: renvoyer = -1 for i in range(len(resultats)): if resultats[i][0] == 1: configs[configuration] = (1, resultats[i][1]) return 1 elif resultats[i][0] == 0: configs[configuration] = (0, resultats[i][1]) # a priori renvoyer = 0 if renvoyer == -1: configs[configuration] = (-1, None) # On est fichu return renvoyer else: renvoyer = 1 for i in range(len(resultats)): if resultats[i][0] == -1: configs[configuration] = -1 return -1 elif resultats[i][0] == 0: renvoyer = 0 configs[configuration] = renvoyer return renvoyer vide = (("", "", ""), ("", "", ""), ("", "", "")) mouline((vide, "X")) mouline((vide, "O")) for config in configs: if type(configs[config]) == tuple: # on retire l'information qui ne servait que pour la récursion configs[config] = configs[config][1] return configs ## Tests : ### dico = morpion() ### print(dico[((("X", "", ""), ("", "O", "O"), ("", "X", "O")), "X")]) # Quoi qu'il fasse c'est perdu : 1 ### print(dico[((("", "", ""), ("", "", ""), ("", "", "")), "O")]) # A priori on peut toujours faire une partie nulle, donc (2, 2) par défaut parce qu'on met à jour à chaque 0 rencontré ici. ### print(dico[((("", "O", ""), ("", "", ""), ("", "", "")), "X")]) # Là aussi c'est encore 0 car même ce mauvais coup n'est pas grave a priori. # Exercice 9 def arene_marienbad(): """Construit l'arène du jeu de Marienbad. Il s'agit d'un jeu où les joueurs retirent à tour de rôle autant d'objets (au moins un) d'un tas non vide, en commençant avec quatre tas ayant respectivement 1, 3, 5 et 7 objets. Celui qui retire le dernier objet a perdu (mais pour l'arène ce n'est pas encore considéré). La valeur de retour est un triplet formé par une liste, un dictionnaire et une liste à la manière des arènes du TP. Les clés du dictionnaire sont toutes les configurations possibles et les valeurs sont les indices du sommet correspondant dans l'arène. Les éléments de la première liste sont les clés du dictionnaire correspondant, renversant l'indexation. """ arene = [[True, []]] indices = {((1, 3, 5, 7), True) : 0} sommets = [((1, 3, 5, 7), True)] for i in range(2): for j in range(4): for k in range(6): for l in range(8): if i + j + k + l < 16: for b in [False, True]: indices[((i, j, k, l), b)] = len(arene) arene.append((b, [])) sommets.append(((i, j, k, l), b)) for i in range(2): for j in range(4): for k in range(6): for l in range(8): for b in [False, True]: if i + j + k + l < 16 or b: valeurs = (i, j, k, l) for tas in range(4): for moins in range(valeurs[tas]): valeurs2 = valeurs[:tas] + (moins, ) + valeurs[tas+1:] indice1 = indices[(valeurs, b)] indice2 = indices[(valeurs2, not b)] arene[indice1][1].append(indice2) return sommets, indices, arene def strategie_marienbad(): """Détermine une stratégie gagnante pour Ève au jeu de Marienbad. La valeur de retour est un dictionnaire donnant le nombre d'objets à laisser après chaque coup d'Ève. Si Ève n'a pas de stratégie gagnante depuis un sommet, l'élément associé du dictionnaire est None. """ sommets, indices, arene = arene_marienbad() objectif = [indices[((0, 0, 0, 0), False)]] # Pour gagner, il faut qu'il ne reste plus d'objet et que ce soit le tour d'Ève # creer_boucle = indices[((0, 0, 0, 0), True)] # Dans la version précédente de l'attracteur, un sommet sans successeur était perdant pour son propriétaire. # arene[creer_boucle][1].append(creer_boucle) # Ces deux lignes étaient alors nécessaire. strat = strategie(arene, objectif) rep = {} for i in range(len(strat)): if not arene[i][0]: # C'est à Ève de jouer if strat[i] in [None, "OK"]: # Soit Ève ne peut pas gagner, soit on a le cas particulier du sommet gagnant rep[sommets[i][0]] = strat[i] else: rep[sommets[i][0]] = sommets[strat[i]][0] # On retire la mention du booléen qui ne sert à rien. return rep ## Tests : ### strat = strategie_marienbad() ### print(strat[(1, 1, 4, 4)]) # None car le sommet est perdant ### print(strat[(1, 2, 3, 4)]) # (1, 2, 3, 0) # Exercice 10 def jouer_marienbad(): """Permet de jouer contre une IA au Marienbad. Il s'agit d'un jeu où les joueurs retirent à tour de rôle autant d'objets (au moins un) d'un tas non vide, en commençant avec quatre tas ayant respectivement 1, 3, 5 et 7 objets. Celui qui retire le dernier objet a perdu. L'IA n'a pas de stratégie gagnante au début de la partie mais elle joue optimalement si son adversaire ne joue pas le seul coup gagnant à chaque tour. """ print("""Bienvenue pour une partie de Marienbad. Je commence en retirant un objet du tas de 7.""") sommets, indices, arene = arene_marienbad() strat = strategie_marienbad() # on inverse l'ordre, comme si l'humain était Adam avec 1, 3, 5, 6 comme configuration initiale (un peu en mode "vol de stratégie") cfg = (1, 3, 5, 6) amoi = True # à moi de jouer while cfg != (0, 0, 0, 0): if amoi: print("Le nombre d'objets restants par tas est ", cfg, ".", sep = "") coup_valide = False while not coup_valide: tas = input("De quel tas retirer des objets ? (entre 0 et 3) ") if tas not in ["0", "1", "2", "3"]: print("Veuillez entrer 0, 1, 2 ou 3") elif cfg[int(tas)] == 0: print("Ce tas est déjà vide") else: effectif = cfg[int(tas)] nombre = input("Combien d'objets en retirer ? (entre 1 et %d) "%effectif) if nombre not in [str(i) for i in range(1, effectif+1)]: print("Veuillez entrer un nombre entre 1 et %d."%effectif) else: nv_conf = list(cfg) nv_conf[int(tas)] = nv_conf[int(tas)] - int(nombre) cfg = tuple(nv_conf) print("C'est noté, le nouveau nombre d'objets restants par tas est ", cfg, ".", sep = "") coup_valide = True amoi = False else: print("C'est à mon tour.") nv_conf = strat[cfg] if nv_conf is None: print("Je suis assez embêté !") j = 3 while cfg[j] == 0: # Au moins une fois ce sera faux j -= 1 nv_conf = cfg[:j] + (cfg[j]-1, ) + cfg[j+1:] print("Je retire un objet du tas %d."%j) cfg = nv_conf else: for j in range(4): if cfg[j] != nv_conf[j]: nombres = ["", "un", "deux", "trois", "quatre", "cinq", "six", "sept"] pluriels = [""] * 2 + ["s"] * 6 retrait = cfg[j]-nv_conf[j] print("Je retire %s objet%s du tas %d."%(nombres[retrait], pluriels[retrait], j)) cfg = nv_conf amoi = True if amoi: print("Félicitations, vous avez gagné !") else: print("Dommage, c'est moi qui ai gagné !") ## Tests : ### jouer_marienbad()