Methoden Mögliche Spielstände bei TicTacToe

[shiroX]

Hallo,

ich hänge momentan an einer Aufgabe an der Uni. Wir sollen beim Spiel TicTacToe (dürfte ja bekannt sein) einen Code schreiben der die Anzahl aller möglichen gültigen Spielenden (nicht Spielzüge) ausgibt.
Ich habe jetzt also ein 2-Dimensionales Array erstellt und mein Gedanke ist einfach darum herum quasi noch ein Feld zu bauen, ab wo es ungültig wird, also quasi ein[5][5] Array (das Spielfeld ist ja an sich nur 3x3 groß), wobei ich dann dem Kreuz den int-Wert 1 gebe, dem Kreis -1 und den ungültigen Feldern die Zahl 100.
Dort würde das ganze dann abbrechen, da dies ja schonmal kein gültiger Zug wäre.

Sähe dann so aus:

static int zugberechnung(int a[][]){
     int spielstaende = 0;
     int kreuz = 1;
     int kreis = -1;
     int ungueltig = 100;
   
       for(int i=0; i<5; i++){
         a[i][0][I] = ungueltig;
         a[I][i][0] = ungueltig;
         a[i][4][I] = ungueltig;
         a[i][I][4] = ungueltig;
       }

Allerdings fehlt mir jetzt ein bisschen der Ansatz wie ich weiter vorgehen soll. In der Aufgabe steht "..., indem Sie systematisch alle erreichbaren Spielsituationen durchgehen und zählen".

Da ich aber schon alleine am Anfang ja eine Wahl von 9 Feldern habe auf die ich mein Zeichen setzen kann, müsste ich ja 9 for-Schleifen machen die dann alle möglichen Züge simulieren und zudem noch prüfen, ob ein Spieler schon 3 in einer Reihe hat - also quasi wähle ich jedes der 9 Felder einmal als Start aus.

Aber vielleicht habt ihr ja ein paar bessere Ansätze, vermutlich denke ich nur zu kompliziert.

 

[CSHW89]

Den ungültigen Rand brauchst du meiner Meinung nicht. Mit ungültig meint die Aufgabe eher, dass ein Spielende nicht entstehen kann, z.b.:
x x x
o o o
x o x
... kann nicht passieren, da x oder o bereits gewonnen hat, bevor der andere 3 in eine Reihe bringen kann.

Ich denke, ich würde es mit Backtracking machen. Wenn dir der Name nichts sagt, schaue mal bei Wiki nach. Du schreibst eine Methode, die eine for-Schleife von 1-9 laufen lässt, wenn das Feld noch nicht belegt ist, setze dort den aktuellen Spieler und rufe die Methode in der for-Schleife selbst auf mit dem anderen Spieler als aktuellen. Bei jedem Setzen eines Feldes, schaust du, ob die Spielsituation bereits gewonnen ist.

lg Kevin

PS: du musst dann bei jedem Spielende noch prüfen, ob dieses bereits durch eine andere Zugfolge erreicht wurde.

Eine andere Möglichkeit wäre es, jede Spielsituation 3^9 (jedes der 9 Felder x, o oder nicht belegt) zu generieren, und zu prüfen, ob es ein gültiges Spielende ist. Der einfachheithalber gehen wir davon aus, dass x immer startet. Ein gültiges Spielende ist dann, wenn eine dreier o Reihe vorhanden ist und die Anzahl der 'o' gleich die Anzahl der 'x' ist, oder wenn eine dreier x Reihe vorhanden ist und die Anzahl der 'x' eins höher ist als die Anzahl der 'o'. Und dann müsste man noch gucken, dass es keine zweite oder dritte dreier Reihe vorhanden ist, es sei denn, zwei dreier Reihen haben ein gemeinsames Feld.
Dies wäre ungültig:
x x x
o o o
x o x
Das hier wäre aber gültig, da das Feld oben links als letztes gewählt werden könnte:
x x x
x o o
x o o

 

[CSHW89]

Übrigens zur Kontrolle für dich: ich hab mit beiden Methoden 958 raus.

 

[shiroX]

Hallo, danke erstmal für deine Vorschläge, ich versuche sie gerade umzusetzen. Die Idee mit der for-Schleife ist mir auch schon gekommen, aber die würde mir doch das Array vergrößern oder? Die Felder sind ja (0,0)(0,1) ... usw bis (3,3), ich hatte eher dran gedacht zwei for-Schleifen zu machen die eben das Array abgehen, vielleicht kannst du mir ja mal mit deinem Code zeigen was du damit meinst zumindest

 

[CSHW89]

Geht genauso:

for(int y = 0; y < 3; ++y) {
  for(int x = 0; x < 3; ++x) {
    ...
  }
}

... oder ...

for(int f = 0; f < 9; ++f) {
  int x = f/3;   // 0-2
  int y = f%3;   // 0-2
  ...
}

PS: Ich meinte übrigend 0-8, statt 1-9. Aber wie gesagt, Doppel-Schleife geht auch

 

[shiroX]

Geht genauso:

for(int y = 0; y < 3; ++y) {
  for(int x = 0; x < 3; ++x) {
    ...
  }
}

... oder ...

for(int f = 0; f < 9; ++f) {
  int x = f/3;   // 0-2
  int y = f%3;   // 0-2
  ...
}

Ja genau, das war auch mein Ansatz, dann habe ich 2 Spieler die abwechselnd dran sind, einer davon setzt ein Kreuz und einer davon einen Kreis, also ich habe insgesamt 4 for-Schleifen wo jeweils geprüft wird, ob das Feld entweder "leer" (also Inhalt 0) oder eins der beiden Symbole hat. Ist es leer kann der Spieler setzen, ist schon was drin geht die for-Schleife weiter. Jetzt frage ich mich nur wie ich damit alle möglichen Enden simulieren kann, da der Algorithmus ja eigentlich immer den gleichen Weg geht.

 

[CSHW89]

Mit 4 for-Schleifen hast du nur 2 Züge, es können aber maximal 9 Züge stattfinden. Deshalb bräuchtest du 9x2 Schleifen. In der ersten Doppel-Schleife setzt der erste Spieler sein Symbol. In den inneren Schleifen finden die weiteren Züge statt. Wenn alle inneren Schleifen durchgelaufen sind, setzt du den ersten Zug wieder zurück (setze das Feld wieder auf "leer"). Das machst du jetzt in jeder der 9 Doppel-Schleifen.

Einfacher wäre es allerdings mit einer Rekursion. In dem du eine einzige Doppel-Schleife schreibst, und drinnen die eigene Methode wieder aufrufst.

 

[shiroX]

Ja daran habe ich gedacht, deswegen habe ich auch die beiden for-Schleifen in while-Schleifen mit einer boolean-Abfrage gesetzt. Also quasi player1 und player2 sind jeweils boolean-Werte, die am Ende eines Zuges vertauscht werden, also wenn player1 true ist setzt er sein Symbol und wird dann am Zugende auf false gesetzt, dann ist Spieler 2 dran usw. Als letztes müsste ich ja quasi nur noch die gültigen Spielenden (also wenn jemand gewinnt) zählen, wofür ich dann eine extra Methode mit for-Schleifen schreiben würde, die dann auf 3 gleiche Symbole in einer Reihe prüfen.

 

[shiroX]

Vielleicht könntest du mir ja mal deine Lösung zeigen, mein Code geht schon an die 70 Zeilen ich glaube ich denke zu kompliziert Wäre echt super

 

[CSHW89]

Das wird so nicht funktionieren, da wie du schon selber sagst, wird nur eine einzige Zugfolge berechnet. Zeig doch einfach mal dein Code, dann kann man besser helfen, als einfach nur die Lösung zu präsentieren.

 

[Blender3D]

Also Ihr geht das Thema zu kompliziert an.
x0x
0x0
x0x
So sieht ein mögliches Ergebnis in Tic Tac Toe aus.
xxx
000
xxx
Dieses ist falsch, weil die Spieler abwechselnd ihre Zeichen setzen. Daraus folgt. Die Anzahl der richtigen Ergebnisse, ist einfach zu berechnen.
Tauscht man bei obigem gültigem Ergebnis die Zeichen mit Nullen und Einsen und nimmt die Zeilenumbrüche weg sieht es so aus: 101010101
Es handelt sich um eine Binäre Zahl mit 9 Stellen. Also 2^9 = 512 möglichen Kombinationen. Gültige Ergebnisse haben aber entweder genau 4 Einser und 5 Nullen oder umgekehrt. Es gilt also alle möglichen Kombinationen einer Binären Zahl mit 9 Stellen, bei der genau 4 Einser vorkommen zu ermitteln und das Ergebnis mit 2 zu muliplizieren.
Mathematisch entspricht das dem Binomialkoeffizient von (9 über 4 ) x 2 = 126 x 2 = 256
Der Java Code dafür:

    public static int binom(int n, int k) {
        if (k == 1)
            return n;
        else if (n >= k && k == 0)
            return 1;
        else
            return (n * binom(n - 1, k - 1) / k);
    }

 

[CSHW89]

Da vergisst du aber die Situationen, in denen man vor 9 Zügen gewonnen hat. Wie gesagt, ich bin mir eigentlich ziemlich sicher, dass die Antwort 958 ist.

 

[Dukel]

Eine Frage ist auch, ob alle Züge gezählt werden sollen oder ob die, die gleich sind, wenn man das Spielfeld dreht nicht gezählt werden.
Am Anfang gibt es nur drei Möglichkeiten, Mitte, Rand-Mitte oder Ecke.

 

[shiroX]

Das wird so nicht funktionieren, da wie du schon selber sagst, wird nur eine einzige Zugfolge berechnet. Zeig doch einfach mal dein Code, dann kann man besser helfen, als einfach nur die Lösung zu präsentieren.

Also mein Ansatz ist erstmal der, dass ich mit einem bestimmten Zugmuster anfange, also z.B. an Feld [0][0] ein X und dann halt so weiter:

public static int zugberechnung(int a[][]){
        int kreuz = 1;
        int kreis = -1;
        boolean spieler1 = true;
        boolean spieler2 = false;
           
        while (spieler1){
            for(int i=0; i<3; ++i){
                for(int j=0; j<3; ++j){
                    if(a[i][j] == 0 && a[i][j] != kreis){
                    a[i][j] = kreuz;
                    spieler1 = false;
                    spieler2 = true;
               
                    }
                }
            }
        }

Das gleiche dann halt nochmal für Spieler 2. Am Ende prüfe ich alle möglichen Gewinnsituationen um das Spiel zu beenden, das wäre das hier:

for(int i=0; i<3; i++){
                 if ((a[0][i] == kreis && a[1][i] == kreis  && a[2][i] == kreis) || (a[0][i] == kreuz && a[1][i] == kreuz  && a[2][i] == kreuz)) {
                     spielstaende++;
                     break;
                 }
            }
            for (int j=0; j<3; j++){
                if ((a[j][0] == kreis && a[j][1] == kreis  && a[j][2] == kreis) || (a[j][1] == kreuz && a[j][2] == kreuz  && a[j][3] == kreuz)){
                    spielstaende++;
                    break;
                }
            }
               
            if((a[0][0] == kreis && a[1][1] == kreis && a[2][2] == kreis) || (a[0][0] == kreuz && a[1][1] == kreuz && a[2][2] == kreuz)){
                spielstaende++;
                break;
            }
           
            if((a[0][2] == kreis && a[1][1] == kreis && a[2][0] == kreis) || (a[0][2] == kreuz && a[1][1] == kreuz && a[2][0] == kreuz)){
                spielstaende++;
                break;
            } else {
                spielstaende++;

Hätte ich auch mit equals machen können, ist mir aber erst zu spät eingefallen.

Irgendwie glaube ich dass ich das viel zu kompliziert angehe

 

[Blender3D]

Da vergisst du aber die Situationen, in denen man vor 9 Zügen gewonnen hat. Wie gesagt, ich bin mir eigentlich ziemlich sicher, dass die Antwort 958 ist.

Du hast recht. Es gibt ja die dumme Möglichkeit wie z.B.
xxx
oo.
...
außerdem könnten bei den Permutationen auch solche Fälle auftreten.
xxx
xox
ooo
Die muss man auch abziehen.
Für die vollständig ausgefüllten Lösungen müsste man dann waagerecht 2x2x3x3 + senkrecht 2x2x3x3 2 x abziehen. Also 256 - 2x 2 x 36 = 184. Dann müsste man alle nicht vollständigen noch dazu addieren.