''' Intelligence artificielle & theorie de jeux'''
''' Jeu des tablettes '''

#________________________________________________
##  Partie 1 - Lister les coups possibles
#________________________________________________
# Q1 - Etat de x
''' Situation 1: x=[[0,1],[0,1],[1,1],[1,1]]
    Situation 2: x=[[0,2],[1,1],[1,1]]
'''
# Q2 - empile
def empile(x,i,j):
    """ empile ( x : list, i : int, j : int )-> list
        entrees : x, liste de listes(ci,hi), represente la situation initiale. Chaque sous liste correspod à une pile représntée par (ci=couleur du haut,hi=hauteur)
                : i, j, entiers, indices des piles que l'on veut empiler 
        sortie; LXij , liste de situations possibles après empilement
    """
    LXij = []
    ci , hi = x[i]
    cj , hj = x[j]
    if ci==cj or hi==hj : #empilement possible 
        reste = x[:i] + x[i+1:j] + x[j+1:]
        pij = [ci,hi+hj] # pile ci sur cj (arbitrairement)
        X = reste + [pij]
        X.sort()
        LXij.append(X)
        if ci!=cj: # si couleur différente => ajouter la situation avec cj au dessus
            pji = [cj,hi+hj] # pile cj sur ci
            X = reste + [pji]
            X.sort()
            LXij.append(X)
    return LXij

# tests de la fonction empile
x = [ [0,1] , [0,1] , [1,1] , [1,1] ] # situation 1
res1 = empile( x, 0, 1 )
print( res1 )   # affiche [[[0, 2], [1, 1], [1, 1]]]

x = [ [0,1],[0,1],[1,1],[1,1]]  # situation 1
res2 = empile(x,0,3)
print(res2)     # affiche [[[0, 1], [0, 2], [1, 1]], [[0, 1], [1, 1], [1, 2]]]

x = [ [0,2],[0,2],[1,1],[1,1]]  
res3 = empile(x,0,1)
print(res3)     # affiche [[[0, 4], [1, 1], [1, 1]]]

x = [[0,2],[1,1],[1,1]]
res4 = empile(x,0,1)
print(res4)     # affiche []

# Q3 - coups
def coups(x):
    """ coups(x : list) -> list
        entree: x, liste de liste(ci,hi), situation initiale
        sortie : ensemble des situations possibles en realisant toutes les combinaisons d'empilement possibles 
                (chaque situation est unique => doublons elimines)
    """
    LX = []
    for i in range( len(x) ):
        for j in range( i+1 , len(x) ):
            LXij = empile( x,i,j )
            for X in LXij:
                if X not in LX: # On n'ajoute la situation que si elle n'a pas dejà ete stockée
                    LX.append(X)
    return LX

x = [ [0,2],[0,3],[1,1],[1,2] ]

lesCoups1 = coups(x)
print( lesCoups1 )
# affiche [[[0, 5], [1, 1], [1, 2]], [[0, 3], [0, 4], [1, 1]], [[0, 3], [1, 1], [1, 4]], [[0, 2], [0, 3], [1, 3]]]

x = [[0,1],[0,1],[1,1],[1,1]]
lesCoups2 = coups(x)
print( lesCoups2 )
# affiche [[[0, 2], [1, 1], [1, 1]], [[0, 1], [0, 2], [1, 1]], [[0, 1], [1, 1], [1, 2]], [[0, 1], [0, 1], [1, 2]]]


'''
sans sort dans empile, les élèves ne trouveront pas le même résultat 
'''
#________________________________________________
##      Partie 2 : Création du graphe du jeu
#________________________________________________
# Q4 - init
def init(C,N):
    """ init( C : int, N: int ) -> list
        entrees : C, entier positif, nombre de couleurs differentes
                : N , entier positif, nombre de tablettes par couleur
        sortie : x0, liste de listes (ci,hi) correspondant à la situation initiale (hi est systematiqueme =1)
    """
    x0 = []
    for c in range(C):
        for _ in range(N):
            x0.append([c,1])
    x0.sort() # Inutile compte tenu de la programmation avec c croissant
    return x0

test = init(3,4)
print(test)  
# affiche [[0, 1], [0, 1], [0, 1], [0, 1], [1, 1], [1, 1], [1, 1], [1, 1], [2, 1], [2, 1], [2, 1], [2, 1]]

# Q5 - Tuple
def Tuple(L):
    """
        Tuple(L:list)-> tuple
        fonction recursive
        entree : L,liste de liste de liste, ... que l'on veut transformer en tuple de tuple de tuple, ...
        sortie : tuple
    """
    if L==[]:
        return ()
    elif type(L[0])!=list:
        return tuple(L)
    else:
        Res = []
        for l in L:
            Res.append(Tuple(l))
        return tuple(Res)

L = [ [ [1,2],[3,4,5] , [[6]]] ]
#lesTuples = Tuple(L)
#print(lesTuples) # affiche (((1, 2), (3, 4, 5), ((6,),)),)

"""
L1 = [[1]]
lesTuples2 = Tuple(L1)
print(lesTuples2) # affiche  ((1,),)
"""

# Q6 - graphe
from collections import deque
def graphe(C,N):
    """ graphe(C : int ,N:int )-> dict
        entrees : C, entier positif, nombre de couleurs differentes
                : N , entier positif, nombre de tablettes par couleur
        sortie : G, dictionnaire, representant le graphe :clé : tuple de la situation, valeur : liste de liste de situation atteignables   
    """
    # constitution de la situation initiale
    x0 = init(C,N) 
    G = {} # initialisation du dictionnaire G qui représente le graphe    
    file = deque()
    file.append(x0) # initialisation de la file avec la situation initiale x0
    while len(file) != 0:
        x = file.popleft()  # recuperation du 1er element de la file
        Cle = Tuple(x)      # génération de la cle sous forme de tuple 
        LCoupsSuivants = coups(x)       # recuperation de la liste des situations atteignables depuis x
        #Valeur = LCoupsSuivants
        G[Cle] = LCoupsSuivants # ajout dans le graphe du couple clé, valeur
        # ajout dans la file des differentes situations (si elles n'ont pas dejà été stockées) pour traitement ultérieur
        for c in LCoupsSuivants:
            if Tuple(c) not in G:
                file.append(c)
    return G

print("Constitution du graphe")
C,N = 2,2
Graphe = graphe(C,N)
print(Graphe)
# affiche (avec mise en forme)
"""
{((0, 1), (0, 1), (1, 1), (1, 1)): [[[0, 2], [1, 1], [1, 1]], 
                                    [[0, 1], [0, 2], [1, 1]],
                                    [[0, 1], [1, 1], [1, 2]],
                                    [[0, 1], [0, 1], [1, 2]]],
 ((0, 2), (1, 1), (1, 1))        : [[[0, 2], [1, 2]]],
 ((0, 1), (0, 2), (1, 1))        : [[[0, 3], [1, 1]],
                                    [[0, 2], [0, 2]],
                                    [[0, 2], [1, 2]]],
 ((0, 1), (1, 1), (1, 2))        : [[[0, 2], [1, 2]], 
                                    [[1, 2], [1, 2]], 
                                    [[0, 1], [1, 3]]], 
 ((0, 1), (0, 1), (1, 2))        : [[[0, 2], 
                                    [1, 2]]], 
 ((0, 2), (1, 2))                : [[[0, 4]], 
                                   [[1, 4]]], 
 ((0, 3), (1, 1))                : [], 
 ((0, 2), (0, 2))                : [[[0, 4]]], 
 ((1, 2), (1, 2))                : [[[1, 4]]], 
 ((0, 1), (1, 3))                :  [],
 ((0, 4),): [], 
 ((1, 4),): []
 }
"""

# Définition des positions pour la suite
Pos_0 = [[0,1],[0,1],[1,1],[1,1]]
Pos_1a = [[0,2],[1,1],[1,1]]
Pos_1b = [[0,1],[0,2],[1,1]]
Pos_1c = [[0,1],[1,1],[1,2]]
Pos_1d = [[0,1],[0,1],[1,2]]
Pos_2a = [[0,2],[1,2]]
Pos_2b = [[0,3],[1,1]]
Pos_2c = [[0,2],[0,2]]
Pos_2d = [[1,2],[1,2]]
Pos_2e = [[0,1],[1,3]]
Pos_3a = [[0,4]]
Pos_3b = [[1,4]]

# Q7 - N1 et N2

N1 = len(Graphe)
N2 = sum([len(Graphe[x]) for x in Graphe])

'''
print("Sommets:",N1)
print("Arêtes:",N2)
'''

''' Résultat
Sommets: 12
Arêtes: 16
'''

# Q8 - Remplissage du tableau
from time import perf_counter 
C,N = 2,2 # A modifier pour chaque cas
tic = perf_counter()
Graphe = graphe(C,N)
toc = perf_counter()
T = toc - tic

print("Pour C = "+str(C)+" et N = "+str(N))
Nb_Sommets = len(Graphe) # N1
print("Sommets:",Nb_Sommets)
Nb_Aretes = sum([len(Graphe[x]) for x in Graphe]) # N2
print("Arêtes:",Nb_Aretes)
print("Temps (s):",T)

''' Résultat
Pour C = 2 et N = 2
Sommets: 12
Arêtes: 16
Temps (s): 8.039999966058531e-05

'''

## Graphe biparti
# Q9 - sommets_12
def sommets_12( G, C, N ):
    """ sommets_12( G, C, N )
        entrees : G, dictionnaire, represente le graphe
                : C, N, entiers representant le nombre de couleurs et le nombre de tablettes
        sorties: 2 tuples pour les sommets de J1 et de J2
    """
    S1 = []
    S2 = []
    n = N*C # nombre total de tablettes = nb de piles initial
    for e in G:
        if len(e)%2 == n%2: 
            S1.append(e)
        else:
            S2.append(e)
    return tuple(S1),tuple(S2) # S1 et S2 déjà Tuples, donc Tuples inutile

# Q10 - Création des sommets S1 et S2

C,N = 2,2
Graphe = graphe(C,N)
S1,S2 = sommets_12(Graphe,C,N)

'''
print("Sommets S1:",S1)
print("Sommets S2:",S2)
'''

''' Résultat
Sommets S1: (((0, 1), (0, 1), (1, 1), (1, 1)), ((0, 2), (1, 2)), ((0, 3), (1, 1)), ((0, 2), (0, 2)), ((1, 2), (1, 2)), ((0, 1), (1, 3)))
Sommets S2: (((0, 2), (1, 1), (1, 1)), ((0, 1), (0, 2), (1, 1)), ((0, 1), (1, 1), (1, 2)), ((0, 1), (0, 1), (1, 2)), ((0, 4),), ((1, 4),))
Soit:
S1: 0 2a 2b 2c 2d 2e
S2:  1a 1b 1c 1d 3a 3b
'''

## Les parties

# Q11 - Une partie
C,N = 2,2
Graphe = graphe(C,N) #generation du graphe du jeu
x0 = init(C,N) #situation initiale
Joueur = 1
print( "Joueur:" , Joueur )
print( "Jeu:", x0 )
lesSuccesseurs = Graphe[Tuple(x0)] #successeurs de la situation initiale
while len( lesSuccesseurs )>0:
        succ = lesSuccesseurs[0] #1er successeur
        Joueur = 3 - Joueur
        print( "Joueur:", Joueur )
        print( "Jeu:",succ )
        lesSuccesseurs = Graphe[Tuple(succ)] #successeurs du 1er successeur

''' Résultat
Joueur: 1
Jeu: [[0, 1], [0, 1], [1, 1], [1, 1]]
Joueur: 2
Jeu: [[0, 2], [1, 1], [1, 1]]
Joueur: 1
Jeu: [[0, 2], [1, 2]]
Joueur: 2
Jeu: [[0, 4]]
Le joueur 2 a gagné
Cela correspond à 0 - 1a - 2a - 3a
'''

## Détermination des positions gagnantes

# Q12 - Positions gagnantes sur le schéma

'''
Positions
2b 2e 3a 3b pas gagnantes car pas de successeurs
2a 2c 2d gagnantes car au moins un successeur n'est pas gagnant
1a et 1d pas gagnant car tous les successeurs sont gagnants (2a)
1b gagnant car au moins un successeur pas gagnant (2b)
1c gagnant car au moins un successeur pas gagnant (2e)
0 gagnant car au moins un successeur pas gagnant (1a et 1d)

Finalement, les positions gagnantes sont:
0 1b 1c 2a 2c 2d
'''

# Q13 - est_gagnante
'''
Version 1: On vérifie que tous les successeurs sont gagnants
Pour gagner du temps, on s'arrête dès qu'un successeur pas gagnant a été trouvé
'''
def est_gagnante(G,x): # x liste ou Tuple
    """ est_gagnante(G : dict, x : list)-> bool
        entrees : G, dictionnaire, représente le graphe (tuple(position), liste des successeurs)
                : x ; liste, position pour laquelle on souhaite savoir si elle gagnante ou pas
        sortie: booleen qui indique si la position est gagnante ou pas
    """
  
'''
L_Pos = [Pos_0,Pos_1a,Pos_1b,Pos_1c,Pos_1d,Pos_2a,Pos_2b,Pos_2c,Pos_2d,Pos_2e,Pos_3a,Pos_3b]
L_Pos_Nom = ["0","1a","1b","1c","1d","2a","2b","2c","2d","2e","3a","3b"]
for i in range(len(L_Pos)):
    Pos = L_Pos[i]
    Nom = L_Pos_Nom[i]
    print(Nom + ":",est_gagnante(Graphe,Pos))
'''

''' Résultat
0: True
1a: False
1b: True
1c: True
1d: False
2a: True
2b: False
2c: True
2d: True
2e: False
3a: False
3b: False
'''

# Q14 - dico_gagnant

def dico_gagnant(G):
    """ dico_gagnant(G)
        entrees : G, dictionnaire, représente le graphe (tuple(position), liste des successeurs)
        sortie: dico , dictionnaire qui contient pour chaque position(cle) si elle est gagnante ou pas (position, booleen)
    """


"""
C,N = 2,2
Graphe = graphe(C,N)
x0 = init(C,N)
dico_g = dico_gagnant(Graphe)

print(dico_g)
"""
#affiche {((0, 1), (0, 1), (1, 1), (1, 1)): True, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): True, ((0, 1), (1, 1), (1, 2)): True, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): True, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): True, ((1, 2), (1, 2)): True, ((0, 1), (1, 3)): False, ((0, 4),): False, ((1, 4),): False}
Statut_x0 = dico_g[Tuple(x0)]
print("Le joueur 1 dispose d'une position gagnante ?",Statut_x0)

''' Résultat
Le joueur 1 dispose d'une position gagnante ? True
'''

##___________________________________ 
# Calcul des attracteurs
##___________________________________
# Q18 - init_attracteurs
def init_attracteurs(G,S1):
    """ init_attracteurs(G : dict, S1 list)
        entrees : G : dictionnaire representant le graphe
                : S1, liste des sommets gagnants du joueur1
        sortie : d1, d2, dictionnaires - cle : sommet (tuple), valeur : booleen inidiquant si le sommet est dans les sommets gagnants du joueur j1 
    """


"""
C,N = 2,2
Graphe = graphe(C,N)
S1,S2 = sommets_12(Graphe,C,N)
dA1,dA2 = init_attracteurs(Graphe,S1)
print("dA1=",dA1)
print("dA2=",dA2)
"""
''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): False, ((0, 4),): True, ((1, 4),): True}
{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): True, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): True, ((0, 4),): False, ((1, 4),): False}
'''

# Q19 - cond_1
def cond_1(G,di,x):
    ''' cond_1(G : dict ,di : dict ,x : list)
        entrees : G, dictionnaire, qui représente le graphe
                : di, dictionnaires des attracteurs
                : x, liste représentant le sommet
        sortie : booléen, à True si au moins un successeur de x est à True dans di'''


'''
test = cond_1(Graphe,dA1,Pos_2a)
print(test)
test = cond_1(Graphe,dA1,Pos_2b)
print(test)
test = cond_1(Graphe,dA1,Pos_2c)
print(test)
test = cond_1(Graphe,dA1,Pos_2d)
print(test)
test = cond_1(Graphe,dA1,Pos_2e)
print(test)

test = cond_1(Graphe,dA2,Pos_1a)
print(test)
test = cond_1(Graphe,dA2,Pos_1b)
print(test)
test = cond_1(Graphe,dA2,Pos_1c)
print(test)
test = cond_1(Graphe,dA2,Pos_1d,)
print(test)

test = cond_1(Graphe,dA2,Pos_2a)
print(test)
test = cond_1(Graphe,dA2,Pos_2b)
print(test)
test = cond_1(Graphe,dA2,Pos_2c)
print(test)
test = cond_1(Graphe,dA2,Pos_2d)
print(test)
test = cond_1(Graphe,dA2,Pos_2e)
print(test)

test = cond_1(Graphe,dA1,Pos_1a)
print(test)
test = cond_1(Graphe,dA1,Pos_1b)
print(test)
test = cond_1(Graphe,dA1,Pos_1c)
print(test)
test = cond_1(Graphe,dA1,Pos_1d)
print(test)
'''

''' Résultat
True  : de 2a, 1 peut mener à A1 (3a et 3b)
False : de 2b, 1 ne mène pas à A1
True  : de 2c, 1 peut mener à A1 (3a)
True  : de 2d, 1 peut mener à A1 (3b)
False : de 2e, 1 ne mène pas à A1

False : de 1a, 2 ne mène pas à A2
True  : de 1b, 2 peut mener à A2 (2b)
True  : de 1c, 2 peut mener à A2 (2e)
False : de 1d, 2 ne mène pas à A2

False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés

False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
'''

# Q20 - cond_2
def cond_2(G,di,x):
    ''' cond_2(G : dict ,di : dict ,x : list)
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs
                    : x, liste représentant le sommet
            sortie : booléen, à True si tous les successeurs de x sont True dans di
    '''


'''
test = cond_2(Graphe,dA1,Pos_2a)
print(test)
test = cond_2(Graphe,dA1,Pos_2b)
print(test)
test = cond_2(Graphe,dA1,Pos_2c)
print(test)
test = cond_2(Graphe,dA1,Pos_2d)
print(test)
test = cond_2(Graphe,dA1,Pos_2e)
print(test)

test = cond_2(Graphe,dA2,Pos_1a)
print(test)
test = cond_2(Graphe,dA2,Pos_1b)
print(test)
test = cond_2(Graphe,dA2,Pos_1c)
print(test)
test = cond_2(Graphe,dA2,Pos_1d)
print(test)

test = cond_2(Graphe,dA2,Pos_2a)
print(test)
test = cond_2(Graphe,dA2,Pos_2b)
print(test)
test = cond_2(Graphe,dA2,Pos_2c)
print(test)
test = cond_2(Graphe,dA2,Pos_2d)
print(test)
test = cond_2(Graphe,dA2,Pos_2e)
print(test)

test = cond_2(Graphe,dA1,Pos_1a)
print(test)
test = cond_2(Graphe,dA1,Pos_1b)
print(test)
test = cond_2(Graphe,dA1,Pos_1c)
print(test)
test = cond_2(Graphe,dA1,Pos_1d)
print(test)
'''

''' Résultat
True  : de 2a, 1 mène forcément à A1 (3a et 3b)
False : de 2b, 1 ne mène pas à A1 (mène nulle part)
True  : de 2c, 1 mène forcément à A1 (3a)
True  : de 2d, 1 mène forcément à A1 (3b)
False : de 2e, 1 ne mène pas à A1 (mène nulle part)

False : de 1a, 2 ne mène pas que à A2
False : de 1b, 2 ne mène pas que à A2
False : de 1c, 2 ne mène pas que à A2
False : de 1d, 2 ne mène pas que à A2

False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés

False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
'''

# Q21 - attracteurs_it
def attracteurs_it(G,di,Si):
    """ attracteurs_it(G,di,Si)-> bool
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs du joueur i modifie en place
                    : Si, liste représentant les sommets du joueur i
            sortie : booléen, à True si une modification a été apportée a di
    """




# Q22 - attracteurs_Ji

def attracteurs_Ji(G,di,Si):
    """ attracteurs_it(G,di,Si)
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs du joueur i rempli intégralement par la focntion
                    : Si, liste représentant les sommets du joueur i
    """



# Q23 - attracteurs

def attracteurs(G,C,N):
    """ attracteurs(G,C,N)-> dict, dict
            entrees : G, dictionnaire, qui représente le graphe
                    : C,N, entiers respectivement nombre de couleurs et de jetons par couleur
            sorties : dA1, dA2, dictionnaires qui correspondent aux attracteurs de J1 et J2
    """


"""
C,N = 2,2
Graphe = graphe(C,N)
dA1,dA2 = attracteurs(Graphe,C,N)
"""
'''
print(dA1)
print(dA2)
'''

''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): True, ((0, 2), (1, 1), (1, 1)): True, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): True, ((0, 2), (1, 2)): True, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): True, ((1, 2), (1, 2)): True, ((0, 1), (1, 3)): False, ((0, 4),): True, ((1, 4),): True}
Sont à True: 0 1a 1d 2a 2c 2d 3a 3b

{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): True, ((0, 1), (1, 1), (1, 2)): True, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): True, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): True, ((0, 4),): False, ((1, 4),): False}
Sont à True: 1b 1c 2b 2e
'''

# Q24 - dico_gagnant_att

def dico_gagnant_att(G,C,N):
    """ dico_gagnant_att(G,C,N)->dict
            entrees : G, dictionnaire, qui représente le graphe
                    : C,N, entiers respectivement nombre de couleurs et de jetons par couleur
            sorties : dico, dictionnaires qui indique pour chaque position si elle est gagnante ou pas
    """

"""
C,N = 2,2
Graphe = graphe(C,N)
dico_g_att = dico_gagnant_att(Graphe,C,N)
dico_g = dico_gagnant(Graphe)
test = dico_g==dico_g_att
"""
'''
print('Dictionnaires identiques ?',test)
'''

''' Résultat
Dictionnaires identiques ? True
'''

## Stratégie optimale

# Q25 - strategie_opt

from random import randint as rd

def strategie_opt(G,dg,x):
    """ strategie_opt(G,dg,x)-> list
        entrees : G, dictionnaire, qui représente le graphe
                : dg, dictionnaire ( positions, bool)
                : x, liste , position
        sortie : Choix, liste, position à choisir (optimale si possible) 
    """


"""
C=N=2
G = graphe(C,N)
dg = dico_gagnant(G)
"""
'''
x0 = init(C,N)
for _ in range(5):
    test = strategie_opt(G,dg,x0)
    print(test)
'''

''' Résultat
On arrive sur les deux positions
[[0, 1], [0, 1], [1, 2]] # 1d
[[0, 2], [1, 1], [1, 1]] # 1a
On ne tombe jamais sur 1b
'''

'''
x0 = init(C,N)
for _ in range(10):
    test = strategie_opt(G,dg,x0)
    bool = (test==Pos_1a) or (test==Pos_1d)
    print(bool)
'''

''' Résultat
True
True
True
True
True
True
True
True
True
True
'''

# Q26 - strategies_opt

def strategies_opt(G,dg):
    """strategies_opt(G : dict,dg:dict) ->dict
            entrees : G, dictionnaire, qui représente le graphe
                : dg, dictionnaire ( positions, bool)
            sortie : dico_s, dictionnaire, qui correspond à l'ensemble des positions gagnantes
    """

"""
C=N=2
G = graphe(C,N)
dico_g = dico_gagnant(G)
st_opt = strategies_opt(G,dico_g)
"""


''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): [[0, 2], [1, 1], [1, 1]], ((0, 2), (1, 1), (1, 1)): [[0, 2], [1, 2]], ((0, 1), (0, 2), (1, 1)): [[0, 3], [1, 1]], ((0, 1), (1, 1), (1, 2)): [[0, 1], [1, 3]], ((0, 1), (0, 1), (1, 2)): [[0, 2], [1, 2]], ((0, 2), (1, 2)): [[1, 4]], ((0, 3), (1, 1)): [], ((0, 2), (0, 2)): [[0, 4]], ((1, 2), (1, 2)): [[1, 4]], ((0, 1), (1, 3)): [], ((0, 4),): [], ((1, 4),): []}
'''

## Simulation de jeu en IA

# Q27 - Simulation d'un jeu

def jeu(C,N):




# Q28 - Utilisation du jeu