import random

BREITE = 4
HOEHE = 3

                 # Alternative Eingabe per Unicode-Nummer 
gelb = '🟡'      # '\U0001f7e1'
blau = '🔵'      # '\U0001f535'
leer = '⬜'      # '\u2b1c'
randfeld = '⬛'  # '\u2b1b'

        
def startaufstellung():
    '''Erzeugt ein Spielfeld in Startaufstellung als Array = Liste von Listen
       und liefert dieses Array als Rückgabewert zurück.
       Empfehlung: Um das eigentliche Spielfeld einen Rand aus Randfeldern anlegen.
       Dies hat Vorteile beim Prüfen, ob ein Zug erlaubt ist (denn sonst muss man checken, ob man am Rand ist.)
       Dann ist es ein Array der Form (BREITE+2)x(HOEHE+2).
       Beispiel: Für BREITE=4 und HOEHE=3 soll das Spielfeld so aussehen:
       ⬛⬛⬛⬛⬛⬛
       ⬛🟡🟡🟡🟡⬛
       ⬛⬜⬜⬜⬜⬛
       ⬛🔵🔵🔵🔵⬛
       ⬛⬛⬛⬛⬛⬛
       Das blau besetze Feld links unten ist das Feld a1,
       das blau besetze Feld rechts unten ist d1.
       Im Array an Position [4][1] ist also blau zu speichern.
       '''
    # Leeres Spielfeld.
    brett = [[leer for y in range(HOEHE+2)] for x in range(BREITE+2)]
    # Startstellung
    for x in range(1, BREITE+1):
        brett[x][1] = blau
        brett[x][HOEHE] = gelb
    # Umgebendes Rechteck nicht verwendbarer Felder
    for x in range(BREITE+2):
        brett[x][0] = randfeld
        brett[x][-1] = randfeld
    for y in range(HOEHE+2):
        brett[0][y] = randfeld
        brett[-1][y] = randfeld
    return brett

def spielbrett_als_string():
    '''Liefert als Rückgabewert das aktuelle Spielbrett als String (inklusive Zeilenumbrüche).'''
    s = ''
    for y in range(HOEHE, 0, -1):
        z = str(y)
        for x in range(1, BREITE+1):
            z = z+brett[x][y]
        z = z+'\n'
        s = s+z
    z = ' '
    for x in range(1, BREITE+1):
        z = z + chr(ord('a')-1+x)+' '
    z = z
    s = s+z
    return s

    # Alternative:
    # zeilen = [f"{y}{''.join([brett[x][y] for x in range(1, BREITE+1)])}" for y in range(1, HOEHE+1)]
    # s = '\n'.join(zeilen[::-1]) 
    # s += '\n ' + ''.join([chr(ord('a')+x)+' ' for x in range(BREITE)])
    # return s
    
def gegner(s):
    '''Liefert den Gegner von s als Rückgabewert,
       also blau für s==gelb und sonst gelb.'''
    if s == gelb:
        return blau
    else:
        return gelb
    
    # Alternative:
    # return blau if s == gelb else gelb
    
def vorwaerts(s):
    '''Liefert die Vorwärtsrichtung von s,
       also -1 für s==gelb und sonst 1.'''
    if s == gelb:
        return -1
    else:
        return 1
        
    # Alternative:
    # return -1 if s == gelb else 1
    
def info_spielanfang():
    '''Gibt Anfangsinformation zum Spiel aus.'''
    print(f'''
{BREITE}x{HOEHE}-Schach
----------    
Eingabe der Züge in Schachnotation.
Beispiel: a{HOEHE}-a{HOEHE-1}.''')

def info_spielende():
    '''Gibt aus, dass das Spiel zu Ende ist, und nennt die Gewinnerfarbe.'''

    print('Spielende')
    print(f'Gewinner ist {gegner(am_zug)}.\n')
          
def zug_erlaubt(ax, ay, bx, by):
    '''Gibt True oder False zurück, je nachdem, ob der Spielzug 
       vom Feld (ax, ay) zum Feld (bx, by) erlaubt ist oder nicht.
       Beachte, dass die Variable am_zug speichert, welcher Spieler an der Reihe ist.'''
    if brett[ax][ay] == am_zug:
        vw = vorwaerts(am_zug)
        if by == ay+vw:
            if bx == ax and brett[bx][by] == leer:
                # Zug vorwaerts auf freies Feld
                return True
            if bx in {ax-1, ax+1} and brett[bx][by] == gegner(am_zug):
                # Diagonales Schlagen
                return True
    return False
        
def fuehre_zug_aus(ax, ay, bx, by):
    '''Führt den Spielzug vom Feld (ax, ay) zum Feld (bx, by) aus, d. h.
       die globalen Variablen brett und am_zug werden entsprechend aktualisiert.
       Deswegen muss man diese beiden Variablen als global deklarieren.'''
    global brett, am_zug
    brett[ax][ay] = leer
    brett[bx][by] = am_zug
    am_zug = gegner(am_zug)

def schachnotation_aus_koordinaten(x, y):
    '''Liefert etwa für (x, y) = (3, 1) die zugehörige Schachnotation 'c1' als String.
       Verwende chr(Nummer) und ord(Zeichen), um ASCII-Code-Nummern in Zeichen umzurechnen und umgekehrt.'''
    return f'{chr(ord('a')-1+x)}{y}'

def gib_zuginformation_aus(ax, ay, bx, by):
    '''Gibt den Spielzug von (ax, ay) nach (bx, by) in Schachnotation aus und davor, wer zieht.
       Beispiel: Zug von 🟡: a3-a2.
       Verwende die Funtkion schachnotation_aus_koordinaten'''
    print(f'Zug von {am_zug}: {schachnotation_aus_koordinaten(ax, ay)}-{schachnotation_aus_koordinaten(bx, by)}.')

def endstellung():
    '''Liefert True oder False, je nachdem, ob das Spielbrett in einer Endstellung ist oder nicht.
       Also True, falls ein Spieler die gegnerische Endreihe erreicht hat oder der Spieler, der aktuell am Zug ist,
       keinen erlaubten Zug durchführen kann (verwende die Funktion zug_erlaubt).'''
    kein_zug_moeglich = True
    for x in range(1, BREITE+1):
        for y in range(1, HOEHE+1):
            if brett[x][y] == am_zug:
                vw = vorwaerts(am_zug)
                for dx in range(-1, 2):
                    if zug_erlaubt(x, y, x+dx, y+vw):
                        kein_zug_moeglich = False
    endlinie_erreicht = False
    for x in range(1, BREITE+1):
        if brett[x][1] == gelb or brett[x][HOEHE] == blau:
            endlinie_erreicht = True
    return endlinie_erreicht or kein_zug_moeglich

def koordinaten_aus_schachnotation(s):
    '''Erwartet eine String s aus zwei Zeichen, etwa 'c2',
       und liefert als Rückgabewert die beiden zugehörigen Koordinaten, etwa 4, 2.'''
    return ord(s[0])-ord('a')+1, int(s[1])

def ermittle_zug_von_benutzer():
    '''Fragt den Benutzer (der am Zug ist) nach seinem Zug und 
       liefert diesen Zug als Tupel von 4 Zahlen zurück.
       Der Zug soll in Schachnotation eingegeben werden. 
       Beispiel: a3-a2 liefert das Rückgabetupel 1, 3, 1, 2.
       Verwende die Funktionen koordinaten_aus_schachnotation und zug_erlaubt.
       Wir nehmen an, dass die Eingabe das korrekte Format hat.
       Ist der Zug nicht erlaubt, so wiederholt sich das ganze.'''
    while True:
        s = input(f'Zug von {am_zug} eingeben: ')
        ax, ay = koordinaten_aus_schachnotation(s[:2])
        bx, by = koordinaten_aus_schachnotation(s[3:])
        if zug_erlaubt(ax, ay, bx, by):
            return ax, ay, bx, by
        else:
            print('\nxxxxxxxxxx Unerlaubter Zug. Nächster Versuch. xxxxxxxxxxxxxx')

def ermittle_zufaelligen_computerzug():
    '''Ermittelt alle möglichen Computerzüge und wählt zufällig einen davon aus.
       Dieser wird als Tupel zurückgegeben (etwa 3, 1, 3, 2 für den Zug c1-c2).
       Der Befehl random.choice(Liste) wählt einen zufälligen Eintrag aus einer Liste.'''  
    liste_moeglicher_zuege = []
    for x in range(1, BREITE+1):
        for y in range(1, HOEHE+1):
            if brett[x][y] == am_zug:
                vw = vorwaerts(am_zug)
                for dx in range(-1, 2):
                    if zug_erlaubt(x, y, x+dx, y+vw):
                        liste_moeglicher_zuege.append((x, y, x+dx, y+vw))
    return random.choice(liste_moeglicher_zuege)

#############################
# Neues für Minimax, Beginn #
#############################

UNENDLICH = 1000

zug_an_wurzel = None
# Speichert den obersten Zug im Suchbaum in der Form (ax, ay, bx, by).

def liste_aller_moeglichen_zuege():
    '''Liefert eine Liste aller möglichen Züge. 
    Die Einträge der Liste sind 4-Tupel (ax, ay, bx, by),
    in denen die Koordinaten von Start- und Zielfeld stehen.
    Beispielsweise könnte die folgende Liste zurückgegeben werden:
    [(2, 1, 1, 2), (2, 1, 2, 2), (3, 1, 3, 2), (4, 1, 4, 2)]'''

def mache_zug_rueckgaengig(ax, ay, bx, by, startfarbe, zielfarbe):
    '''Setzt die startfarbe auf das Spielfeld (ax, ay) und die zielfarbe auf das Spielfeld (bx, by).
    Ausserdem wird der Wert der Variablen am_zug auf den anderen Wert gesetzt, also gelb zu blau oder umgekehrt.'''
    global am_zug

def maximiere(tiefe):
    '''Ermittelt die Bewertung der aktuellen Stellung. Die Variable tiefe gibt die Tiefe an, in der wir uns gerade im Suchbaum befinden. Die Wurzel hat die Tiefe 0.
    Die Bewertung der aktuellen Stellung (in der der Maximierer dran ist) wird wie folgt ermittelt:
    (1) Ist die aktuelle Stellung eine Endstellung, so wird als Bewertung -UNENDLICH+1+tiefe zurückgegeben (je länger das Spiel dauert, desto besser für den Maximierer)
    (2) Sonst: Erzeuge alle Nachfolgestellungen, bewerte diese mit der Minimier-Funktion und ermittle das Maximum all dieser Bewertungen (im Fall, dass wir an der Wurzel
               des Suchbaums sind, also tiefe=0 gilt: Speichere den/einen Zug, der dieses Maximum erreicht, in der Variablen zug_an_wurzel in der Form (ax, ay, bx, by)). 
               Gib das Maximum als Rückgabewert zurück.
    Empfehlung beim Erzeugen der Nachfolgestellungen: Führe für jeden möglichen Zug diesen aus, bewerte die erreichte Stellung und mache den Zug wieder rückgängig.
    (Das benötigt insgesamt relativ wenig Speicher.)'''
    global zug_an_wurzel

def minimiere(tiefe):
    '''Im Wesentlichen dasselbe wie die Maximierfunktion, nur ist nun der Minimierer dran, der das Minimum aller Nachfolgestellungen als Bewertung zurückliefert.'''
    global zug_an_wurzel

def bester_zug():   
    '''Ruft entweder die Maximierfunktion (mit Tiefe 0) auf, wenn Gelb dran ist, sonst die Minimierfunktion.
    Als Rückgabewert wird der Wert der Variablen zug_an_wurzel zurückgeliefert.''' 
    # Gelb maximiert,
    # Blau minimiert.

###########################
# Neues für Minimax, Ende #
###########################

brett = startaufstellung()
info_spielanfang()
am_zug = gelb        
while True:
    print(spielbrett_als_string())
    if endstellung():
        break
    if am_zug == gelb:
        ax, ay, bx, by = ermittle_zug_von_benutzer()
    else:
        # ax, ay, bx, by = ermittle_zufaelligen_computerzug()
        ##############################
        # Aufruf der neuen Funktion: #
        ##############################
        ax, ay, bx, by = bester_zug()

    gib_zuginformation_aus(ax, ay, bx, by)    
    fuehre_zug_aus(ax, ay, bx, by)
info_spielende()