import matplotlib.pyplot as plt
import numpy as np

# Questions 2,3,4 & 5

n=4
p=3
L=["Morgan","Malo"]
Opp={L[0]:L[1],L[1]:L[0]} 

def Milka(n,p):
    """Fabrique une tablette de chocolat avec n lignes et p colonnes,
        et la marmotte, elle met le chocolat dans le papier d'alu"""
    return {(i,j) for i in range(n) for j in range(p)}

tab=Milka(n,p)

def Montrer(tab):
    """Affiche la tablette de chocolat"""
    plt.figure()
    plt.xlim(-1,n)# 
    plt.ylim(-1,p)#
    plt.plot([e[0] for e in tab-{(0,0)}],[e[1] for e in tab-{(0,0)}],"s",color="brown",markersize=50)
    plt.plot([0],[0],"rx",markersize=50)
    plt.show()
    
def Mange(tab,i,j):
    """Mange le carré i,j et tout ce qui est en haut à droite de ce carré"""
    return {(a,b) for (a,b) in tab if a<i or b<j}
    
def JoueurHumain(tab,joueur):
    """Demande à l'humain de jouer"""
    c=eval(input(joueur+" Entrez un couple valide parmi "+str(tab)+" : "))
    while c not in tab:
        c=eval(input(joueur+" n'a rien compris! Carré déjà mangé! Entrez un couple valide!"))
    return c      
    
def Partie(n,p,S1,S2,afficher):    
    """Joue une partie avec n lignes et p colonnes,
    le joueur 1 joue avec la stratégie S1
    le joueur 2 avec la stratégie S2
    """
    tab=Milka(n,p) # on crée la tablette
    DS={L[0]:S1,L[1]:S2} # le joueur 1 joue avec S1, 2 avec S2
    joueur=L[0] # le joueur 1 commence
    while True: # boucle faussement infinie, car le return arrête la fonction
        if afficher:
            Montrer(tab)
        (i,j)=DS[joueur](tab,joueur)
        tab=Mange(tab,i,j)
        joueur=Opp[joueur] # on change de joueur
        if len(tab)==0: # partie finie
            return joueur # on renvoie le vainqueur, arrête le while/la fonction

#print(Partie(n,p, JoueurHumain,JoueurHumain,True),"a gagné") # ne fonctionne que sous Spyder

#%%

# Question 6

def ListeVoisins(s):
    tab=s[0]
    joueur=s[1]
    return [(Mange(tab,i,j),Opp[joueur]) 
            for (i,j) in tab-{(0,0)}]

# Question 7

def GrapheTab(tab,joueur):
    for (tabb,o) in ListeVoisins((tab,joueur)):
        if (tabb,o) not in G:
            G.append((tabb,o))
            GrapheTab(tabb,o)
n=4
p=3
L=["Morgan","Malo"]
Opp={L[0]:L[1],L[1]:L[0]} 
tab=Milka(n,p)

G=[(tab,L[0])] # Initialisation de la liste des sommets du graphe
GrapheTab(tab,L[0]) # Création du graphe où le joueur L[0] commence

print("Le graphe G a pour ordre",len(G),".")

#%%

# Question 8

def Existence(X,s):
    """Renvoie True s’il existe un successeur de s dans X"""
    for succ in ListeVoisins(s):
        if succ in X: # l'un des successeurs est dans X
            return True
    return False
       
def PourTout(X,s):
    """Renvoie True si tous les successeurs de s sont dans X"""
    for succ in ListeVoisins(s):
        if succ not in X: # l'un des successeurs n'est pas dans X
            return False
    return True # Tous les successeurs sont dans X

def F(X,j):
    L=[]
    for s in G:
        if s not in X and s[1]==j and Existence(X,s): # s est contrôlé par j
            L.append(s)
        if s not in X and s[1]!=j and PourTout(X,s): # s est contrôlé par l'adversaire
            L.append(s)   
    return L

def Attracteur(joueur):
    """Renvoie l'attracteur du joueur"""
    X=[({(0,0)},Opp[joueur])] # Liste des sommets gagnants pour joueur
    Y=F(X,joueur)
    while len(Y)>0: # tant qu'il y a des choses à rajouter
        X=X+Y # On actualise X
        Y=F(X,joueur)
    return X

n,p=4,3
L=["Morgan","Malo"]
Opp={L[0]:L[1],L[1]:L[0]} 
Attr={L[0]:Attracteur(L[0]),L[1]:Attracteur(L[1])}
print("Le joueur",L[0],"a ",len(Attr[L[0]]),"attracteurs")
print("Le joueur",L[1],"a ",len(Attr[L[1]]),"attracteurs")

if (tab,L[0]) in Attr[L[0]]:
    print("Le joueur qui commence a une stratégie gagnante")
else:
    print("Le joueur qui ne commence pas a une stratégie gagnante")

#%%

# Question 9

def StrategieAleatoire(tab,joueur):
    """Joue au hasard sauf le carré empoisonné si possible"""
    if len(tab)==1:
        return (0,0)
    L=list(tab-{(0,0)})
    return L[np.random.randint(len(L))]

# Question 10

Attr={L[0]:Attracteur(L[0]),L[1]:Attracteur(L[1])}

def StrategieGagnante(tab,joueur): 
    if (tab,joueur) in Attr[joueur]:
        for (i,j) in tab-{(0,0)}:
            if (Mange(tab,i,j),Opp[joueur]) in Attr[joueur]:
                return (i,j)
    return StrategieAleatoire(tab,joueur)


def Partie(n,p,S1,S2,afficher):    
    """Joue une partie avec n lignes et p colonnes,
    le joueur 1 joue avec la stratégie S1,
    le joueur 2 avec la stratégie S2
    """
    tab=Milka(n,p) # on crée la tablette
    DS={L[0]:S1,L[1]:S2}# l e joueur 1 joue avec S1, 2 avec S2
    joueur=L[0] # le joueur 1 commence
    while 1>=0: # boucle faussement infinie, car le return arrête la fonction
        if afficher:
            Montrer(tab)
        (i,j)=DS[joueur](tab,joueur)
        tab=Mange(tab,i,j)
        joueur=Opp[joueur] # on change de joueur
        if len(tab)==0: # partie finie
            return joueur # on renvoie le vainqueur, arrête le while/la fonction

print(Partie(n,p, StrategieGagnante,StrategieAleatoire,False),"a gagné")
print(Partie(n,p, StrategieAleatoire,StrategieGagnante,False),"a gagné")
#%%

# Question 12

def h(tab):
    if tab=={(0,0)}:
        return -1
    if {i for (i,j) in tab}=={0} or {j for (i,j) in tab}=={0}:
        return 1
    return 0

# Question 13

def minimax(p,n):
	if n == 0 or ListeVoisins(p) == []:
		return h(p)
	mini = np.inf
	for pk in ListeVoisins(p):
		s = maximin(pk,n-1)
		if s < mini:
			mini = s
	return mini

def maximin(p,n):
	if n == 0 or ListeVoisins(p) == []:
		return h(p)
	maxi = -np.inf
	for pk in ListeVoisins(p):
		s = minimax(pk,n-1)
		if s > maxi:
			maxi = s
	return maxi

# Question 14

def minimax(tab,pro):
    if pro==0 or len(tab)<=1:
        return (-h(tab),0,0)
    mini=np.inf
    for (i,j) in tab-{(0,0)}:
        m=maximin(Mange(tab,i,j),pro-1)[0]
        if m<=mini:
            mini,i0,j0=m,i,j
    return (mini,i0,j0)

def maximin(tab,pro):
    if pro==0 or len(tab)<=1:
        return (h(tab),0,0)
    maxi=-np.inf
    for (i,j) in tab-{(0,0)}:
        m=minimax(Mange(tab,i,j),pro-1)[0]
        if m>=maxi:
            maxi,i0,j0=m,i,j
    return (maxi,i0,j0)

def StrategieMiniMax3(tab,joueur):
    return maximin(tab,3)[1:3]

def StrategieMiniMax7(tab,joueur):
    return maximin(tab,7)[1:3]

#%%

# Question 9 et 15

def Bilan(S1,S2,Nb):
    """Renvoie le pourcentage de parties gagnées par L[0] avec la stratégie S1, 
    de parties gagnées par L[1] avec la stratégie S2, ces pourcentages sont
    approximés en effectuant N parties"""
    DB={L[0]:0,L[1]:0}
    for i in range(Nb):
        a=Partie(n,p,S1,S2,False) # Résultat de la partie
        DB[a]=DB[a]+1
    return {k:DB[k]*100/Nb for k in DB}

G=[(tab,L[0])] # Liste des sommets du graphe
GrapheTab(tab,L[0]) # Création du graphe
A={L[0]:Attracteur(L[0]),L[1]:Attracteur(L[1])}
S=[StrategieAleatoire,StrategieGagnante]
S=[StrategieAleatoire,StrategieGagnante,StrategieMiniMax3,StrategieMiniMax7]
for S1 in S:
    for S2 in S:
        B=Bilan(S1,S2,5*10**2)
        print(str(S1)[19:28],"joue en 1er et gagne à",B[L[0]]," % contre ",str(S2)[19:28])