import nodo, random, copy, sys
def lugaresDisponibles(Estado):
    z=1
    for x in Estado:
        for y in x:
            if(y==0):
        print str(z)+" ",
            z+=1
def numeroHijos(Estado):        #regresa el numero de hijos
    if(terminal(Estado)!=2):    #si es terminal, no tiene hijos
        return 0
    cont = 0
    for x in Estado:
        for y in x:
            if (y==0):
                cont+=1     #se le suma al numero de hijos
    return cont        #regresa el numero de hijos

def profundidad(Estado):    #regresa que tan profundo es el estado
    cont = 0
    for x in Estado:
        for y in x:
            if (y==0):
                cont+=1     #se le suma uno porque se va uno para abajo
    return 9-cont          #regresa la profundidad

def imprimeEstado(Estado):
    z=1
    for x in Estado:
        for y in x:
            if(y == 1):
                print "X ",
        elif(y == -1):
                print "O ",
            else:
                print str(z)+" ",#imprime el numero de la casilla
            z+=1
        print " "
def mejorMov(Estado, nivel, profund): #devuelve el mejor movimiento posible
    i = creaHijos(Estado)
    for x in i:
        x.setCalificacion(calificarArbol(x.getEstado(),nivel,profund))
    turno = profundidad(Estado)
    turno = turno%2
    temp = 0
    pos = 0
    if(turno == 0): #es decir, es max
        temp =-100
        cont = 0
        for x in i:
            if(x.getCalificacion() > temp):
                temp = x.getCalificacion()
                pos=cont
            cont+=1
    else: # es min
        temp= 100
        cont = 0
        for x in i:
            if(x.getCalificacion() < temp):
                temp= x.getCalificacion()
                pos=cont
            cont+=1
    veces=0
    for x in i:
        if(x.getCalificacion()==temp):
            veces+=1
    if(veces==1):
        return i.pop(pos).getEstado()
    else:
        posix=random.randint(1,veces)
        vecbuenos = 0
        for x in i:
            if(x.getCalificacion()==temp):
                vecbuenos+=1
        if(vecbuenos == posix):
                return x.getEstado()
    return None #regresa ninguno porque no hay hijo bueno

def calificarArbol(Estado,nivel,profund):
    if(terminal(Estado)!=2 or (profundidad(Estado)-nivel)==profund): #califica el hijo ya que es terminal
        return calificahijo(Estado)
    i = creaHijos(Estado)
    for x in i:
        x.setCalificacion(calificarArbol(x.getEstado(),nivel,profund)) #calificas el arbol desde este punto recursivamente
    prof = profundidad(Estado)
    prof = prof%2
    temp = 0
    if(prof == 0): #es decir, es max
        temp =-100
        for x in i:
            if(x.getCalificacion() > temp):
                temp = x.getCalificacion()
    else: # es min
        temp= 100
        for x in i:
            if(x.getCalificacion() < temp):
                temp= x.getCalificacion()
    return temp #regresa la calificacion seleccionada

def terminal(Estado): #checa si es un juego terminado
    cont = 0
    rango =range(3)
    for i in rango:     #checa verticales
        for x in Estado:
            cont+=x[i]
        if(cont==3):
            return 1 #Max gana
        elif(cont==-3):
            return -1 #Min gana
        else:
            cont = 0

    for x in Estado:           #checa horizontales
        for y in x:
            cont+=y
        if(cont==3):
            return 1 #Max gana
        elif(cont==-3):
            return -1 #Min gana
        else:
            cont = 0
    z = 0
    for x in Estado:        #checa diagonal \
        cont+=x[z]
        z+=1
    if(cont==3):
        return 1 #Max gana
    elif(cont==-3):
        return -1 #Min gana
    else:
        cont = 0
    z = 2
    for x in Estado:        #checa diagonal /
        cont+=x[z]
        z-=1
    if(cont==3):
        return 1 #Max gana
    elif(cont==-3):
        return -1 #Min gana
    else:
        cont = 0
    for x in Estado:    #checa si hay espacios vacios
        for y in x:
            if(y==0):
                return 2 #no ha acabado
    return 0 #esta lleno el tablero, entonces han empatado



def creaHijos(Estado): #crea los hijos posibles
    nhijos = numeroHijos(Estado)
    nivel = profundidad(Estado)
    turno = nivel%2
    i = range(nhijos)
    listadehijos = []
    for hijos in i:
        temporal = copy.deepcopy(Estado)  #copia el estado original para hacer los hijos
        hijo = nodo.hijo()
    nhijo = -1
        for x in temporal:
            cont =0
            for y in x:
                if(y==0):
                    nhijo+=1
                    if(nhijo==hijos):
                        x.pop(cont)
                        x.insert(cont,1-(turno*2))#asigna X o O dependiendo
                cont+=1
        hijo.setEstado(temporal)
        listadehijos.append(hijo)


    return listadehijos

def calificahijo(Estado):
    if(terminal(Estado)==1): #gano X
        return 100
    if(terminal(Estado)==-1): #gano O
        return -100
    if(terminal(Estado)==1): #empataron
        return 0
             #empieza la evaluacion ya que no es terminal
    matrix = [[0,0,0],[0,0,0],[0,0,0]]
    for x in Estado:
        cont = 0
        for y in x:
            matrix.pop(cont)
            if(y==0):   #Si esta vacio, agrega 4
                matrix.insert(cont,4)
            elif(y==-1): #si hay O, pone un 1
                matrix.insert(cont,1)
            elif(y==1): #si hay X, pone 2
                matrix.insert(cont,2)
            cont +=1
    cont = 0
    heuristica = 0
    rango =range(3)
    for i in rango:     #checa verticales
        for x in matrix:
            cont+=x
        if(cont==6):
            heuristica+=-3 #hay dos O y uno vacio
        elif(cont==9):
            heuristica+=-2 # hay un o y dos vacios
        elif(cont==10):
            heuristica+=2 # hay una x y dos vacio
        else:
            heuristica+=3 #hay dos x y uno vacio
        cont=0

    for i in rango:           #checa horizontales
        for y in matrix:
            cont+=y
        if(cont==6):
            heuristica+=-3 #hay dos O y uno vacio
        elif(cont==9):
            heuristica+=-2 # hay un o y dos vacios
        elif(cont==10):
            heuristica+=2 # hay una x y dos vacio
        else:
            heuristica+=3 #hay dos x y uno vacio
        cont=0
    z = 0
    for x in matrix:        #checa diagonal \
        cont+=x
        z+=1
    if(cont==6):
        heuristica+=-3 #hay dos O y uno vacio
    elif(cont==9):
        heuristica+=-2 # hay un o y dos vacios
    elif(cont==10):
        heuristica+=2 # hay una x y dos vacio
    else:
        heuristica+=3 #hay dos x y uno vacio
    cont=0
    z = 2
    for x in matrix:        #checa diagonal /
        cont+=x
        z-=1
    if(cont==6):
        heuristica+=-3 #hay dos O y uno vacio
    elif(cont==9):
        heuristica+=-2 # hay un o y dos vacios
    elif(cont==10):
        heuristica+=2 # hay una x y dos vacio
    else:
        heuristica+=3 #hay dos x y uno vacio
    return heuristica #esta lleno el tablero, entonces han empatado

def main():
    print "Juego de Gato, la pc comienza usando el 'X'"
    print "Escoge la dificultad (1-3-9): ",
    dificultad = input()
    estadoactual = [[0,0,0],[0,0,0],[0,0,0]]
    imprimeEstado(estadoactual)
    duracion = range(9)
    for x in duracion:
        nivel = profundidad(estadoactual)
        nivel = nivel%2
        if(nivel!=0):
        valido = False
        while(not valido):
                print "Digite la casilla a tirar "
                lugaresDisponibles(estadoactual)
                print "Cual quiere?: ",
                seleccion = input()
                f = 0
                c = 0
                if(seleccion==1):
                    f = 0
                    c = 0
                if(seleccion==2):
                    f = 1
                    c = 0
                if(seleccion==3):
                    f = 2
                    c = 0
                if(seleccion==4):
                    f = 0
                    c = 1
                if(seleccion==5):
                    f = 1
                    c = 1
                if(seleccion==6):
                    f = 2
                    c = 1
                if(seleccion==7):
                    f = 0
                    c = 2
                if(seleccion==8):
                    f = 1
                    c = 2
                if(seleccion==9):
                    f = 2
                    c = 2
        if(estadoactual[c][f] == 0):
                    valido = True
                else:
                    print "Casilla ocupada, seleccione otra"
            estadoactual[c][f] = -1 #pone el tiro del jugador en el estado actual
            print "Tu Turno"
            imprimeEstado(estadoactual)
    else:
            print "Turno de Max:"
            estadoactual = mejorMov(estadoactual,profundidad(estadoactual),dificultad)
            imprimeEstado(estadoactual)
        if(terminal(estadoactual)==1 and terminal(estadoactual)!=0):
            print "Perdiste..."
            sys.exit()
        elif(terminal(estadoactual)==0):
            print "Empataron..."
            sys.exit()
        elif (terminal(estadoactual)==-1):
            print "Ganaste!"
            sys.exit()



main()
#hijo = nodo.hijo()

#lugaresDisponibles(hijo.getEstado())