Autor Beitrag
LINUS19
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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:
ausblenden volle Höhe 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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:
ausblenden Java
1:
int bestRow, bestCol;					

und dann entsprechend zuweisen sowie nach dem Aufruf der MinMax-Methode auswerten...

Für diesen Beitrag haben gedankt: LINUS19
LINUS19 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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:
ausblenden 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
ausblenden 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.
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: Do 01.03.18 16:45 
So müsste es stimmen :
ausblenden 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.
ausblenden Quelltext
1:
2:
3:
4:
if (tiefe == eingestellteTiefe) {
bestCol=i;
bestRow=j;            
}
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 491
Erhaltene Danke: 188

W7
Delphi 6 pro
BeitragVerfasst: 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
ausblenden volle Höhe 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=0or 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: Sa 03.03.18 09:55 
Du hattest deine Main-Methode doch schon richtig:
ausblenden 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:
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: So 04.03.18 10:26 
Dann zeige noch mal deine beiden Methoden.

Für diesen Beitrag haben gedankt: LINUS19
LINUS19 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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:

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: So 04.03.18 13:26 
Die Spielsituation
ausblenden Quelltext
1:
2:
3:
XOX
XXO
OX*

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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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.
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 3832
Erhaltene Danke: 781

Win7
C++, C# (VS 2015/17)
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 156
Erhaltene Danke: 1

Windows 10, 7
Java(Eclipse)
BeitragVerfasst: 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