IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Problème de référencement pour des arbres


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Mai 2018
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Mai 2018
    Messages : 1
    Par défaut Problème de référencement pour des arbres
    Bonjour à tous, je suis en train de créer une sorte d'algorithme neuronal pour gagner au morpion (je laisse le jeu de go aux amateurs... :-°)

    Pour enregistrer un grand nombre de partie, j'ai opté pour une structure d'arbre où la profondeur p correspond à l'emplacement joué au tour p.

    Je veux donc faire un tableau qui enregistre les parties gagnées, et un autre pour les parties perdues; mais le problème c'est que lorsque j'ajoute un élément à un arbre, cet élément est également ajouté au deuxième arbre (comme si les deux variables ont la même référence).

    je vous montre le code de la classe Arbre (seule la fonction ajouter est utilisé pour l'instant) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    class Arbre():
        """
        Un abre contient des parties sous forme de liste : la liste [4,0,1,5,7] correspond à:
                                                                -J1 joue en 4
                                                                -J2 joue en 0
                                                                -J1 joue en 1
                                                                -J2 joue en 5, etc...
        on accède à toute les parties avec arbre.lister(); mais la recherche d'une partie est en O(ln(9)), donc très rapide
        """
     
        def __init__(self,value=None,fils=[]):
            self.fils = fils
            self.value = value
     
     
        def ajouter(self,liste):
            """
            ajoute une partie à l'arbre
            """
            if liste == []:   #On est arrivé à la fin de la partie
                return None
            v = liste[0]
            for k in self.fils:
                if k.value == v:     #Si une partie commencant de la même manière existe déja
                    return k.ajouter(liste[1:])  #On ajoute la fin de cette partie au fils correspondant
            #Sinon
            a = Arbre(v,[])
            a.ajouter(liste[1:])
            self.fils.append(a)  #on créé une nouvelle branche contenant la partie
     
        def descendre(self, valeur):
            """
            accéder au sous-arbre (au fils) correspondant au parties commençant par 'valeur', utilisé pour la recherche de partie
            Si aucune partie ne correspond, on renvoie None
            """ 
            for k in self.fils:
                if k.value == value:
                    return k
            return None
     
        def lister(self):
            """
            Renvoie un tableau avec toutes les parties enregistrées dans l'arbre
            """
            if self.fils == []:
                return [[self.value]]
            l=[]
            for k in self.fils:
                l+=[ [self.value]+v for v in k.lister() ]
            return l
     
        def fils_aleat(self):
            """
            Pour plus tard, lors d'une partie, on joue aléatoirment parmis les coup ayant déja été enregstré comme gagnant
            """
            return self.fils[randint(0,len(self.fils)-1)]
    et le code pour remplir les arbres (comprendre le principe des fonctions n'est pas nécéssaire, elles sont fonctionnelles) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    from random import randint
     
    def gagne(pions):
     
        lignes = [ [0,1,2],   # la grille est :       0 | 1 | 2
                [3,4,5],      #                       ---------              
                [6,7,8],      #                       3 | 4 | 5             
                [0,3,6],      #                       ----------                     
                [1,4,7],      #                       6 | 7 | 8                    
                [2,5,8],      #                                                      
                [0,4,8], 
                [2,4,6] ]     #j'ai noté les lignes gagnantes 
     
        for l in lignes:
            aux = True     #On regarde si la ligne l est rempie
            for k in l:
                if not(k in pions):
                    aux = False
            if aux==True:
                return True
        return False
     
    def simulationAleat(arbreGagne,arbrePerds):
        t=True
        pions_joueur = []
        pions_ordi = []
        cases_libres = [k for k in range(9)]
        historique = []  #le tableau correspondant à la partie en cours
        while True:
            if len(cases_libres)==0:
                return None
            if t:  #C'est à l'ordi de jouer
                k = cases_libres[randint(0,len(cases_libres)-1)] #Il joue aléatoirement parmis les cases disponibles
                pions_ordi.append(k)   #On place le pion
                cases_libres.remove(k)  #La case est plus dispo
                historique.append(k)   #on met à jour la parie
                if gagne(pions_ordi):      #si l'ordi gagne, la partie est enregistré
                    arbreGagne.ajouter(historique)
                    return None
            else: #C'est la même chose mais c'est au tour du joueur (qui joue aussi aléatoirement)
                k = cases_libres[randint(0,len(cases_libres)-1)]
                pions_joueur.append(k)
                cases_libres.remove(k)
                historique.append(k)
                if gagne(pions_joueur):  #Si le joueur gagne
                    arbrePerds.ajouter(historique)
                    return None
            t=not(t)
     
    def remplirArbre(n):  #on simule n parties
        G=Arbre(value=None)
        P=Arbre(value=None)
        for k in range(n):
            simulationAleat(G,P)
        return G,P
    Pour accéder à l'ensemble des parties, c'est la fonction Arbre.lister(),

    Essayez de taper :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    G,P=remplirArbre(100)
    print(G.lister())
    print(P.lister())
    les tableaux sont égaux !

    Merci d'avance, je peux apporter plus d'info sur la structure du programme si nécessaire.

  2. #2
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 756
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 756
    Par défaut
    Salut,

    Citation Envoyé par Vincenzooo Voir le message
    Essayez de taper :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    G,P=remplirArbre(100)
    print(G.lister())
    print(P.lister())
    les tableaux sont égaux !
    Quand je lis:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
        def __init__(self,value=None,fils=[]):
    alors les "tableaux" sont égaux.

    Car un mutable dans les paramètres par défaut d'une fonction produit ce genre de résultat... qui surprend toujours ceux qui débutent avec Python.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  3. #3
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Je pense qu'il y a un sérieux problème de conception.

    Dire qu'une partie c'est simplement la liste des cases jouées : OK.
    Mais dans ce cas :

    1) Pour créer n parties suffit de prendre n éléments au hasard dans l'ensemble des permutations possible de la liste [0,1,2,3,4,5,6,7,8].
    Ca prend une ligne :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    from random import sample
    from itertools import permutations
     
    n=10 ### nombre de parties
    print(sample(list(permutations([0,1,2,3,4,5,6,7,8])),n))
    Ok on calcule ici toute les permutations pour n'en prendre que n mais bon on peut se le permettre sur un si petit ensemble.
    Ceci dit ne pas toutes les calculer se fait également très bien. Une partie c'est simplement un mélange possible de la liste [0,1,2,3,4,5,6,7,8].

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    from random import sample
     
    def melange(liste):
         return random.sample(liste,len(liste))
     
    n=10 ### nombre de parties
    print([ melange([0,1,2,3,4,5,6,7,8]) for _ in range(n) ])
    2) Pour chaque partie (donc pour chaque liste) le vainqueur s'identifie en regardant les sous-listes 1 élément sur 2 et voyant s'il n'y a pas une ligne là dedans. On pourra dire alors que le joueur gagnant est 0 ou 1 (selon si c'est le joueur qui a démarré ou non). Car finalement qui perd ou qui gagne, c'est complètement symétrique en fonction de qui commence !


    Ensuite pour qu'on puisse éxécuter votre code il faudrait la classe Arbre ...

  4. #4
    Expert confirmé
    Avatar de fred1599
    Homme Profil pro
    Lead Dev Python
    Inscrit en
    Juillet 2006
    Messages
    4 064
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Lead Dev Python
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Juillet 2006
    Messages : 4 064
    Par défaut
    @lg_53,

    Dans ton code, n'y a-t-il pas une chance de tomber sur deux séries identiques, voir plus ?
    Cette chance est mince, mais la question est, est-ce possible ?

  5. #5
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Citation Envoyé par fred1599 Voir le message
    @lg_53,

    Dans ton code, n'y a-t-il pas une chance de tomber sur deux séries identiques, voir plus ?
    Cette chance est mince, mais la question est, est-ce possible ?
    Avec celui qui calcule toutes les permutations d'abord, non.
    Avec l'autre oui il y a une petite chance, mais ce n'est pas bien grave. Ca veut juste dire que l'IA a une petite proba de faire ces optimisations sur n-1 cas plutot que n. Sinon on peut itérer jusqu'à tant d'avoir des cas vraiments distincts mais ca complexifie beaucoup le code pour qqch de peu utile.

  6. #6
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 756
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 756
    Par défaut
    Citation Envoyé par lg_53 Voir le message
    Ensuite pour qu'on puisse éxécuter votre code il faudrait la classe Arbre ...
    Elle est là.
    Et si on dégomme le mutable dans les valeurs par défaut, on obtient bien des arbres différents. Après on peut vouloir écrire un meilleur code, ce n'est pas la question initiale, mais si vous avez du temps...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  7. #7
    Membre Expert

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    Elle est là.
    Et si on dégomme le mutable dans les valeurs par défaut, on obtient bien des arbres différents. Après on peut vouloir écrire un meilleur code, ce n'est pas la question initiale, mais si vous avez du temps...

    - W
    Oups, lu trop vite le post initial. En effet la classe Arbre est bien là

Discussions similaires

  1. Probléme de mémoire pour des grosses matrices
    Par astragoth dans le forum Calcul scientifique
    Réponses: 1
    Dernier message: 06/11/2009, 15h21
  2. Réponses: 3
    Dernier message: 29/08/2008, 09h49
  3. Réponses: 11
    Dernier message: 12/03/2008, 16h25
  4. Problème de format pour des chiffres à virgule
    Par bob75000 dans le forum Access
    Réponses: 5
    Dernier message: 21/07/2006, 10h42
  5. [SimpleXML] Problème PHP5/XML pour des affichages particuliers
    Par vanilla dans le forum Bibliothèques et frameworks
    Réponses: 7
    Dernier message: 20/04/2006, 13h22

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo