# question 1

def init() -> list:
    '''
    retourne la grille initiale
    '''
    return [[0 for y in range(6)] for x in range(7)]

# question 2

def display(G:list):
    '''
    affiche la grille G
    '''
    D = ['.','x','o']
    for y in range(6):
        s = ""
        for x in range(7):
            s += D[G[x][5-y]]+' '
        print(s)
    print()

"""
G = init()
G[3][0] = G[4][0] = 1
G[3][1] = 2
display(G)
"""

# question 3

def tous_alignements():
    ''' -> list
    retourne la liste des tuples de 4 positions alignées
    '''
    L = []
    # vertical
    for x in range(7):
        for y in range(3):
            L.append(((x,y),(x,y+1),(x,y+2),(x,y+3)))
    # horizontal
    for y in range(6):
        for x in range(4):
            L.append(((x,y),(x+1,y),(x+2,y),(x+3,y)))
    # diagonal haut-droite
    for x in range(4):
        for y in range(3):
            L.append(((x,y),(x+1,y+1),(x+2,y+2),(x+3,y+3)))
    # diagonal haut-gauche
    for x in range(3,7):
        for y in range(3):
            L.append(((x,y),(x-1,y+1),(x-2,y+2),(x-3,y+3)))
    return L


# question 4

def coups(G):
    '''
    retourne la liste des coups possibles sous la forme d'une liste de tuples (x,y)
    '''
    L = []
    for x in range(7):
        y = 6
        while y>0 and G[x][y-1]==0:
            y -= 1
        if y<6:
            L.append((x,y))
    return L

def coups(G):
    L=[]
    for i in range(7):
        j=0
        while (j<6 and G[i][j]!=0):
            j+=1
        if j!=6:
            L.append((i,j))
    return L

# question 5
def fini(G:list) -> int:
    '''
    retourne j (1 ou 2) si la partie est gagnée par le joueur j, 0 sinon
    '''
    for A in tous:
        if sum(G[x][y]==1 for x,y in A)==4:
            return 1
        if sum(G[x][y]==2 for x,y in A)==4:
            return 2
    return 0

def fini(G):
    for t in tous:
        aligne=[0,0]
        for p in t:
            x,y=p
            if G[x][y]==1:
                aligne[0]+=1
            elif G[x][y]==2:
                aligne[1]+=1
        if aligne[0]==4:
            return 1
        elif aligne[1]==4:
            return 2
    return 0

# question 6

from random import randrange

def joue_random():
    G=init()
    joueur=1
    fin=0
    C=[(0,0)]
    while(len(C)!=0 and fin==0):
        C=coups(G)
        if len(C)>0:
            c=randrange(0,len(C))
            x,y=C[c]
            G[x][y]=joueur
            fin=fini(G)
            joueur=2 if joueur==1 else 1
    return G,fin

def joue_random() -> list:
    '''
    retourne la grille finale obtenue après une partie complètement aléatoire
    '''
    G = init() # initialisation de la grille
    joueur = 1 # joueur courant
    for i in range(42): # nombre de coups maximum
        L = coups(G) # liste des coups possibles
        x,y = L[randrange(len(L))] # choix d'un coup aléatoire
        G[x][y] = joueur # on joue ce coup
        if fini(G)!=0: # on teste si la partie est gagnée
            break
        joueur = 3-joueur # on change de joueur
    return G

"""
# score moyen du joueur 1 lors d'une partie aléatoire -> ~ 0.56
tous = tous_alignements()
S = [0.5,1,0]
total = 0.
N = 100000
for n in range(N):
    total += S[fini(joue_random())]
    print(n+1,total/(n+1))
"""

"""
# nombre moyen de parties nulles ? -> extrêmement faible, moins de 1%
tous = tous_alignements()
total = 0.
N = 100000
for n in range(N):
    if fini(joue_random())==0:
        total += 1
    print(n+1,total/(n+1))
"""


# question 8

def utilité(G:list, k:int, w:list) -> float:
    '''
    fonction d'utilité pour le joueur k, associée à la fonction de poids w
    '''
    U = 0
    for A in tous: # boucle sur tous les alignements
        n_k = sum([ G[x][y]==k for x,y in A ])        # nombres de pions du joueur dans A
        n_autre = sum([ G[x][y]==3-k for x,y in A ])  # nombres de pions de l'autre joueur
        if n_k==0 or n_autre==0:
            U += w[n_k] - w[n_autre] # mise à jour de l'utilité
    return U

def utilite(G,k,w):
    n=[0,[],[]]
    Uk=0
    for A in tous:
        n=[0,0,0]
        for i in range(4):
            x,y=A[i]
            #calcul des ni
            n[G[x][y]]+=1
        if n[3-k]==0:
            Uk+=w[n[k]]
        elif n[k]==0:
            Uk-=w[n[3-k]]
    return Uk

# question 9

def minmax(G:list, k:int, w:list, p:int) -> (float,tuple):
    '''
    retourne la fonction d'utilité à profondeur p pour le joueur k
    ainsi qu'un coup (x,y) aléatoire réalisant cette utilité
    '''
    L = coups(G)
    if p==0 or len(L)==0 or fini(G)!=0:
        return utilité(G,k,w),None
    Uopt = -float('inf')
    copt = []
    for x,y in L:
        G[x][y] = k # joue en x,y
        U,c0 = minmax(G,3-k,w,p-1)
        U = -U
        # met à jour le maximum
        if U>Uopt: # nouveau maximum
            Uopt = U
            copt = []
        if U==Uopt: # ajout d'un coup réalisant Uopt
            copt.append((x,y))
        G[x][y] = 0 # "déjoue" en x,y
    # choisit un coup aléatoire réalisant Uopt
    c = copt[randrange(len(copt))]
    return Uopt, c


# question 10

def partie(w1:list, p1:int, w2:list, p2:int, affiche:bool) -> list:
    '''
    retourne la grille finale obtenue après une partie (w1,p1) contre (w2,p2)
    (affiche les grilles intermédiaires si affiche est True)
    '''
    G = init() # initialisation de la grille
    joueur = 1 # joueur courant
    for i in range(42): # nombre de coups maximum
        if affiche: # affichage de la grille (si demandé)
            display(G)
        if joueur==1:
            U,c = minmax(G,1,w1,p1) # stratégie min-max pour le joueur 1
        else:
            U,c = minmax(G,2,w2,p2) # stratégie min-max pour le joueur 2
        x,y = c
        G[x][y] = joueur # on joue le coup choisi
        if fini(G)!=0: # on teste si la partie est gagnée
            break
        joueur = 3-joueur # on change de joueur
    return G

"""
tous = tous_alignements()
w = [0,1,10,1000,float('inf')]
G = partie(w,2,w,4,False)
display(G)
print("vainqueur: ",fini(G))
"""
# question 11

def perf(w1:int, p1:int, w2:list, p2:int, Nparties:int) -> float:
    '''
    évaluation des performances de la stratégie (w1,p1) pour le joueur 1
    contre la stratégie (w2,p2) pour le joueur 2 (Nparties jouées)
    retourne le score moyen (en comptant 0 pour une défaite, 1 pour une victoire, 0.5 pour un nul)
    '''
    tot = 0.
    S = [0.5,1,0]
    for n in range(Nparties):
        tot += S[fini(partie(w1,p1,w2,p2,False))]
    return tot/Nparties

#Question 12

def stat2(Nparties:int):
    '''
    évaluation de l'influence de la profondeur (affichage)
    '''
    w = [None,\
         [0,1,10,1000,float('inf')],\
         [0,1,10,100,float('inf')],\
         [0,1,10,30,float('inf')],\
         [0,1,2,4,float('inf')]]
    profondeur = 2
    print("w2  =  1    2    3    4")
    for i1 in range(1,5):
        s = "w1="+str(i1)+": "
        for i2 in range(1,5):
            p = perf(w[i1],profondeur,w[i2],profondeur,Nparties)
            s += str(int(100*p)/100)+" "
        print(s)

"""
tous = tous_alignements()
stat2(100)
exit(1)
"""

# question 13
def humain_vs_machine(w:list, p:int):
    '''
    gère une partie interactive (au clavier) entre un humain et l'algorithme min-max
    (liste de poids w, profondeur d'analyse p)
    '''
    humain = 1+randrange(2) # tirage au sort du numéro du joueur humain
    print("Le tirage au sort vous a désigné comme le joueur numéro",humain)
    G = init()
    joueur = 1 # joueur courant
    for i in range(42):
        print("position actuelle:")
        display(G)
        if joueur==humain:
            ok = False
            while not ok:
                col = input("dans quelle colonne (1 à 7) voulez-vous jouer ? ")
                x = int(col)-1
                ok = x>=0 and x<=6 and G[x][5]==0
            y = 5
            while y>0 and G[x][y-1]==0:
                y -= 1
        else:
            U,c = minmax(G,joueur,w,p)
            x,y = c
            print("L'ordinateur joue dans la colonne",x+1)
            print("score estimé:",U)
        G[x][y] = joueur
        f = fini(G)
        if f!=0:
            break
        joueur = 3-joueur
        print()
    if f==0:
        print("Match nul !")
    elif f==humain:
        print("Vous avez gagné !")
    else:
        print("L'ordinateur a gagné !")
    print()
    print("position finale:")
    display(G)
    print()

tous = tous_alignements()
w = [0,1,10,30,float('inf')]
humain_vs_machine(w,5)