import logging
from math import *
from queue import *

from igra import IGRALEC_M, IGRALEC_R, PRAZNO, NI_KONEC, KONEC, nasprotnik

#############################

class AlfaBeta():

    ZMAGA = 10 ** 5 # Mora biti vsaj 10^5
    NESKONCNO = ZMAGA + 1 # Več kot zmaga
    ENOTA = 1
    MALO = ENOTA / 10000

    def __init__(self, globina):
        self.globina = globina
        self.prekinitev = False
        self.igra = None
        self.jaz = None
        self.poteza = None

    def prekini(self):
        """Metoda, ki jo pokliče GUI, če je treba nehati razmišljati, ker
           je uporabnik zaprl okno ali izbral novo igro."""
        self.prekinitev = True

    def izracunaj_potezo(self, igra):
        """Izračunaj potezo za trenutno stanje dane igre."""
        # To metodo pokličemo iz vzporednega vlakna
        self.igra = igra
        self.prekinitev = False # Glavno vlakno bo to nastavilo na True, če moramo nehati
        self.jaz = self.igra.na_potezi
        self.poteza = None # Sem napišemo potezo, ko jo najdemo
        # Poženemo alfabeta
        (poteza, vrednost) = self.alfabeta(
        self.globina, -AlfaBeta.NESKONCNO, AlfaBeta.NESKONCNO, True
        )
        self.jaz = None
        self.igra = None

        if not self.prekinitev:
            # Potezo izvedemo v primeru, da nismo bili prekinjeni
            self.poteza = poteza

    def alfabeta(self, globina, alfa, beta, maksimiziramo):
        """Glavna metoda rezanje alfabeta."""
        if self.prekinitev:
            # Sporočili so nam, da moramo prekiniti
            logging.debug ("Alfabeta prekinja, globina = {0}".format(globina))
            return (None, 0)
        if self.igra.stanje_igre == KONEC:
            # Igre je konec, vrnemo njeno vrednost
            if self.igra.zmagovalec == self.jaz:
                return (None, self.ZMAGA)
            elif self.igra.zmagovalec == nasprotnik(self.jaz):
                return (None, -self.ZMAGA)
            else:
                return (None, 0)
        elif self.igra.stanje_igre == NI_KONEC:
            # Igre ni konec
            if globina == 0:
                return (None, self.vrednost_pozicije())
            else:
                # Naredimo eno stopnjo alfabeta
                if maksimiziramo:
                    # Maksimiziramo
                    najboljsa_poteza = None
                    vrednost_najboljse = -AlfaBeta.NESKONCNO
                    for p in self.igra.veljavne_poteze():
                        self.igra.povleci_potezo(p)
                        vrednost = self.alfabeta(globina-1, alfa, beta, not maksimiziramo)[1]
                        self.igra.razveljavi()
                        if vrednost > vrednost_najboljse:
                            vrednost_najboljse = vrednost
                            alfa = max(alfa, vrednost)
                            najboljsa_poteza = p
                        if alfa >= beta:
                            break
                else:
                    # Minimiziramo
                    najboljsa_poteza = None
                    vrednost_najboljse = AlfaBeta.NESKONCNO
                    for p in self.igra.veljavne_poteze():
                        self.igra.povleci_potezo(p)
                        vrednost = self.alfabeta(globina-1, alfa, beta, not maksimiziramo)[1]
                        self.igra.razveljavi()
                        if vrednost < vrednost_najboljse:
                            vrednost_najboljse = vrednost
                            najboljsa_poteza = p
                            beta = min(beta, vrednost_najboljse)
                        if alfa >= beta:
                            break

                assert (najboljsa_poteza is not None), "alfabeta: izračunana poteza je None"
                return (najboljsa_poteza, vrednost_najboljse)
        else:
            assert False, "alfabeta: nedefinirano stanje igre"


    def razdalja(self, polje_1, polje_2, igralec):
        """Vrne razdalje med dvema sosednjima poljema. Razdalja je odvisna od
        tega, kako so polja pobarvana."""
        (stolpec_1, vrstica_1) = polje_1
        (stolpec_2, vrstica_2) = polje_2
        if igralec == IGRALEC_M:
            zacetek = (-1, -1)
        elif igralec == IGRALEC_R:
            zacetek = (-2, -2)
        # Definiramo razdaljo za namišljeni končni polji
        if polje_1 == (12, 12):
            if (self.igra.plosca[stolpec_2][vrstica_2] == PRAZNO) and igralec == IGRALEC_R:
                return self.ENOTA
            elif (self.igra.plosca[stolpec_2][vrstica_2] == IGRALEC_R) and igralec == IGRALEC_R:
                return self.MALO
            else:
                return self.NESKONCNO
        elif polje_2 == (12, 12):
            if (self.igra.plosca[stolpec_1][vrstica_1] == PRAZNO) and igralec == IGRALEC_R:
                return self.ENOTA
            elif (self.igra.plosca[stolpec_1][vrstica_1] == IGRALEC_R) and igralec == IGRALEC_R:
                return self.MALO
            else:
                return self.NESKONCNO
        elif polje_1 == (11, 11):
            if (self.igra.plosca[stolpec_2][vrstica_2] == PRAZNO) and igralec == IGRALEC_M:
                return self.ENOTA
            elif (self.igra.plosca[stolpec_2][vrstica_2] == IGRALEC_M) and igralec == IGRALEC_M:
                return self.MALO
            else:
                return self.NESKONCNO
        elif polje_2 == (11, 11):
            if (self.igra.plosca[stolpec_1][vrstica_1] == PRAZNO) and igralec == IGRALEC_M:
                return self.ENOTA
            elif (self.igra.plosca[stolpec_1][vrstica_1] == IGRALEC_M) and igralec == IGRALEC_M:
                return self.MALO
            else:
                return self.NESKONCNO
        # Definiramo še razdaljo za začetni namišljeni polji
        elif polje_1 == zacetek and self.igra.plosca[stolpec_2][vrstica_2] == PRAZNO:
            return self.ENOTA
        elif polje_1 == zacetek and self.igra.plosca[stolpec_2][vrstica_2] == igralec:
            return self.MALO
        elif polje_1 == zacetek and self.igra.plosca[stolpec_2][vrstica_2] == nasprotnik(igralec):
            return self.NESKONCNO
        # Definiramo še razdaljo med dvema dejanskima poljema na plošči
        elif self.igra.plosca[stolpec_1][vrstica_1] == PRAZNO and self.igra.plosca[stolpec_2][vrstica_2] == PRAZNO:
            return self.ENOTA
        elif self.igra.plosca[stolpec_1][vrstica_1] == nasprotnik(igralec) or self.igra.plosca[stolpec_2][vrstica_2] == nasprotnik(igralec):
            return self.NESKONCNO
        elif self.igra.plosca[stolpec_1][vrstica_1] == igralec and self.igra.plosca[stolpec_2][vrstica_2] == igralec:
            return self.MALO
        elif self.igra.plosca[stolpec_1][vrstica_1] == igralec and self.igra.plosca[stolpec_2][vrstica_2] == PRAZNO:
            return self.ENOTA
        elif self.igra.plosca[stolpec_1][vrstica_1] == PRAZNO and self.igra.plosca[stolpec_2][vrstica_2] == igralec:
            return self.ENOTA

    def najkrajsa_pot(self, igralec):
        # Dijkstrov algoritem za iskanje najkrajše poti
        # množica vozlišč so vsa polja in robne črte
        # Slovar vozlišč in pripadajočih razdalj
        vozlisca = {}
        for j in range(11):
            for i in range(11):
                vozlisca[(j, i)] = self.NESKONCNO
        # dodamo še spodnji in desni rob
        vozlisca[(12, 12)] = self.NESKONCNO
        vozlisca[(11, 11)] = self.NESKONCNO
        if igralec == IGRALEC_M:
            # zacetno vozlisce
            vozlisca[(-1, -1)] = 0
            # koncno vozlisce
            tarca = (11, 11)
        elif igralec == IGRALEC_R:
            # zacetno
            vozlisca[(-2, -2)] = 0
            # koncno
            tarca = (12, 12)
        while vozlisca:
            trenutno_polje = min(vozlisca, key=vozlisca.get)
            if trenutno_polje == tarca:
                return vozlisca[trenutno_polje]
            pot = vozlisca[trenutno_polje]
            del vozlisca[trenutno_polje]
            for sosed in self.igra.najdi_vse_sosede(trenutno_polje):
                if sosed in vozlisca:
                        nova_pot = pot + self.razdalja(trenutno_polje, sosed, igralec)
                        if nova_pot < vozlisca[sosed]:
                            vozlisca[sosed] = nova_pot

    def vrednost_pozicije(self):
        # Oceni pozicijo na podlagi razlike med najkrajšo potjo do zmage igralca in nasprotnika
        modra_pot = self.najkrajsa_pot(IGRALEC_M)
        rdeca_pot = self.najkrajsa_pot(IGRALEC_R)
        if self.igra.na_potezi == IGRALEC_M:
            vrednost = - 0.5 * modra_pot + 1.5 * rdeca_pot
        elif self.igra.na_potezi == IGRALEC_R:
            vrednost = - 0.5 * rdeca_pot + 1.5 * modra_pot
        return vrednost
