Autor |
Beitrag |
LINUS19
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Di 27.02.18 18:13
Hallo,
ich wollte für Tictactoe einen Computergegner machen, der den Minimax Algorithmus verwendet. Dazu wollte ich den Pseudocode von Wikipedia übersetzen ( 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:
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
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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:
Java
und dann entsprechend zuweisen sowie nach dem Aufruf der MinMax-Methode auswerten...
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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 ;- ).
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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; } |
|
|
Th69
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Do 01.03.18 09:56
Ja, deine Gewinnüberprüfung ist falsch, s. z.B. Algorithm for Determining Tic Tac Toe Game Over.
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: Do 01.03.18 16:45
|
|
Th69
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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).
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
      
Beiträge: 617
Erhaltene Danke: 364
W7
Delphi 6 pro
|
Verfasst: 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
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
Einloggen, um Attachments anzusehen!
_________________ Fietes Gesetz: use your brain (THINK)
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: 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)
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: So 04.03.18 10:26
Dann zeige noch mal deine beiden Methoden.
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: So 04.03.18 13:26
Die Spielsituation
Quelltext
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.
Für diesen Beitrag haben gedankt: LINUS19
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
|
|
Th69
      

Beiträge: 4795
Erhaltene Danke: 1059
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Di 06.03.18 09:51
Ich habe jetzt den Beitrag für dich als "erledigt" markiert.
Und bitte demnächst bei Crosspostings diese hier selber angeben: Java tictactoe problems with minmax algorithm
|
|
LINUS19 
      
Beiträge: 156
Erhaltene Danke: 1
Windows 10, 7
Java(Eclipse)
|
Verfasst: 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
|
|