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!

    • Ich komm so nicht weiter, der Biergartenbesuch hat in der Richtung auch nix gebracht (in meiner Verzweiflung probier' ich halt diverse Möglichkeiten aus). Ich werde jetzt mal ein Minimalprogramm probieren, das mit Rekursion auch alle möglichen Züge durch spielt (ohne jetzt was zu bewerten). Wenn ich das geschafft habe, bin ich ein großes Stück weiter.

      @Michael es geht so langsam, weil in der Ausgabe (die die Leds ansteuert) ein wait 1 drin steht, damit man die Züge verfolgen kann. Das werd' ich dann, wenn wirklich alle Züge probiert werden, reduzieren oder gar entfernen, damit der Zug nicht abendfüllend wird :D
      Raum für Notizen

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

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

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

    • mac5150 schrieb:

      tschoeatsch schrieb:

      Ich werde jetzt mal ein Minimalprogramm probieren, das mit Rekursion auch alle möglichen Züge durch spielt (ohne jetzt was zu bewerten)
      Hi Mike,
      Rekursion wird doch gerade zum Bewerten genutzt.

      LG
      Mathias
      Da hast du schon recht, aber meine Rekursion funktioniert halt noch nicht. Irgendwo hab' ich wohl einen fetten Denkfehler drin, das es an bascom liegt, schließ ich erst mal aus.
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Ok, die Rekursion scheint jetzt alle Möglichkeiten zu erreichen. Es schaut bisschen so aus, wie zum Ende des Films 'war games'


      ok, nur ein bisschen, zerplatzt ist noch nix 8o

      BASCOM-Quellcode

      1. 'main
      2. Sp_r.15 = 1 'bit15 von Spieler rot zur Unterscheidung setzen
      3. Cs = 1
      4. Gosub Init_max7219
      5. Call Anzeige(sp_r , Sp_g )
      6. Do
      7. For N = 0 To 8
      8. Sp_r.n = 1 'erster Zug
      9. Incr Zug_tiefe
      10. Call Anzeige(sp_r , Sp_g)
      11. Call Rekursion(sp_g , Sp_r) 'Zugbaum durch gehen, Grün macht den nächsten Zug
      12. Sp_r.n = 0 'Zug zurück setzen
      13. Decr Zug_tiefe
      14. Next N
      15. Stop
      16. Loop
      17. End
      18. 'subs
      19. Sub Rekursion(byval A As Word , Byval B As Word) 'Spieler A ist am Zug
      20. Local M As Byte 'Zähler
      21. For M = 0 To 8 'Spielfeldstellen durch gehen
      22. If A.m = 0 And B.m = 0 Then 'Spielfeldstelle frei?
      23. A.m = 1 'besetzen
      24. Incr Zug_tiefe
      25. Call Anzeige(a , B)
      26. Call Rekursion(b , A) 'durch Vertauschen von A und B ist der andere am nächsten Zug
      27. A.m = 0 'Zug zurück nehmen
      28. Decr Zug_tiefe
      29. End If
      30. Next M 'nächste Spielfeldstelle nehmen
      31. End Sub
      32. Sub Anzeige(byval A As Word , Byval B As Word )
      33. Local Temp As Word
      34. Dat(0).7 = R_am_zug : Dat(0).6 = G_am_zug
      35. If A.15 = 0 Then 'bit15 gesetzt, dann a = Spieler rot, b = Spieler grün
      36. Temp = A : A = B : B = Temp 'Daten vertauschen
      37. End If
      38. Dat(0).5 = A.2 : Dat(0).3 = A.1 : Dat(0).1 = A.0
      39. Dat(0).4 = B.2 : Dat(0).2 = B.1 : Dat(0).0 = B.0
      40. Dat(1).5 = A.5 : Dat(1).3 = A.4 : Dat(1).1 = A.3
      41. Dat(1).4 = B.5 : Dat(1).2 = B.4 : Dat(1).0 = B.3
      42. Dat(2).5 = A.8 : Dat(2).3 = A.7 : Dat(2).1 = A.6
      43. Dat(2).4 = B.8 : Dat(2).2 = B.7 : Dat(2).0 = B.6
      44. Digit = 1
      45. Shiftout P_out , P_clock , Digit , 1
      46. Shiftout P_out , P_clock , Dat(0) , 1
      47. Cs = 0
      48. Cs = 1
      49. Digit = 2
      50. Shiftout P_out , P_clock , Digit , 1
      51. Shiftout P_out , P_clock , Dat(1) , 1
      52. Cs = 0
      53. Cs = 1
      54. Digit = 3
      55. Shiftout P_out , P_clock , Digit , 1
      56. Shiftout P_out , P_clock , Dat(2) , 1
      57. Cs = 0
      58. Cs = 1
      59. End Sub
      Alles anzeigen
      Ich hab' den Tipp von @hero umgesetzt und dem Spieler rot als Erkennung das bit15 gesetzt. Die sub Rekursion bekommt 2 words übergeben, das erste davon ist der Spieler, der jetzt einen Zug macht. Durch Vertauschen der words bei dem erneuten Aufruf wechseln sich die Spieler ab.
      Jetzt geht's ans Bewerten der Züge, mein bisheriger Plan war ja nix und jetzt steh' ich wieder planlos da. Ich muss doch jetzt vom tiefsten Zug immer weiter zurück nach oben gehen und die Bewertung mit ziehen, oder ist das schon mein nächster Denkfehler?
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Neuer Gedankengang:
      Ich lege 2 arraya(9) an, ein min(9) und ein max(9). Jeder Zug wird geprüft auf Gewinn, dann kommt in max() ein Wert (10-Zugtiefe) rein, aber nur, wenn dieser Wert größer ist als der bisherige Inhalt. Bei Verloren kommt in min() ein Wert (-10+Zugtiefe) rein, aber nur, wenn dieser Wert kleiner als der vorherige Inhalt ist. Dann kann als max() der größte Wert 10 sein, das heißt mit diesem Zug kann der Computer sofort gewinnen, als minimaler Wert bei min() kann dann -9 drin stehen, das heißt nachdem der Computer gezogen hat, kann der Gegner mit diesem Zug gewinnen. Ich muss also, um den besten Zug zu ermitteln, die Absolut-Werte vergleichen und den Zug mit dem höchsten Absolut-Wert wählen. Ganz einfach, eigentlich :D
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Der Thread ist ja jetzt schon ganz schön lang. Irgendwo kam doch schon einmal die Info, dass vor der ganzen Rechnerei erst mal zwei Dinge geprüft werden sollten:
      1. Kann ich mit dem anstehenden Zug das Spiel gewinnen?
      2. gibt es einen Zugzwang, damit ein Sieg des Gegners im nächsten Zug abgewendet wird
      Erst danach kann man meiner Meinung nach weiterarbeiten.

      Gruß Christian
      Wenn das die Lösung ist, möchte ich mein Problem wieder haben.
    • Mitch64 schrieb:

      Alternativ ist auch eine globale Variable möglich.
      so ist mein Plan


      ceperiga schrieb:

      Der Thread ist ja jetzt schon ganz schön lang. Irgendwo kam doch schon einmal die Info, dass vor der ganzen Rechnerei erst mal zwei Dinge geprüft werden sollten:
      1. Kann ich mit dem anstehenden Zug das Spiel gewinnen?
      2. gibt es einen Zugzwang, damit ein Sieg des Gegners im nächsten Zug abgewendet wird
      Erst danach kann man meiner Meinung nach weiterarbeiten.

      Gruß Christian
      genau, das wird ja auch so gemacht. Nur wenn mit diesem einen Zug nicht gewonnen oder ein Verlieren verhindert wird, wird tiefer gegangen. Das Erkennen des Zugzwanges geht ja nur, wenn ich die Möglichkeiten des Gegners nach meinem Zug erkunde.
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Ich krieg's nicht hin a_56_df238249 Ich hab' also eine Funktion, die für einen Spieler die Gewinnsituation prüft. Und ich hab' die Rekursion, die sich durch alle möglichen Züge durch kämpft. Wo es hängt, ist den besten Zug zu erkennen. Dieses minmax-Verfahren. Mal eine Spielsituation:
      Ich fange an und setzte in die Mitte
      . . .
      . x .
      . . .
      der Komputer findrt nix schlimmes und setzt
      . . o
      . x .
      . . .
      ich setze auf
      . . o
      . x .
      . . x
      wenn jetzt die Rekursion los läuft, würde der Computer probehalber
      . o o
      . x .
      . . x
      setzen und eine Stufe tiefer mal auf
      x o o
      . x .
      . . x
      kommen, was ihn dann alarmiert, weil der Gewinncheck die 3 Kreuze findet. Diese 3 Kreuze findet er bei 5 weiteren Kombinationen mit der gleichen Suchtiefe. Wie mach ich das jetzt für den Computer klar, dass er als nächsten Zug links oben setzen muss, um meinen Sieg zu verhindern?
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Ok, minmax schaff ich nicht umzusetzen, dann mach ich mir meine eigene 'Tschoeatsche Gewinnformel'. Die geht so:
      der Komputer macht einen Probezug, der wird auf Gewinn überprüft, wenn ja, wird dem Element des 'Ergebnisarrays' für dieses Feld ein Wert 20 zugewiesen. Ist es kein 'Sofortgewinn, wird in die Rekursion gesprungen. Da wird mit dem gegnerischen Stein ein 2.Zug probiert. Gewinnprobe, liegt ein Gewinn vor, wird dem 'Ergebnisarrayplatz' für diese Spielfeldstelle der Wert 20-Zugtiefe=19 zugewiesen. Kein Gewinn nur der Wert 10-Zugtiefe und es wird in die Rekursion gesprungen. Bei jedem Sprung wird die Spielerfarbe für den nächste Zug gewechselt und die Zugtiefe erhöht. Vergleicht man mein oben angeführtes Beispiel, dann hätte nach 1 Zugtiefe Ergebnis(1), das rote o den Wert 10 und Ergebnis(2), das rote x den Wert 19. Bei der Rekursion wird dem Ergebnis nur dann ein Wert zugewiesen, wenn der vorherige kleiner war. Im dem array stehen dann nach dem Durchprobieren aller Züge die maximal-Werte drin, die sich irgendwann einmal ergeben haben. Jetzt den Maximalwert von Ergebnis() finden und der index gibt die Stelle für den anstehenden, optimalen Zug wieder.
      Dateien
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Hi
      Ich habe mir schon folgendes Vorgehen überlegt.
      Wenn der Computer am Zug ist und er den Stein setzen soll, analysiert er das Spielfeld in 3 Schritten

      1. Er prüft, ob er irgendwo eine eigene Reihe vervollständigen kann um den Gewinn zu erreichen. Dann Stein dort setzen. Weitere Analyse würde entfallen. Spiel beendet

      2. Trifft 1. nicht zu folgt folgende Prüfung: Alle Reihen prüfen, ob der Gegner irgendwo eine Reihe vervollständigen könnte, dann Gegner blockieren indem er einen Stein in seine Reihe setzt. Weitere Analyse würde entfallen. Der Gegner wäre dran

      3. Trifft 1. und 2. nicht zu, durchsucht der Computer das Spielfeld, wo er überhaupt noch komplette Reihen setzen könnte. Dabei ist zu beachten, dass es Felder gibt, an deren Stelle sich gleich 2, 3 oder sogar 4 mögliche Reihen ergeben könnten. Es ist die Steinposition vorzuziehen, an der möglichst viele Reihen ermöglicht werden.

      Hierzu kleines Beispiel.
      Der Computer soll das Spiel eröffnen und den ersten Stein setzen.
      Würde er oben Mitte setzen, hätte er für 2 Reihen gleichzeitig bereits den 1. Stein gesetzt.
      .x.
      ...
      ...

      Würde der Computer eine Ecke nehmen, hätte er gleichzeitig 3 Reihen angefangen. Dieser Zug wäre natürlich besser
      x..
      ...
      ...
      Dann könnte noch die Mitte/Mitte gesetzt werden. In dem Fall wären gleichzeitig 4 Reihen begonnen. Das wäre noch besser.
      ...
      .x.
      ...

      Nach diesem Schema würde das ganze ohne Rekursion funktionieren. Ich tue mich da auch schwer, die Daten zu verwalten, wenn ich alle Züge durch alle Ebenen vorausberechnen wollte.

      Diese Wertung wo der Stein platziert wird, kann auch bei 2. angewendet werden. Mann kann schauen, ob man vielleicht gleich mehrere mögliche Reihen des Gegners blockieren kann.

      Eine Voraus-Berechnung würde in diesem Fall natürlich nicht statt finden. Man geht ja nur vom aktuellen Stand aus.

      Mitch
    • Ich möchte hier mal meinen Software-Stand den interessierten Lesern zeigen.
      Dazu muss ich noch folgendes sagen.

      Das Programm ist für den Simulator konzipiert, erfordert also keine Hardware. Eingaben und Ausgaben werden über das Bascom-Terminal
      im Simulator abgewickelt. Das hat den Vorteil, dass jeder den Code direkt ausprobieren kann.
      Sollten Eingaben nicht angenommen werden, drauf achten, dass das Terminal (UART0) den Focus hat.

      Das Programm selbst ist als Statemachine aufgebaut, dadurch fallen verschachtelte Schleifen weg und der Code wird übersichtlicher.
      Außerdem kann der Programmablauf besser kontrolliert und erweitert/geändert werden.

      Was noch nicht geht:
      Der Computer setzt noch keinen Stein und macht auch keine Analyse. Er übergibt die Kontrolle direkt wieder dem Spieler. Das ist im Moment so, um dem Programm-Ablauf zu testen.

      Was geht:
      Spielstein kann ausgewählt werden und wer das Spiel eröffnen soll. Gewinnprüfung.

      Viel Spaß beim probieren

      Ach ja, Kritik und Lob am Programmierstiel und Lösungsansatz erwünscht.
      Dateien
    • tschoeatsch schrieb:

      Vergleicht man mein oben angeführtes Beispiel, dann hätte nach 1 Zugtiefe Ergebnis(1), das rote o den Wert 10 und Ergebnis(2), das rote x den Wert 19.
      Bedeutet das, dass du den nächsten o auf das Feld setzen würdest, welches x den Wert 19 bringen würde, oder welches Feld würde ausgewählt?

      Mitch64 schrieb:

      3. Trifft 1. und 2. nicht zu, durchsucht der Computer das Spielfeld, wo er überhaupt noch komplette Reihen setzen könnte. Dabei ist zu beachten,
      dass es Felder gibt, an deren Stelle sich gleich 2, 3 oder sogar 4
      mögliche Reihen ergeben könnten. Es ist die Steinposition vorzuziehen,
      an der möglichst viele Reihen ermöglicht werden.
      ...

      Nach diesem Schema würde das ganze ohne Rekursion funktionieren. Ich tue
      mich da auch schwer, die Daten zu verwalten, wenn ich alle Züge durch
      alle Ebenen vorausberechnen wollte.
      Mit dieser Vorgehensweise wirst du aber nicht weit kommen, da man das leicht in eine Falle (Zwickmühle) leiten kann. Und die erkennst du erst, wenn es zu spät ist.
    • hero schrieb:

      Bedeutet das, dass du den nächsten o auf das Feld setzen würdest, welches x den Wert 19 bringen würde, oder welches Feld würde ausgewählt?
      Die Stelle, an der das x steht, hätte für den Computer den Wert 19 und somit den höchsten Wert. Also würde der Computer sein o dort setzen.

      Ich habe jetzt das minmax-Verfahren wohl geschafft. Es tut zumindest so ^^ Kann es sein, das dieses System nicht optimal spielt, also auch verlieren kann. Wenn der Mensch beginnt, sind für den Computer alle 8 freien Felder gleichwertig, egal, wo der Mensch gesetzt hat.
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Was ist aber, wenn der Spieler gerne das O nehmen will?
      Ich hab bei meinem Programm (ok das ist nicht das was du möchtest) über die Steine bestimmt wer anfängt.
      Da O vor X kommt fängt also immer der an der das O hat.
      Bei mir läuft das ganz auch über ein Array(9)
      Array(x) = 0 = Feld frei
      Array(x) = 1 = Spieler 1 hat das Feld belegt
      Array(x) = 2 = Computer oder Spieler 2 hat das Feld belegt
      Somit ist egal wer welchen Stein hat.

      tschoeatsch schrieb:

      Wenn der Mensch beginnt, sind für den Computer alle 8 freien Felder gleichwertig, egal, wo der Mensch gesetzt hat.
      Es gibt 5 "wichtige" Felder die geprüft werden sollten. Das sind die 4 Ecken und die Mitte. Jetzt musst du (der Computer) einen Zug machen der dem Spieler den nächsten Zug "versaut". Setzt der Spieler in einer der Ecken würde ich in der Mitte setzen. Setzt der Spieler in der Mitte wären dann für den Computer die Ecken wichtig.
      Eine Lösung habe ich nicht, aber mir gefällt Ihr Problem.
    • djmsc schrieb:

      Es gibt 5 "wichtige" Felder die geprüft werden sollten.

      Ok, sind das jetzt Erfahrungen oder kann mann das auch berechnen, eben durch minmax-Methode?
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • djmsc schrieb:

      Es gibt 5 "wichtige" Felder die geprüft werden sollten. Das sind die 4 Ecken und die Mitte. Jetzt musst du (der Computer) einen Zug machen der dem Spieler den nächsten Zug "versaut". Setzt der Spieler in einer der Ecken würde ich in der Mitte setzen. Setzt der Spieler in der Mitte wären dann für den Computer die Ecken wichtig.
      Ich habe mal den ganzen Baum in Excel gebaut, wobei ich alles weggelassen habe, was durch Rotation oder Spiegelung identisch ist. Und dabei sieht man, dass der Baum ziemlich simpel wird, wenn man in der Mitte anfängt. Danach gibt es nur zwei verschiedene Möglichkeiten. Ecke oder nicht Ecke. Da wir Menschen diese gleichen Stellungen sehr schnell überblicken, würde ich es als Computer meiden . Es gibt 7 Zwickmühlen für den ersten und 2 für den zweiten Spieler.

      Die Ecken als erstes Feld sehen schon besser aus, da gibt es immerhin 5 verschiedene Antwortmöglichkeiten. Die führen zu 15 Zwickmühlen für den ersten Spieler und nur 2 für den zweiten.

      Richtig kompliziert wird es, wenn man auf den anderen Randfelder anfängt. Da gibt es auch 5 Fortsetzungen, allerdings ist danach fast nichts spiegelbildlich. Und da gibt es 40 Zwickmühlen für den ersten und 23 für den zweiten Spieler.

      Ob der MiniMax Algorhitmus das auch so sieht, kann ich nicht sagen. Jedenfalls macht es meiner Meinung nach überhaupt nur Sinn, diese Zwickmühlen zu finden. Alles andere wird der Mensch nur aus Versehen verlieren.


      tschoeatsch schrieb:

      Kann es sein, das dieses System nicht optimal spielt, also auch verlieren kann. Wenn der Mensch beginnt, sind für den Computer alle 8 freien Felder gleichwertig, egal, wo der Mensch gesetzt hat.
      Naja, der findet halt immer eine Möglichkeit, im dritten Zug einen Sieg zu erringen. Natürlich wird der Gegner das nicht zulassen, aber je nachdem wie du das bewertest, ist das bei 10-Zugtiefe immer gleich. Schau doch mal, ob er die Zwickmühlen bemerkt.
    • Nach meinen Recherchen im net sollte der minmax optimal Spielen, also mindestens Unentschieden. Ich hab' mir jetzt eingebildet, ich hätte es geschafft, aber Pustekuchen. Wenn ich beginne und in der Mitte setze, dann rechnet der Computer die Wertung für die umliegenden Felder aus. Das sollte doch punktsymmetrisch sein. Bei mir leider nicht :cursing: . Und ich hab' gedacht, ganz so schwer kann's doch nicht sein...
      Raum für Notizen

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

      -----------------------------------------------------------------------------------------------------
    • Ich hänge mal wieder fest. Wenn ich als Mensch den mittleren Stein als ersten Zug setze, bekommt der Computer, der in der Reihenfolge
      2 1 0
      5 4 3
      8 7 6
      also von rechts oben nach links, von rechts mitte nach links und rechts unten nach links auf freie Felder prüft und ggf setzt, unterschiedliche Bewertungen für eigentlich symmetrisch liegende Felder heraus.
      Das schaut dann so aus
      -13 -13 -13
      0 -30 -13
      0 0 0.
      -30 bedeutet, Feld ist besetzt und die restlichen Werte geben die Wertung ab, je höher, umso besser, wenn man diesen Platz besetzt. Nachdem die Abarbeitung für das Suchen der höchsten Wertung in der gleichen Reihenfolge abläuft, wird vom Computer links mitte gesetzt. Nur, wo soll ein Unterschied sein, zwischen rechts oben und links unten, oder links mitte und rechts mitte? Wenn ich die Abarbeitung in meinem Programm umkehre, kehren sich auch die Wertungen um. Also ist was in meinem Programm faul, aber ich find's nicht ;( Hat hier jemand Lust, mal drüber zu schauen, speziell ob ich mit meinem Verfahren auch alle Zugmöglichkeiten erwische, oder ob da ein Denkfehler drin steckt?
      Das Hauptprogramm

      BASCOM-Quellcode

      1. Do
      2. Sp_r = &B1000000000000000 : Sp_g = 0 'Spieler löschen
      3. R_am_zug = 0 : G_am_zug = 0 'Led Zuganzeige = aus
      4. Call Anzeige(sp_r , Sp_g )
      5. Do
      6. Gosub Warte_auf_taste
      7. If Key = &B100_000000000 Then
      8. R_am_zug = 1 : G_am_zug = 0
      9. End If
      10. If Key = &B001_000000000 Then
      11. R_am_zug = 0 : G_am_zug = 1
      12. End If
      13. Loop Until Key > &B100_000_000
      14. 'Spiel beginnt
      15. Call Anzeige(sp_r , Sp_g )
      16. Do
      17. If R_am_zug = 0 Then 'Spieler grün am Zug
      18. If Zug_noch_moeglich(sp_r , Sp_g) = 1 Then 'Zug noch möglich
      19. Zug_ok = 0
      20. Do
      21. Check_1 = Sp_r Or Sp_g
      22. Gosub Warte_auf_taste
      23. Check_1 = Check_1 And Key
      24. If Check_1 = 0 Then Zug_ok = 1 'Test ob Stelle frei
      25. If Key > &B100_000_000 Then Zug_ok = 0 'ungültige Taste
      26. Loop Until Zug_ok = 1
      27. Sp_g = Sp_g Or Key 'Spieler grün aktualisieren
      28. R_am_zug = 1 : G_am_zug = Not R_am_zug 'Wer macht den nächsten Zug anzeigen
      29. End If
      30. Else 'Spieler rot am Zug
      31. If Zug_noch_moeglich(sp_r , Sp_g) = 1 Then 'Zug noch möglich
      32. ' If Sp_r = &B1000000000000000 And Sp_g = 0 Then 'Spieler rot fängt an
      33. ' Gosub Zug_auslosen
      34. ' Else
      35. Cls
      36. Zwischenergebnis = -30
      37. For N = 0 To 8
      38. Ergebnis(n) = -30 'Ausgangswerte setzen
      39. Next N
      40. For N = 0 To 8
      41. If Sp_g.n = 0 And Sp_r.n = 0 Then 'nur für freie Felder
      42. Sp_r.n = 1 'Zug probieren
      43. If Teste_auf_gewinn(sp_r) = 0 Then
      44. Ergebnis(n) = Rekursion(sp_g , Sp_r) 'Zug auf Gewinn prüfen und ggf. Zugbaum durch gehen, grün macht den nächsten Zug
      45. Else
      46. Ergebnis(n) = Teste_auf_gewinn(sp_r)
      47. End If
      48. Sp_r.n = 0 'Zug zurück nehmen um anderen Zug zu probieren
      49. End If
      50. Next N
      51. Locate 1 , 1 : Lcd Ergebnis(2)
      52. Locate 1 , 5 : Lcd Ergebnis(1)
      53. Locate 1 , 10 : Lcd Ergebnis(0)
      54. Locate 2 , 1 : Lcd Ergebnis(5)
      55. Locate 2 , 5 : Lcd Ergebnis(4)
      56. Locate 2 , 10 : Lcd Ergebnis(3)
      57. Locate 3 , 1 : Lcd Ergebnis(8)
      58. Locate 3 , 5 : Lcd Ergebnis(7)
      59. Locate 3 , 10 : Lcd Ergebnis(6)
      60. For N = 0 To 8 'höchstes Ergebnis finden
      61. If Zwischenergebnis < Ergebnis(n) And Ergebnis(n) > -20 Then
      62. Zwischenergebnis = Ergebnis(n)
      63. Bester_zug = N
      64. End If
      65. Next N
      66. 'Zug ausführen
      67. Sp_r.bester_zug = 1 'Spielstein setzen
      68. ' End If
      69. R_am_zug = 0 : G_am_zug = Not R_am_zug 'Wer macht den nächsten Zug anzeigen
      70. End If
      71. End If
      72. Call Anzeige(sp_r , Sp_g )
      73. Call Check_gewinn(sp_r , Sp_g)
      74. Loop Until Gewinn_r = 1 Or Gewinn_g = 1 Or Zug_noch_moeglich(sp_r , Sp_g) = 0
      75. If Gewinn_r = 1 Then
      76. For N = 0 To 10
      77. Waitms 200
      78. Sp_r = Sp_r - Gewinn_stellung
      79. Call Anzeige(sp_r , Sp_g )
      80. Waitms 200
      81. Sp_r = Sp_r + Gewinn_stellung
      82. Call Anzeige(sp_r , Sp_g )
      83. Next N
      84. End If
      85. If Gewinn_g = 1 Then
      86. For N = 0 To 10
      87. Waitms 200
      88. Sp_g = Sp_g - Gewinn_stellung
      89. Call Anzeige(sp_r , Sp_g)
      90. Waitms 200
      91. Sp_g = Sp_g + Gewinn_stellung
      92. Call Anzeige(sp_r , Sp_g)
      93. Next N
      94. End If
      95. Gewinn_r = 0 : Gewinn_g = 0
      96. Wait 2
      97. Loop
      98. End
      Alles anzeigen


      In Zeile 40 ist die Reihenfolge, wie die Züge durch probiert werden. Die gleiche Reihenfolge habe ich in der Rekursion.

      BASCOM-Quellcode

      1. Function Rekursion(byval A As Word , Byval B As Word)as Integer 'Spieler A ist am Zug
      2. Local M As Byte
      3. Local Wertung As Integer , Wertung_1 As Integer , Minimum As Integer , Maximum As Integer
      4. Wertung = 0 : Minimum = 100 : Maximum = -100
      5. For M = 0 To 8 'Spielfeldstellen durch gehen
      6. If A.m = 0 And B.m = 0 Then 'Spielfeldstelle frei?
      7. A.m = 1 'Zug probieren
      8. Wertung = Teste_auf_gewinn(a)
      9. If Wertung = 0 Then
      10. Wertung_1 = Rekursion(b , A) 'durch Vertauschen von A und B ist der andere am nächsten Zug
      11. If A.15 = 0 Then 'die Wertung_1 kommt durch Bewertung eines eigenen Zuges
      12. If Maximum < Wertung_1 Then
      13. Maximum = Wertung_1
      14. End If
      15. Wertung = Maximum
      16. Else 'die Wertung_1 kommt durch Bewertung eines gegnerischen Zuges
      17. If Minimum > Wertung_1 Then
      18. Minimum = Wertung_1
      19. End If
      20. Wertung = Minimum
      21. End If
      22. End If
      23. A.m = 0 'Zug zurück nehmen, um nächsten Zug zu probieren
      24. End If
      25. Next M
      26. If Wertung < 0 Then Incr Wertung
      27. If Wertung > 0 Then Decr Wertung
      28. Rekursion = Wertung
      29. End Function
      Alles anzeigen
      Noch der Teil, um einen Sofortgewinn zu erkennen

      BASCOM-Quellcode

      1. Function Teste_auf_gewinn(byval A As Word)as Integer
      2. Local Check As Word
      3. Local Wertung As Integer
      4. Wertung = 0
      5. Check = A And &B111_000_000
      6. If Check = &B111_000_000 Then Wertung = 1
      7. Check = A And &B111_000_000
      8. If Check = &B111_000_000 Then Wertung = 1
      9. Check = A And &B000_111_000
      10. If Check = &B000_111_000 Then Wertung = 1
      11. Check = A And &B000_000_111
      12. If Check = &B000_000_111 Then Wertung = 1
      13. Check = A And &B100_100_100
      14. If Check = &B100_100_100 Then Wertung = 1
      15. Check = A And &B010_010_010
      16. If Check = &B010_010_010 Then Wertung = 1
      17. Check = A And &B001_001_001
      18. If Check = &B001_001_001 Then Wertung = 1
      19. Check = A And &B100_010_001
      20. If Check = &B100_010_001 Then Wertung = 1
      21. Check = A And &B001_010_100
      22. If Check = &B001_010_100 Then Wertung = 1
      23. If A.15 = 1 Then
      24. Wertung = Wertung * 20
      25. Else
      26. Wertung = Wertung * -20
      27. End If
      28. Teste_auf_gewinn = Wertung
      29. End Function
      30. Function Zug_noch_moeglich(byval A As Word , Byval B As Word)
      31. Local Check As Word
      32. Check = A Or B
      33. If Check < &B1000000111_111_111 Then
      34. Zug_noch_moeglich = 1
      35. Else
      36. Zug_noch_moeglich = 0
      37. End If
      38. End Function
      Alles anzeigen
      Ich denke schon, dass ich das minmax verstanden habe und entsprechend umgesetzt. Aber wie es zu unsymmetrischen Wertungen kommt, kann ich mir nicht erklären und das sollte ja auch nicht so sein a_28_2c02f089
      Raum für Notizen

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

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