Entwickler-Ecke
Alle Sprachen - Alle Plattformen - Java Minimax Algoritmus
LINUS19 - Di 27.02.18 18:13
Titel: Java Minimax Algoritmus
Hallo,
ich wollte für Tictactoe einen Computergegner machen, der den Minimax Algorithmus verwendet. Dazu wollte ich den Pseudocode von Wikipedia übersetzen (
Minimax-Algorithmus [
https://de.wikipedia.org/wiki/Minimax-Algorithmus]). Bei Tictactoe kann ja der komplette Suchbaum durchlaufen werden und und am Ende werden die Blätter mit 1, -1 oder 0 bewertet.
Ich verstehe nicht wo dieses "gespeicherterZug=Zug" herkommt. Hier mein bisheriger Versuch:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39:
| static char[][] Feld = { { '*', '*', '*' }, // Spielfeld { '*', '*', '*' }, { '*', '*', '*' } }; char Spieler = 'X'; // Spieler und Computer Figuren char Computer ='O'; //
int eingestellteTiefe = 9; // Suchtiefe
int max(char Spieler, int tiefe) { // Spieler if (tiefe == 0)// Ende vom Suchbaum, Züge werden bewertet return bewerteZug(); // 1 bei gewinn, 0 bei remis, -1 bei Verlust
int maxWert = Integer.MIN_VALUE; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (Feld[i][j] == '*') { // Wenn Feld frei, Zug wird ausgeführt Feld[i][j] = Spieler; // Spieler macht Zug
int wert = min(Computer, tiefe - 1); // Zug wird bewertet Feld[i][j] = '*'; // Zug wird rückgängig gemacht
if (wert > maxWert) { maxWert = wert;
if (tiefe == eingestellteTiefe) { // gespeicherterZug = Zug; // wo soll der Zug "gespeichert" werden? } } } } } return maxWert; }
int min(char Computer, int tiefe) { // ist ja das selbe wie max() return minWert; } |
LG
LINUS19
Th69 - Di 27.02.18 19:37
In deinem Fall willst du ja Zeile und Spalte (
i und
j) speichern, d.h. du benötigst zwei (Member-)Variablen:
und dann entsprechend zuweisen sowie nach dem Aufruf der MinMax-Methode auswerten...
LINUS19 - Di 27.02.18 21:54
In Zeile 12 werden die Züge mit bewerteZug() doch schon bewertet. Jenachdem ob Gewinn , unentschieden oder Niederlage mit 1, 0 und -1. Deswegen verstehe ich noch nicht ganz ,wo für ich noch diese Variablen mit besterReihe und besterSpalte brauche.
Th69 - Mi 28.02.18 09:02
Die Zeile 12 ist ja nur der Rückgabewert des Aufrufs der rekursiven Methode in Zeile 21 (im Wechsel min() und max()).
Und gesucht ist ja der beste Zug insgesamt (d.h. der ersten Rekursionsebene).
M.E. ist aber die Abfrage in Zeile 11 (noch) nicht ganz richtig - es fehlt ja noch "oder keineZuegeMehr(spieler)". Oder rufst du diese Methode nach jedem gemachten Zug mit einer um 1 reduzierten Zugtiefe auf (d.h. veränderst du eingestellteTiefe)?
Auf jeden Fall solltest du aber (in Zeile 11) jedesmal auf einen Sieg eines Spielers überprüfen, damit dann der Algorithmus nicht weiterrechnet (sonst kann es ja evtl. zwei Sieger geben ;- ).
LINUS19 - Mi 28.02.18 19:23
Ich wollte jetzt erstmal eine Brettstellung vom Computer bewerten lassen(das einfach der entsprechnede Wert zurückgegeben wird), deswegen habe ich Spieler und Computer, bei min() und max() vertauscht. Und eine Methode boolean Gewinn() gemacht, die den Gewinn überprüft.
Meintest du das mit bestRow und bestCol so:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| if (tiefe == eingestellteTiefe) { bestCol=i; bestRow=j; } ...
public static void main(String[] args) { int bewertung =max(Computer,9); Feld[bestRow][bestCol]='X'; } |
Bei mir werden die dann immer auf 0 gesetzt. In Zeile 21 wird ja min() mit tiefe-1 aufgerufen und dann wird diese Bedingung
if(tiefe== eingestellteTiefe )// 9 doch nie erreicht, weswegen bestCol und bestRow immer 0 sind.
EDIT : Wenn ich jetzt
Quelltext
1: 2:
| int bewertung =max(Computer,9); System.out.println(bewertung); |
bei leerem Brett aufrufe wird 1 returnt , dabei müsste eigentlich 0 zurückgegeben werden.
Ich denke es liegt an der Gewinn Überprüfung. Dort wird immer true Returnt.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
|
static boolean Reihe() { for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { if(Feld[i][j]=='*' break; if(j==2) Return true; } } return false; } |
LINUS19 - Do 01.03.18 16:45
So müsste es stimmen :
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| public static boolean Reihe() { for(int i=0; i<3; i++) { int zähler=0; for(int j=0; j<3; j++) { if(Feld[i][j]=='O') zähler++; } if(zähler==3) return true; // 3 in einer Reihe } System.out.println(zzähler); return false; } |
Ist das den so richtig ?, die Bedingung wird doch eigentlich nie erreicht weswegen immer bestRow=0 und bestCol=0.
Quelltext
1: 2: 3: 4:
| if (tiefe == eingestellteTiefe) { bestCol=i; bestRow=j; } |
Th69 - Do 01.03.18 16:59
So überprüfst du nur die Reihen - es fehlen noch die Überprüfungen für Spalten sowie die beiden Diagonalen.
Außerdem solltest du den abzufragenden Spieler als Parameter angeben.
Doch, beim direkten Aufruf (aus deiner Main) ist ja die Bedingung erfüllt (nur für die weiteren rekursiven Aufrufe wird ja die Tiefe erniedrigt).
LINUS19 - Do 01.03.18 17:27
Ja, ich muss noch die anderen Überprüfungen machen.
Es müsste doch 9! verschiedene Spielbäume geben, wenn ich jetzt in der main max(Computer, 9)aufrufe und die Aufrufe der Methode zähle, kommt aber als Ergebnis 426457.
In der Main muss ich doch das Feld durchlaufen und dann max(Computer ,eingestellteTiefe-1) aufrufen.
Fiete - Fr 02.03.18 18:15
Moin LINUS19,
im Anhang befindet sich eine ausführliche Anleitung zur Strategieprogrammierung, als Beispiel
habe ich TicTacToe gewählt.
Das MiniMax-Verfahren sieht so aus
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38:
| Procedure TStrategie.MinmaxSuche(Var BestZug:TSpielZug;Var MinMax:Integer; B:TBewertung;N:Integer;F:TSpielFeld;Amzug:TSpieler); Var VirtuelleFeld:TSpielFeld; VirtuelleBewertung:TBewertung; Zug:TSpielZug; ZugListe:TSpielZugListe; M,I,Anzahl,Zeile,Spalte:Integer; AbZeile:String; Begin If (N=0) or Schluss(B) or Remis(B) Then MinMax:=Wert(B) Else Begin GenZugListe(F,Amzug,Anzahl,ZugListe); If Amzug=Computer Then Begin M:=MinInt;I:=0; While I<Anzahl Do Begin VirtuelleFeld:=F;VirtuelleBewertung:=B;Inc(I);Zug:=ZugListe[I]; MachZug(VirtuelleFeld,VirtuelleBewertung,Zug,Computer); MinmaxSuche(BestZug,MinMax,VirtuelleBewertung,N-1,VirtuelleFeld,Mensch); If M<MinMax Then M:=MinMax; End End Else Begin M:=MaxInt;I:=0; While I<Anzahl Do Begin VirtuelleFeld:=F;VirtuelleBewertung:=B;Inc(I);Zug:=ZugListe[I]; MachZug(VirtuelleFeld,VirtuelleBewertung,Zug,Mensch); MinmaxSuche(BestZug,MinMax,VirtuelleBewertung,N-1,VirtuelleFeld,Computer); If M>MinMax Then M:=MinMax End End; MinMax:=M End End; |
Viel Erfolg beim Studieren!
Gruß Fiete
LINUS19 - Fr 02.03.18 19:51
Danke für die Unterlagen.
Jetzt wird immer 2,2 als bester Anfangszug ausgegeben. Die max Methode muss ich doch in der Main für jedes freie Feld aufrufen und dann den besten Zug bestimmen.
Th69 - Sa 03.03.18 09:55
Du hattest deine Main-Methode doch schon richtig:
Java
1: 2: 3: 4:
| public static void main(String[] args) { int bewertung = max(Computer,9); Feld[bestRow][bestCol]='X'; } |
Die
max-Methode bestimmt doch schon den besten Zug für alle freien Felder...
Bei einem insgesamt leeren TicTacToe-Feld sollte eigentlich 0,0 herauskommen (wegen der Abfrage
(wert > maxWert)) und als Bewertung ebenfalls 0.
Laß mal den Spieler den ersten Zug machen und dann rufe den Algorithmus auf (dann sollte sich der Zug entsprechend ändern).
Du brauchst natürlich in der Main-Methode noch eine Schleife, in der der Spieler und der Computer abwechselnd die Züge ausführen.
Besser ist es auch, du benutzt den Minimax (Negamax)-Algorithmus - dann hast du nur eine Methode (so wie bei Fietes Delphi-Code) und mußt nicht die nötigen Unterschiede beachten.
Ich sehe gerade, daß du ja die Variablen
Spieler und
Computer falsch benutzt.
Bisher rufst du ja strikt
min(Computer, tiefe - 1) auf, d.h. du gehst von einem Spielerzug aus. Wenn du jedoch die Max-Methode für den Computer aufrufst, dann ist der Aufruf falsch (denn dann soll ja der Spieler übergeben werden).
Darum wird im Wiki-Code auch
-Spieler benutzt (d.h. aus 1 wird -1 und umgekehrt).
Wenn du bei 'X' und 'O' bleiben willst, dann schreibe dir eine Methode, welchen den Gegner zurückgibt und rufe es dann so auf:
Java
1:
| min(Gegner(spieler), tiefe - 1); // ändere die lokale Variable ab, damit du nicht mit den beiden Member-Variablen Spieler und Computer durcheinanderkommst |
(ebenso in der min-Methode)
LINUS19 - So 04.03.18 00:14
Ich habe jetzt in dem Feld ein Zug vom Spieler gemacht, egal wo ich das 'O' hinsetze, der Computer setzt es immer in die linke obere Ecke (ich rufe es dann mit max(8) auf). Nur wenn ich das 'O' in die linke obere Ecke setze, setzt der Computer ein Feld darunter, dann kann er aber die Zwickmühle nicht mehr abwehren.(also ein schlechter Zug vom Computer)
Bei max() und min() habe ich jetzt auch nur noch den Parameter tiefe, weil min () und max() ja schon für Spieler und Computer stehen und das ganze sonst noch verwirrender ist.
Th69 - So 04.03.18 10:26
Dann zeige noch mal deine beiden Methoden.
LINUS19 - So 04.03.18 13:02
Bei den Methoden min() und max() habe ich eigentlich nichts verändert, bis auf bei der min() Methode, dort habe jetzt noch
bestCol=i; bestRow=j;
(was ja nicht im Pseudocode stand, wenn das aber nicht dort steht und der Computer gegen sich selbst spielt wird nur ein Feld gefüllt)
eingefügt. Wenn ich dass dann so aufrufe:
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| public static void main(String[] args) int i=9; while(i>0) { // Computer spielt gegen sich selbst if(i%2==1 ) { max(i); Feld[bestCol][bestRow]='X'; } else { min(i); Feld[bestCol][bestRow]='O'; } i--; } min(1); // irgendwie funktionierts nur so, dass am Ende ein Unentschieden rauskommt Feld[bestCol][bestRow]='O'; // Wenn das weg ist, kommt als Ergebnis: XOX dann wäre ja Spieler 'O' am Zug und es wäre auch remis XXO OX* } |
kommt ein Unentschieden als Ergebnis :
XOX
XXO
OXO
Th69 - So 04.03.18 13:26
Die Spielsituation
kann ja nicht stimmen, denn dann wäre 'X' ja 5 mal an Zug gewesen und 'O' nur 3 mal.
Wie schon geschrieben, verwende besser den Minimax-Algorithmus, da du dann explizit den Spieler ('X' oder 'O') übergibst und du nicht zwei verschiedene Methoden aufrufen mußt.
LINUS19 - So 04.03.18 14:33
Du meintest den Negamax Algorithmus, oder?
Ich wollte das erstmal so zum laufen bekommen, auch wenn das andere übersichtlicher ist.
Hier ist noch einmal die max() Methode, ich konnte keinen Fehler mehr finden.
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
| public static int max(int tiefe) { if (tiefe == 0) { return bewerteZug(); } int maxWert = Integer.MIN_VALUE; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (Feld[i][j] == '*') { // Wenn Feld frei, Zug wird ausgeführt Feld[i][j] = Computer; // Computer macht Zug
int wert = min(tiefe - 1); // Zug wird bewertet Feld[i][j] ='*'; // Zug wird rückgängig gemacht
if (wert > maxWert) { maxWert = wert; if (tiefe == eingestellteTiefe) { bestCol=i; bestRow=j; } } } } } return maxWert; } |
Edit: Mir ist gerade aufgefallen dass ich die Diagonalen in der Bewertungsfunktion vergessen habe.
Edit:Habe die Diagonalen jetzt eingefügt und es funktioniert immer noch nicht
LINUS19 - Mo 05.03.18 21:16
Jetzt funktioniert es. Bei StackOverflow habe ich den Hinweis bekommen das bei den Aufrufen in der main() Methode was falsch war.
LG
LINUS19
LINUS19 - So 11.03.18 14:14
Ich hatte noch eine Frage zur Bewertungsfunktion und wollte deswegen keinen Extra Thread aufmachen.
Ich wollte für Vier gewinnt jetzt folgende Bewertungsfunktion machen: Für jeden der eigenen Steine schauen ob sie sich diagonal, horizontal, vertikal... noch zu einer Viererkette ausbauen lassen, wenn das der Fall ist gibt es jeweils einen Punkt. Wenn ein Spieler 4 in einer Reihe hat, wird jenachdem +unendlich, oder -unendlich zurückgeben.
Ergibt die Bewertungsfunktion so Sinn und ist sie so vielleicht auch relativ spielstark, oder hat noch jemand einen anderen Vorschlag für eine Bewertungsfunktion, weil ich im Internet nicht viel dazu gefunden habe.
LG
LINUS19
Th69 - So 11.03.18 15:28
Doch, bitte erzeuge ein neues Thema dafür!
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!