Tic Tac Toe has_won() Methode einbauen



  • Hallo,

    Gibt es eine Methode in Tic Tac Toe die has_won() Methode einzubauen, ohne einen Vektor mit allen Möglichkeiten anzulegen (8) und dann basierend auf allen Möglichkeiten nach den bisher gesetzten Stein-Koordinaten des Spielers zu suchen?

    Mir scheint das irgendwie sehr uneffizient. Irgendwelche Vorschläge?



  • Evtl. das längste zusammenhängende Fragment aus den gesetzten Koordinaten bestimmen. Das muss die Länge 3 haben.

    p.s. Fragment war jetzt sehr ungenau... Du suchst drei Punkte, die auf einer Geraden liegen.



  • @eigenartig So aus dem Bauch heraus würde ich sagen:

    Eine dieser Bedingungen muss für die (x, y)-Koordinaten von 3 Symbolen eines Spielers muss gelten :

    • x=y
    • x=3-y
    • x=i für ein i aus { 0, 1, 2 }
    • y=i für ein i aus { 0, 1, 2 }

    { 0, 1, 2 } sind hier die möglichen Werte, die eine Koordinate für x oder y annehmen kann.

    ... könnte das passen?

    Edit: hoffentlich etwas klarer formuliert.



  • @Finnegan sagte in Tic Tac Toe has_won() Methode einbauen:

    ... könnte das passen?

    Verstehe ich auf den ersten Blick nicht. Wieso 0, 1, 2?



  • @Mechanics sagte in Tic Tac Toe has_won() Methode einbauen:

    @Finnegan sagte in Tic Tac Toe has_won() Methode einbauen:

    ... könnte das passen?

    Verstehe ich auf den ersten Blick nicht. Wieso 0, 1, 2?

    Oh, nicht erwähnt. Das sind die Koordinaten des 3x3-TicTacToe-Felds.



  • Das muss zumindest nicht für alle gelten. Du kannst ja auch Punkte platzieren, die falsch liegen. Du musst drei finden, die passen.



  • @Mechanics sagte in Tic Tac Toe has_won() Methode einbauen:

    Das muss zumindest nicht für alle gelten. Du kannst ja auch Punkte platzieren, die falsch liegen. Du musst drei finden, die passen.

    Oh ja, das hab ich echt verpeilt. Hatte nur das erkennen der drei Sieg-Symbole im Sinn, aber da gibt es ja noch andere Positionen 😉 Gut, es muss drei Positionen geben, bei denen eine der Regeln für alle 3 gilt (passe das eben in meiner Antwort an).


  • Mod

    @eigenartig sagte in Tic Tac Toe has_won() Methode einbauen:

    Mir scheint das irgendwie sehr uneffizient. Irgendwelche Vorschläge?

    8 einfache, vordefinierte Maskenvergleiche sollen ineffizient sein?

    Du kannst die Regeln natürlich selber implementieren, also so mit geschachtelten Schleifen, die systematisch alles durchtesten. Wenn du dich besser dabei fühlst. Aber das wäre dann ineffizient, weil dann für jede Prüfung zur Laufzeit das Wissen erneut ausgerechnet wird, das in den vordefinierten Vergleichen schon fest verdrahtet ist.

    Aber die Maskenvergleiche sind mit etwas geschickter Speicherung des Spielfeldes nur 16 bitweise UND. Das macht ein Prozessor mal eben nebenher zwischen zwei Speicherzugriffen.



  • @SeppJ sagte in Tic Tac Toe has_won() Methode einbauen:

    8 einfache, vordefinierte Maskenvergleiche sollen ineffizient sein?

    Ich mag das Hard-coding daran halt nicht so.

    @SeppJ sagte in Tic Tac Toe has_won() Methode einbauen:

    Du kannst die Regeln natürlich selber implementieren, also so mit geschachtelten Schleifen, die systematisch alles durchtesten. Wenn du dich besser dabei fühlst. Aber das wäre dann ineffizient, weil dann für jede Prüfung zur Laufzeit das Wissen erneut ausgerechnet wird, das in den vordefinierten Vergleichen schon fest verdrahtet ist.

    *kopfkratz* ... ok.

    Es scheint mir halt einfach so, dass ich das Feld irgendwie durch-bruteforcen muss, wo ich dachte, dass es mit einem einzigen Schleifendurchlauf mit den Koordinaten der bisher gesetzten Steine eines Spielers möglich wäre. Teilt man die 9 Spielzüge in Zwei sollten das doch sehr wenige Schleifendurchläufe sein?

    Ich hab meine Koordinaten (die gesetzten des Spielers, sowie die Gewinnmöglichkeiten) in einem sortierten Set abgelegt. Das vereinfacht so manches.


  • Mod

    Egal, ob du es als verschachtelte Schleifen oder als sonstwie aufschreibst: Ist es weniger als 16 vorgegebene Operationen?

    Ich verstehe ja vollkommen deinen Gedankengang, dass Hardcodierung im allgemeinen inelegant ist, aber hier finde ich es irgendwie die "coolere" Lösung, da sie zeigt, dass man darüber nachgedacht hat, was wohl effizient wäre, und dabei zu einem unerwarteten Ergebnis gekommen ist.

    Du kannst die Masken ja auch einmalig zum Programmstart ausrechnen, dann hast du das beste beider Ansätze.



  • @SeppJ, ok cool danke für die Antwort. Und auch den anderen.

    Aber jetzt gehen wir noch einen Schritt weiter und man schreibt ein generisches Tic Tac Toe mit zB 10x10. Dann muss man ja schon fast irgendwie "mathematischer" vorgehen.

    Ebenso für die KI, wo ich beispielsweise will, dass der NPC erkennt, dass du im nächsten Zug gewinnen wirst und der das abblockt usw.

    Aber mir fällt grad ein, ich kann auch die Map hernehmen, dabei Zeilen / Kolonnen extrahieren und einfach nur Zeichen-Vergleiche/Abzählungen mache. Das schwebt mir gerade etwas einfacher und performanter vor.



  • @eigenartig sagte in Tic Tac Toe has_won() Methode einbauen:

    Aber mir fällt grad ein, ich kann auch die Map hernehmen, dabei Zeilen / Kolonnen extrahieren und einfach nur Zeichen-Vergleiche/Abzählungen mache. Das schwebt mir gerade etwas einfacher und performanter vor.

    Wenn du wirklich so einen großen Wert auf die Performance legst, dann kommst du nicht um das von SeppJ vorgeschlagene Bitgefummel herum. Das ist vor allem deshalb flott, weil es die kompakteste Repräsentation fürs Spielfeld ist und alles in CPU-Register passt (Speicher ist nicht selten ein größerer Flaschenhals als ein schlechter Algorithmus).

    Da ich grad Spass en dem Problem hatte, hier eine völlig obskure, hartcodierte Bitfummel-Lösung mit möglichst vielen "Magic Numbers", die in einem SWAR-Ansatz mit jeder logischen Bitoperation gleich 3 Konstellationen parallel prüft:

    #include <iostream>
    #include <cstdint>
    #include <bitset>
    
    void print(std::uint32_t field)
    {
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                if (field & (std::uint32_t{ 1 } << (i * 3 + j)))
                    std::cout << "X";
                else
                    std::cout << ".";
            }
            std::cout << "\n";
        }
    }
    
    auto has_won(std::uint32_t field) -> bool
    {
        std::uint32_t f = field | (field << 10) | (field << 20);
        return (((f | 244139U) + 1049601U) & 537395712U) + (((f | 230012342U) + 1049601U) & 537395712U) + (((f | 66526712U) + 1049601U) & 537395712U);
    }
    
    auto main() -> int
    {
        for (std::uint32_t field = 0; field < 512; ++field)
        {
            if (std::bitset<9>{ field }.count() != 3)
                continue;
            if (has_won(field))
            {
                print(field);
                std::cout << "\n";
            }
        }
    }
    

    (Bäm! Erklärung bei Interesse 😜 )

    Für die meisten Fälle wird aber wird aber dein erster Ansatz mit dem Lösungs-Vektor völlig ausreichend sein. Man sollte es nicht übertreiben mit dem Optimieren, sonst werden Programme nämlich ganz schnell nicht mehr zu bändigen und nie fertig - und optimieren auch noch mit viel Aufwand an den Stellen, wo es keinen Profit abwirft.



  • Definitiv kein guter Code und keine gute Lösung, aber vielleicht ein Denkanstoß. Schau dir mal meine calculate Methoden an:

    https://www.c-plusplus.net/forum/topic/348797/tictactoe/1



  • @Finnegan, danke für den Beitrag, aber das ist mir irgendwie noch zu hardcorig 😄

    Momentan löse ich das so, dass ich alle Zeilen und Kolonnen (sowie die beiden Diagonale) aus der Map auslese und dann Zeichenüberprüfungen mache. Das Ganze funktioniert soweit auch sehr gut 🙂 👍



  • @eigenartig sagte in Tic Tac Toe has_won() Methode einbauen:

    @Finnegan, danke für den Beitrag, aber das ist mir irgendwie noch zu hardcorig 😄

    Danke, aber das würde mir ganz genau so gehen, wenn jemand sowas vor meinen Füssen auskippt (war auch Absicht, da ich zunächst vorhatte das in einen Einzeiler zu bekommen). Der Sinn erschliesst sich auch erst, wenn man die Zahlen binär ausschreibt und ist dann auch nicht annähernd so kompliziert, wie es aussieht. Wie gesagt, bei Bedarf 😉

    Momentan löse ich das so, dass ich alle Zeilen und Kolonnen (sowie die beiden Diagonale) aus der Map auslese und dann Zeichenüberprüfungen mache. Das Ganze funktioniert soweit auch sehr gut 🙂 👍

    "Funktionieren" ist auch erstmal das richtige. Optimieren besser erst wenn es zum Problem wird.



  • Eine für mich akzeptable Lösung wäre alle Siegmöglichkeiten in einer Textdatei abzuspeichern, die dann gelesen wird und mit dem Feld verglichen. Wie sehr man das optimiert, also obs z.B. in Masken umgerechnet wird, ist vermutlich am Ende irrelevant, weil man hier wohl sehr lange kein Performanceproblem messen kann.

    Ein solcher Algorithmus wäre dann aber sehr simpel erweiterbar für beliebige Größen, wenn einfach nochmal eine Schleife aussenrum Spielfeld und Siegmuster gegeneinander verschieben kann. Er könnte dann genauso z.B. 4Gewinnt berechnen.


Anmelden zum Antworten