print("##############################################")
print("#      premier test du jeu Morpion           #")
print("##############################################")


#creation d'un jeu
def nouveauJeu():
    t=['.']*9
    return tuple(t)

jeu=nouveauJeu()
print(jeu)

#afficher un jeu
def affiche(jeu):
    print (jeu[0],jeu[1],jeu[2])
    print (jeu[3],jeu[4],jeu[5])
    print (jeu[6],jeu[7],jeu[8])

affiche(jeu)

#retourner les coups
# tous les non '.'
def coupPossible(jeu):
    res=[];
    for i in range(9):
        if (jeu[i]=='.'):
            res+=[i]
    return(res)

print(coupPossible(nouveauJeu()))

#trouver le joueur
#en fonction de la difference 'X', 'O'
def joueur(jeu):
    joueurX=0
    joueurO=0
    for i in range(9):
        if (jeu[i]=='X'):
            joueurX=joueurX+1
    for i in range(9):
        if (jeu[i]=='O'):
            joueurO=joueurO+1
    if (joueurX==joueurO):
        return('X')
    else:
        return('O')
    
    
# jouer un coup
def jouer(jeu,num):
    res=list(jeu)
    coups=coupPossible(jeu)
    if (num in coups):
        res[num]=joueur(jeu)
    return(tuple(res))


jeu2=jouer(jeu,2)
print("*****jeu****")
affiche(jeu)
print("*****jeu2****")
affiche(jeu2)
print("*****jeu3****")
jeu3=jouer(jeu2,1)
affiche(jeu3)
    
print(coupPossible(jeu3))

#gagner/perdre
def resultat(jeu):
    res='.'
    if (jeu [0]!= '.' and jeu [0]== jeu [3]== jeu [6]):
        res=jeu [0]
    if (jeu [1]!= '.' and jeu [1]== jeu [4]== jeu [7]):
        res=jeu [1]
    if (jeu [2]!= '.' and jeu [2]== jeu [5]== jeu [8]):
        res=jeu [2]
    if (jeu [0]!= '.' and jeu [0]== jeu [1]== jeu [2]):
        res=jeu [0]
    if (jeu [4]!= '.' and jeu [4]== jeu [5]== jeu [3]):
        res=jeu [3]
    if (jeu [7]!= '.' and jeu [7]== jeu [8]== jeu [6]):
        res=jeu [6]
    if (jeu [0]!= '.' and jeu [0]== jeu [4]== jeu [8]):
        res=jeu [0]
    if (jeu [2]!= '.' and jeu [2]== jeu [4]== jeu [6]):
        res=jeu [2]
    if (res == 'O'):
        return ( -1)
    else:
        if res =='X':
            return (1)
    return (0)
    

#########################
# algorithme minmax de base en deux fonctions
#########################
compteur=0;

def valeurMax(jeu):
    #on compte le nb fois
    global compteur
    compteur=compteur+1

    #on calcule
    res=resultat(jeu)
    # si il y a un gagnant ou un pedrant, fini
    if (res==1)or(res==-1):
        return(res)
    #si plus de coup
    coups=coupPossible(jeu)
    if (len(coups)==0):
        return(0)
    
    #sinon on retourne la meilleure valeur
    maximum=-2
    meilleurCoup=-1
    for coup in coups:
        jeuSuivant=jouer(jeu,coup)
        val=valeurMin(jeuSuivant)
        #si le coup est meilleur quoique fasse l'autre
        if (val>maximum):
            maximum=val
            meilleurCoup=coup

    return(maximum)
            
    
        
def valeurMin(jeu):
    #on compte le nb fois
    global compteur
    compteur=compteur+1

    res=resultat(jeu)
    # si il y a un gagnant ou un pedrant, fini
    if (res==1)or(res==-1):
        return(res)
    #si plus de coup
    coups=coupPossible(jeu)
    if (len(coups)==0):
        return(0)
    #sinon on retourne la meilleure valeur
    minimum=1
    meilleurCoup=-1
    for coup in coups:
        jeuSuivant=jouer(jeu,coup)
        val=valeurMax(jeuSuivant)
        #si le coup est meilleur quoique fasse l'autre
        if (val<minimum):
            minimum=val
            meilleurCoup=coup
    return(minimum)


#test
import time
print()
print("##############################################")
print("#      on lance Min Max                      #")
print("##############################################")
tempsDebut=time.time()
valDepart=valeurMax(nouveauJeu())
print("valeur de état de depart:",valDepart)
print("nombre noeuds parcourus:",compteur)
tempsFin=time.time()
tempsMinMax=tempsFin-tempsDebut
print("temps:", tempsMinMax, " secondes")



##### minmaxOptimise -- on passe plusieurs fois par le meme point
# dire qu'on va stocker les valeurs des qu'on les a
#
# marche car non cyclique
# sinon cela pose des soucis
#######
# pour calculer a on doit calculer B qui necessite de cacluler A
#######

def valeurMaxOptimise(jeu,table):
    #si on l'a deja calcule
    if (jeu in table):
        return(table[jeu])

    #on compte le nb fois
    global compteur
    compteur=compteur+1    

    #on calcule
    res=resultat(jeu)
    # si il y a un gagnant ou un pedrant, fini
    if (res==1)or(res==-1):
        return(res)
    #si plus de coup
    coups=coupPossible(jeu)
    if (len(coups)==0):
        return(0)
    
    #sinon on retourne la meilleure valeur
    maximum=-2
    meilleurCoup=-1
    for coup in coups:
        jeuSuivant=jouer(jeu,coup)
        val=valeurMinOptimise(jeuSuivant,table)
        #si le coup est meilleur quoique fasse l'autre
        if (val>maximum):
            maximum=val
            meilleurCoup=coup

    #on met  jour la table
    table[jeu]=maximum
    return(maximum)
            
    
        
def valeurMinOptimise(jeu,table):
    #si on l'a deja calcule
    if (jeu in table):
        return(table[jeu])

    #on compte le nb fois
    global compteur
    compteur=compteur+1
        
    res=resultat(jeu)
    # si il y a un gagnant ou un pedrant, fini
    if (res==1)or(res==-1):
        return(res)
    #si plus de coup
    coups=coupPossible(jeu)
    if (len(coups)==0):
        return(0)
    #sinon on retourne la meilleure valeur
    minimum=1
    meilleurCoup=-1
    for coup in coups:
        jeuSuivant=jouer(jeu,coup)
        val=valeurMaxOptimise(jeuSuivant,table)
        #si le coup est meilleur quoique fasse l'autre
        if (val<minimum):
            minimum=val
            meilleurCoup=coup

    table[jeu]=minimum
    return(minimum)

def calculeTable():
    table=dict()
    jeu=nouveauJeu()
    global compteur
    compteur=0
    valeurMaxOptimise(jeu,table)
    return(table)


print()
print()
print("##############################################")
print("#      on lance Min Max  Optimise            #")
print("##############################################")
tempsDebut=time.time()
table=calculeTable()
print("nombre noeuds parcourus:",compteur)
tempsFin=time.time()
print("temps:", tempsFin-tempsDebut, " secondes")
tempsMinMaxOpt=tempsFin-tempsDebut
print("le 2e va ", tempsMinMax/tempsMinMaxOpt, " fois plus vite")

print()
print()


def afficheCoups(jeu,table):
    coups=coupPossible (jeu)
    print ("*********** Jeu ********")
    affiche(jeu)
    print ("*********** Joueur ********")
    print (joueur(jeu))
    print ("*********** coups *********")
    for coup in coups:
        njeu=jouer(jeu,coup)
        print ("-",coup," : ",table[njeu])


print()
print()
print("##############################################")
print("#      on déroule une partie                 #")
print("##############################################")


print("## nouveau jeu  ##")
jeu=nouveauJeu()
afficheCoups(jeu, table)
print("## joueur X peut jouer n'importe quoi et cela conduit égalité    ##")
print("## le premier coup n'a pas d'importance si joueurs sont optimaux ##")
print("## joueur X joue 0 ##")
jeu=jouer(jeu,0)
afficheCoups(jeu, table)

print("## joueur O doit jouer 4 sinon il perd ##")
print("## joueur O joue 1 ##")
print("## joueur O a perdu si joueur X joue bien ##")
jeu=jouer(jeu,1)
afficheCoups(jeu, table)

print("## joueur X sait qu'il peut gagner de 3 manieres ##")