Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Récursivité]Jeu de dames en python

Sujet résolu
    3 mai 2020 à 15:23:03

    Bonjour,

    Je tente depuis quelques jours de créer un jeu de dames sur python (sans interface graphique pour le moment, chaque chose en son temps) dans le but par la suite de tenter de créer une IA basée sur l'algorithme minmax par la suite.

    Cependant, je rencontre un problème dans une fonction qui me servirait à établir les pions jouables par un jour, sachant que la règle aux dames stipule que seuls les pions (et les dames) pouvant prendre un maximum de pions (et de dames) ont le droit d'être joué par un joueur.

    Pour faire cette fonction, je me suis lancé dans l'obscur domaine de la récursivité, qui est assez compliqué à comprendre quand on a pas fait MP spé info...

    L'objectif de cette fonction serait de me renvoyer une liste comprenant le pion étudié, puis tous les chemins qu'il peut prendre avec le nombre de pion prenable associé à chaque chemin. Voici la fonction dont je parle, sachant que le cas de la dame n'est pas encore traité car je compte le calquer sur le cas du pion :

    def obliger_manger(Pion, indice):
        """On indique tous les pions pouvant en manger d'autres."""
    
        if Pion.classe() == 'pion':
            liste_cibles = []
            for cible in liste_pions:
                nouvelle_position = Pion.position
                if Pion.possibilite_manger(cible) == True:
                    liste_cibles.append(cible)
                    indice += 1
                    if Pion.position[0] > cible.position[0] and Pion.position[1] > cible.position[1]:
                        nouvelle_position = [cible.position[0] - 1, cible.position[1] - 1]
                    elif Pion.position[0] > cible.position[0] and Pion.position[1] < cible.position[1]:
                        nouvelle_position = [cible.position[0] - 1, cible.position[1] + 1]
                    elif Pion.position[0] < cible.position[0] and Pion.position[1] < cible.position[1]:
                        nouvelle_position = [cible.position[0] + 1, cible.position[1] + 1]
                    elif Pion.position[0] < cible.position[0] and Pion.position[1] > cible.position[1]:
                        nouvelle_position = [cible.position[0] + 1, cible.position[1] - 1]
                    if nouvelle_position == Pion.position:
                        break
                    nouveau_pion = pion(damier, Pion.couleur, nouvelle_position)
                    if len(obliger_manger(nouveau_pion, indice)[1]) != 0:
                        liste_cibles.append(obliger_manger(nouveau_pion, indice)[1])
                    liste_cibles.append(indice)
                    nouveau_pion.retirer()
            return([Pion, liste_cibles])
        
    pionB = pion(damier, 1, (5,5))
    liste_pions.append(pionB)
    pionN1 = pion(damier, -1, (4,4))
    liste_pions.append(pionN1)
    pionN2 = pion(damier, -1, (6,6))
    liste_pions.append(pionN2)
    pionN3 = pion(damier, -1, (2,4))
    liste_pions.append(pionN3)
    
    # Ce que me renvoie le programme :
    
    >>> damier.plateau
    array([[ 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,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0, -1,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  1,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0, -1,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]])
    
    >>> obliger_manger(pionB, 0)
    [<__main__.pion object at 0x03C334C0>, [<__main__.pion object at 0x03C334F0>, [<__main__.pion object at 0x0C50CBE0>, 2], 1, <__main__.pion object at 0x0C50C520>, 2]]
    
    
    # Ce que j'aimerais bien qu'il me renvoie:
    
    >>> damier.plateau
    array([[ 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,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0, -1,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  1,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0, -1,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
           [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]])
    
    >>> obliger_manger(pionB, 0)
    [<__main__.pion object at 0x03C334C0>, [[<__main__.pion object at 0x03C334F0>, <__main__.pion object at 0x0C50CBE0>, 2], [<__main__.pion object at 0x0C50C520>, 1]]
    

    Et voici l'ensemble de mon programme pour le moment, sachant que le dernière fonction n'est pour le moment pas aboutie, je préfère d'abord être sûr de ce que me renvoie ma fonction obliger_manger^^:

    # coding = utf-8
    
    import numpy as np
    
    
    # -------------------- CLASSES DU JEU DE DAMES --------------------------
    
    
    class damier():
    
        def __init__(self):
            """Les cases vides sont symbolisées par des 0."""
    
            self.plateau = np.zeros((10,10), dtype = int)
            self.coordonneesX = [i for i in range(10)]
            self.coordonneesY = [i for i in range(10)]
    
    class pion():
    
        def __init__(self, damier, couleur, position):
            """La variable couleur vaut 1 ou -1, et position est un couple de variables."""
            
            self.couleur = couleur
            self.position = position
            self.damier = damier
            self.damier.plateau[self.position[0]][self.position[1]] = self.couleur
            self.etat = True
    
    
        def classe(self):
            return('pion')
        
    
        def retirer(self):
            """C'est relativement évident."""
    
            self.damier.plateau[self.position[0]][self.position[1]] = 0
            self.etat = False
            
    
        def placer(self, coordonnees):
            """Ca reste relativement évident."""
    
            self.position = coordonnees
            self.damier.plateau[self.position[0]][self.position[1]] = self.couleur
            self.etat = True
            
    
        def deplacer_droite(self, coordonnees):
            """La donnée coordonnees est un couple de variables.
               Pour déplacer un pion, on détermine la droite ou la gauche dans le sens de l'avancée du pion."""
    
            if self.etat == False:
                return("Le pion n'est pas sur le plateau.")
            
            if np.sign(self.couleur) == 1:
                if (coordonnees[0] == self.position[0] - 1) and (coordonnees[1] == self.position[1] + 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                    self.retirer()
                    self.placer(coordonnees)
                else:
                    print("Mouvement impossible.")
            else:
                if (coordonnees[0] == self.position[0] + 1) and (coordonnees[1] == self.position[1] - 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                    self.retirer()
                    self.placer(coordonnees)
                else:
                    print("Mouvement impossible.")
                    
    
        def deplacer_gauche(self, coordonnees):
            """Voir les remarques précédentes."""
    
            if self.etat == False:
                return("Le pion n'est pas sur le plateau.")
            
            if np.sign(self.couleur) == 1:
                if (coordonnees[0] == self.position[0] - 1) and (coordonnees[1] == self.position[1] - 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                    self.retirer()
                    self.placer(coordonnees)
                else:
                    print("Mouvement impossible.")
            else:
                if (coordonnees[0] == self.position[0] + 1) and (coordonnees[1] == self.position[1] + 1) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                    self.retirer()
                    self.placer(coordonnees)
                else:
                    print("Mouvement impossible.")
                    
    
        def possibilite_manger(self, pion):
            """On regarde si le pion peut en manger un autre."""
    
            if self.etat == False:
                return False
    
            if np.sign(pion.couleur) != np.sign(self.couleur) :
                if pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] + 1] == 0:
                    return True
                elif pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] - 1] == 0:
                    return True
                elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
                    return True
                elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
                    return True
            return False
            
        
        def manger(self, pion):
            """On mange le pion."""
    
            if self.possibilite_manger(pion) == False:
                return("Mouvement impossible.")
    
            if np.sign(pion.couleur) != np.sign(self.couleur) :
                if pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] + 1] == 0:
                    self.retirer()
                    self.placer((pion.position[0] + 1, pion.position[1] + 1))
                    pion.retirer()
                elif pion.position[0] == self.position[0] + 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] + 1, pion.position[1] - 1] == 0:
                    self.retirer()
                    self.placer((pion.position[0] + 1, pion.position[1] - 1))
                    pion.retirer()
                elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] - 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
                    self.retirer()
                    self.placer((pion.position[0] - 1, pion.position[1] - 1))
                    pion.retirer()
                elif pion.position[0] == self.position[0] - 1 and pion.position[1] == self.position[1] + 1 and self.damier.plateau[pion.position[0] - 1, pion.position[1] - 1] == 0:
                    self.retirer()
                    self.placer((pion.position[0] - 1, pion.position[1] + 1))
                    pion.retirer()
            
    
    class dame(pion):
    
        def classe(self):
            return('dame')
    
    
        def deplacer_droite(self, coordonnees):
            """La donnée coordonnees est un couple de variables.
               Pour déplacer une dame, on détermine la droite ou la gauche dans le sens de l'avancée du pion.
               Une dame blanche vaut 2, une dame noire vaut -2."""
    
            if self.etat == False:
                return("La dame n'est pas sur le plateau.")
            
            if np.sign(self.couleur) == 1:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] + i) <= 10:
                    if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] + i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                        self.retirer()
                        self.placer(coordonnees)
                        break
                    i += 1
            else:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
                    if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] - i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                        self.retirer()
                        self.placer(coordonnees)
                        break
                    i += 1
            if self.position != coordonnees:
                print("Mouvement impossible.")
                
                    
        def deplacer_gauche(self, coordonnees):
            """La donnée coordonnees est un couple de variables.
               Pour déplacer une dame, on détermine la droite ou la gauche dans le sens de l'avancée du pion."""
    
            if self.etat == False:
                return("La dame n'est pas sur le plateau.")
            
            if np.sign(self.couleur) == 1:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
                    if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] - i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                        self.retirer()
                        self.placer(coordonnees)
                        break
                    i += 1
            else:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] + i) <= 10:
                    if (coordonnees[0] == self.position[0] - i) and (coordonnees[1] == self.position[1] + i) and (self.damier.plateau[coordonnees[0]][coordonnees[1]] == 0):
                        self.retirer()
                        self.placer(coordonnees)
                        break
                    i += 1
            if self.position != coordonnees:
                print("Mouvement impossible.")
                
                
        def possibilite_manger(self, pion, coordonnees):
            """On regarde si la dame peut en manger un pion."""
    
            if self.etat == False:
                return False
    
            if np.sign(pion.couleur) != np.sign(self.couleur) and self.damier.plateau[coordonnees[0],coordonnees[1]] == 0:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
                    if pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] + i:
                        if i >= 0:
                            if coordonnees[0] > pion.position[0] and coordonnees[1] > pion.position[1]:
                                return True
                        elif coordonnees[0] < pion.position[0] and coordonnees[1] < pion.position[1]:
                            return True
                    elif pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] - i:
                        if i >= 0:
                            if coordonnees[0] > pion.position[0] and coordonnees[1] < pion.position[1]:
                                return True
                        elif coordonnees[0] < pion.position[0] and coordonnees[1] > pion.position[1]:
                            return True
                    i += 1
                return False
    
            
        def manger(self, pion, coordonnees):
            """On mange le pion."""
    
            if self.possibilite_manger(pion, coordonnees) == False:
                return("Mouvement impossible")
    
            if np.sign(pion.couleur) != np.sign(self.couleur) and self.damier.plateau[coordonnees[0],coordonnees[1]] == 0:
                i = self.position[0] - 9
                while (self.position[0] - i) >= 0 and (self.position[1] - i) >= 0:
                    if pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] + i:
                        self.retirer()
                        self.placer((coordonnees[0], coordonnees[1]))
                        pion.retirer()
                    elif pion.position[0] == self.position[0] + i and pion.position[1] == self.position[1] - i:
                        self.retirer()
                        self.placer((coordonnees[0], coordonnees[1]))
                        pion.retirer()
                    i += 1
    
    
    
    
    # -------------------- VARIABLES ET LISTES ------------------------------
    
    
    damier = damier()
    liste_pions = []
    liste_dames = []
    
    
    
    
    # -------------------- FONCTIONS ET REGLES ------------------------------
    
    
    def init_partie(damier, liste_pions):
        """Mise en place des pions pour le début de la partie."""
        
        for x in damier.coordonneesX:
            for y in damier.coordonneesY:
                if (x%2 != y%2) and x < 4:
                    liste_pions.append(pion(damier, -1, (x,y)))
                elif (x%2 != y%2) and x > 5:
                    liste_pions.append(pion(damier, 1, (x,y)))
                    
    
    def pion_vers_dame(damier, liste_pions, liste_dames):
        """On vérifie tous les pions, et on change ceux qui sont à dame."""
        
        for pion in liste_pions:
            if pion.couleur == 1 and pion.position[0] == 0:
                pion.retirer()
                liste_dames.append(dame(damier, 2, (pion.position[0],pion.position[1])))
                liste_pions.remove(pion)
            if pion.couleur == -1 and pion.position[0] == 9:
                pion.retirer()
                liste_dames.append(dame(damier, -2, (pion.position[0],pion.position[1])))
                liste_pions.remove(pion)
                
        
    def fin_partie(liste_pions, liste_dames):
        """La partie se termine lorsqu'il ne reste plus qu'une couleur en jeu."""
        
        try:
            for pion in liste_pions:
                if pion.couleur != liste_pions[0].couleur:
                    return False
            for dame in liste_dames:
                if dame.couleur != liste_pions[0].couleur:
                    return False
            return True
        except:
            for dame in liste_dames:
                if dame.couleur != liste_dames[0].couleur:
                    return False
            return True
    
    
    def obliger_manger(Pion, indice):
        """On indique tous les pions pouvant en manger d'autres."""
    
        if Pion.classe() == 'pion':
            liste_cibles = []
            for cible in liste_pions:
                nouvelle_position = Pion.position
                if Pion.possibilite_manger(cible) == True:
                    liste_cibles.append(cible)
                    indice += 1
                    if Pion.position[0] > cible.position[0] and Pion.position[1] > cible.position[1]:
                        nouvelle_position = [cible.position[0] - 1, cible.position[1] - 1]
                    elif Pion.position[0] > cible.position[0] and Pion.position[1] < cible.position[1]:
                        nouvelle_position = [cible.position[0] - 1, cible.position[1] + 1]
                    elif Pion.position[0] < cible.position[0] and Pion.position[1] < cible.position[1]:
                        nouvelle_position = [cible.position[0] + 1, cible.position[1] + 1]
                    elif Pion.position[0] < cible.position[0] and Pion.position[1] > cible.position[1]:
                        nouvelle_position = [cible.position[0] + 1, cible.position[1] - 1]
                    if nouvelle_position == Pion.position:
                        break
                    nouveau_pion = pion(damier, Pion.couleur, nouvelle_position)
                    if len(obliger_manger(nouveau_pion, indice)[1]) != 0:
                        liste_cibles.append(obliger_manger(nouveau_pion, indice)[1])
                    liste_cibles.append(indice)
                    nouveau_pion.retirer()
            return([Pion, liste_cibles])
        else:
            pass
                                            
                    
    def tour_joueur(damier, liste_pions, liste_dames):
        """Le joueur joue les blancs."""
        
        liste_pions_jouables = []
        for pion in liste_pions:
            if pion.couleur == 1:
                if liste_pions_jouables == []:
                    liste_pions_jouables.append(obliger_manger(pion, 0))
                else:
                    if obliger_manger(pion, 0)[1] == liste_pions_jouables[0][1]:
                        liste_pions_jouables.append(obliger_manger(pion, 0))
                    elif obliger_manger(pion, 0)[1] > liste_pions_jouables[0][1]:
                        liste_pions_jouables = []
                        liste_pions_jouables.append(obliger_manger(pion, 0))
        for dame in liste_pions:
            if dame.couleur == 1:
                if liste_pions_jouables == []:
                    liste_pions_jouables.append(obliger_manger(dame, 0))
                else:
                    if obliger_manger(dame, 0)[1] == liste_pions_jouables[0][1]:
                        liste_pions_jouables.append(obliger_manger(dame, 0))
                    elif obliger_manger(dame, 0)[1] > liste_pions_jouables[0][1]:
                        liste_pions_jouables = []
                        liste_pions_jouables.append(obliger_manger(dame, 0))
        for pion in liste_pions_jouables:
            if pion.classe() == 'pion':
                print("Vous pouvez jouer le pion situé aux coordonnees {} ; {}".format(pion[0].position[0] + 1, pion[0].position[1] + 1))
            if pion.classe() == 'dame':
                print("\nVous pouvez jouer la dame situé aux coordonnees {} ; {}".format(pion[0].position[0] + 1, pion[0].position[1] + 1))
        drapeau = 0
        while drapeau == 0:
            input("\nEntrez les coordonnees du pion ou de la dame que vous voulez déplacer. Exemple : (3,2).\n", coordonnees_jouees)
            coordonnees_jouees[0] -= 1
            coordonnees_jouees[1] -= 1
            for pion in liste_pions_jouables:
                if pion[0].position == coordonnees_jouees:
                    pion_selectionne = pion
                    drapeau = 1
            if drapeau == 0:
                print("Le pion ou la dame sélectionné n'est pas jouable.")

    Merci d'avance si vous pouvez m'aider, ça fait plusieurs jours que j'essaie de corriger cette fonction et je n'y arrive vraiment pas !

    • Partager sur Facebook
    • Partager sur Twitter
      3 mai 2020 à 15:58:59

      tu utilises un algorithme de remplissage à pile ?
      • Partager sur Facebook
      • Partager sur Twitter

      "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

        3 mai 2020 à 16:01:54

        Bonjour, non je ne sais pas comment cela fonctionne, je connais le fonctionnement d'une pile mais je n'ai jamais vraiment étudié ses applications 

        • Partager sur Facebook
        • Partager sur Twitter
          3 mai 2020 à 16:26:29

          Curieux, quelqu'un m'avait posé le problème (ou qqchose de très proche) en début d'année, voici à quoi j'étais arrivé :

          import sys
          N = 10
          
          def saut(lig, col, dl, dc, blancs, damier):
              return (0 <= lig + dl < N and 0 <= col + dc < N
                      and (lig + dl // 2, col + dc // 2) in blancs
                      and (lig + dl, col + dc) not in blancs
                      and damier[lig + dl][col + dc] != 'x')
          
          
          def f(lig, col, blancs, damier):
              sauts = [((lig + dl, col + dc), (lig + dl // 2, col + dc // 2))
                       for (dl, dc) in ((-2, 2), (-2, -2), (2, -2), (2, 2))
                       if saut(lig, col, dl, dc, blancs, damier)]
              if not sauts:
                  return 0
              L = []
              for (moi, blanc) in sauts:
                  damier[lig][col] = '.'
                  i, j = moi
                  damier[i][j] = 'x'
                  blancs.discard(blanc)
                  L.append(f(i, j, blancs, damier))
                  blancs.add(blanc)
                  damier[lig][col] = 'x'
                  damier[i][j] = '.'
              return 1 + max(L)
          
          
          def couleur(damier, coul):
              couleurs = set()
              for i in range(N):
                  for j in range(N):
                      if damier[i][j] == coul:
                          couleurs.add((i, j))
              return couleurs
          
          def main(damier):
              damier = [list(ligne) for ligne in damier.split()]
              blancs = couleur(damier, 'o')
              noirs = couleur(damier, 'x')
              if not noirs:
                  return 0
              return max(f(lig, col, blancs, damier) for (lig, col) in noirs)
          
          damier = (""""\
          ..........
          ........o.
          .......x..
          ..o.o.o...
          ..........
          ....o.....
          ...x......
          ..........
          ..........
          ..........""")
          
          print(main(damier))



          Effectivement ça peut se faire récursivement. L'idée de base est simple : tu regardes les sauts que tu peux faire (ligne 12), tu lances récursivement (ligne 23) ta fonction pour chacun des sauts (ligne 18) et tu prends le max (ligne 27 et 44). Faut juste faire gaffe à remettre le plateau en état (lignes 24-25-26) quand on termine la fonction récursive. Celui qui joue (moi) a les noir (pions x).

          Peut-être que le code ci-dessus pourra t'être utile.

          • Partager sur Facebook
          • Partager sur Twitter
            3 mai 2020 à 17:01:41

            Si on part d'un pion en (i, j), on peut parcourir son voisinage pour en sortir une liste des pions à prendre. Puis pour chaque pions à prendre, on peut "simuler" la prise du pion, se retrouver à une nouvelle position (i', j') et recommencer tant que la liste de pions à prendre n'est pas vide.

            Première étape, parcourir le voisinage de (i, j) pour sortir une liste de (pion à prendre, nouvelle position, les prises suivantes).

            A cette étape, les prises suivantes est une liste vide.

            Si cette liste est vide, on a fini et on retourne []

            Sinon, on itère sur les éléments de la liste et à chaque itération:

            • on retire le pion à prendre
            • on s'appelle soit même avec la nouvelle position (et le damier étant global).
            • on récupère une liste que l'on range dans les prises suivantes
            • on se remet le pion qui a été pris,
            • on replace le pion en (i, j)

            et on recommence avec le pion suivant.

            A la fin, on obtient une liste qui ressemble plutôt à un arbre puisqu'à chaque pion à prendre est associée "les prises suivantes" plus ou moins profond.

            Reste à choisir le chemin le plus long... et peut être optimiser l'algorithme pour éviter de tout balayer.

            Ce que je raconte là est un algorithme. Çà s'écrit d'abord en français. On le teste un peu sur quelques exemples pour s'assurer qu'on n'a rien oublié. Et quand on a l'impression que çà tient la route, on peut le coder pour voir si il vole.

            • Partager sur Facebook
            • Partager sur Twitter
              3 mai 2020 à 17:24:14

              Perso je fais pas de fonction récursive, j'itère sur une liste que je remplis au fur et à mesure. La dernière entrée est forcément le plus long chemin.
              • Partager sur Facebook
              • Partager sur Twitter

              "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                3 mai 2020 à 17:26:08

                Merci pour vos réponses !

                PascalOrtiz, ton programme est intéressant, mais comment ensuite peux-tu retrouver le chemin entier ? Car j'ai l'impression que ton programme ne renvoie que le pion de plus grand indice (sauf erreur de ma part, car l'écriture de ton code est assez compacte et concise, du coup je peine un peu à le comprendre car je n'ai pas un niveau si avancé^^)

                mps, c'est globalement ce que je fais dans mon code, notamment l'idée de l'arbre, c'est ce que je fais aussi, cependant je rencontre 2 difficultés : 

                • Je ne sais pas comment faire pour faire retomber ma variable "indice" à 0 quand je passe sur une autre branche de l'arbre, ce qui fait que mon programme me renvoie mon arbre avec un indice qui ne fait que croître, et je ne sais pas où dire au programme de fixer la variable indice à 0 car l'appel récursif empêchera alors de faire grimper cet indice pour les branches plus longues.
                • Je ne sais pas non plus, encore pour des raisons de récursivité, comment réussir à renvoyer une liste de la forme [[pion1, pion2, 2], [pion3, 1]], où pion1 et pion2 représentent un chemin de prises et pion3 un autre, car mon programme me renvoie plutôt [pion1, 1, [pion2, 2], pion3, 2], ce qui rend le parcours de l'arbre plus compliqué ensuite.

                josmiley a écrit:

                Perso je fais pas de fonction récursive, j'itère sur une liste que je remplis au fur et à mesure. La dernière entrée est forcément le plus long chemin.

                Que veux-tu dire par là ? Car je ne vois pas comment mettre ça en oeuvre avec plusieurs chemins possibles. Si il y a une solution qui exclut la récursivité, je suis preneur !

                Merci pour votre aide !



                -
                Edité par BouloukaouzeOulouzek 3 mai 2020 à 17:39:05

                • Partager sur Facebook
                • Partager sur Twitter
                  3 mai 2020 à 18:14:14

                  je vais essayé de t'expliquer pour 1 pion

                  un chemin se lit ainsi 

                  [position de depart, position pion adverse pris, position suivante, position pion adverse pris, position suivante, ... , position pion adverse pris, position finale]


                  au début chaque chemin n'est que la position d'un pion.

                  chemins = [[(2.4)],[chemin autre pion],...[chemin dernier pion]]


                  pour chaque chemin de la liste chemins, tu lis la dernière position de ton pion(soit chemin[-1]) et tu ajoutes à chemins le chemin actuel étendu des pions adverses pris et des nouvelles positions de ton pion.

                  par exemple ton pion en (2,4) peut prendre le pion adverse en (1,5) et se retrouvera alors en (0,6)

                  chemins vaudra

                  [[(2.4)],...,[(2,4),(1,5),(0,6)]]

                  ton pion peut aussi prendre en (3,5) et se retrouvera en (4,6)

                  chemins vaudra

                  [[(2.4)],...,[(2,4),(1,5),(0,6)],[(2,4),(3,5),(4,6)]]

                  l'itértion s'arrêtera quand il n'y aura plus de chemin à ajouter, et les chemins les plus longs sont toujours à la fin de la liste.


                  -
                  Edité par josmiley 3 mai 2020 à 18:17:23

                  • Partager sur Facebook
                  • Partager sur Twitter

                  "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                    3 mai 2020 à 18:35:15

                    Ah oui bien vu !

                    Donc dans cette situation c'est plutôt une boucle while qu'on utilise alors, si je comprends bien.

                    • Partager sur Facebook
                    • Partager sur Twitter
                      3 mai 2020 à 18:39:20

                      Non, for chemin in chemins, c'est un truc assez cool en python de pouvoir append une liste en cours d'itération.
                      • Partager sur Facebook
                      • Partager sur Twitter

                      "il vaut mieux vivre en France qu'en Italie, la France a de plus jolies prisons"

                        3 mai 2020 à 18:59:38

                        Ok, je vais essayer ça, merci beaucoup à toi et aux autres qui ont également proposé des solutions !
                        • Partager sur Facebook
                        • Partager sur Twitter
                          3 mai 2020 à 19:15:38

                          BouloukaouzeOulouzek a écrit:

                          mps, c'est globalement ce que je fais dans mon code, notamment l'idée de l'arbre, c'est ce que je fais aussi, cependant je rencontre 2 difficultés.

                          Honnêtement, je ne comprends pas votre code. A quoi sert l'indice? Pourquoi tester tous les pions (au lieu de ceux qui sont dans le voisinage de la position)? A quoi doit ressembler l'arbre qui remonte?

                          Après, çà regarde s'il est possible de manger le pion, mais çà n'a pas l'air de le manger.

                          C'est pour çà qu'il faut essayer d'écrire les choses en français avant de coder.

                          Sinon, on va le lire en se demandant ce qu'il fait. Sûr qu'on fait çà avec un certain à priori et que si on n'y retrouve pas trop ce qu'on cherche assez vite... car on ne peut pas y passer des heures... Cà ne va pas être facile de vous aider.

                          Je ne vois pas trop l'intérêt de cet indice: il donne le niveau de ce qu'on va ajouter dans l'arbre mais après, il faudra quand même le parcourir pour sortir la branche la plus profonde.

                          et si la structure de l'arbre qui se construit à chaque itération n'est pas décrit. On sait pas trop ce qu'on veut ni à quoi çà va bien pouvoir servir.

                          • Partager sur Facebook
                          • Partager sur Twitter
                            3 mai 2020 à 23:27:38

                            BouloukaouzeOulouzek a écrit:

                            PascalOrtiz, ton programme est intéressant, mais comment ensuite peux-tu retrouver le chemin entier ? Car j'ai l'impression que ton programme ne renvoie que le pion de plus grand indice 


                            Il faut adapter le code pour récupérer un plus long chemin. J'ai essayé de le faire, le problème c'est qu'initialement le problème était pas prévu pour ça. Voici ce que ça donne, je te garantie pas que ce soit juste mais au moins tu as l'idée :

                            import sys
                            # taille du damier
                            N = 10
                             
                            def saut(lig, col, dl, dc, blancs, damier):
                                return (0 <= lig + dl < N and 0 <= col + dc < N
                                        and (lig + dl // 2, col + dc // 2) in blancs
                                        and (lig + dl, col + dc) not in blancs
                                        and damier[lig + dl][col + dc] != 'x')
                             
                             
                            def f(lig, col, blancs, damier):
                                sauts = [((lig + dl, col + dc), (lig + dl // 2, col + dc // 2))
                                         for (dl, dc) in ((-2, 2), (-2, -2), (2, -2), (2, 2))
                                         if saut(lig, col, dl, dc, blancs, damier)]
                                if not sauts:
                                    return (0, [])
                                M=0
                                for (moi, blanc) in sauts:
                                    damier[lig][col] = '.'
                                    i, j = moi
                                    damier[i][j] = 'x'
                                    blancs.discard(blanc)
                                    maxi, path=f(i, j, blancs, damier)
                                    if maxi>M:
                                        M=maxi
                                        maxi_path=path
                                        edge=(moi, (lig, col))
                                    blancs.add(blanc)
                                    damier[lig][col] = 'x'
                                    damier[i][j] = '.'
                                    
                                if M==0:
                                    moi, blanc=sauts[0]
                                    return 1, [(moi, (lig, col))]
                                maxi_path=maxi_path+[edge]
                                
                            
                                return len(maxi_path), maxi_path
                             
                             
                            def couleur(damier, coul):
                                couleurs = set()
                                for i in range(N):
                                    for j in range(N):
                                        if damier[i][j] == coul:
                                            couleurs.add((i, j))
                                return couleurs
                             
                            def main(damier):
                                damier = [list(ligne) for ligne in damier.split()]
                                print(*damier,  sep='\n')
                                blancs = couleur(damier, 'o')
                                noirs = couleur(damier, 'x')
                            
                                N, path=max(f(lig, col, blancs, damier) for (lig, col) in noirs)
                                
                                return N, [z[::-1] for z in path[::-1]]
                            
                            damier = ("""\
                            .x........
                            ..o.....o.
                            .x.....x..
                            ..o.o.o...
                            ...x......
                            ..o.o..x..
                            .o...o....
                            ..o.o.o...
                            ...o......
                            ....x.....""")
                             
                            print(*main(damier), sep='\n')
                            6
                            [((2, 7), (4, 5)), ((4, 5), (2, 3)), ((2, 3), (4, 1)), ((4, 1), (6, 3)), ((6, 3), (8, 5)), ((8, 5), (6, 7))]



                            Les indices sont (ligne, colonne) et commencent à 0. Autrement dit, tu pars de (2,7) tu manges un blanc et tu arrives en (4,5) et de là tu manges encore un blanc et tu arrives en (2, 3), etc. Fais des tests pour vérifier.

                            La fonction récursive f renvoie un tuple (N, path) où N est le nombre maximal de prises à partir de la position noire (lig, col) et path est un chemin réalisant une prise de N pions blancs.

                            EDIT : le principe est très simple : je regarde chaque case blanche voisine que je peux manger depuis la position (lig, col), je demande à la fonction récursive de me dire, une fois que j'ai mangé le pion blanc en question, combien je mangerais de nouveaux pions blancs. Ensuite, je prends la combinaison qui rapporte le plus et je la prolonge par la prise depuis (lig, col) du pion blanc qui rapporte le plus. Ce n'est pas une récursivité compliquée. Fin du EDIT

                            Tu peux aussi certainement l'écrire itérativement et probablement de manière plus efficace que ci-dessus. L'idée d'une pile comme josmiley l'a proposé est exactement ce qu'il faut. Chaque fois que tu empiles c'est que tu manges un blanc, chaque fois que tu dépiles, c'est tu as regardé toutes les possibilités de manger un éventuel voisin blanc et que tu reviens là où tu étais avant avoir mangé le dernier pion blanc. Tu dois surveiller la longueur de ta pile, quand elle est de longueur maximale comme te l'as dit josmiley, la suite des éléments de la pile te donne une combinaison qui récupère le maximum de pions. Je trouve ça moins facile à écrire, surtout pour gérer «proprement» cette longueur maximale.

                            -
                            Edité par PascalOrtiz 3 mai 2020 à 23:56:20

                            • Partager sur Facebook
                            • Partager sur Twitter
                              4 mai 2020 à 17:24:09

                              mps, effectivement l'indice ne servait à rien, je l'ai retiré.

                              PascalOrtiz, en m'inspirant du fonctionnement de ton code, je suis arrivé à une solution, et tout fonctionne bien !

                              Merci pour votre aide ! Je vais maintenant m'attaquer aux règles pour les dames...

                              • Partager sur Facebook
                              • Partager sur Twitter

                              [Récursivité]Jeu de dames en python

                              × 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.
                              • Editeur
                              • Markdown