Minimax-Algorithmus

M3lem

Mitglied
Hallo zusammen,
ich wollte den besten Zug für meinen Spiel implementieren und zwar mit Hilfe von Minimax-Algorithmus.
Um ein besseres Verständnis von meinem Problem zu empfinden, poste ich meinen ganzen Code.

Java:
import java.util.*;
public class Board implements VierGewinntGame {
   private int[] grid = {  2,2,2,2,2,2,2,2,2,
                           2,0,0,0,0,0,0,0,2,
                           2,0,0,0,0,0,0,0,2,
                           2,0,0,0,0,0,0,0,2,
                           2,0,0,0,0,0,0,0,2,
                           2,0,0,0,0,0,0,0,2,
                           2,0,0,0,0,0,0,0,2,
                           2,2,2,2,2,2,2,2,2
   }; // Nullen sind die sichbaren Felder

   private int idx;
   private int[] memory = {55,56,57,58,59,60,61};
   private final int[] direction = {9,1,10,8};
   public int counter = 0;
   private int currentPlayer = 1;
   private int pos;

   private List<Integer> moves = new ArrayList<>();

   public Board() {

   }

    public Board(Board different) {
        this.grid = different.grid; //copy constructor
        this.idx = different.idx;
        this.memory = different.memory;
        this.counter = different.counter;
        this.currentPlayer = different.currentPlayer;
        this.pos = different.pos;
        this.moves = different.moves;
    }
    public int[] getGrid() {
        return grid;
    }
public int move(int columnNumber) {

       assert columnNumber >= 1 && columnNumber <= 7;
       assert fourInArow() == 0: "GAME OVER! Player "+-currentPlayer+" is won";
       //assert counter < 42 : "grid is full, DRWA!";
       pos = columnNumber;
       if(fourInArow() == 0) {
           if (memory[columnNumber - 1] >= 10) {
               grid[memory[columnNumber - 1]] = currentPlayer;
               idx = memory[columnNumber - 1];
               moves.add(idx);
               memory[columnNumber - 1] -= 9;
               currentPlayer = -currentPlayer;
               counter++;
           }
       }
       return idx;
   }
public void undoMove(){
       assert moves.size() != 0;
       grid[idx] = 0;
       memory[pos - 1] += 9;
       moves.remove(moves.size() - 1);
       currentPlayer = -currentPlayer;

   }
    public int fourInArow() {
       if(counter >= 4 && grid[idx] != 0){

           for(int d : direction){
               int s = 1;
               int i = idx + d;
               while (grid[i] == -currentPlayer){
                   s += 1;
                   i += d;
               }
               i = idx - d;
               while (grid[i] == -currentPlayer){
                   s += 1;
                   i -= d;
               }
               if(s >= 4) return -currentPlayer;
           }
       }
       return 0;
    }
    List<Integer> generatePossibleMoves(){
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 7; i++){
            if(grid[i+9] != 0) continue;
            list.add(i);
        }
        return list;

    }
    int randomlyMove(Board b){
        int value = b.fourInArow();
        while (value == 0){
            List<Integer> moves = b.generatePossibleMoves();
            if(moves.size() == 0) return 0;
            Random random = new Random();
            int randomMove = moves.get(random.nextInt(moves.size()));
            b.move(randomMove);
            value = b.fourInArow();
        }
        return value;
    }
int[] simulateMoves(Board b, int number) {
        assert number >= 1;
        int[] count = {0,0,0}; // Verluste, unntschieden, Gewinnne
        while (number > 0){
            Board a = new Board();
            b = new Board(a);
            count[randomlyMove(a) + 1] += 1;
            number -= 1;
        }
        return count;
    }
    List<List<Integer>>  evaluateMoves(Board b, int number) {
        assert number >= 1;
        List<Integer> moves = b.generatePossibleMoves();
        List<List<Integer>> values = new ArrayList<>();
        for(int move : moves) {
            b.move(move);
            values.add(Arrays.stream(simulateMoves(b,number)).boxed().toList());
            b.undoMove();
        }
        return values;
    }
    public String toString() {
        String s = "";
        for(int i = 0; i < grid.length; i++) {
            if (i % 9 == 8) {
                s += "\n\n";
            }
            if (grid[i] == 0) {
                s += "| " + "_" + " |  ";
            }
            else if(grid[i] == 1) {
                s += "| " + "X" + " |  ";
            }
            else if(grid[i] == -1) {
                s += "| " + "O" + " |  ";
            }

        }

        return s;
    }
}

Der Algorithmus, den ich implementiert habe, gibt eine Fehlermeldung zurück.

Code:
int max(Board b, int currentPlayer, int depth) {
        if(depth == 0 || b.fourInArow() != 0) {
            return evaluation(b);
        }
        int maxValue = -10;
        for (int i : generatePossibleMoves()){
            b.move(i);
        }
        while (b.fourInArow() == 0) {
            b.move(pos);
            int value = min(b,-currentPlayer,depth - 1);
            b.undoMove();
            if(value > maxValue) {
                maxValue = value;
                if(depth == desiredDepth){
                     savedMove = move(pos);
                }
            }
        }
        return maxValue;
    }
    int min(Board b, int currentPlayer, int depth) {
        if(depth == 0 || b.fourInArow() != 0) {
            return evaluation(b);
        }
        int maxValue = 10;
        for (int i : generatePossibleMoves()){
            b.move(i);
        }
        while (b.fourInArow() == 0) {
            b.move(pos);
            int value = max(b,-currentPlayer,depth - 1);
            b.undoMove();
            if(value > maxValue) {
                maxValue = value;
                if(depth == desiredDepth){
                    savedMove = move(pos);
                }
            }
        }
        return maxValue;
    }
 

Jw456

Top Contributor
Eigentlich hat mich die Fehlermeldung Interessiert.

Deine beiden Methoden rufen sich ja gegenseitig auf. Da wird es wohl zu einem Überlauf kommen kommen.
 

Jw456

Top Contributor
Zb hier holst du immer wider eine neue Liste. Erstellt immer wider eine neu Liste .
Kann nicht sinnvoll sein. Habe deinen Code nicht logisch durchdacht was du eigentlich machen willst.

Java:
List<Integer> generatePossibleMoves(){
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 7; i++){
            if(grid[i+9] != 0) continue;
            list.add(i);
        }
        return list;

    }

//die Liste ist der schleife zu verändern ist nicht gut.
for (int i : generatePossibleMoves()){
            b.move(i);
        }
 

Jw456

Top Contributor
Java:
List<Integer> suchListe = generatePossibleMoves();
for (int i : suchListe ){
            b.move(i);
        }

// macht sicherlich mehr sinn.
 

M3lem

Mitglied
Jetzt noch mal bitte die gesamte Fehlermeldung Posten. Die du bekommst.
Java:
int desiredDepth = 4;
    int evaluation(Board b) {
        return max(b,1,desiredDepth);
    }


jshell> Board b = new Board()
b ==>

| _ |  | _ |  | _ |  | _ |  | _ |  | _ |  | _ | ...  | _ |  | _ |  | _ |




jshell> b.evaluation(b)
|  Exception java.lang.AssertionError: GAME OVER! Player 1 is won
|        at Board.move (#2:57)
|        at Board.min (#2:221)
|        at Board.max (#2:204)
|        at Board.min (#2:225)
|        at Board.max (#2:204)
|        at Board.evaluation (#2:191)
|        at (#5:1)
 
Zuletzt bearbeitet:

yfons123

Top Contributor
in der Chat box gibt es das </> symbol damit kannst du code posten und formatieren

ist viel besser als bilderr da man selber ausprobieren kann und zeilen einfach als antwort kopieren kann

auch bei fehlermeldungen
 

M3lem

Mitglied
Zb hier holst du immer wider eine neue Liste. Erstellt immer wider eine neu Liste .
Kann nicht sinnvoll sein. Habe deinen Code nicht logisch durchdacht was du eigentlich machen willst.

Java:
List<Integer> generatePossibleMoves(){
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= 7; i++){
            if(grid[i+9] != 0) continue;
            list.add(i);
        }
        return list;

    }

//die Liste ist der schleife zu verändern ist nicht gut.
for (int i : generatePossibleMoves()){
            b.move(i);
        }
Die Methode generiert mögliche Züge, die dann bei evaluateMoves genutzt werden, um die Spielsituation zu bewerten
 

Jw456

Top Contributor
int desiredDepth = 4; int evaluation(Board b) { return max(b,1,desiredDepth); }
Erstmal ist der Code nicht in deinem ersten Post #1 enthalten.
Du versuchst dich ja selber zurück zugeben.
Wenn diese Bedingung erfüllt ist
Java:
int max(Board b, int currentPlayer, int depth) { if(depth == 0 || b.fourInArow() != 0) { return evaluation(b); }

Gibst du dich selber zurück.
 

M3lem

Mitglied
Erstmal ist der Code nicht in deinem ersten Post #1 enthalten.
Du versuchst dich ja selber zurück zugeben.
Wenn diese Bedingung erfüllt ist
Java:
int max(Board b, int currentPlayer, int depth) { if(depth == 0 || b.fourInArow() != 0) { return evaluation(b); }

Gibst du dich selber zurück.
Ich habe einfach die Stellen weggenommen, mit denen der Code nicht funktioniert.
was wäre dann richtig in dieser Stelle?
 

Jw456

Top Contributor
Exception java.lang.AssertionError: GAME OVER! Player 1 is won
Hast du dir mal angesehen wann oder warum diese Fehlermeldung kommt?
Kennst du den Befehl „assert“ ?

Die Meldung kommt wenn der Ausdruck die Bedingung „assert fourInArow() == 0 “ nicht true ist.
Also deine Methode „fourInArrow()“ gibt ungleich null zurück.
Wieso das so ist liegt in deiner Hand das zuprüfen.

 
Zuletzt bearbeitet:

M3lem

Mitglied
Hast du dir mal angesehen wann oder warum diese Fehlermeldung kommt?
Kennst du den Befehl „assert“ ?

Die Meldung kommt wenn der Ausdruck die Bedingung „assert fourInArow() == 0 “ nicht true ist.
Also deine Methode „fourInArrow()“ gibt ungleich null zurück.
Wieso das so ist liegt in deiner Hand das zuprüfen.

ich habe die assert Anweisung deswegen genutzt, weil von der Hochschule gewisse Voraussetzung gefordert werden und eine davon ist assert Anweisung zu nutzen und das Programm soll auf die Konsole laufen. ich kann das Programm auch ohne assert laufen lassen
 

M3lem

Mitglied
Und wo ist jetzt dein Problem?

Du hast von einer Fehlermeldung gesprochen.
ich bekomme ohne assert java.lang.StackOverflowError
Java:
jshell> b.evaluation(b)
|  Exception java.lang.StackOverflowError
|        at Board.max (#2:195)
|        at Board.evaluation (#2:191)
|        at Board.max (#2:196)
|        at Board.evaluation (#2:191)
|        at Board.max (#2:196)
|        at Board.evaluation (#2:191)
 

KonradN

Top Contributor
Also das bedeutet doch dann schlicht, dass Du eine Rekursion hast, bei der die Abbruchbedingungen nicht stimmen. Das musst Du also überprüfen. Spiel dazu den Algorithmus selbst durch. Schau was passiert in Deinem Code! Hast Du verstanden, was der Algorithmus machen soll? (Das ist eine absolute Vorbedingung, um einen funktionierenden Code schreiben zu können!) Der Min-MaX Algorithmus wird ja im Netz an vielen Stellen gut beschrieben, z.B. in einem Video unter
(Habe ich mir jetzt nicht im Detail angesehen.)

Dann noch eine kleine Anmerkung zu Assertions / Deiner Nutzung von eben diesen:
Und Deine Verwendung von assert zeugt doch etwas von einem Unverständnis, was das überhaupt ist. Das macht so teilweise keinen Sinn in Deinem Code. Im Netz findet sich dazu prinzipiell einiges - da kannst Du z.B. https://dbs.cs.uni-duesseldorf.de/lehre/docs/java/javabuch/html/k100044.html ansehen.

Nur kurz zur Erläuterung, was mir da direkt ins Auge gefallen ist:
Java:
       assert fourInArow() == 0: "GAME OVER! Player "+-currentPlayer+" is won";
       // ...
       if(fourInArow() == 0) {

Die assert Anweisung verhindert eine weitere Ausführung, wenn fourInArow() != 0 ist.
Und das ist eine Validitätsprüfung! Wenn ich da die Meldung anschaue, dann ist das für Dich aber scheinbar eine Ablaufsteuerung mit Notifikation, dass ein Spieler gewonnen hat.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
JavaKaffee Minimax-Algorithmus Verständnis Java Basics - Anfänger-Themen 12
T Veränderung eines MiniMax- Algorithmus zur Alpha-Beta-Suche Java Basics - Anfänger-Themen 3
A MiniMax- Algorithmus für 4-Gewinnt Java Basics - Anfänger-Themen 3
I Facharbeit: Tic Tac Toe mit Minimax Java Basics - Anfänger-Themen 1
H MiniMax Alogrithmus Java Basics - Anfänger-Themen 15
D minimax algprithmus Java Basics - Anfänger-Themen 5
mervanpolat Binary Search Algorithmus ausführen Java Basics - Anfänger-Themen 1
J Rekursiver Algorithmus Java Basics - Anfänger-Themen 9
M monte carlo Algorithmus für 4 gewinnt Java Basics - Anfänger-Themen 12
izoards Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten Java Basics - Anfänger-Themen 33
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
rosima26 Merge-Algorithmus Java Basics - Anfänger-Themen 53
C Ein Algorithmus soll schneller werden Java Basics - Anfänger-Themen 24
D Dijkstra Algorithmus Hilfe!! Java Basics - Anfänger-Themen 9
U Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus) Java Basics - Anfänger-Themen 14
s_1895 Pseudocode Naiver Algorithmus Java Basics - Anfänger-Themen 17
H String verschlüsseln - eigener Algorithmus Java Basics - Anfänger-Themen 104
T Algorithmus für Index mit min-Wert Java Basics - Anfänger-Themen 2
Düsseldorf2002 Testen meines Algorithmus Java Basics - Anfänger-Themen 1
D Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Algorithmus java searchAll IKey Java Basics - Anfänger-Themen 4
S Algorithmus Datensätze einfügen wenn... Java Basics - Anfänger-Themen 26
KogoroMori21 MergeSort Algorithmus Java Basics - Anfänger-Themen 2
KogoroMori21 Textdatei einlesen im Array (Selection Sort Algorithmus) Java Basics - Anfänger-Themen 3
fendix Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen Java Basics - Anfänger-Themen 7
S Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen Java Basics - Anfänger-Themen 4
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
D Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema Java Basics - Anfänger-Themen 1
N Selection Algorithmus: Methode wird nicht erkannt (BlueJ) Java Basics - Anfänger-Themen 3
U Meinung zum Dijkstra Algorithmus Java Basics - Anfänger-Themen 6
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
L Math.exp also eigenen Algorithmus Java Basics - Anfänger-Themen 2
Kirby.exe Algorithmus entwickeln Java Basics - Anfänger-Themen 37
M Algorithmus Max-Heap? Java Basics - Anfänger-Themen 3
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
CptK Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
A Algorithmus effizienter machen Java Basics - Anfänger-Themen 1
V Algorithmus zur fortlaufenden Berechnung des duechscjnt Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Labyrinth Algorithmus Java Basics - Anfänger-Themen 3
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
D Algorithmus in Pseudocode mit log2(n) Operationen erstellen Java Basics - Anfänger-Themen 3
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
H aufgabe java luhn algorithmus Java Basics - Anfänger-Themen 10
A Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten Java Basics - Anfänger-Themen 1
J Algorithmus für eine Reihe implementieren Java Basics - Anfänger-Themen 2
S Dijkstra Algorithmus funktioniert nicht Java Basics - Anfänger-Themen 4
N Denksportaufgabe durch Algorithmus lösen Java Basics - Anfänger-Themen 2
S Problem mit einem rekursivem FloodFill Algorithmus Java Basics - Anfänger-Themen 62
B Algorithmus Square und Multiply Java Basics - Anfänger-Themen 3
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D Frage Boyer-Moore Algorithmus Java Basics - Anfänger-Themen 7
M Komplexität Algorithmus Java Basics - Anfänger-Themen 8
H Zeichen im algorithmus Java Basics - Anfänger-Themen 4
B Code Verständnisfragen - FLoyd Warshall Algorithmus Java Basics - Anfänger-Themen 1
B Algorithmus zum entmischen einer Zahlenfolge Java Basics - Anfänger-Themen 15
T Algorithmus zur Überprüfung eines binären Suchbaums Java Basics - Anfänger-Themen 2
K Best Practice Algorithmus für Berechnung von Zahlenreihenfolge Java Basics - Anfänger-Themen 12
M Simpler Algorithmus läuft extrem langsam. Java Basics - Anfänger-Themen 3
K Erste Schritte Brute Force Algorithmus Java Basics - Anfänger-Themen 2
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
B gibt es ein Stundenplan-Algorithmus? Java Basics - Anfänger-Themen 11
O Algorithmus-Problem Java Basics - Anfänger-Themen 5
P Euklidischer Algorithmus Java Basics - Anfänger-Themen 9
L Greates Commong Dividend - euklidischer Algorithmus, modulos not positive Java Basics - Anfänger-Themen 5
J Euklidischer Algorithmus Java Basics - Anfänger-Themen 1
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
S GraphNode --- Dijkstra Algorithmus : NullPointerException Java Basics - Anfänger-Themen 1
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
V Algorithmus in einer Methode ausführen Java Basics - Anfänger-Themen 3
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
M Dijkstras Algorithmus Java Basics - Anfänger-Themen 5
S Zusammenhang Datenstruktur/Algorithmus Java Basics - Anfänger-Themen 1
M Simulation - Algorithmus Java Basics - Anfänger-Themen 3
F Erste Schritte Hilfe beim Algorithmus finden Java Basics - Anfänger-Themen 8
D Algorithmus für Punkte auf einem Kreis Java Basics - Anfänger-Themen 0
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
B Doppelte Werte aus Array entfernen ohne Import - Algorithmus Java Basics - Anfänger-Themen 5
C Ideen für einen Algorithmus Java Basics - Anfänger-Themen 1
F Best Practice Algorithmus optimieren - Binaeruhr Java Basics - Anfänger-Themen 2
S Euklid Algorithmus zur Berechnung des GGTs Java Basics - Anfänger-Themen 2
L Welcher Algorithmus ist das ? Java Basics - Anfänger-Themen 9
J Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig? Java Basics - Anfänger-Themen 2
O Java Zufalls-Verteil-Algorithmus Java Basics - Anfänger-Themen 3
P ganz simpler algorithmus Java Basics - Anfänger-Themen 3
C Sortieren ohne Algorithmus Java Basics - Anfänger-Themen 8
J Algorithmus: Grad von floating zu Grad/Minute/Sekunde Java Basics - Anfänger-Themen 3
A Text Verschriebung/Algorithmus(?) Java Basics - Anfänger-Themen 8
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
E Algorithmus für kart. Produkt: als int [] Feld repräsentiert Java Basics - Anfänger-Themen 10
U Peterson Algorithmus Java Basics - Anfänger-Themen 13
algebraiker Collections Bräuchte Hilfe bei dem Algorithmus - LinkedHashMap Java Basics - Anfänger-Themen 2
S A* Path Algorithmus in Java schon vorhanden Java Basics - Anfänger-Themen 3
S Bubble Sort Algorithmus Java Basics - Anfänger-Themen 3
N Unerklärlich: Rekursiver Algorithmus gibt falschen Datentyp zurück... Java Basics - Anfänger-Themen 4
S Algorithmus (Programmablaufplan) Java Basics - Anfänger-Themen 11
S Algorithmus für Spielbaum Java Basics - Anfänger-Themen 5

Ähnliche Java Themen

Neue Themen


Oben