Java Dodelschach: Herausfinden, ob jemand schon gewonnen hat?

CyborgBeta · 27. Dezember 2022

Hi Leute,

ich bin vorhin auf ein interessantes Problem gestoßen, und zwar soll mit nur einer äußeren Schleife überprüft werden, ob jemand und wer beim Spiel Tic-Tac-Toe gewonnen hat:

Java:

package org.example;

public class Dodelschach {
    private static int s_i = 1;

    public static void print_helper(int a, int b) {
        System.out.println(s_i++);
        for (int i = 0; i < 9; ) {
            boolean printed = false;
            if (i == a) {
                printed = true;
                System.out.print("a");
            }
            if (i == b) {
                printed = true;
                System.out.print("b");
            }
            if (printed) {
                System.out.print(" ");
            } else {
                System.out.print("_ ");
            }
            i++;
            if (i % 3 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public static int getResult(int[] c) {
        for (int i = 0; i < 3; i++) {
            boolean wins1 = true;
            boolean wins2 = true;
            // Reihe:
            for (int j = 0; j < 2; j++) {
                int idx1 = 3 * i + j;
                int idx2 = 3 * i + j + 1;
                print_helper(idx1, idx2);
//                if (c[idx1] == 0 || c[idx2] == 0) {
//                    wins1 = false;
//                    break;
//                }
//                if (c[idx1] != c[idx2]) {
//                    wins2 = false;
//                    break;
//                }
            }
//            if (wins1 && wins2) {
//                return c[3 * i];
//            }

            wins1 = true;
            wins2 = true;
            // Spalte:
            for (int j = 0; j < 2; j++) {
                int idx1 = j * 3 + i;
                int idx2 = (j + 1) * 3 + i;
                print_helper(idx1, idx2);
//                if (c[idx1] == 0 || c[idx2] == 0) {
//                    wins1 = false;
//                    break;
//                }
//                if (c[idx1] != c[idx2]) {
//                    wins2 = false;
//                    break;
//                }
            }
//            if (wins1 && wins2) {
//                return c[i];
//            }

            wins1 = true;
            wins2 = true;
            // Haupt- und Nebendiagonale:
            for (int j = 0; j < 2; j++) {
                if (i == 2) {
                    wins1 = false;
                    break;
                }
                int idx1 = j * 3 + j; // <- Was stimmt hier nicht?
                int idx2 = (j + 1) * 3 + j + 1 - i * j * 2;
                print_helper(idx1, idx2);
//                if (c[idx1] == 0 || c[idx2] == 0) {
//                    wins1 = false;
//                    break;
//                }
//                if (c[idx1] != c[idx2]) {
//                    wins2 = false;
//                    break;
//                }
            }
//            if (wins1 && wins2) {
//                return c[i * 3];
//            }
        }
        return 0;
    }

    public static void main(String[] args) {
        getResult(new int[9]);
    }
}

Die Ausgabe stimmt so weit - bis auf Nummer 11 (Zeile 51):

Code:

1
a b _
_ _ _
_ _ _

2
_ a b
_ _ _
_ _ _

3
a _ _
b _ _
_ _ _

4
_ _ _
a _ _
b _ _

5
a _ _
_ b _
_ _ _

6
_ _ _
_ a _
_ _ b

7
_ _ _
a b _
_ _ _

8
_ _ _
_ a b
_ _ _

9
_ a _
_ b _
_ _ _

10
_ _ _
_ a _
_ b _

11
a _ _
_ b _
_ _ _

12
_ _ _
_ a _
b _ _

13
_ _ _
_ _ _
a b _

14
_ _ _
_ _ _
_ a b

15
_ _ a
_ _ b
_ _ _

16
_ _ _
_ _ a
_ _ b

diese müsste eigentlich wie folgt sein:

11
_ _ a
_ b _
_ _ _

das Problem dabei ist, wenn man idx1 (Zeile 81) ändert, beeinflusst das auch die Ausgabe von 5, 6 und 12...

Hätte vielleicht jemand eine Idee?

Danke, und kommt alle gut und wohlbehalten ins neue Jahr.

DaysShadow · 27. Dezember 2022

CyborgBeta schrieb:
auf ein interessantes Problem gestoßen

Auf deinem Hausaufgabenzettel nehme ich an. Dafür müssen deine Fragen schon spezifischer sein, sonst gilt https://www.computerbase.de/forum/threads/fragen-hausaufgaben-co.1767679/

CyborgBeta schrieb:
das Problem dabei ist, wenn man idx1 (Zeile 81) ändert, beeinflusst das auch die Ausgabe von 5, 6 und 12...

Hab's mir nicht angeschaut, aber grundlegendes Vorgehen: Frag dich halt wieso das so ist und versuch es nachzuvollziehen, geh es im Kopf durch oder im Debugger.

CyborgBeta · 27. Dezember 2022

DaysShadow schrieb:
Auf deinem Hausaufgabenzettel nehme ich an. Dafür müssen deine Fragen schon spezifischer sein, sonst gilt https://www.computerbase.de/forum/threads/fragen-hausaufgaben-co.1767679/

Bist du generell unfreundlich, oder nur bei diesem Problem? Na ja, eine gute Kinderstube hatte eben nicht jeder...

Um auf deine Gegenfrage zu antworten: Nein, das sind keine Hausaufgaben.

DaysShadow · 27. Dezember 2022

Ok cool, hast du die Quelle für das Problem mit der Aufgabenstellung? Interessiert mich auch.

CyborgBeta schrieb:
ich bin vorhin auf ein interessantes Problem gestoßen

Sollte ja kein Problem sein

CyborgBeta · 27. Dezember 2022

DaysShadow schrieb:
die Quelle für das Problem mit der Aufgabenstellung?

Ja, ich.

Du musst hier nicht antworten, wenn du die Frage nicht verstehst. Es besteht kein Zwang zur Antwort...

Bunkeropfer · 27. Dezember 2022

Ohne zu wissen, was genau dein idx_ für i und j genau bedeutet, so ist der Fehler hier zumindest offensichtlich in #81:
Sonst hast du für diesen Wert immer beide Variablen i und j verwendet, nur hier eben nicht. Daher ist bei der Paarung (i,j)=(0,0) und (1,0) immer der Wert "0" für idx1 festgelegt. (also bei den Fällen 5 und 11). Bei Fall 5 ist das kein Problem, da du dich ja nur auf der Hauptdiagonalen von links-oben nach rechts-unten bewegst.
Für die anders gerichtete Diagonale musst du aber im Array beim Feld [2] starten, also idx1 = 2 berechnen für (1,0) und somit einen i-abhängigen Teil einbauen (irgendwas mit "+2*i" vermutlich).
Das genau zu berechnen überlasse ich dir gerne.
(beim idx2 hast du ja sowas in der Art dabei mit 2*i*j)

EDIT:
Zahlendreher korrigiert bei (0,0) und (1,0)

Iqra · 28. Dezember 2022

Okay, bin offiziell verwirrt.

Was hat die Problemstellung gemäß Thread-Titel mit dem Lösungsansatz zu tun?

getResult() liefert einen Int. Was sagt mir der Int? Verwendet wird er ja nicht.
wenn ich die Konfiguration auf "hat gewonnen" testen will, dann brauch ich erstmal ein Spielfeld als Parameter. Soweit so gut. Nur wird keins übergeben. Das ist vermutlich auch schon aufgefallen, soweit sich das aus den auskommentierten Zeilen schließen läßt.
müßig an der Stelle zu erwähnen daß getResult() viel zuviel tut. Sowas wie public bool testResult(Spielfeld sp) hätte ich zwar erwartet, fehlt aber.
im sinne von "Interessant" sehe ich spontan (ohne besonders drüber nachgedacht zu haben)

1. Hashfunktion (Bucket entspricht Position im Spielfeld => muß man dann gucken ob man aus dem Hashwert den Spieler ableiten kann oder ob man noch was mitführen muß)
2. Primzahlzerlegung mit 0 gleich "nicht. belegt" und PZ als ID für den jeweiligen Spieler
3. das Spielfeld ist ne Matrix, naja irgendwas wird sich doch auf der Basis wohl machen lassen.

Soweit es mich betrifft sind 100 Codezeilen die offensichtlich das Problem noch nicht lösen für einen simplen yes/no Test (viel) zuviel. Hier geht es (gerade)noch. Aber irgendwann läßt sich das nicht mehr händeln.

CyborgBeta · 28. Dezember 2022

Ok, ich konnte es lösen.

@Iqra Es sollte mit folgendem Snippet klarer sein, was die Methode tut:

Java:

package org.example;

public class Dodelschach {
    private static int s_i = 1;

    public static void print_helper(int a, int b) {
        System.out.println(s_i++);
        for (int i = 0; i < 9; ) {
            boolean printed = false;
            if (i == a) {
                printed = true;
                System.out.print("a");
            }
            if (i == b) {
                printed = true;
                System.out.print("b");
            }
            if (printed) {
                System.out.print(" ");
            } else {
                System.out.print("_ ");
            }
            i++;
            if (i % 3 == 0) {
                System.out.println();
            }
        }
        System.out.println();
    }

    public static int getResult(int[] c) {
        for (int i = 0; i < 3; i++) {
            int j;
            // Reihe:
            for (j = 0; j < 2; j++) {
                int idx1 = 3 * i + j;
                int idx2 = 3 * i + j + 1;
                print_helper(idx1, idx2);
                if (c[idx1] == 0 || c[idx2] == 0) {
                    break;
                }
                if (c[idx1] != c[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return c[3 * i];
            }

            // Spalte:
            for (j = 0; j < 2; j++) {
                int idx1 = j * 3 + i;
                int idx2 = (j + 1) * 3 + i;
                print_helper(idx1, idx2);
                if (c[idx1] == 0 || c[idx2] == 0) {
                    break;
                }
                if (c[idx1] != c[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return c[i];
            }

            // Haupt- und Nebendiagonale:
            for (j = 0; j < 2; j++) {
                if (i == 2) {
                    break;
                }
                int idx1 = j * 3 + j - i * (j - 1) * 2; // <- solved :)
                int idx2 = (j + 1) * 3 + j + 1 - i * j * 2;
                print_helper(idx1, idx2);
                if (c[idx1] == 0 || c[idx2] == 0) {
                    break;
                }
                if (c[idx1] != c[idx2]) {
                    break;
                }
            }
            if (j == 2) {
                return c[i * 3];
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        // Es hat noch keiner gewonnen:
        System.out.println(getResult(new int[]{
                0, 0, 0,
                0, 0, 0,
                0, 0, 0,
        }));
        // Spieler 2 gewinnt:
        System.out.println(getResult(new int[]{
                1, 1, 2,
                1, 0, 2,
                2, 1, 2,
        }));
    }
}

Es wird immer eine Kopie des aktuellen "Spielfelds" übergeben. Dabei steht 0 für noch nicht belegt, 1 für belegt durch Spieler 1, und 2 für belegt durch Spieler 2.

Die Methode soll nun alle Reihen, Spalten und(!) Diagonalen überprüfen, ob sich 3 gleiche in einer Sequenz befinden. Ist das der Fall, gibt die Methode den Sieger zurück.

Die Schwierigkeit bestand aber darin, dass ich alle Überprüfungen innerhalb nur einer äußeren Schleife machen wollte, also loop unrolling (Optimierung) heißt das, glaube ich.

Suche

Java Dodelschach: Herausfinden, ob jemand schon gewonnen hat?

CyborgBeta

Commander

DaysShadow

Admiral

CyborgBeta

Commander

DaysShadow

Admiral

CyborgBeta

Commander

Bunkeropfer

Lt. Junior Grade

Iqra

Gast

CyborgBeta

Commander

Ähnliche Themen