Cleverer: Die doppelte Prüfmethode

Wie geht ein durchschnittlich begabter menschlicher Spieler an das Spiel TicTacToe heran, wenn er am Zug ist? Ich denke, er macht in der Regel vor allem zwei Dinge. Er prüft, ob er mit dem aktuellen Zug vielleicht eine Reihe schließen kann und damit das Spiel gewinnt. Wenn ja, dann tut er das, und das Spiel ist zu Ende. Wenn nein, dann prüft er noch eine zweite Sache: Nämlich, ob der Gegenspieler vielleicht mit dem nächsten Zug eine Reihe bilden könnte. Wenn ja, dann verhindert er dies, indem er seinen eigenen Zug dort macht, wo der Gegner die Reihe schließen könnte.

Wenn das beides nicht geht – dann setzt er sein Symbol vielleicht einfach irgendwo hin … und wartet, was der Gegenspieler macht.

Genau diese Strategie kann man bei TicTacToe auch relativ einfach programmieren. Alles, was wir hinzufügen müssen, ist eine Methode computerZug(), die die Nummer des Kästchens zurückgibt, in das er seinen nächsten Zug machen will.

Was muss diese Methode machen?

• Sie erstellt eine Liste aller freien Felder.

• Sie geht alle freien Felder durch, setzt dort (nur in der Liste, nicht sichtbar auf dem Spielfeld) ihr Symbol und prüft mit der Funktion gewonnen(), ob sie damit das Spiel gewinnt. Wenn ja, dann hat sie den richtigen Zug gefunden und meldet diesen zurück

• Wenn alle freien Felder durchgeprüft sind und sie nicht gewinnen konnte, geht sie nochmals alle Felder durch. Diesmal setzt sie dort aber das Symbol des Gegners und prüft, ob er vielleicht mit einem Zug gewinnen kann. Wenn ja, dann meldet sie diese Position zurück, um dort den eigenen Zug zu machen.

• Wenn das alles kein Ergebnis gebracht hat, ist es egal, wo sie den Zug macht, und sie liefert eine Zufallsposition zurück (die Funktion aus dem letzten Programmbeispiel).

Das setzen wir jetzt in einer neuen, zusätzlichen Methode für unsere Spielverwaltung um: Der Anfang ist fast gleich wie bei der Zufallsfunktion. Erst einmal wird eine Liste aller leeren Felder erstellt.

def computerZug(self):
    leer = []
    for x in range(0,9):
        if self.spielstand[x] == 0:
            leer.append(x)
    anzahl = len(leer)
    backup = self.spielstand[:]

Zusätzlich wird am Schluss eine Kopie der spielstand-Liste in der Variable backup gespeichert. Warum? Weil die Funktion anschließend etwas in der spielstand-Variable »herumpfuscht« und damit verschiedene Spielstände auf Gewinn testet. Daher brauchen wir ein Backup, mit dem wir nach jeder Prüfung den Original-spielstand wiederherstellen können. Das Backup erstellen wir mit [:] – das bedeutet, es werden alle einzelnen Elemente der Liste, vom ersten bis zum letzten, in eine neue Liste kopiert. Das muss auf diese Weise gemacht werden, damit die Liste wirklich in eine neue kopiert wird und nicht nur eine neue Variable entsteht, die auf die alte Liste verweist.

So, jetzt wird getestet, ob der Computer mit einem Zug bereits gewinnen kann. Dazu muss er in der spielstand-Liste nacheinander alle Züge machen, die möglich sind (also einmal die Liste leer durchgehen, weil darin alle freien Positionen gespeichert sind), testweise eine 2 hineinsetzen (der Computer ist ja Spieler Nr. 2) und dann immer mit der Funktion gewonnen() prüfen, ob ihm das einen Sieg einbringt. Wenn ja, dann gibt er die Position, an der sein Zug gewinnt, per return-Kommando zurück – durch return wird die gesamte Funktion beendet. Vorher, wie vor jeder neuen Prüfung, muss er aber noch den Original-spielstand wiederherstellen.

    # Gewinnmöglichkeit checken
    for x in range(0,anzahl):
        self.spielstand = backup[:]
        self.spielstand[leer[x]] = 2
        if self.gewonnen(2):
            self.spielstand = backup[:]
            return leer[x]

Wenn der Computer in einem Zug gewinnen kann, dann wäre die Funktion also hier beendet. Wenn er aber alle Zugmöglichkeiten durchlaufen hat und mit keinem Zug gewinnt, geht die Funktion weiter zum nächsten Block.

Plan B – es muss geprüft werden, ob der Gegenspieler mit einem Zug gewinnen könnte. Das muss verhindert werden. Der Block läuft fast genauso ab – nur dass jetzt eine 1 statt einer 2 nacheinander testweise an jede freie Stelle gesetzt und geprüft wird, ob der Gegenspieler damit gewinnt.

    # Verliermöglichkeit verhindern
    for x in range(0,anzahl):
        self.spielstand = backup[:]
        self.spielstand[leer[x]] = 1
        if self.gewonnen(1):
            self.spielstand = backup[:]
            return leer[x]

Wieder wird die gesamte Funktion beendet, wenn das Programm ein Feld findet, mit dem der Gegenspieler gewinnen würde. Der Computer verhindert dies, indem er sein eigenes Symbol hineinsetzt.

Was aber, wenn auch ein solches Feld nicht gefunden wird?

Dann geht die Funktion in die letzte Phase. Nachdem offenbar kein akuter Handlungsbedarf besteht, geht das Programm davon aus, das es nun egal ist, wohin das Symbol gesetzt wird, und gibt eine Zufallsposition zurück (ermittelt mit der Funktion zufallsZug(), die wir ja schon haben).

    # Sonst: Zufallszug
    self.spielstand = backup[:]
    return self.zufallsZug()

Auf die Weise kommt also immer ein Zug des Computers zustande – entweder ein Gewinnerzug oder ein Zug, der das Verlieren verhindert, oder ansonsten ein zufälliger.

Die mausKlick()-Funktion, in der alles ausgelöst wird, ändert sich auch, aber nur geringfügig. Hier wird statt zufallsZug() jetzt computerZug() aufgerufen – und man kann auch die Nachrichten entsprechend anpassen.

def mausKlick(ereignis):
    # geklickte Zelle ermitteln:
    zellenPos = feld.toLocationInGrid(ereignis.getX(),ereignis.getY())
    zx = zellenPos.getX()
    zy = zellenPos.getY()
    # Wenn Zelle leer, dann weiter:
    if spiel.zellePruefen(zx,zy) == 0:
        spiel.setzen(zx,zy,spiel.aktiver_spieler)
        if spiel.gewonnen(spiel.aktiver_spieler):
            msgDlg("Der Spieler hat gegen den Computer gewonnen!")
        elif (spiel.brettVoll()):
            msgDlg("Das Spiel ist beendet: Unentschieden!")
        else:
            spiel.aktiver_spieler = 2
            delay(1000)
            spiel.nrSetzen(spiel.computerZug(),2)
            if spiel.gewonnen(spiel.aktiver_spieler):
                msgDlg("Der Computer hat gegen den Spieler gewonnen!")
            elif (spiel.brettVoll()):
                msgDlg("Das Spiel ist beendet: Unentschieden!")
            else:
                spiel.aktiver_spieler = 1

Fertig! Jetzt kannst du das Spiel gegen eine einfache KI testen. Wenn du nicht aufpasst, gewinnt der Computer. Wenn du besser aufpasst, kommt es meist zum Unentschieden – und wenn du richtig clever spielst, kannst du den Computer auch schlagen.

Abbildung 22.7    Siehe da: Der Computer hat gewonnen … dank KI.

Die künstliche Intelligenz kann es schon mit der Spielweise eines, sagen wir, 8-jährigen Kindes aufnehmen. Das Programm macht keine groben Fehler und übersieht keine Chance, kann aber mit etwas Überlegung schon auch ausgetrickst werden.

Die Schwächen dieser Methode liegen vor allem darin, dass der Computer nicht vorausdenkt. Er hat keine eigene Strategie, sondern versucht nur, bei jedem Zug direkt zu gewinnen oder den Sieg des Gegners direkt zu vermeiden. Ansonsten macht er einen Zufallszug, ohne dabei darauf zu achten, ob der ihn wirklich weiterbringt.

Das ist zwar nicht dumm gespielt, aber auch nicht hochintelligent. Gibt es denn auch eine Methode, mit der der Computer unschlagbar wird?

Ja, die gibt es. Aber dieses Buch reicht in seinem Umfang leider nicht aus, um sie im Detail zu erläutern und in ein Programm umzusetzen. Damit du aber einen Einblick bekommst, wie Profis eine »echte« künstliche Intelligenz programmieren würden, mit der das Programm dem Spieler gleichwertig oder überlegen wäre, will ich wenigstens kurz das Prinzip erklären.