monte carlo Algorithmus für 4 gewinnt

M3lem

Mitglied
Hallo zusammen

ich wollte den besten Zug für meinen Spiel implementieren und zwar mit Hilfe von monte carlo Algorithmus.
Erst mal stelle ich die "normalen Zug" Methode vor:
Java:
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(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;
   }
Als Parameter soll die Spaltennummer eingegeben werden und die Methode gibt die Position, wo der Stein heruntergefallen wurde.
Die Position hier ist irrelevant, ich brauche es nur für die Oberfläche.

Für den besten Zug sind folgende Methoden:
Code:
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 = random.nextInt(7)+1;
            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;
    }
int randomlyMove(Board b) macht einen zufälligen Spiel und gibt am Ende den Spiel an, der gewonnen hat.
int[] simulateMoves(Board b, int number) simuliert einen Spiel und gibt anhand der Spielsituation, wie viele Gewinne, Verluste und Unentschieden daraus kommt.
Z.b. für einen leeren Spielbrett gibt die Methode das aus.
Code:
jshell> b.simulateMoves(b,100)
$6 ==> int[3] { 46, 0, 54 }
evaluateMoves(Board b, int number) gibt anhand der Spielsituation an, wie viel Prozent man bei welcher Spalte gewinnen verloren oder unentschieden das Spiel ist.
Code:
jshell> b.evaluateMoves(b,100)
$7 ==> [[51, 1, 48], [46, 0, 54], [42, 0, 58], [36, 0, 64], [45, 1, 54], [50, 1, 49], [34, 1, 65]]
ich habe auch eine Methode, die die maximalen Zahl aus dieser Listen raussucht und das soll den besten Zug sein.
Mein Problem ist, dass der Algorithmus nicht richtig funktioniert. Der wählt als erstes immer die 7. Spalte oder die 1. Spalte.

Könnte mir jemand helfen?
 
Hallo M3lem,

leider hast du die Methode, die die maximale Zahl aus dieser Liste raussucht nicht gepostet, so dass es nicht möglich ist, auf Fehlersuche zu gehen.
Ich habe daher selbst was geschrieben. Ich denke, das hilft dir weiter.

Viele Grüße!

Java:
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Listfunction {
    
    public static void main(String[] args) {   
        List<List<Integer>> moves = new ArrayList<>();
        
        moves.add(IntStream.of(33, 1, 66).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(46, 0, 54).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(42, 0, 58).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(36, 0, 64).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(45, 1, 54).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(50, 1, 49).boxed().collect(Collectors.toList()));
        moves.add(IntStream.of(34, 1, 65).boxed().collect(Collectors.toList()));
        
        int max = 0;
        int indexOfMax = 0;
        
        for(int i = 0; i < moves.size(); i++) {
            if (moves.get(i).get(0) > max) {
                max = moves.get(i).get(0);
                indexOfMax = i;
            }
        }

        System.out.println("Bester Zug (Position in Liste): " + indexOfMax + ". Der Zug lautet: " + moves.get(indexOfMax));
    }
}
 

M3lem

Mitglied
Vielen Dank für deine Rückmeldung
Java:
int maxInList(List<Integer> values) {
        int max = values.get(0);
        for (int value : values) {
            if (max < value) {
                max = value;
            }
        }
        return max;
    }

    public int bestMovez(Board b) {
        List<List<Integer>> lists = evaluateMoves(b,100);
            List<Integer> result = lists.get(0);
            int max = maxInList(result);
            int index = 0;
            int counter = 0;
            for (int i = 1, n = lists.size(); i < n; i++) {
                    List<Integer> list = lists.get(i);
                    int listMax = maxInList(list);
                    if (max < listMax) {
                            result = list;
                            max = listMax;
                            counter++;
                    }
                            index = i+1;
            }
        if(counter == 0){
        index = 0;
            return index+1;
        }
            return index
        ;
    }
Die Methode liefert immer 7, obwohl den besten Zug hier die 4. Spalte sein muss.
Code:
jshell> b.bestMovez(b)
$9 ==> 7
Viele Grüße
 
Ich würde dein Beispiel sehr gerne nachvollziehen. Kannst du auch noch posten, wie die Klasse Board aussieht? Es ist sonst echt schwer, das nachzustellen. Weiterhin wäre hilfreich zu wissen, was als Kriterium für den besten Zug gilt.

Aus dem Ergebnis von evaluateMoves
[[51, 1, 48], [46, 0, 54], [42, 0, 58], [36, 0, 64], [45, 1, 54], [50, 1, 49], [34, 1, 65]] wüsste ich jedenfalls ohne Erläuterung nicht, warum du hier die 4. Spalte, also ich nehme an [45, 1, 54] als den besten Zug ansiehst. Bei dem Progrämmchen oben bin ich davon ausgegangen, dass die höchste erste Zahl (Gewinn in %) aus den 7 Spalten der beste Zug sein müsste.
 

M3lem

Mitglied
ja gerne ich kann die Klasse Board posten.
Abgesehen von meinem Programm sollte der Algorithmus den besten Zug (hier die 4. Spalte) raussuchen, aber mein Programm tut es nicht und da hakt bei mir aus.
Übrigens die Logik habe ich von Tic-Tac-Toe übernommen und da ist der Link zum Video
Hier ist die Klasse:
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 List getListMoves() {
        List<Integer> moveList = new ArrayList<>();
        for(int i = 1;i < grid.length;i++) {
            if (grid[i] == 0) {
                moveList.add(i);
            }
        }
        return moveList;
    }*/

    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(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 bestMove() {
        move(bestMovez(new Board()));
   }

   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 = random.nextInt(7)+1;
            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;
    }
    int maxInList(List<Integer> values) {
        int max = values.get(0);
        for (int value : values) {
            if (max < value) {
                max = value;
            }
        }
        return max;
    }

    public int bestMovez(Board b) {
        List<List<Integer>> lists = evaluateMoves(b,100);
            List<Integer> result = lists.get(0);
            int max = maxInList(result);
            int index = 0;
            int counter = 0;
            for (int i = 1, n = lists.size(); i < n; i++) {
                    List<Integer> list = lists.get(i);
                    int listMax = maxInList(list);
                    if (max < listMax) {
                            result = list;
                            max = listMax;
                            counter++;
                    }
                            index = i+1;
            }
        if(counter == 0){
        index = 0;
            return index+1;
        }
            return index
        ;
    }


    

    


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





}
 
Ich habe versucht, so wenig wie möglich in deiner Methode bestMovez zu ändern. Die Änderungen habe ich einkommentiert.
Damit sollte das gewünschte Ergebnis rauskommen. Ich habe mir das Video auch angesehen und kam zum Schluss, dass nur der dritte Wert (Gewonnen) betrachtet werden soll, nicht der höchste Wert der 3 Werte (Verloren, Unentschieden, Gewonnen).


Java:
    public int bestMovez(Board b) {
        List<List<Integer>> lists = evaluateMoves(b, 100);
        List<Integer> result = lists.get(0);
        int max = maxInList(result);
        
        int index = 0;
        int counter = 0;
        for (int i = 1, n = lists.size(); i < n; i++) {
            List<Integer> list = lists.get(i);
            int listMax = list.get(2);    // maxInList(list);
            System.out.println(max + " < " + listMax);
            if (max < listMax) {
                result = list;
                max = listMax;
                index = i;            // eingefügt
                counter++;
            }
            // index = i + 1;        // auskommentiert
        }
        if (counter == 0) {
            index = 0;
            return index + 1;
        }
        return index;
    }
 
So sollte es aber auch gehen (ist ein bisschen kürzer):
Java:
    public int bestMovez(Board b) {
        List<List<Integer>> lists = evaluateMoves(b, 100);
      
        int max = 0;
        int index = 0;
      
        for (int i = 1; i < lists.size(); i++) {
            List<Integer> list = lists.get(i);
            int listMax = list.get(2);    // maxInList(list);

            if (max < listMax) {
                max = listMax;
                index = i;
            }
        }

        return index;
    }
 
Zuletzt bearbeitet:

M3lem

Mitglied
Vielen herzlichen Dank
ich habe jetzt das Spiel in der Oberfläche gespielt und war besser als vorher aber der Computer spielt immer noch nicht perfekt.
Außerdem habe ich ein anderen Problem, wenn ich mehrere Züge mache, übernehme ich den Zug für den Computer und ich finde den Grund dafür nicht.
Im Bild habe ich angefangen und habe den roten Stein, nach 7 meiner Würfe ist der Computer dran aber hier tut er nichts, anstatt mache ich selber den Zug.
Screenshot 2022-08-05 202511.png
 
Ad hoc würde ich sagen, es fehlt noch der Teil zu sagen, welcher Spieler gerade dran ist.

Ich habe gerade wenig Zeit. Aber schau mal dein Video, bei dem das TicTacToe in Python programmiert wurde. Hier wird immer ein Wechsel vollzogen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
X Monte Carlo Simulation (integral) Java Basics - Anfänger-Themen 4
M Monte Carlo Methode zur Bestimmung von PI Java Basics - Anfänger-Themen 9
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
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
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
A double and add algorithmus für elliptische kurven/ integer binär darstellen Java Basics - Anfänger-Themen 14
H Algorithmus von Hierholzer Java Basics - Anfänger-Themen 3
Binary.Coder Welcher Datentyp für den Simplex Algorithmus Java Basics - Anfänger-Themen 3
N Huffman algorithmus Java Basics - Anfänger-Themen 35
JavaKaffee Minimax-Algorithmus Verständnis Java Basics - Anfänger-Themen 12
B Lee-Algorithmus Java Basics - Anfänger-Themen 2

Ähnliche Java Themen


Oben