#**************************************************************
# definition du jeu de morpion
#**************************************************************


#construit un jeu vide
def nouveauJeu():
    return ('.','.','.','.','.','.','.','.','.')

#permet d'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])

print("affiche jeu vide")
affiche(nouveauJeu())


#permet de savoir qui doit jouer
def joueur(jeu):
    J1=0
    J2=0
    for i in jeu:
        if i=='X':
           J1+=1
        if i=='O':
           J2+=1
    if J1==J2:
        return 'X'
    return('O')

#retourne les coups possibles
# a savoir les cases vides avec un '.' dedans
def coupPossible(jeu):
    res=[]
    for i in range(9):
        if jeu[i]=='.':
            res+=[i]
    return res

print("coups possibles")
print(coupPossible(nouveauJeu()))


#permet de jouer un coup sur une case
def jouer(jeu,coup):
    if jeu[coup]!='.':
        print("case occupee")
    else:
        liste=[]
        liste+=jeu
        liste[coup]=joueur(jeu)
        return(tuple(liste))

#test jouer
print("joue un coup en 5")
affiche(jouer(nouveauJeu(),5))

#permet de savoir si le joueur 1 'X' gagne une partie
def gagner(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)

#test gagner
jeu=nouveauJeu()
print('jeu vide',gagner(jeu));
jeu=jouer(jeu,0)
affiche(jeu)
print('jeu faux',gagner(jeu));
jeu=jouer(jeu,1)
affiche(jeu)
print('jeu faux',gagner(jeu));
jeu=jouer(jeu,3)
affiche(jeu)
print('jeu faux',gagner(jeu));
jeu=jouer(jeu,4)
affiche(jeu)
print('jeu faux',gagner(jeu));
jeu=jouer(jeu,6)
affiche(jeu)
print('jeu vrai',gagner(jeu));



#**************************************************************
# creation de trajectoire etat initial --> etat terminal
#**************************************************************

import random;

#création d'une trajectoire jusque la fin
def trajectoire(depart, valeur):
    jeu=depart
    # boolean qui explicite quand la trajectoire est finie
    fini=False
    #tant que ni gagne ni fini
    while (not fini):
        affiche(jeu)
        print('---------------')
        coups=coupPossible(jeu)
        #si pas de coup possible on s'arrete
        if (len(coups)==0):
            fini=True
        #si gagné ou perdu, on s'arrete
        elif (gagner(jeu)!=0) :
            fini=True
        #sinon on joue un coup au hasard parmi les coups possibles
        else:
            numcoup=random.randint(0,len(coups)-1)
            coup=coups[numcoup]
            jeu=jouer(jeu,coup)

print("*********************\ntest de trajectoire\n**************\n")
val={}
trajectoire(nouveauJeu(),val)


#**************************************************************
# Approche par trajectoires et calcul des valeurs
#**************************************************************


#donne la valeur d'un jeu gagnant en fonction du joueur
def valGagnant(joueurEnCours):
    if joueurEnCours=='X' :
        gagne=1
    else :
        gagne=-1
    return(gagne)
        
#donne la valeur d'un jeu perdant en fonction du joueur
def valPerdant(joueurEnCours):
    if joueurEnCours=='X' :
        perdu=-1
    else :
        perdu=1
    return(perdu)

#calcul des fils
# retourne [filsgagnant, filsperdant, filsegalite,filsincoonu]
def calculFils(jeu,table):
    gagnant=[]
    perdant=[]
    inconnu=[]
    egalite=[]

    joueurEnCours=joueur(jeu)
    
    #determine gagne/perdu
    gagne=valGagnant(joueurEnCours)
    perdu=valPerdant(joueurEnCours)
        
    #recupere la liste des coups
    coups=coupPossible(jeu)
    # parcours les coups possibles
    for coup in coups:
        # fait le coup
        njeu=jouer(jeu,coup)
        
        # si non connu ajoute comme inconnu
        if tuple(njeu) not in table:
            inconnu.append(coup)
        #attention gerer joueurs
        elif (table[njeu])==gagne:
            gagnant.append(coup)
        elif (table[njeu])==0 :
            egalite.append(coup)
        else:
            perdant.append(coup)  
    return [gagnant,perdant,egalite,inconnu]



#parcours jusque fin
def trajectoire2(depart, valeur):
    jeu=depart
    fini=False
    
    #tant que ni gagne ni fini
    while (not fini):

        gagne=valGagnant(joueur(jeu))
        perdu=valPerdant(joueur(jeu))
            
        #affiche(jeu)
        #print('---------------')

        #recupere les coups
        coups=coupPossible(jeu)
        res=calculFils(jeu,valeur)
        gagnant=res[0]
        perdant=res[1]
        egalite=res[2]
        inconnu=res[3]

        #si etat courant gagné ou perdu
        if (gagner(jeu)!=0) :
            valeur[jeu]=gagner(jeu)
            fini=True

        #si un coup gagnant
        elif (len(gagnant)>0):
            #on met à jour et on arrete
            valeur[jeu]=gagne
            fini=True
            
        #si un coup inconnu
        elif (len(inconnu)>0):
            #on choisit un coup au hasard parmi les inconnus
            numcoup=random.randint(0,len(inconnu)-1)
            coup=inconnu[numcoup]
            jeu=jouer(jeu,coup)

        #pas de coup gagnt ni inconnu
        # si egalite, valeur c'est 0
        elif (len(egalite)>0):
            valeur[jeu]=0
            fini=True

        #que des perdants
        elif (len(perdant)>0):
            valeur[jeu]=perdu
            fini=True

        #pas de coup, on s'errete
        else :
            fini=True
            valeur[jeu]=gagner(jeu)

#construction tant que initial n'a pas de valeur associée
def calcul(depart):
    valeur={}
    while (depart not in valeur):
        jeu=depart
        trajectoire2(jeu,valeur)
    return valeur


#*******************************************************
# fonction pour lancer une partie
#********************************************************


#coupMeilleur
def coupMeilleur(jeu,table):
    #cherche le coup égal à la valeur
    coups=coupPossible(jeu)
    valeur=table[jeu]

    #pour faire au hasard
    #on choisit le coup au hasard parmi les meilleurs
    fini=False
    while (not fini):
        #choisit un coup au hasard
        coup=coups[random.randint(0,len(coups)-1)]
        #si la valeur est celle attendue, on return
        njeu=jouer(jeu,coup)
        #si la cle existe
        if (njeu in table):
            if (table[njeu]==valeur):
                return coup


#permet de lancer une partie
def partie(depart,table):
    jeu=depart
    #tant que le jeu n'est pas fini
    while (gagner(jeu)==0) and len(coupPossible(jeu))!=0:
        coup=coupMeilleur(jeu,table)
        print("coup joue", coup)
        jeu=jouer(jeu,coup)
        affiche(jeu)
        print("-----")

#permet de choisir le coup
def afficheMatrice():
    print ("------")
    print ("0 1 2")
    print ("3 4 5")
    print ("6 7 8")
    print ("------")
    

#permet de jouerPartie
def jouerPartie(depart,table,humain):
    jeu=depart
    print("******* bonne partie *****")
    affiche(jeu)
    #tant que le jeu n'est pas fini
    while (gagner(jeu)==0) and len(coupPossible(jeu))!=0:
        #si c'est au joueur
        if joueur(jeu)==humain :
            print("----- a vous -----") 
            coup=-1
            #demander coup valide
            coups=coupPossible(jeu)
            afficheMatrice()
            while(coup not in coups):
                coup=int(input("quel coup jouer ? "))
            #jouer coup
            jeu=jouer(jeu,coup)
            affiche(jeu)
            
        # si c'est au programme
        else:
            print("----- a moi -----")
            #deux cas se posent
            # si la situation n'est pas connue, on la calcule
            #cela arrive si on sort du chemin optimal
            if (jeu not in table):
                table=calcul(jeu)
            #joue le meilleur coup
            coup=coupMeilleur(jeu,table)
            jeu=jouer(jeu,coup)
            affiche(jeu)
                
                    
    

#********************************
# lancement du jeu
#*******************

jeu=nouveauJeu()
valeur=calcul(jeu)
print(valeur[jeu])
jouerPartie(jeu,valeur,'X')