################################################################################
################################################################################
#   OTHELLO
################################################################################
################################################################################

import  numpy.random as rd

global pinf,minf
pinf=float('inf')
minf=-float('inf')


################################################################################
#   FONCTIONS DU JEU
################################################################################


def valide(pos):
    """valide(pos:list)->bool
    pos : position [i,j]
    Renvoie True si pos est une position du plateau, False sinon"""
    i,j=pos
    return i>=0 and i<4 and j>=0 and j<4


def adversaire(x):
    """adversaire(x:int)->int
    Renvoie l'adversaire du joueur x"""
    return 1-x


def etat(tab,pos):
    """etat(tab:list,pos)->int or None
    tab : liste décrivant un plateau de jeu
    pos : une position[i,j] du plateau
    Renvoie l'état de la case en position pos"""
    i,j=pos
    return tab[i][j]


def place(tab,pos,J_i):
    """place(tab:list,pos:list,J_i:int)->None
    tab : liste décrivant un plateau de jeu
    pos : une position [i,j] du plateau
    J_i : numéro d'un joueur
    Place le pion de J_i en position pos"""
    i,j=pos
    tab[i][j]=J_i

    
def bascule(tab,pos):
    """"bascule(tab:list,pos:list)->None
    tab : liste décrivant un plateau de jeu
    pos : une position [i,j] du plateau
    Bascule la case en position pos dans le camp adverse"""
    J_i=etat(tab,pos)
    place(tab,pos,adversaire(J_i))


def suivant(pos,direction):
    """suivant(pos:list,direction:list)->list
    pos : une position [i,j] du plateau
    direction : une direction [di,dj]
    Renvoie la position [i+di,j+dj]"""
    i,j=pos
    di,dj=direction
    return [i+di,j+dj]


def retourne_dir(tab,pos,direction,J_i):
    """"retourne_dir(tab:list,pos:list,direction:list,J_i:int)->list
    tab : liste décrivant un plateau de jeu
    pos : position [i,j]
    direction : une direction [di,dj]
    J_i : numéro d'un joueur
    Renvoie la liste des cases à retourner selon direction
    si le joueur J_i joue en pos"""
    res=[]
    pos_cur=pos[:]
    fini=False
    while not fini:
        pos_cur=suivant(pos_cur,direction)
        fini=not valide(pos_cur) or etat(tab,pos_cur)!=adversaire(J_i)
        if not fini:
            res.append(pos_cur)
    if valide(pos_cur) and etat(tab,pos_cur)==J_i:
        return res
    return []


def init_tab():
    """init_tab()->list
    Creation du plateau de jeu initial"""
    tab=[[None]*4 for k in range(4)]
    tab[1][1]=0
    tab[1][2]=1
    tab[2][1]=1
    tab[2][2]=0
    return tab


def aff(tab):
    """aff(tab:list)->None
    Affichage du plateau de jeu décrit par tab"""
    n=len(tab)
    dico={None:'   ', 0:' O ', 1:' X '}
    ligne="   "
    for i in range(n):
        ligne+="| "+str(i)+" "
    print(ligne)
    print("----"*(n+1))
    for i in range(n):
        ligne=" "+ str(i)+" |"
        for j in range(n):
            ligne+=dico[tab[i][j]]
            if j<n-1:
                ligne+="|"
        print(ligne)
        if i<n-1:
            print("----"*(n+1))


def retourne(tab,pos,J_i):
    """retourne(tab:list,pos:list,J_i:int)->list
    tab : liste décrivant un plateau de jeu
    pos: une position [i,j] du plateau
    J_i : numéro du joueur
    Renvoie la liste des cases à retourner si le joueur J_i joue en pos"""
    res=[]
    L_direction=[[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]
    for direction in L_direction:
        res+=retourne_dir(tab,pos,direction,J_i)
    return res


def coup_valide(tab,pos,J_i):
    """coup_valide(tab:list,pos:list,J_i:int)->bool
    tab : liste décrivant un plateau de jeu
    pos : une position [i,j] du plateau
    J_i : numéro de Joueur
    Renvoie True si J_i peut jouer en pos, False sinon"""
    return len(retourne(tab,pos,J_i))>0


def joue(tab,pos,J_i):
    """"joue(tab:list,pos:list,J_i:int)->None
    tab : liste décrivant un plateau de jeu
    pos : une position [i,j] du plateau
    J_i : numéro de Joueur
    Joue pour J_i en pos, position valide pour J_i"""
    place(tab,pos,J_i)
    L_pos=retourne(tab,pos,J_i)
    for pos_retourne in L_pos:
        bascule(tab,pos_retourne)


def cases_libres(tab):
    """cases_libres(tab:list)->list
    tab : liste décrivant un plateau de jeu
    Renvoie la liste des cases inoccupées de tab"""
    res=[]
    for i in range(4):
        for j in range(4):
            if tab[i][j]==None:
                res.append([i,j])
    return res


def cases_jouables(tab,J_i):
    """cases_jouables(tab:list,J_i:int)->list
    tab : liste décrivant un plateau de jeu
    J_i : numéro du joueur
    Renvoie la liste des cases jouables par le joueur J_i"""
    res=[]
    for pos in cases_libres(tab):
        if coup_valide(tab,pos,J_i):
            res.append(pos)
    return res


def score(tab):
    """score(tab:list)->float
    tab : liste décrivant un plateau de jeu
    Renvoie +inf si J_0 gagne, -inf si J_1 gagne et 0 sinon"""
    n0,n1=comptage(tab)
    if n0>n1:
        return pinf
    elif n0<n1:
        return minf
    else:
        return 0
    
def comptage(tab):
    """comptage(tab:list)->tuple
    tab : liste décrivant un plateau de jeu
    Renvoie le tuple (n0,n1) où
    n0 : nombre de pions de J_0
    n1 : nombre de pions de J_1"""
    n0,n1=0,0
    for i in range(4):
        for j in range(4):
            val=etat(tab,[i,j])
            if val==0:
                n0+=1
            elif val==1:
                n1+=1
    return n0,n1


def partie_finie(tab):
    """partie_finie(tab:list)->bool
    tab : liste décrivant un plateau de jeu
    Renvoie True si la partie est finie, False sinon"""
    J0_bloque=len(cases_jouables(tab,0))==0
    J1_bloque=len(cases_jouables(tab,1))==0
    return J0_bloque and J1_bloque


################################################################################
#   OTHELLO ALEA
################################################################################


# othello_alea()
# pas utile pour la suite
# laissé à titre d'exemple pour se familiariser au jeu 

def othello_alea():
    """othello_alea()->None
    Jeu d'Othello contre la machine
    J_0 : joueur 
    J_1 : machine"""
    tab=init_tab()
    J_i=1
    fini=False
    print("Partie d'Othello")
    print("J_0 -> O")
    print("J_1 -> X")
    print()
    while not fini:
        J_i=adversaire(J_i)
        aff(tab)
        jouables=cases_jouables(tab,J_i)
        if len(jouables)>0:
            if J_i==0:
                valide=False
                while not valide:
                    print()
                    saisie=input("J_"+str(J_i)+" : x,y =")
                    coords=saisie.split(",")
                    pos=[int(coords[0]),int(coords[1])]
                    valide=pos in jouables
                    if not valide:
                        print("Coup invalide")
            else:
                ind=rd.randint(len(jouables))
                pos=jouables[ind]
                print("\nLa machine joue ",pos)
            joue(tab,pos,J_i)
        elif len(cases_libres(tab))>0:
            print("\nJ_"+str(J_i)+" passe")
        fini=partie_finie(tab)
        print()    
    n0,n1=comptage(tab)
    if n0>n1:
        print("J_0 gagne")
        print("O = ",n0, " X =",n1)
    elif n0<n1:
        print("J_1 gagne")
        print("O = ",n0, " X =",n1)
    else:
        print("Match nul")
    print()
    aff(tab)


################################################################################
#   CONVERSION TAB-INT
################################################################################


def tab_int(tab):
    """tab_int(tab:list)->int
    Convertit une liste de plateau de jeu en nombre écrit en base 3
    Suit l'algorithme de Horner"""
    dico={None:0,0:1,1:2}
    # A COMPLETER
    pass

def int_tab(N):
    """int_tab(N:int)->list
    Convertit un nombre en base 3 en liste de plateau de jeu"""
    dico={0:None,1:0,2:1}
    # A COMPLETER
    pass


################################################################################
#   GENERATION GRAPHE
################################################################################


def joue_partie(N_tab,J_i):
    """joue_partie(N_tab:int,J_i:int)->None
    Construit récursivement le graphe de jeu
    depuis le plateau de jeu codé par N_tab avec J_i qui joue"""
    global G, N
    # A COMPLETER
    # ON UTILISERA LES FONCTIONS SUIVANTES :
    # int_tab, partie_finie, comptage, cases_jouables, adversaire, tab_int, joue, joue_partie
    pass
    

    
def joue_graphe():
    """joue_graphe()->None
    Génération du graphe de jeu et de la liste des parties nulles
    L'état initial est le plateau initial et le joueur J_0 commence"""
    global G, N
    G,N={},[]
    joue_partie(tab_int(init_tab()),0)


print("Génération du graphe du jeu et des positions nulles")
joue_graphe()


################################################################################
#   OTHELLO MINIMAX - ARENE
################################################################################

def est_feuille(noeud):
    """est_feuille(noeud:int)->bool
    Renvoie True si noeud est une feuille du graphe G
    et False sinon"""
    return G[noeud]==[]


def minimax_arene(noeud,J_i):
    """minimax_arene(noeud:int,J_i:int)->float
    noeud : entier codant un plateau de jeu
    J_i : joueur donc c'est le tour
    Calcule la fonction d'évaluation du jeu depuis (noeud,J_i)"""
    # A COMPLETER
    # ON UTILISERA LES FONCTIONS SUIVANTES :
    # est_feuille, score, int_tab, minimax_arene, adversaire
    pass



def partie_minimax():
    """partie_minimax()->None
    Partie d'othello contre la machine qui suit l'algorithme Minimax
    J_0 : joueur
    J_1 : machine"""
    tab=init_tab()
    J_i=1
    fini=False
    print("Partie d'Othello")
    print("J_0 -> O")
    print("J_1 -> X")
    print()
    while not fini:
        J_i=adversaire(J_i)
        aff(tab)
        jouables=cases_jouables(tab,J_i)
        if len(jouables)>0:
            if J_i==0:
                valide=False
                while not valide:
                    print()
                    saisie=input("J_"+str(J_i)+" : x,y =")
                    coords=saisie.split(",")
                    pos=[int(coords[0]),int(coords[1])]
                    valide=pos in jouables
                    if not valide:
                        print(jouables)
                        print("Coup invalide")
                joue(tab,pos,J_i)
                N_tab=tab_int(tab)
            else:
                print()
                m=pinf
                # examen de coup possible
                for fils in G[N_tab]:
                    aux=minimax_arene(fils,0)
                    if aux<m:
                        m=aux
                        succ=fils
                N_tab=succ
                tab=int_tab(N_tab)
        elif len(cases_libres(tab))>0:
            print("\nJ_"+str(J_i)+" passe")
        fini=partie_finie(tab)
        print()
    n0,n1=comptage(tab)
    if n0>n1:
        print("J_0 gagne")
        print("O = ",n0, " X =",n1)
    elif n0<n1:
        print("J_1 gagne")
        print("O = ",n0, " X =",n1)
    else:
        print("Match nul")
    print()
    aff(tab)