plateau1 = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 1, 2, 2, 1, 0, 0], [2, 1, 2, 1, 2, 1, 2]] def plateau_vide(): """ plateau_vide()-> list sortie : liste de liste de 6x7 contenant des 0 Renvoie un plateau vide, c'est-à-dire une matrice de 6 lignes et 7 colonnes, rempli de 0 """ return [[0 for _ in range(7)] for _ in range(6)] def afficher(plateau): """afficher(plateau: list) Affiche le plateau, ne renvoie rien.: entrée : plateau, liste de liste représentant le plateau de jeu """ conversion = {0:"⚪", 1:"🔴", 2:"🟡"} for ligne in plateau: for element in ligne: print(conversion[element], end="") print() print() def copie(plateau): """ copie(plateau:list) -> list Renvoie une copie du plateau en argument, ne modifie pas plateau entrée : plateau, liste de liste représentant le plateau de jeu sortie : liste de liste, copie du plateau """ return [ligne.copy() for ligne in plateau] def jouer(plateau, joueur, colonne): """ jouer(plateau :list, joueur: int, colonne : int) -> list Renvoie une copie du plateau dans lequel le joueur (1 ou 2) a joué dans la colonne colonne (en supposant que c'est possible) entrées : plateau, liste de liste représentant le plateau de jeu : joueur, entier, numero du joueur (1 ou 2) : colonne, entier, numero de la colonne dans laquelle on veut mettre le jeton sortie : liste de liste, représentant le plateau dans lequel a été ajouté le jeton """ plateau1 = copie(plateau) ligne = 0 while ligne < 6 and plateau[ligne][colonne] == 0: ligne += 1 plateau1[ligne - 1][colonne] = joueur return plateau1 afficher(plateau1) afficher(jouer(plateau1, 1, 2)) # Complexité : O(n⋅m), coût de la recopie. Le reste est en O(n). # Pour obtenir une complexité en O(1), il faudrait # utiliser des listes (type liste chaînées) à remplir avec des append, pour # les colonnes, plutôt que de mettre des 0 pour les cases vides. # Et il faudrait aussi éviter la recopie avec la possibilité d'annuler un coup # grâce à pop(). def coups_possibles(plateau): """ coups_possibles(plateau:list) -> list Renvoie la liste des indices de colonnes dans lesquels on peut jouer. entrées : plateau, liste de liste représentant le plateau de jeu sortie : liste comportant les indices des colonnes possibles """ return [colonne for colonne in range(7) if plateau[0][colonne] == 0] # Complexité : O(m) plateauTest = [[1 for j in range(7)] for i in range(6)] plateauTest[0][2] = plateauTest[0][4] = 0 afficher(plateauTest) print(coups_possibles(plateauTest)) #[2, 4] inf = float('inf') dico_score = {(0, 1): -1, (0, 2): -2, (0, 3): -3, (0, 4): -inf, (1, 0): 1, (2, 0): 2, (3, 0): 3, (4, 0): inf} #CORRECTION # Segments horizontaux : 6 (ligne début) x 4 (colone début) = 24 # Segments verticaux : 3 (ligne début) x 7 (colonne début) = 21 # Segments diagonaux : 2 (symétrie) x 4 (ligne début) x 3 (colonne début) = 24 # Soit 69 segments au total. def score_segment( plateau, i, j, di, dj, dicoS=dico_score ): """Calcule le score lié au semgent (i, j), (i + di, j + dj), (i + 2×di, j + 2×dj), et (i + 3×di, j + 3×dj) entrées : plateau, liste de liste représentant le plateau de jeu : i,j: entiers, coordonnees du jeton : di,dj : entiers, direction du segment : dico_score, dictionnaire des scores au format (Nb jetons joueur1,Nb jetons joueur2 ):score sortie : entier, score du segment """ nbJetons = { 1:0, 2:0 } for k in range(4): # Calcul du nombre de jetons de chaque couleur jeton = plateau[i + k * di][ j + k * dj] if jeton != 0 : nbJetons[jeton] += 1 couple = ( nbJetons[1], nbJetons[2] ) if 0 not in couple or couple == (0, 0) or couple not in dicoS: return 0 return dicoS[couple] afficher(plateau1) print(score_segment(plateau1, 5, 0, 0, 1, dico_score)) # 0 print(score_segment(plateau1, 2, 1, 1, 0, dico_score)) # 2 print(score_segment(plateau1, 2, 1, 1, 1,dico_score)) # -2 def score_plateau(plateau, dicoS=dico_score): """ Calcule le score lié au plateau entier (teste toutes les lignes, colonnes et diagonales). entree : plateau, liste de liste représentant le plateau de jeu sortie : score, entier, score du plateau entier """ score = 0 #nbSegments =0 directions = ( (1, 0), (0, 1), (1, 1), (1, -1) ) # definition des 4 directions possibles for i in range(6): for j in range(7): for di, dj in directions: if 0 <= ( i + 3 * di ) < 6 and 0 <= (j + 3 * dj) < 7: #Vérifications importantes pour ne pas dépasser les bornes score += score_segment(plateau, i, j, di, dj) # pour compter le nombre de segments #nbSegments += 1 #print(nbSegments) return score print(score_plateau(plateau1)) #8 def strategie_j1_glouton(plateau, score_plateau): """Renvoie une copie de plateau sur laquelle le coup optimal du premier joueur a été joué.""" meilleur_score = -float(inf) #meilleur_coup = None meilleur_plateau = None for colonne in coups_possibles(plateau): plateau1 = jouer(plateau, 1, colonne) score = score_plateau(plateau1) if score > meilleur_score: meilleur_score = score #meilleur_coup = colonne meilleur_plateau = plateau1 return meilleur_plateau def strategie_j2_glouton(plateau, score_plateau): """Renvoie une copie de plateau sur laquelle le coup optimal du premier joueur a été joué.""" meilleur_score = float(inf) #meilleur_coup = None meilleur_plateau = None for colonne in coups_possibles(plateau): plateau1 = jouer(plateau, 2, colonne) score = score_plateau(plateau1) if score < meilleur_score: meilleur_score = score #meilleur_coup = colonne meilleur_plateau = plateau1 return meilleur_plateau plateau = plateau_vide() afficher(plateau) plateau = strategie_j1_glouton(plateau, score_plateau) afficher(plateau) plateau = strategie_j2_glouton(plateau, score_plateau) afficher(plateau) # Le joueur 1 va gagner. def maximin(plateau, p, score_plateau): """Renvoie le coup optimal à profondeur p pour le joueur 1 entrées : plateau, liste de liste représentant le plateau de jeu : p, entier, profondeur : score_plateau : nom de la fonction heuristique sortie : liste de liste, grille obtenue avec le meilleur coup """ liste_coups = coups_possibles(plateau) # Si pas de coup à jouer, on ne fait rien et on retourne plateau. if if p == 0: # si profondeur nulle => approche gloutonne pour obtenir le meilleur plateau # sinon on regarde chaque coup possible et appels récursifs à minimax pour chaque coup # (sauf si un unique coup possible ou si le score obtenu vaut l infini) maxi = plateau_max = for coup in liste_coups: return plateau_max def minimax(plateau, p, score_plateau): """Renvoie le coup optimal à profondeur p pour le joueur 2 entrées : plateau, liste de liste représentant le plateau de jeu : p, entier, profondeur : score_plateau : nom de la fonction heuristique sortie : liste de liste, grille obtenue avec le meilleur coup """