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

    Aufgrund technischer Veränderungen ist der Mailverkehr innerhalb des Forums (Private Nachrichten) nur noch eingeschränkt möglich. Die Einschränkung ist notwendig, um zusätzliche Betriebskosten für das Forum zu vermeiden. Näheres zu den Hintergründen im Thread "Aktuelles zum Forum".Wir bitten um Verständnis.

    Hinweis kann nach Kenntnisnahme deaktiviert werden!

    • So, die Testhardware ist fertig. Die Tasten werden mit einem Analogeingang eingelesen (da hab' ich lange geschwitzt, bis die ordentlich gingen. Ich hab' allerdings auch 5% Widerstände verwendet, das ist wohl bei so viel Tasten grenzwertig, dass man nicht die berechneten Werte verwenden kann. Ich hab' dann Spannung für jede Taste gemessen und selbst berechnet. Ist jetzt keine Kritik an @Zitronenfalter!), die Duo-Leds werden von einem max7219 angetrieben. Dazu hab' ich mir ein 'shield' gebastelt, das anstelle von den üblichen 8x8Matixen aufgesteckt werden kann.
      Momentan geht nur ein Spieler-gegen-Spieler-Spiel, dem Programm fehlt es noch an Intelligenz. Mir war jetzt eine Testplattform wichtig, um meine Programmierversuche zu testen. Die oberste Led zeigt an, wer den Zug machen kann. Die obersten Tasten dienen zur Vorwahl, wer beginnt.
      Raum für Notizen

      -----------------------------------------------------------------------------------------------------

      -----------------------------------------------------------------------------------------------------
    • Noch ist es bei mir nicht so toll. Meine KI (oder AI) hat derzeit einen IQ von einem Gartenlicht, es leuchtet bunt 8|
      Ich bin gerade bei der Rekursion. Meine Funktion prüft die aktuelle Stellung der 'Steine' auf Gewinn, oder Verloren, ist das nicht der Fall, dann wird die nächste freie Stelle probehalber besetzt und mit derselben Funktion geprüft... Gibt es keine Stelle mehr zu besetzen, wird der Probeversuch rückgängig gemacht und die nächste freie Stelle probiert. So sollten eigentlich alle Stellungen durch probiert werden, tut's aber nicht. Noch ist es so, das Spielfeld wird gefüllt, dann wird der letzte Zug zurück genommen und der vorletzte. jetzt sind 2 Felder frei und es sollte das Spielfeld wieder gefüllt werden, nur das jetzt die Reihenfolge der 2 freien Stellen unterschiedlich wäre. Das passiert nicht, was mich vor große Rätsel stellt. Es wird in der Funktion mit einer lokalen for..next-Schleife auf freie Stellen am Spielfeld geprüft, aber es werden die Lücken nach einen Rückgängigmachen eines Zuges nicht erkannt.
      Das wäre ein Teil des Hauptprogramm, hier wird ein möglicher Zug gemacht und zur Prüfung an die Funktion geschickt.

      BASCOM-Quellcode

      1. Do
      2. If R_am_zug = 0 Then 'Spieler grün am Zug
      3. If Zug_noch_moeglich(sf) = 1 Then
      4. Zug_ok = 0
      5. Do
      6. Gosub Warte_auf_taste
      7. Check = Sf And Key
      8. If Check = 0 Then Zug_ok = 1 'Test ob Stelle frei
      9. If Key > &B100_000_000 Then Zug_ok = 0 'ungültige Taste
      10. Loop Until Zug_ok = 1
      11. Incr Zug_nr
      12. Sp_g = Sp_g Or Key 'Spieler grün aktualisieren
      13. R_am_zug = 1 : G_am_zug = Not R_am_zug 'Wer macht den nächsten Zug anzeigen
      14. End If
      15. Else 'Spieler rot am Zug
      16. If Zug_noch_moeglich(sf) = 1 Then
      17. For Z = 0 To 8 'mögliche Spielfelder
      18. Ergebnis(z) = 0 'frühere Ergebnisse löschen
      19. R_am_zug_kopie = 1 'Spieler rot wäre dran
      20. If Sf.z = 0 Then 'Spielfeld unbelegt
      21. Sp_r.z = 1 'Spielstein setzen
      22. Sf = Sp_g Or Sp_r 'Spielfeld aktualisieren
      23. Gosub Anzeige
      24. Ergebnis(z) = Pruefe_zug()
      25. Sp_r.z = 0 'Spielstein wieder zurück nehmen
      26. Sf = Sp_g Or Sp_r 'Spielfeld aktualisieren
      27. Gosub Anzeige
      28. End If
      29. Next Z
      30. 'für besten Zug entscheiden
      31. Zwischenergebnis = 0
      32. For Z = 0 To 8
      33. If Ergebnis(z) >= Zwischenergebnis Then
      34. Zwischenergebnis = Ergebnis(z)
      35. Bester_zug = Z
      36. End If
      37. Next Z
      38. 'Zug ausführen
      39. Sp_r.bester_zug = 1 'Spielstein setzen
      40. Incr Zug_nr
      41. R_am_zug = 0 : G_am_zug = Not R_am_zug 'Wer macht den nächsten Zug anzeigen
      42. End If
      43. End If
      44. Sf = Sp_r Or Sp_g 'Spielfeldbelegung aktualisieren
      45. Gosub Anzeige
      46. Gosub Check_gewinn
      47. Loop Until Gewinn_r = 1 Or Gewinn_g = 1 Or Zug_noch_moeglich(sf) = 0
      Alles anzeigen

      Die Funktion schaut so aus

      BASCOM-Quellcode

      1. Function Pruefe_zug()
      2. Local X As Byte , Ergebnis As Byte
      3. Ergebnis = 10
      4. Gosub Check_gewinn
      5. If Gewinn_r = 1 Then
      6. Ergebnis = 20 - Zug_tiefe 'Zugtiefe mit bewerten
      7. End If
      8. If Gewinn_g = 1 Then
      9. Ergebnis = 1 + Zug_tiefe
      10. End If
      11. If Gewinn_r = 0 And Gewinn_g = 0 Then
      12. Incr Zug_tiefe 'tieferen Zug betrachten
      13. Toggle R_am_zug_kopie 'Spieler für den nächsten Zug umschalten
      14. For X = 0 To 8 'mögliche Spielfelder
      15. If Sf.x = 0 Then 'Spielfeld unbelegt
      16. If R_am_zug_kopie = 1 Then
      17. Sp_r.x = 1 'Spielstein setzen
      18. Else
      19. Sp_g.x = 1
      20. End If
      21. Sf = Sp_g Or Sp_r 'Spielfeld aktualisieren
      22. Gosub Anzeige
      23. Ergebnis = Pruefe_zug()
      24. If R_am_zug_kopie = 1 Then
      25. Sp_r.x = 0 'Spielstein wieder zurück nehmen
      26. Else
      27. Sp_g.x = 0
      28. End If
      29. Sf = Sp_g Or Sp_r 'Spielfeld aktualisieren
      30. Gosub Anzeige
      31. End If
      32. Next X
      33. Toggle R_am_zug_kopie 'Spieler zurück schalten
      34. Decr Zug_tiefe
      35. End If
      36. If Ergebnis(z) < Ergebnis Then
      37. Pruefe_zug = Ergebnis
      38. Else
      39. Pruefe_zug = 1
      40. End If
      41. End Function
      Alles anzeigen
      Als Film schaut's so aus
      Raum für Notizen

      -----------------------------------------------------------------------------------------------------

      -----------------------------------------------------------------------------------------------------
    • Hallo Tschoeatsch,
      ich glaube, dass du mit der rekursiven Funktion nicht glücklich wirst, wenn du immer auf den globalen Variablen Sp_r und Sp_g arbeitest. Dann musst du immer Züge setzen und wieder zurücknehmen.
      Rekursiv ist dadurch so elegant, dass du alle wichtigen Informationen auf die nächste Ebene übergibst und dort die Berechnungen in lokalen Variablen durchführst. Wenn du zurückspringst, hast du dann automatisch wieder die Umgebung von vorher.
      Also Sp_r/g als Parameter an die Funktion Pruefe_Zug übergeben, Sf brauchst du nicht, dass kannst du ja einfach aus "Or"en berechnen. Ich würde mich auch nicht um r und g kümmern, sondern immer davon ausgehen, dass das erste Argument zieht. Also wechselst du die Reihenfolge der Parameter beim Aufruf. Um nun MiniMax zu erreichen, musst du aber wissen, ob du gerade minimierst oder maximierst. Kannst du durch eine zusätzliche Variable oder durch die freien Bits von Sp_r/g erreichen.
    • Michael schrieb:

      Die Strategie des Menschen muss doch nicht berechnet werden?
      Sinn und Zweck der KI ist es, den Menschen zu überlisten :)
      Die Züge des Menschen sollten lediglich in die Gewinn-Strategie mit einbezogen werden.
      Also welches Feld die KI belegen muss, damit der Mensch nicht gewinnt oder es zu einem unentschieden kommt.

      Wie Michael schon geschrieben hat brauchst du die möglichen Züge des Menschen nicht mit berechnen.
      Deine KI sollte nur von den bereits belegten Felder ausgehen.
      Eine Lösung habe ich nicht, aber mir gefällt Ihr Problem.
    • Michael schrieb:

      tschoeatsch schrieb:

      Meine KI (oder AI) hat derzeit einen IQ von einem Gartenlicht, es leuchtet bunt
      in dem Video wird von der "KI" auch die Farbe des menschlichen Spielers gesetzt (außer das erste mal)Hast du dein Programm jetzt doppelt gebaut? Die Strategie des Menschen muss doch nicht berechnet werden?
      Natürlich muss ich auch die Züge vom 'Mensch' mit probieren, wenn ich das nicht machen würde, könnte ich doch nur die derzeit freien Plätze durch probieren, das nütz mir nix, oder wenig.

      @hero Ich werde mal deinen Hinweisen nach gehen.
      Aber mal von allem abgesehen, warum klappt meins nicht? Das Spielfeld wird aufgefüllt, es wird also die Funktion rekursiv auf gerufen, das scheint zu passen. Jetzt ist das Spielfeld mit dem letzten Zug belegt, Aufruf der Funktion: die prüft auf Gweinn/Verloren und sucht mit der for next nach einem freien Platz, findet keinen und es geht zurück. Hier wird der letzte Zug rückgängig gemacht, diese for..next ist aber schon beim letzten Element, die Funktion geht zurück. Die letztgesetzte Led ist jetzt aus. In der jetzt aktuellen Funktion wird der Zug zurück gesetzt, der mit dem vorletztem Element der for nexht-Schleife gesetzt wurde, die vorletztgesetzte Led geht aus. Die for next nimmt das letzte Elemen, Platz ist frei, Zug wird gesetzt. Das sieht man im Film. Jetzt wird zum Prüfen wieder die Funktion aufgerufen, die prüft mit ihrer for next auf freie Stellen und müsste jetzt die Lücke finden, das tut sie aber nicht. Es müssten sich die beiden letztgesetzten Leds im Spielfeld von der Farbe her tauschen. Das kapier ich nicht, wo da der Wurm drin steckt. Aber vielleicht ist das mit Parameterübergabe besser.

      hero schrieb:

      Um nun MiniMax zu erreichen, musst du aber wissen, ob du gerade minimierst oder maximierst.
      ich dachte mir, ich lege in meinem array Ergebnis(x) den max-Wert hinein, der mit diesem Zug x und dessen weitergehenden Varianten erreichbar ist. Ein Überprüfen auf min wollte ich mir sparen.


      @ceperiga an ein debugging-LCD hab' ich auch schon gedacht, wenn's weiter so schräg läuft, werd' ich die installieren.
      Raum für Notizen

      -----------------------------------------------------------------------------------------------------

      -----------------------------------------------------------------------------------------------------
    • Da er danach nie wieder tiefer geht, würde ich mal auf die Variable Zugtiefe tippen.
      Schau dir doch mal an, ob du die korrekt zurücksetzt.
      MiniMax heißt doch, dass immer wenn der erste Spieler dran ist (auch in der Tiefe), er immer den besten Zug nimmt. Ist dagegen der andere dran, nimmt er immer den schlechtesten für den ersten Spieler. Die vielen guten ignoriert er also.

      Edit: Ich dachte, dass Zugtiefe für eine Überprüfung auf Abbruch benutzt wird, aber das scheint nicht der Fall zu sein. Problem wird also doch woanders liegen.
    • hero schrieb:

      MiniMax heißt doch, dass immer wenn der erste Spieler dran ist (auch in der Tiefe), er immer den besten Zug nimmt. Ist dagegen der andere dran, nimmt er immer den schlechtesten für den ersten Spieler. Die vielen guten ignoriert er also.
      wenn der Computer dran ist, spielt der doch ab der derzeitigen Spielsituation alle möglich Folgezüge durch und schaut bei jedem Zug, ob er dadurch gewinnen kann (daß das 'Intelligenz' genannt wird, hm, eher 'brute force'). Es muss also den Zug werten, um aus der Vielzahl den besten erkennen zu können. Aber er braucht die Wertung für die aktuell möglichen. Der 'Zugbaum', der an den derzeit möglichen Zügen dran hängt ist für jeden Zug gleich lang, man könnte alle Wertungen der Züge addieren. Wenn er mit dem anstehenden Zug gewinnen kann, ist der besser zu werten als wenn noch der Gegener zieht und dann erst der Gewinnzug gemacht werden kann. Das soll mit der Variablen Zugtiefe gelöst werden, je tiefer der Zug zum Gewinn führt umso weniger Wert hat der Zug, weil der Gegner ja nicht genau die angedachten Züge machen muss. Und ein für den Gegner guter Zug hat natürlich geringen Wert.
      Raum für Notizen

      -----------------------------------------------------------------------------------------------------

      -----------------------------------------------------------------------------------------------------
    • Wenn er direkt gewinnen kann, ist das keine Frage, was er macht. Schwieriger wird die Bewertung, wenn der Sieg erst beim nächsten Zug kommt.
      Stell dir vor, Feld 1 (oben links) und Feld 2(oben Mitte) hat Spieler B, Feld 4 (mitte links) hat Spieler A. A (der µC) ist dran. Zieht er jetzt auf Feld 5 (mitte mitte) dann könnte er im folgenden Zug auf Feld 6 setzen und hätte gewonnen. Damit würde der Zug eine hohe Bewertung bekommen. Dumm ist nur, dass Spieler B vorher auf Feld 3 setzt. D.h. Feld 3 ist Pflicht für Spieler A.
      MiniMax erkennt das, weil dabei immer abwechselnd der beste und der schlechteste Zug für A gewählt wird. Wenn A im Baum dran ist und es gibt mehrere Bewertungen, nimmt man die beste, wenn B dran ist, die schlechteste. Damit würde für Feld 5 eine sehr schlechte Bewertung kommen, weil es zum Sieg von B führt.
      Das mit der Zugtiefe habe ich nachher auch verstanden.
    • Jetzt mal was grundsätzliches:
      die Funktion bekommt die Spielstellung für den Spieler rot (Sp_r = Computer) und die Spielstellung für Spieler grün (Sp_g = Mensch) und wer gerade gezogen hat mit geteilt.
      Jetzt prüft die Funktion auf Gewinn oder Verloren. Ist beides nicht der Fall, nimmt sie das nächste freie Feld (ermittelt aus sp_r or Sp_g) durch die for next-Schleife und setzt den Zug für den Spieler, der jetzt dran wäre. Diese neuen Spielstände werden jetzt zur Prüfung an die Funktion übermittelt. Das geht so weit, bis das Spielfeld voll ist.

      hero schrieb:

      Wenn du zurückspringst, hast du dann automatisch wieder die Umgebung von vorher.
      Wenn jetzt die Funktion zurück springt, muss ich doch trotzdem den Zug zurück setzen, um wieder an der Position zu sein, vor dem gerade geprüften Zug, um jetzt den nächst möglichen zu ziehen und prüfen zu lassen.
      Und wenn die for-next noch nicht komplett durch ist, dann wird wieder gezogen und zur Prüfung geschickt. Dieser Aufruf der Funktion sollte der for next doch von neuem starten. Dadurch müssten die Lücken gefunden werden, tuts aber nicht X/ Gibt's einen Rat dazu?

      hier mal das aktuelle Programm
      tic-tac-toe-KI-V0.14.bas




      hero schrieb:

      Stell dir vor, Feld 1 (oben links) und Feld 2(oben Mitte) hat Spieler B, Feld 4 (mitte links) hat Spieler A. A (der µC) ist dran. Zieht er jetzt auf Feld 5 (mitte mitte) dann könnte er im folgenden Zug auf Feld 6 setzen und hätte gewonnen. Damit würde der Zug eine hohe Bewertung bekommen. Dumm ist nur, dass Spieler B vorher auf Feld 3 setzt. D.h. Feld 3 ist Pflicht für Spieler A.
      MiniMax erkennt das, weil dabei immer abwechselnd der beste und der schlechteste Zug für A gewählt wird. Wenn A im Baum dran ist und es gibt mehrere Bewertungen, nimmt man die beste, wenn B dran ist, die schlechteste. Damit würde für Feld 5 eine sehr schlechte Bewertung kommen, weil es zum Sieg von B führt.
      Ok, dann ist meiner Version nix. Neue Baustelle :huh:
      Raum für Notizen

      -----------------------------------------------------------------------------------------------------

      -----------------------------------------------------------------------------------------------------

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

    • tschoeatsch schrieb:

      Wenn jetzt die Funktion zurück springt, muss ich doch trotzdem den Zug zurück setzen, um wieder an der Position zu sein, vor dem gerade geprüften Zug, um jetzt den nächst möglichen zu ziehen und prüfen zu lassen.

      Das hängt davon ab, wie du das Ziehen umsetzt. Bascom kann das glaube ich nicht, aber richtig wäre es so:
      call pruefe_zug(sp_r OR aktueller_Zug, sp_g)
      damit wäre der eher hypothetisch, der würde nur geprüft. Damit ist er in der aktuellen Ebene nicht ausgeführt. Das Programm weiß aber, welcher Zug dran war und kann die zurückgegebene Bewertung diesem zuordnen. Und dann einfach den nächsten auswählen.
      Du kannst das so machen, indem zu aktueller_Zug als Parameter übergibst und dann in dem Funktionsbody als erstes setzt. Deswegen ist es auch einfacher, wenn immer der erste Parameter (Spieler) am Zug ist, dann kannst du den ver"OR"en, ohne erst zu fragen, wer dran ist.

      Ich sagte ja ganz zu Anfang, dass es etwas schwierig wird, das zu durchschauen. Hat man es mal gepackt, dann ergibt das sehr kompakten und leicht zu verstehenden Code. Und das Beste ist, bis auf die Funktionen pruefe_sieg und bewerte_zug allgemein verwendbar ist.
    • tschoeatsch schrieb:

      Natürlich muss ich auch die Züge vom 'Mensch' mit probieren
      ahh, jetzt verstehe ich, du bist noch beim ersten Zug...
      Es geht halt so dermaßen langsam, selbst ein schwacher Tiny hätte das schneller berechnet, als das Auge sehen kann.

      Lass dir die einzelnen Variablen auf die serielle schicken und rechne selber nach.
      Alternativ natürlich (was sonst) einen Programmablaufplan.
    • Hallo zusammen,
      ich verfolge das Thema schon eine ganze Weile und hab mir auch schon Gedanken bezüglich der Rekursion gemacht.
      Ich hatte das auch so verstanden, dann immer wenn man in die Ebene tiefer geht, dass dann die Rekursion aufgerufen wird.
      Also wenn z.B. der Computer am Zug ist und das wäre Zug n, dann wäre der Mensch dann als Nächster dran und das wäre Zug n+1, dann wieder der Computer n+2 usw.
      Der Wert n wäre also die Tiefe und damit ein Rekursiver Aufruf der Funktion.

      Wenn jetzt aber nur auf einer Ebene, also nur der aktuelle Zug zu bewerten ist, bräuchte man doch gar keine Rekursion.
      Oder habe ich da was falsch verstanden?
    • Hallo Mitch,
      die Bewertung der aktuell möglichen Felder ergibt sich erst, wenn man sich ansieht, was der Gegener dann macht. Und auf dessen Zug kann man ja selber wieder ziehen usw. Das ist die rekursive Bewertung der Züge.
      Es kann auch sein, dass das Besetzen eines Feldes jetzt einen viel niegrigere Bewertung hat als später, wo das gleiche Feld evtl. der Siegeszug ist.