from random import choice


# 1
def init():
    return [[0 for y in range(6)] for x in range(7)]


def affiche(G):
    print()
    for y in range(5, -1, -1):
        ligne = ''
        for x in range(7):
            if G[x][y] == 0:
                ligne += '. '
            elif G[x][y] == 1:
                ligne += 'o '
            else:  # G[x][y] == 2
                ligne += 'x '
        print(ligne)
    # print('-------------')
    print('0 1 2 3 4 5 6')


G = init()
G[0][0] = 1
G[3][0] = 2
G[3][1] = 1
affiche(G)


## 2
def coups(G):
    def hauteur(x):
        """
        renvoie la hauteur de la colonne x dans la grille G
        """
        for y in range(6):
            if G[x][y] == 0:
                return y
        return 6
    res = []
    for x in range(7):
        y = hauteur(x)
        if y != 6:
            res.append((x, y))
    return res


# Test
affiche(G)
print(coups(G))


##
def tous_alignements():
    res = []
    # horizontaux
    for x in range(4):
        for y in range(6):
            ligne = []
            for k in range(4):
                ligne.append((x + k, y))
            res.append(ligne)
    # verticaux
    for x in range(7):
        for y in range(3):
            ligne = []
            for k in range(4):
                ligne.append((x, y + k))
            res.append(ligne)
    # diag nord-est
    for x in range(4):
        for y in range(3):
            ligne = []
            for k in range(4):
                ligne.append((x + k, y + k))
            res.append(ligne)
    # diag nord-ouest
    for x in range(3, 7):
        for y in range(3):
            ligne = []
            for k in range(4):
                ligne.append((x - k, y + k))
            res.append(ligne)
    return res


tous = tous_alignements()


## 3

def compte(G, ligne):
    """G est la grille de jeu,
    ligne est une liste de 4 couples de coordonnées,
    renvoie la 3-liste du nombre de cases vides, du joueur 1,
    du joueur 2 dans la liste ligne"""
    n = [0 for j in range(3)]
    for couple in ligne:
        x, y = couple
        j = G[x][y]
        n[j] += 1
    return n


def fini(G):
    for ligne in tous:
        n = compte(G, ligne)
        if n[1] == 4:
            return 1
        elif n[2] == 4:
            return 2
    return 0


def fini1(G):
    def gagnant(ligne):
        """ renvoie le numéro (1 ou 2) du joueur si toutes les cases de
        ligne sont occupées par ce joueur; 0 sinon"""
        x, y = ligne[0]
        joueur = G[x][y]
        for i in range(1, len(ligne)):
            x, y = ligne[i]
            if G[x][y] != joueur:
                return 0
        return joueur
    for ligne in tous:
        joueur = gagnant(ligne)
        if joueur != 0:
            return joueur
    return 0


def fini2(G):
    for ligne in tous:
        for joueur in [1, 2]:
            res = True
            k = 0
            while res and k < 4:
                x, y = ligne[k]
                res = (G[x][y] == joueur)
                k += 1
            if res:
                return joueur
    return 0


G = [[2, 1, 2, 1, 1, 0], [1, 2, 1, 2, 1, 2], [2, 1, 1, 2, 1, 2],
     [2, 1, 2, 2, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
affiche(G)
print(fini(G))
G[3][4] = 1
affiche(G)
print(fini(G))
G[3][4], G[4][3] = 0, 2
affiche(G)
print(fini(G))


## 4
def joue_hasard():
    G = init()
    joueur = 1
    for i in range(42):  # au plus 42 coups
        L = coups(G)
        x, y = choice(L)
        G[x][y] = joueur
        joueur = 3 - joueur
        if fini(G) != 0:
            return G
    return G


G = joue_hasard()
affiche(G)
print(fini(G))

N = 1000
nb = 0
for k in range(N):
    G = joue_hasard()
    if fini(G) == 1:
        nb += 1
print(nb/N)


## 5
def heuristique(G, w):
    score = 0
    for ligne in tous:
        n = compte(G, ligne)  # fonction compte définie pour script 3
        if n[2] == 0:
            score += w[n[1]]
        elif n[1] == 0:
            score -= w[n[2]]
    return score


G = [[2, 1, 2, 1, 1, 0], [1, 2, 1, 2, 1, 2], [2, 1, 1, 2, 1, 2],
     [2, 1, 2, 2, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 100, float('inf')]
affiche(G)
print(heuristique(G, w))  # résultat : 53
G[3][4] = 1
affiche(G)
print(heuristique(G, w))  # résultat : inf
G[3][4], G[4][3] = 0, 2
affiche(G)
print(heuristique(G, w))  # résultat : -inf


## 6
def choix_minmax(scores_coups, joueur):
    """
    scores_coups est une liste de couples non vide dont le premier élément
    est un nombre
    la fonction renvoie un couple parmi ceux qui ont le plus grand premier
    élément si joueur 1, plus petit si joueur 2.
    """
    score = scores_coups[0][0]
    L_coups = [scores_coups[0][1]]
    for k in range(1, len(scores_coups)):
        val, coup = scores_coups[k][0], scores_coups[k][1]
        if (joueur == 1 and val > score) or (joueur == 2 and val < score):
            score = val
            L_coups = [coup]
        elif val == score:
            L_coups.append(coup)
    return score, choice(L_coups)


## Tests choix_minmax

G = [[2, 1, 2, 1, 1, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 1, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 100, float('inf')]

affiche(G)

L = coups(G)
scores_coups = []  # liste des couples (score, coup) des successeurs
for coup in L:
    x, y = coup
    # jouer le coup
    G[x][y] = 1
    scores_coups.append((heuristique(G, w), coup))
    G[x][y] = 0
print(scores_coups)
print('maxi : ', choix_minmax(scores_coups, 1))
print('mini : ', choix_minmax(scores_coups, 2))


##

def minmax(G, joueur, w, p):
    """
    renvoie le score pour une profondeur p pour la grille G ainsi que
    le coup à jouer.
    """
    L = coups(G)
    if p == 0 or len(L) == 0:
        return heuristique(G, w), None
    scores_coups = []  # liste des couples (score, coup) des successeurs
    for coup in L:
        x, y = coup
        # jouer le coup
        G[x][y] = joueur
        scores_coups.append((minmax(G, 3 - joueur, w, p - 1)[0], coup))
        G[x][y] = 0
    return choix_minmax(scores_coups, joueur)


G = [[2, 1, 2, 1, 0, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 2, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 100, float('inf')]
print(minmax(G, 1, w, 3))


## 7

def partie_humain_machine(w, p):
    G = init()
    joueur = 1
    for i in range(42):  # au plus 42 coups
        affiche(G)
        if joueur == 1:
            x = int(input("numéro de colonne : "))
            y = 0
            while G[x][y] != 0:
                y += 1
            G[x][y] = 1
        else:  # joueur 2 : machine
            score, coup = minmax(G, joueur, w, p)
            x, y = coup
            G[x][y] = joueur
        joueur = 3 - joueur
        gagnant = fini(G)
        if gagnant != 0:
            affiche(G)
            if gagnant == 1:
                print("gagné")
            else:
                print("perdu")
            return G
    return G


w = [0, 1, 10, 30, float('inf')]
partie_humain_machine(w, 2)


## 8
def partie2IA(w1, w2, p1, p2, dis):
    W = [w1, w2]
    P = [p1, p2]
    G = init()
    joueur = 1
    for i in range(42):  # au plus 42 coups
        score, coup = minmax(G, joueur, W[joueur - 1], P[joueur - 1])
        x, y = coup
        G[x][y] = joueur
        if dis:
            affiche(G)
        joueur = 3 - joueur
        if fini(G) != 0:
            return G
    return G


## 9
W = [[0, 1, 10, 100, float('inf')],
     [0, 1, 10, 1000, float('inf')],
     [0, 1, 10, 30, float('inf')],
     [0, 1, 2, 4, float('inf')]]

# W = [W[0], W[3]]
# G= partie2IA(W, True)
# print(gagnant)

N = 10
parties_gagnees = [[0 for k in range(4)] for j in range(4)]

for i in range(4):
    for j in range(4):
        for k in range(N):
            G = partie2IA(W[i], W[j], 2, 2, False)
            if fini(G) == 1:
                parties_gagnees[i][j] += 1
print(parties_gagnees)


## 10 Élagage alpha-beta

def alphabeta(G, joueur, w, p, alpha, beta):
    """
    renvoie le score pour une profondeur p pour la grille G ainsi que
    le coup à jouer.
    """
    L = coups(G)
    if p == 0 or len(L) == 0:
        return heuristique(G, w), None
    if joueur == 1:
        score = -float('inf')
    else:
        score = float('inf')
    for coup in L:
        x, y = coup
        # jouer le coup
        G[x][y] = joueur
        val = alphabeta(G, 3-joueur, w, p-1, alpha, beta)[0]
        if joueur == 1:
            if val >= beta:
                G[x][y] = 0
                return val, coup
            if val > alpha:
                alpha = val
            if val >= score:
                score = val
                coup_score = coup
        else:  # joueur 2
            if val <= alpha:
                G[x][y] = 0
                return val, coup
            if val < beta:
                beta = val
            if val <= score:
                score = val
                coup_score = coup
        G[x][y] = 0
    return score, coup_score


G = [[2, 1, 2, 1, 0, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 2, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 30, float('inf')]
affiche(G)
print(minmax(G, 1, w, 3))
print(alphabeta(G, 1, w, 3, -float('inf'), float('inf')))




## negamax : heuristique symétrique par rapport à 0
C = [0, 0]


def negamax(G, joueur, w, p):
    C[0] += 1
    L = coups(G)
    if p == 0 or len(L) == 0:
        if joueur == 1:
            return heuristique(G, w), None
        else:  # joueur 2
            return -heuristique(G, w), None
    score = -float('inf')
    for coup in L:
        x, y = coup
        # jouer le coup
        G[x][y] = joueur
        val = -negamax(G, 3 - joueur, w, p - 1)[0]
        G[x][y] = 0
        if val >= score:
            score = val
            coup_score = coup
    return score, coup_score


G = [[2, 1, 2, 1, 0, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 2, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 30, float('inf')]
affiche(G)
print(minmax(G, 1, w, 1), negamax(G, 1, w, 1))


def negalphabeta(G, joueur, w, p, alpha, beta):
    C[1] += 1
    L = coups(G)
    if p == 0 or len(L) == 0:
        if joueur == 1:
            return heuristique(G, w), None
        else:  # joueur 2
            return -heuristique(G, w), None
    score = -float('inf')
    for coup in L:
        x, y = coup
        # jouer le coup
        G[x][y] = joueur
        val = -negalphabeta(G, 3-joueur, w, p-1, -beta, -alpha)[0]
        if val >= beta:
            G[x][y] = 0
            return val, coup
        if val > alpha:
            alpha = val
        if val >= score:
            score = val
            coup_score = coup
        G[x][y] = 0
    return score, coup_score


G = [[2, 1, 2, 1, 0, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 2, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 30, float('inf')]
affiche(G)
print(minmax(G, 1, w, 2),
      negalphabeta(G, 1, w, 2, -float('inf'), float('inf')))


## comparaison minmax et alphabeta : on compte le nombre d'appels

G = [[2, 1, 2, 1, 0, 0], [1, 2, 1, 2, 0, 0], [2, 1, 1, 2, 1, 2],
     [2, 2, 2, 1, 0, 0], [1, 1, 2, 0, 0, 0], [2, 0, 0, 0, 0, 0],
     [1, 2, 0, 0, 0, 0]]
w = [0, 1, 10, 30, float('inf')]
affiche(G)
for p in range(6):
    C = [0, 0]
    negamax(G, 1, w, p)
    negalphabeta(G, 1, w, p, -float('inf'), float('inf'))
    print(C)