Tic tak toe, wie kann man so ein Spiel umsetzen?

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Hallo Tschoeatsch,
      bestimmt hast Du auch Google schon befragt, denn das haben doch schon Generationen von Informatikern und Programmierer umgesetzt so dass Du das nicht neu erfinden musst.
      Vielleicht kannst Du da Anregungen und fertige Programme finden, die Du maximal noch zu BASCOM umsetzen musst.
      Hier eventuell:
      gm-d.de/wbb/index.php/Thread/2…em-Minimax-Algorithmus-A/
    • Wenn ich diesen link überfliege, dann besteht die künstliche Intelligenz darin, alle momentan möglichen Züge mal zu setzen und zu prüfen, ob ich (Kontroller) oder der Gegner gewinnt. Das wäre dann in @Michaels Sinn. Gut, bleibt mir mal die Überlegung, wie ich am schnellsten erkenne, ob ich oder der Gegner gewinnen würde, außer halt mit 8 if-Abfragen.
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?
    • Mike,
      wie funktioniert es bei dir im Kopf, bei dem Tic-Tac-Toe Spiel?

      Ich denke, wir Menschen gehen ähnlich mit dem Problem um, wenn wir unser Denken verwenden...
      hinzu kommt allerdings die "Mike Variante", nenne ich sie mal :D wir haben ERFAHRUNG, werden also das "NACHDENKEN" erst verwenden, wenn uns kein bekanntes Muster vorliegt.

      Mach den schematischen Teil zur Erkennung eines Zuges und erweitere die "KI" um "ERFAHRUNG"... lass dein Programm "LERNEN"

      Hättest du jetzt Lazarus auf dem Rechner/Laptop, könntest du auch mal schnell im Urlaub sowas eintippen a_38_b45e201d
    • Oh man, ich glaub', ich bin im falschen Film. Du kommst mir so vor: nach Überwinden der mehrstufigen Zugangskontrolle der Basis des weltzerstörenden Schurken, hockst du dich an ein wild blinkendes Terminal (ok, hier brauchst du 2 Sekunden, um dir ein umfassendes Bild der Technik zu machen) und knackst mit wild prasselnden 10-Fingersystem einen unüberwindbaren Sicherheitscode um dann mit einem finalen 'enter' 2 Sekunden vor Weltuntergang das böse System zu stoppen und auf 'wieder gut' umzuswitchen.
      'Programm lernen lassen'..'schnell mal was ein tippen' a_28_2c02f089
      hey, ich doch nicht! Ich versuch grad' den Minmax zu verstehen und da meinst du, ich könnte in meinem Restleben es schaffen, eine 'Erfahrung' in ein eram zu brennen?
      Hättest du für mich nicht paar Tipps, die meinem Niveau entsprechen?
      a_59_ac03eae5
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?
    • Ich denke, wir sind nicht soooo verschieden... :D

      Setze mal den MinMax um und bekomme ein Gefühl dafür, was da abgeht.
      Wenn du weiter im Projekt drin bist, bekommst du auch "Spieltrieb" und Ideen...

      Theoretisch komme ich da auch nicht klar, ich muss das "erleben", "fühlen", "be-spielen".
      Erst die Interaktion mit Software oder Hardware zeigt mir Wege; auch wenn ich vorher kreative Ideen habe, so brauche ich den "Erstkontakt" mit der Materie...

      Egal..., fang an Mike a_14_3ef964b0


      wenn ich bisschen Zeit habe, setze ich das mal in Lazarus um und stelle das hier im "Lazarus for Dummies" ein...
    • Hi tschoeatsch,

      da du also bei tic-tac-toe bleiben willst, habe ich mir auch mal überlegt, wie ich das machen würde.

      Solche Abläufe wie Bäume (deine Graphik) zu durchsuchen, macht man für gewöhnlich, indem man eine rekursive Funktion erstellt, also eine, die sich selber wieder aufruft.

      Viel habe ich zu rekursiven Funktionen in Bascom noch nicht gefunden. Aber bei MCS gibt es tatsächlich ein paar Beispiele. Und ich habe es mal ausprobiert, es funktioniert.

      Dazu muss man alle Variablen, die sich in den verschiedenen Ebenen ändern, zu lokalen Variablen machen. Diese werden dann auf dem Stack abgelegt. Jeder Funktionsaufruf hat dann seine eigene Umgebung. Du merkst sicherlich gleich, dass dann einiges an Speicher verbraucht wird, wenn man tief sucht. Da hier aber maximal 9 Ebenen vorkommen, würde das auch 9 mal die lokalen Variablen bedeuten, was jetzt wahrscheinlich nicht so sonderlich viel sein wird.

      Bei 9 Ebenen könnte man das theoretisch auch noch über 9 Funktionen regeln, aber ich fand den rekursiven Ansatz hier mal interessant.
      Ist aber etwas schwieriger zu durchschauen um den Überblick zu behalten.

      Die Kommunikation zwischen den Ebenen geht dann entweder über globale Variablen oder den Funktionswert.
      Auf jeder Ebene, also bei jedem Aufruf der Funktion würde ich drei Blöcke sehen:
      • Feststellen, ob man selber eines Siegeszug hat. Dann sollte der natürlich gemacht werden.
      • Feststellen, ob der andere im nächsten Zug einen Siegeszug hat. Dann sollte der blockiert werden.
      • Wenn beide nicht, dann ein freies Feld wählen und die Funktion wieder aufrufen mit den Parametern, als wäre dieses Feld belegt.
      Wenn man jetzt deinen Ansatz von ganz zu Anfang mit den 9 Bits in einer Word Variable nimmt, jeweils eine für jeden Spieler, könnte das so aussehen:

      My_move = next_move(spieler1, spieler2, my_status)

      my_status habe ich mal dazugenommen, weil man bestimmt an die nächste Ebene noch irgendetwas übergeben muss

      BASCOM-Quellcode

      1. Function Next_move(ich as word, du as word, status as byte) as word
      2. Local
      3. ‘überprüfe eigenen Siegeszug
      4. ‘überprüfe generischen Siegeszug
      5. ‘wähle ein neues Feld und rufe next_move mit den geänderten Werten für Spieler1 bzw Spieler2 auf
      6. Next_move= was wir gefunden haben
      7. End Function

      Was hältst von dieser Vorgehensweise? Oder hast du schon eine andere konkrete Idee?
    • Meine Idee ist zur Zeit die minmax-Sache nachzubilden. Jeder Spieler hat weiterhin 9 bits eines words. Beide words verodert gibt das Spielfeld. Mit 9 if-Abfragen wird ein freies Feld gesucht und das in einer Kopie von den gerade ziehenden Spieler gesetzt. Gewinnabfrage, ob es sich lohnt weiter in die Tiefe zu gehen und danach zu handeln. Die Wertung des Zuges hab' ich noch nicht eingebaut, aber es wird die Tiefe mit berücksichtigt. Das heißt, ein Gewinn nach 3 durchsuchten Möglichkeiten ist weniger wert als zB. ein Sofortgewinn bei einem alternativen Zug (hab' ich auf einer anderen Seite im Netz aufgeschnappt
      geeksforgeeks.org/minimax-algo…-ai-finding-optimal-move/).
      Mal ganz grob meine Überlegungen

      Quellcode

      1. Sf=A or B 'Spielfeld=Spieler A oder Spieler B
      2. Sf1=Sf 'Spielfeld kopieren
      3. A1=A 'Spieler A kopieren
      4. if Sf.8=0 then Sf1.8=1:A1.8=1:gosub Zug1
      5. ...
      6. if Sf.0=0 then Sf1.0=1:A1.0=1:z=8:gosub Zug1
      7. if zug_1=0 then spielende=1
      8. Zug1:
      9. zug_1=1 'Zug wird ausgeführt
      10. gosub gewinn_prüfen
      11. if gewonnen=1 then
      12. p(z)=1
      13. return
      14. end if
      15. Sf2=Sf1 'Spielfeld kopieren
      16. B1=B 'Spieler B kopieren
      17. if Sf1.8=0 then B1.8=1:gosub Zug2
      18. ...
      19. if Sf1.0=0 then B1.0=1:gosub Zug2
      20. if zug_2=0 then spielende=1
      21. return
      22. Zug2:
      23. zug_2=1 'Zug wird ausgeführt
      24. gosub verlieren_prüfen
      25. if verloren=1 then
      26. p(z)=-1
      27. else
      28. p(z)=0
      29. end if
      30. return
      Alles anzeigen
      Mein Entwurf ist noch sehr, hm, lückenhaft, ich hab' halt jetzt nix gscheits zum Schreiben. Mit dem tablet ist das nicht so toll.
      Deinen Vorschlag muss ich noch bisschen länger durchdenken.
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von tschoeatsch ()

    • hero schrieb:

      Hi tschoeatsch,

      da du also bei tic-tac-toe bleiben willst, habe ich mir auch mal überlegt, wie ich das machen würde.

      Solche Abläufe wie Bäume (deine Graphik) zu durchsuchen, macht man für gewöhnlich, indem man eine rekursive Funktion erstellt, also eine, die sich selber wieder aufruft.

      Viel habe ich zu rekursiven Funktionen in Bascom noch nicht gefunden. Aber bei MCS gibt es tatsächlich ein paar Beispiele. Und ich habe es mal ausprobiert, es funktioniert.

      Dazu muss man alle Variablen, die sich in den verschiedenen Ebenen ändern, zu lokalen Variablen machen. Diese werden dann auf dem Stack abgelegt. Jeder Funktionsaufruf hat dann seine eigene Umgebung. Du merkst sicherlich gleich, dass dann einiges an Speicher verbraucht wird, wenn man tief sucht. Da hier aber maximal 9 Ebenen vorkommen, würde das auch 9 mal die lokalen Variablen bedeuten, was jetzt wahrscheinlich nicht so sonderlich viel sein wird.

      Bei 9 Ebenen könnte man das theoretisch auch noch über 9 Funktionen regeln, aber ich fand den rekursiven Ansatz hier mal interessant.
      Ist aber etwas schwieriger zu durchschauen um den Überblick zu behalten.

      Die Kommunikation zwischen den Ebenen geht dann entweder über globale Variablen oder den Funktionswert.
      Auf jeder Ebene, also bei jedem Aufruf der Funktion würde ich drei Blöcke sehen:
      • Feststellen, ob man selber eines Siegeszug hat. Dann sollte der natürlich gemacht werden.
      • Feststellen, ob der andere im nächsten Zug einen Siegeszug hat. Dann sollte der blockiert werden.
      • Wenn beide nicht, dann ein freies Feld wählen und die Funktion wieder aufrufen mit den Parametern, als wäre dieses Feld belegt.
      Wenn man jetzt deinen Ansatz von ganz zu Anfang mit den 9 Bits in einer Word Variable nimmt, jeweils eine für jeden Spieler, könnte das so aussehen:

      My_move = next_move(spieler1, spieler2, my_status)

      my_status habe ich mal dazugenommen, weil man bestimmt an die nächste Ebene noch irgendetwas übergeben muss

      BASCOM-Quellcode

      1. Function Next_move(ich as word, du as word, status as byte) as word
      2. Local
      3. ‘überprüfe eigenen Siegeszug
      4. ‘überprüfe generischen Siegeszug
      5. ‘wähle ein neues Feld und rufe next_move mit den geänderten Werten für Spieler1 bzw Spieler2 auf
      6. Next_move= was wir gefunden haben
      7. End Function
      Was hältst von dieser Vorgehensweise? Oder hast du schon eine andere konkrete Idee?
      Dieses 'wähle ein neues Feld' wäre mit Zählern zu realisieren, die dann jeweils einen Zug dazu fügen? Diese Zähler wären ja dann auch zum Stoppen der Rekursion nötig, oder sehe ich das falsch?
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?
    • @hero geprüft und für gut empfunden :thumbsup:
      Ich würde aber jetzt keine Funktion nehmen, sondern eine sub. Als Ergebnis brauche ich eine Wertung der möglichen, nächsten Züge, um den besten zu wählen. Ich denke, es wäre ein array Ergebnis(9) as byte dazu ganz praktisch. In der sub wird ein Zahler '1_Zug' mitgeführt, der den index für 'Ergebnis(1_Zug) darstellt. Wird durch die Gewinnprüfung erkannt, das man gewinnen würde, kommt als Wert '10-Suchtiefe' als Ergebnis rein. Bleibt der Test ergebnislos, wäre das Ergebnis '0'. 'Suchtiefe' wäre auch ein Zähler der nach jeweils 9 Durchläufen incrementiert wird, wenn '2_Zug' oder '3_Zug' eben durchgeprüft sind. Eine 'Verlorenprüfung' ergibt '-10+Suchtiefe'. Wenn 'Ergebnis(x)' in allen Fällen =0 ist, müsste das Spiel zu Ende sein.
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?
    • Hallo tschoeatsch,
      der Vorteil von Funktionen ist halt, dass du ohne globale Variablen auskommen kannst, wenn du die wichtigen Informationen über Parameter und Ergebnis austauschst. Das macht besonders bei Rekursion Sinn, da es sonst recht unübersichtlich wird.
      Wenn du das rekursiv machen willst, dann überlegst du, was bei einem einzelnen Zug passieren soll (also z.B. welche Checks du machen willst zur Bewertung), was du dazu benötigst (z.B. Spielfeld, wer ist dran) und was du als Ergebnis zurückbekommen möchtest (z.B. nächster Zug, Bewertung). Dabei ist es vollkommen unerheblich, auf welcher Ebene du dich befindest. Die Rekursion würdest du genauso auch bei einem 4x4 Spielfeld anwenden. Unterschiedlich sind nur die Berechnungen auf jeder Ebene.

      Warum denkst du, ist ein möglicher Sieg in 3 Zügen weniger Wert als einer in 2? Ich denke, du musst eine Möglichkeit suchen, eine Zwickmühle aufzubauen. Alles andere kann ja sofort verhindert werden. Und da liegt das Problem, wie du diese Situation erkennst und dann dorthin steuerst.
    • Der Aufbau dieser "Zwickmühle" ist die einzige Möglichkeit mit Taktik zu gewinnen. Alle anderen Gewinne sind nur auf die "Dummheit" des Gegenspielers zurückzuführen, der eine Situation nicht erkannt hat, den Sieg zu verhindern.

      Das Anstreben einer Konstellation, die dem Gegner keine Ausweichmöglichkeit bietet sollte demnach Ziel der Programmierung sein. Das ist eigentlich das Grundprinzip solcher Spiele, wie beispielsweise auch "Vier gewinnt". Man bemüht sich dann also dem Gegner zwei Schritte voraus zu sein.
      Wenn das die Lösung ist, möchte ich mein Problem wieder haben.
    • @hero so wie ich das in meinem zitierten link geeksforgeeks.org/minimax-algo…-ai-finding-optimal-move/
      verstanden habe, sind 'späte Gewinne' mehr durch Fehler des Gegners erzeugt und somit ist ein Zug in der Richtung nicht so wertvoll, wie ein Sofortgewinn, der ja das Ideale ist. Wenn man da Abstufungen in der Bewertung hat, lässt sich der Sofortgewinn leichter in der Ergebnisliste finden.

      @ceperiga Zwickmühlen sind Teil des 'optimalen' Spiels, so können die vom Gegner, der auch optimal spielt, verhindert werden und es gibt ein Unentschieden. Das war ja mein erster Gedanke, diese Tabelle, die ein optimales Spiel wiedergibt, als Spielplan zu verwenden. Darin ist als schlechtestes Ergebnis nur Unentschieden vorhanden. Die gibt ja ein komplettes Spiel wieder, was man ja auch erreicht, wenn man alle Züge bis zum Ende durch probiert und den besten wählt. Da sind dann auch Zwickmühlen dabei, die dann zu 'frühen' Siegen führen (höhere Bewertung!), weil's der Gegner nicht verhindern kann.
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?
    • Hi Mike,

      ich hab mal ein doch schon sehr umfangreiches Programm geschrieben. Es ist zwar noch nicht ganz perfekt aber man kann gewinnen, verlieren oder ein Unentschieden erreichen.
      Vielleicht lässt sich das ein oder andere auch noch verbessern aber es ist erstmal ein Vorschlag.
      Ich hab jetzt auch nicht so biel im Programm kommentiert also wenn Fragen auftauchen sollten dann einfach fragen.

      Dateien
      • TicTacToe.bas

        (22,16 kB, 11 mal heruntergeladen, zuletzt: )
      Eine Lösung habe ich nicht, aber mir gefällt Ihr Problem.
    • Ja toll! Schaut schon mal nicht schlecht aus. Dein Programm muss ich noch in Ruhe mal durchackern. Deine AI ist jetzt mehr eine Tabelle?

      Ich nutze die Regenzeit um bisschen hardware zu basteln. Ich hab' mir jetzt mal eine Tastatur mit 11 Tasten aufgebaut und eine Anzeige mit 10 Duo-Leds entworfen. Die werden von einem max7219 angesteuert und die Tasten werden durch den AD-Wandler ausgelesen. Dazu hab' ich mal das tool von @Zitronenfalter Verschiedene Tools für die Entwicklung rund um Mikrokontroller verwendet. Wenn meine Kleinkunst funktioniert, zeige ich Bilder.
      Jetzt wird's wieder spannend, werden wir weiße Weihnachten haben?