Aufgaben

Künstliche Intelligenz für Reversi

Othello Brett
Othello (oft Reversi genannt) ist ein 2-Spieler Brettspiel, bei dem die Spieler abwechselnd weiße und schwarze Steine auf ein 8x8 Felder großes Brett legen. Falls du das Spiel nicht kennst, lies dir die Regeln auf Wikipedia durch. In heutigen Spielen kann man meistens auch gegen einen Computergegner, eine sogenannte „KI“ (Künstliche Intelligenz) spielen. Diese soll nun Schritt für Schritt erstellt und verbessert werden.
Computer und das menschliche Gehirn haben unterschiedliche Stärken. Beschreibe in 2-3 Sätzen, in welchen Bereichen Computer dem Menschen überlegen sind und in welchen das menschliche Gehirn noch Vorteile hat.
Computer sind vor allem sehr viel schneller im Berechnen als Menschen, weswegen sie bei rechenintensiven Aufgaben deutliche Vorteile haben. Außerdem können sie viel mehr Daten verarbeiten, was BigData-Anwendungen ermöglicht. Das menschliche Gehirn ist allerdings kreativer und kann Zusammenhänge besser verstehen, weswegen es zum Beispiel auch in der Sprache und Interpretation von Bildern besser ist.
Die KI soll nach dem sogenannten Minimax-Algorithmus aufgebaut werden. Dieser bewertet bis zu einer bestimmten Tiefe die Stellung nach allen möglichen Zügen und wählt bei eigenen Zügen den besten für sich (Maximum) und bei gegnerischen Zügen den besten für den Gegner (Minimum) aus. Unten siehst du ihn als Pseudocode. Markiere die Bestandteile der Rekursion und beschrifte sie mit den Fachbegriffen.
Minimax-Algorithmus

Die drei Bestandteile der Rekursion sind Abbruchbedingung, Rekursionsende und Rekursionsschritt.
In dem Minimax-Algorithmus sind die Bestandteile der Rekursion die folgenden Zeilen:
  • Abbruchbedingung: "maximale Tiefe erreicht oder keine Züge mehr möglich"
  • Rekursionsende: "Bewerte die übergebene Stellung und gib die Wertung zurück"
  • Rekursionsschritt: "minimax(neueStellung, gegnerFarbe, tiefe+1)"
Markierung Bestandteile Rekursion
Die KI benötigt eine Methode mit der sie die aktuelle Stellung bewerten kann. Je besser die Stellung für die KI ist, desto höher soll der berechnete Wert sein.
Lade dir auf Github die Projektvorlage "Othello-BlueJ-Projekt" herunter und implementiere die Methode stellungBewerten(int[][] spielfeld). Teste deine Methode mit 2 Stellungen.
Eine mögliche Lösung zählt die eigenen Steine mit +1 und die gegnerischen Steine mit -1.
Die Implementierung mit +1 für eigene Steine und -1 für gegnerische sieht folgendermaßen aus:
public double stellungBewerten(int[][] spielfeld) {
    int stand = 0;
    for(int i=0; i<8; i++) {
        for (int j=0; j<8; j++) {
            if(spielfeld[i][j] == 0) continue;
            if(spielfeld[i][j] == farbe) stand++;
            else stand--;
        }
    }
    return stand;
}
Natürlich kannst du auch eine ganz andere Bewertung verwenden. Falls du Probleme hast, deine Idee umzusetzen oder andere an deiner Lösung teilhaben lassen möchtest, schreibe doch einen Kommentar!
Was passiert, wenn man die ersten beiden Zeilen des minimax Algorithmus aus Teilaufgabe b) weglässt?
Das Programm hält nicht mehr an, bzw. genauer: Es entsteht ein StackoverflowError, weil das Rekursionsende fehlt und der Rekursionsschritt immer wieder durchgeführt wird, bis der Aufrufspeicher (Stack) von Java überläuft.
Vervollständige den Minimax-Algorithmus im Projekt. Die Klasse Spiel hat nützliche Funktionen, die du dabei verwenden kannst.
Die erste Lücke ist die Abbruchbedingung "maximale Tiefe erreicht". Als Code ist das
tiefe == rechenTiefe
Die nächsten 4 Lücken sind Teil einer Wiederholung mit fester Anzahl, um für alle einzelnen Arrayfelder den Code in der Wiederholung auszuführen. Daher muss i und j von 0 bis 7 zählen, also:
for (int i=0; i<7; i++) {
    for (int j=0; j<7; j++) {
Die nächste Zeile ist für die Bedingung, dass der Zug möglich ist. Dafür hat die Klasse Spiel die statische Methode zugMoeglich.
static boolean zugMoeglich(int[][] spielfeld, int farbe, int x, int y)
Also muss die Lücke lauten:
Spiel.zugMoeglich(spielfeld,aktuelleFarbe, i, j)
In der nächsten Lücke wird die Variable "neueBewertung" initialisiert. Dies ist der Rekursionsschritt. Als Code:
minimax(spielfeldNeu,naechsteFarbe, tiefe + 1);
Die letzten beiden Lücken sind Bedingungen, um das Maximum bzw. Minimum herauszufinden und den bisherigen Wert zu überschreiben. Für das Maximum ist die Bedingung bisherigerWert < neueBewertung, für das Minimum bisherigerWert > neueBewertung

Gesamter Code

public double minimax(int[][] spielfeld, int aktuelleFarbe, int tiefe) {
    if (tiefe == rechenTiefe || !spiel.zuegeMoeglich(spielfeld, aktuelleFarbe)) {
        return stellungBewerten(spielfeld);
    } else {
        Double bisherigerWert = null;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (Spiel.zugMoeglich(spielfeld,aktuelleFarbe, i, j)) {
                    int[][] spielfeldNeu = Spiel.zugSimulieren(spielfeld, aktuelleFarbe, i, j);
                    int naechsteFarbe = Spiel.getGegner(aktuelleFarbe);
                    double neueBewertung = minimax(spielfeldNeu,naechsteFarbe, tiefe + 1);
                    if (farbe == aktuelleFarbe) {
                        //Maximum auswählen
                        if (bisherigerWert == null || bisherigerWert < neueBewertung) {
                            bisherigerWert = neueBewertung;
                        }
                    } else {
                        //Minimum auswählen
                        if (bisherigerWert == null || bisherigerWert > neueBewertung) {
                            bisherigerWert = neueBewertung;
                        }
                    }
                }
            }
        }
        return bisherigerWert;
    }
}
Spiele eine Runde gegen deine KI auf verschiedenen Rechentiefen. Bei welcher Tiefe kannst du sie noch besiegen?
Hier gibt es keine "richtige" Lösung, Spieler mit einiger Erfahrung können die KI vermutlich auch auf höheren Stufen noch schlagen. Ich habe Rechentiefen 3,5,6 und 7 getestet und nur 3 und 5 geschlagen und gegen 6 und 7 verloren.
Schreibe doch einen Kommentar, bis zu welcher Stufe du es geschafft hast!
Wie viele Züge muss die KI für eine Rechentiefe von 6, 7 und 8 Spielzügen (also 3-4 Runden) berechnen, wenn es ungefähr 8 Möglichkeiten pro Spielzug gibt? Wie lang braucht ein Computer dafür, wenn er pro Sekunde 1 Million Züge prüfen kann?
Bei 6 Spielzügen mit je 8 Möglichkeiten müssen 86=262.1448^6 = 262.144 Züge überprüft werden. Dies dauert 262.1441.000.000s0,3s\dfrac{262.144}{1.000.000} s \approx 0,3 s
Bei 7 Spielzügen mit je 8 Möglichkeiten müssen 87=2.097.1528^7 = 2.097.152 Züge überprüft werden. Dies dauert 2.097.1521.000.000s2,1s\dfrac{2.097.152}{1.000.000}s \approx 2,1 s
Bei 8 Spielzügen mit je 8 Möglichkeiten müssen 88=16.777.2168^8 = 16.777.216 Züge überprüft werden. Dies dauert 16.777.2161.000.000s16,8s\dfrac{16.777.216}{1.000.000}s \approx 16,8 s
(optional) Im Moment zieht die KI in der gleichen Stellung jedes Mal den gleichen Zug. Baue einen Zufallsmechanismus ein, der das Verhalten ein wenig abwandelt.
Ein zufälliges Verhalten kann damit erreicht werden, dass bei gleich gut bewerteten Zügen mit 50%-iger Wahrscheinlichkeit trotzdem der Wert geändert wird.
Du musst die Bedingung für Minimum und Maximum abändern, zum Beispiel so:
if (bisherigerWert == null || bisherigerWert > neueBewertung
|| (bisherigerWert == neueBewertung && Math.random()>0.5)) {
    bisherigerWert = neueBewertung;
}
Natürlich gibt es auch andere Wege einen Zufall einzubauen. Schreibe doch einen Kommentar mit deiner Idee.
(optional) Informiere dich über Strategien bei Othello und versuche damit die Methode stellungBewerten() zu verbessern, indem du beispielsweise die Wichtigkeit von den unterschiedlichen Feldern gewichtest.
Eine Implementierung, die X- und C-Felder berücksichtigt und gewichtet sieht folgendermaßen aus:
public double stellungBewertenMitStrategie(int[][] spielfeld) {
    double stand = 0;
    for(int i=0; i<8; i++) {
        for (int j=0; j<8; j++) {
            if(spielfeld[i][j] == 0) continue;
            if(spielfeld[i][j] == farbe) {
                if((i==0 && j==0) || (i==0 && j==7) || (i==7 && j==0) || (i==7 && j==7)){
                    //Ecken sind sehr gut
                    stand = stand + 5;
                } else if((i==1 && j==1) || (i==1 && j==6) || (i==6 && j==1) || (i==6 && j==6)) {
                    //X-Felder sind schlecht
                    stand = stand - 1;
                } else if (i+j == 7 || i==j) {
                    //Die restliche Diagonale ist ein bisschen besser als normal
                    stand = stand + 1.5;
                } else if (i==0 || j==0 || i==7 || j==7) {
                    //C-Felder sind gut
                    stand = stand + 2;
                } else {
                    //Alle anderen sind normal
                    stand = stand + 1;
                }
            }
            else {
                //Das selbe nochmal für den Gegner, nur mit anderen Vorzeichen
                if((i==0 && j==0) || (i==0 && j==7) || (i==7 && j==0) || (i==7 && j==7)){
                    stand = stand - 5;
                } else if((i==1 && j==1) || (i==1 && j==6) || (i==6 && j==1) || (i==6 && j==6)) {
                    stand = stand + 1;
                } else if (i+j == 7 || i==j) {
                    stand = stand - 1.5;
                } else if (i==0 || j==0 || i==7 || j==7) {
                    stand = stand - 2;
                } else {
                    stand = stand - 1;
                }
            }
        }
    }
    return stand;
}
Kommentieren Kommentare