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

Version imprimable

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:

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:

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:

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.

15/05/2018, 17h50
wiztricks
Salut,
Citation:
Envoyé par Vincenzooo

Essayez de taper :

Code:

1 2 3 G,P=remplirArbre(100) print(G.lister()) print(P.lister())

les tableaux sont égaux !
Quand je lis:

Code:

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
15/05/2018, 18h19
lg_53
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:

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:

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 ...
15/05/2018, 18h28
fred1599

@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 ?
15/05/2018, 19h07
wiztricks

Citation:

Envoyé par lg_53

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
15/05/2018, 21h59
lg_53

Citation:

Envoyé par fred1599

@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.
15/05/2018, 22h00
lg_53

Citation:

Envoyé par wiztricks

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à :oops: