Aufgaben zur fortgeschrittenen Programmierung in Java

Künstliche Intelligenz für Reversi

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.
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
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.
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)"
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
Die drei Bestandteile der Rekursion sind Abbruchbedingung, Rekursionsende und Rekursionsschritt.
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.
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; }
(In Github anzeigen)
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!
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
Eine mögliche Lösung zählt die eigenen Steine mit +1 und die gegnerischen Steine mit -1.
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.
Hast du eine Frage oder Feedback?
Kommentiere hier 👇

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;
    }
}

(In Github anzeigen)

Hast du eine Frage oder Feedback?

Kommentiere hier 👇

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!
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
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 $8^6 = 262.144$ Züge überprüft werden. Dies dauert $\dfrac{262.144}{1.000.000} s \approx 0{,}3 s$
Bei 7 Spielzügen mit je 8 Möglichkeiten müssen $8^7 = 2.097.152$ Züge überprüft werden. Dies dauert $\dfrac{2.097.152}{1.000.000}s \approx 2{,}1 s$
Bei 8 Spielzügen mit je 8 Möglichkeiten müssen $8^8 = 16.777.216$ Züge überprüft werden. Dies dauert $\dfrac{16.777.216}{1.000.000}s \approx 16{,}8 s$
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
(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.
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; }
(In Github anzeigen)
Natürlich gibt es auch andere Wege einen Zufall einzubauen. Schreibe doch einen Kommentar mit deiner Idee.
Hast du eine Frage oder Feedback?
Kommentiere hier 👇
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.

(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;
}

(In Github anzeigen)

Hast du eine Frage oder Feedback?

Kommentiere hier 👇

Schreibe in dein Heft 2-3 Sachen, die du neu gelernt hast, oder bei denen du Schwierigkeiten hattest.