Computer (KI) für Tic Tac Toe / Mühle / Schach / 4 Gewinnt mit dem Minimax-Algorithmus & Alpha-Beta-Suche

      Computer (KI) für Tic Tac Toe / Mühle / Schach / 4 Gewinnt mit dem Minimax-Algorithmus & Alpha-Beta-Suche

      Computer (KI) mit Hilfe des Minimax-Algorithmus erstellen



      Inhalt:
      1.0 Vorwort
      2.0 Der Minimax-Algorithmus
      2.1 Was ist der Minimax-Algorithmus
      2.2 Wo kann ich den Minimax-Algorithmus anwenden
      2.3 Wie funktioniert der Minimax-Algorithmus
      2.4 Suchbäume
      2.5 Erweiterung durch Tiefensuche
      2.5 Erweiterung durch Alpha-Beta-Suche
      3.0 Die Erstellung der KI
      3.1 Spiel-Engine
      3.2 Benutzte Scripte kurz erklärt
      3.4 Pseudo Code
      3.5 Fertige GML Scripte
      4.0 Zugbeispiel für Tic Tac Toe
      5.0 Downloads
      6.0 Nachwort



      1.0 Vorwort

      Ein Spiel wie Tac Tac Toe für 2 Spieler zu programmieren ist leicht, jedenfalls für die Meisten von uns.
      Man platziert 9 Steine und lässt abwechselnd Spieler 1 und 2 auf die Steine klicken. Gewonnen hat, wer als erstes 3 Steine in einer Reihe hat.
      Doch wie programmiert man für Tic Tac Toe einen Computergegner ? Man könnte den Computer natürlich zufallsmäßig einen Stein zuteilen, aber das wäre zu langweilig.
      Der Computergegner soll schließlich schlau handeln und auch mal gewinnen, bzw. uns vom Sieg abhalten.
      Eine zweite Möglichkeit wäre eine Reihe von IF-Abfragen doch dies kann ziemlich mühsam sein, denn Tic Tac Toe hat viele verschiedene Spielverläufe.
      Um genau zu sein insgesamt 255.168! Das könnte also Arbeit bedeuten.

      Das ganze lässt sich jedoch viel einfacher lösen. Und zwar mit dem Minimax-Algorithmus, welchen ich euch heute vorstellen möchte.
      Das Tutorial ist jedoch ziemlich lang, da ich es möglichst verständlich erklären möchte. Ganz unten findet ihr ein Beispielprojekt für GM Studio.
      Wenn es eine große Nachfrage nach einem Video gibt, dann könnte ich das Tutorial evtl auch in Videoform anbieten.
      Jedenfalls wünsche ich euch jetzt viel Spaß beim Lesen.


      2.0 Der Minimax-Algorithmus
      2.1 Was ist der Minimax-Algorithmus

      Das Prinzip hinter dem Minimax-Algorithmus lässt sich ganz einfach erklären:
      Es ist ein Algorithmus, um die beste Spielstrategie zu ermitteln.


      2.2 Wo kann ich den Minimax-Algorithmus anwenden

      Der Algorithmus lässt sich bei jedem Spiel mit perfekter Information und einer Spielerzahl von 2 benutzen.
      Perfekte Information bedeutet, dass man während des gesamten Spieles immer den Zug des Gegners voraussagen und Kontern könnte.
      Das ist zum Beispiel bei Schere-Stein-Papier oder auch bei Kartenspielen nicht der Fall.
      Spiele die man mit dem Algorithmus programmieren könnte wären zum Beispiel:
      - Tic Tac Toe
      - Mühle
      - Schach
      - Nim
      - Dame
      - 4 Gewinnt
      - Reversi
      - usw

      2.3 Wie funktioniert der Minimax-Algorithmus

      Es gibt 2 Spieler, wobei der ausführende Spieler als MAX bezeichnet wird und der Gegner als MIN.
      Der Algorithmus soll nun die maximale Gewinnchance für den MAX-Spieler berechnen und die minimalste Gewinnchance für den MIN-Spieler.
      Daher auch der Name "Minimax". Wir möchten also berechnen, welcher Zug für den Computer am besten und für uns am schlechtesten ist.

      Um dies zu tun, muss der Computer vorher jeden möglichen Spielzug berechnen.
      Hierfür werden sogenannte "Suchbäume" benutzt. Der Baum startet oben mit 1 Knoten - der Ausgangssituation.
      Jeder mögliche Spielzug lässt darunter einen neuen Knoten entstehen. Wäre man zum Beispiel bei Tic Tac Toe als erster dran, hätte man 9 verschiedene Möglichkeiten.
      Setzt man jetzt sein Kreuz auf ein Feld, so hat man beim nächsten Zug 8 weitere Möglichkeiten, somit entstehen 8 weitere Knoten.
      Je weiter man also in den Spielbaum geht, desto mehr Knoten entstehen und desto mehr Rechenzeit wird benötigt.

      Jetzt wird immer abwechselnd ein Zug simuliert. Zu erst bestimmt der Computer den besten Zug (MAX), danach wird der schlechteste Zug (MIN) berechnet.
      Je höher ein Zug Zahlenmäßig bewertet wird, so besser ist er. Je niedrieger ein Zug bewertet wird, so schlechter ist er.
      Somit werden alle möglichen Züge abwechselnd berechnet, bis es keinen weiteren Zug mehr gibt.
      Der Computer geht außerdem immer davon aus, dass wir als Mensch keine Fehler und immer den besten Spielzug machen.


      2.4 Suchbäume

      Wir werden uns nun mal einen Suchbaum anschauen.



      Die blauen Kästchen bedeuten, dass der Computer am Zug ist (MAX). Die roten Kreise sind wir - der Gegner (MIN).
      Der Computer möchte nun für sich immer den besten Zug machen und für uns den schlechtesten.

      Das blaue Kästchen ganz oben ist die Ausgangssituation und der Computer möchte nun wissen, welchen Zug er spielen sollte.
      Die Zahlen ganz unten sind Endergebnisse:

      +1 = Der Computer hat gewonnen
      0 = Die Runde geht unentschieden aus
      -1 = Wir haben gewonnen

      Normalerweise würde jeder Zug mittel, gut oder sogar sehr gut bewertet werden.
      Dies wird bei TicTacToe aber nicht benötigt, da wir nur 3 Zustände kennen: Gewonnen, Unentschieden, Verloren.
      Bei Spielen mit vielen Entscheidungen wie zum Beispiel Schach würden wir viele verschiedene Werte bekommen
      und hätten dann zum Beispiel eine Wertung von -1000 bis +1000. Bei TicTacToe benötigen wir lediglich -1, 0 und +1.

      Der Computer möchte also zu einer 1 kommen.

      Wir achten jetzt erst einmal auf 2 Dinge:



      Hier wäre der Computer (MAX) am Zug - er möchte den besten Zug machen.
      Er schaut sich die beiden Möglichkeiten darunter an. Er könnte entweder unentschieden spielen oder aber gewinnen.
      Natürlich möchte er gewinnen. die 1 ist größer als die 0, also nimmt er die 1. Er MAXIMIERT den Zug.



      Das gleiche bei dem Knoten daneben. Da es nur zwei mal -1 gibt, ist hier das Maximale auch nur -1. Er hätte keine andere Wahl als zu verlieren.



      Jetzt wären wir am Zug (MIN).



      Wir als Spieler würden das niedriegste Ergebnis wählen. Denn das niedriegste (die -1) würde für uns den Sieg bedeuten.



      Nach dem Schema füllen wir nun den Suchbaum aus. Sobald wir uns in einem MAX-Bereich befinden ist der Computer an der Reihe und nimmt das höchste Ergebnis.
      Sind wir jedoch in einem MIN-Bereich wären wir am Zug und würden das niedrigste Ergebnis nehmen.



      Als letztes wird noch der gewählte Zug ganz oben eingetragen. (Das höchste von -1 und 1).



      Nun ist der beste Zug schon berechnet.



      Hätte er die linke Route genommen, hätten wir gewonnen.
      Der Computer nimmt jedoch die rechte Route und hat damit eine Gewinnchance.


      2.5 Erweiterung durch Tiefensuche

      Der Minimax-Algorithmus bringt leider ein großes Problem mit sich:
      Je mehr Zugmöglichkeiten es gibt, desto länger wird die Rechenzeit, um alle vorhandenen Züge zu berechnen.
      Bei kleinen Spielen wie Tic Tac Toe ist das eher ein kleines Problem, aber bei Spielen wie bei Schach, braucht man eine maximale Suchtiefe.

      Wenn ihr die oberen Bilder anschaut, dann werdet ihr grüne Zahlen an der linken Seite erkennen.
      Das ist die Tiefe des Suchbaumes. Je tiefer (je höher die Zahl), desto länger dauert die Berechnung.
      Eine Tiefensuche von 0 würde gar keinen Zug vorausberechnen, ein Wert von 1 würde nur den nächstbesten Zug berechnen.

      Ich habe hier mal ein Beispiel mit einem Tic Tac Toe Spiel gemacht, bei dem zwei Computer gegeneinander spielen:

      Tiefensuche von 0
      - Die Züge werden nicht berechnet -> Der Zug wird zufällig gewählt
      - Die Computer handeln nicht schlau

      Ergebnis:

      - Gewinne [Spieler 1]: 12
      - Gewinne [Spieler 2]: 14
      - Unentschieden: 4




      Tiefensuche von 1
      - Die Computer berechnen den nächstbesten Zug
      - Sie gewinnen selbstständig
      - Sie verhindern einen einfachen Sieg des Gegners
      - Sie können keine Zwickmühle vorraussagen [Zwickmühle = Man hat 2 Gewinnmöglichkeiten und der Gegner kann nur 1 blocken]

      Ergebnis:

      - Gewinne [Spieler 1]: 6
      - Gewinne [Spieler 2]: 7
      - Unentschieden: 17




      Tiefensuche von 5
      - Die Computer berechnen die nächsten 5 Züge
      - Sie berechnen soweit, sodass sie nie verlieren können
      - Sie spielen höchstens ein Unentschieden oder gewinnen (gegen menschliche Gegner)

      Ergebnis:

      - Gewinne [Spieler 1]: 0
      - Gewinne [Spieler 2]: 0
      - Unentschieden: 30




      Das Ziel ist es somit die Tiefensuche so einzustellen, dass die Computer schlau genug handeln.
      Sie darf aber auch nicht zu groß sein, damit die Berechnung nicht so lange dauert.


      2.6 Erweiterung durch Alpha-Beta-Suche

      Um die Suche noch besser zu machen gibt es die sogennante Alpha-Beta-Suche, auch Alpha-Beta-Pruning genannt.
      Bei diesem Vorgang werden die besten Ergebnisse in den Variablen Alpha und Beta gespeichert und werden bei Knoten verglichen.


      (Bild von Wikipedia)

      Wenn man sich hier den dritten Knoten (ganz rechts) anschaut, dann sieht man das Ergebnis der Alpha-Beta-Suche.
      Da 5 kleiner als 8 ist, wird der gesamte rechte Baum abgetrennt und ignoriert.
      Das heißt die Züge in dem Baum müssen nicht mehr beachtet werden und es wird Rechenzeit gespart.

      In unserem Beispiel prüft der Minimax-Algorithmus von links nach rechts.
      Das heißt, wenn die Knoten 5 und 8 getauscht werden würden, dann wären trotzdem beide Baume durchsucht worden.

      Anderes Beispiel:



      Der Knoten befindet sich im MIN-Bereich. Das heißt es wird das niedriegste Ergebnis gesucht.
      Als erstes wird die 4 gefunden. Das ist gut, denn dadurch fallen die nächsten Bäume raus, da sie größer als 4 sind.
      Wir können dadurch zwei ganze Bäume weglassen.



      Hier hätte es nicht ganz so gut funktioniert.
      Der Wert wird auf 5 gesetzt, wodurch der Knoten mit der 7 wegfällt (da 7 größer ist als 5).
      Allerdings ist die 4 noch kleiner als 5 und wird nun als neues kleinstes Ergebnis gesetzt.
      Jetzt muss trotzdem noch der Baum mit der 4 durchsucht werden.

      Deswegen sollte man seine Knoten vor der Suche sortieren, um die maximale Performance zu erreichen.
      Beim Schach haben die Figuren zum Beispiel unterschiedliche Prioritäten, sodass man die Züge vorher nach Wichtigkeit sortieren sollte.
      Darauf werde ich hier aber nicht näher eingehen. Vielleicht bei einem späteren Schach-Tutorial.


      3.0 Die Erstellung der KI
      3.1 Spiel-Engine

      So, nach der ganzen Theorie geht es jetzt darum die KI zu programmieren.
      Als erstes brauchen wir natürlich ein Spiel für das wir den Computer programmieren.
      Ich habe dafür eine simple Tic Tac Toe Engine gebastelt. Ihr könnte diese im Anhang runterladen.



      3.2 Benutzte Scripte kurz erklärt

      Die wichtigsten Dinge kurz erklärt:
      - Mit 'R' wird das Spiel neu gestartet
      - Tic Tac Toe hat 9 Felder. Diese werden in einer ds_list gespeichert. Sie haben entweder den Wert 0 (frei), 1 (Im Besitzt von Spieler 1) oder 2 (Im Besitz von Spieler 2). Sie sind von 0 bis 8 indexiert.
      - global.board ist das Spielbrett (die ds_list).
      - global.winner speichert den momentanen Gewinner (0 = Niemand, 1 = Spieler 1, 2 = Spieler 2)
      - global.activePlayer speichert den Spieler, welcher gerade an der Reihe ist.

      setOwner
      Ändert den Besitzer eines Spielsteines (token).

      getOwner
      Gibt den Besitzer eines Spielsteines (token) an.

      movesLeft
      Zählt die verbleibenden Züge. (0 bis 9)

      getEnemy
      Gibt den Gegner des aktuellen Spielers an.

      tokenClicked
      Wird ausgeführt, nachdem ein Spielstein (token) angeklickt wurde.

      checkWin
      Überprüft, ob jemand das Spiel gewonnen hat.

      computerMove
      Lässt den Computer einen Zug machen, welcher mit der Alpha Beta-Suche berechnet wird.

      alphabeta
      Führt den Minimax-Algorithmus mit AlphaBeta - Suche aus, um den besten Spielzug zu bestimmen.


      3.4 Pseudo Code

      Für unsere KI brauchen wir 2 Scripte.
      Der erste Teil heißt "computerMove" und der zweite Teil "alphabeta".
      alphabeta durchsucht die Knotenpunkte und computerMove führt später den besten Zug aus.

      Pseudo Code: computerMove

      Quellcode

      1. spielbrett = argument0
      2. player = argument1
      3. besterZug = -2 (-2 = Unbekannt, da die maximale Suchtiefe erreicht wurde, -1 = Verloren, 0 = Unentschieden, 1 = Gewonnen)
      4. WENN: Noch alle Züge vorhanden
      5. - DANN: 4 zurückgeben, script abbrechen (4 ist der Stein in der Mitte, welche die beste Wahl beim Start ist)
      6. LOOP durch das Spielbrett (ds_list) von 0 bis 8
      7. - WENN: Stein Nummer i noch frei ist
      8. - DANN:
      9. -- Stein dem Spieler geben
      10. -- ergebnisse = alphabeta(spielbrett, Gegner vom aktuellen Spieler, Suchtiefe, -2, 2)
      11. -- Stein wieder freigeben (Niemand besitzt ihn mehr)
      12. -- WENN: Ergebnisse > besterZug - DANN: besterZug = Ergebnisse
      13. LOOP ENDE
      14. Besten Zug ausführen


      Pseudo Code: alphabeta

      Quellcode

      1. tempBoard = argument0 //Speichert das aktuelle Spielbrett
      2. player = argument1 //Speichert abwechselnd den Min bzw. Max Spieler
      3. treeDepth = argument2 //Speichert die maximale Suchtiefe
      4. alpha = argument3 //Speichert den Alpha-Wert
      5. beta = argument4 //Speichert den Beta-Wert
      6. tempWinner = checkWin(tempBoard) //Überprüft, ob es einen möglichen Gewinner gibt
      7. WENN:
      8. Keine Züge mehr möglich sind ODER
      9. Es bereits einen Gewinner gibt ODER
      10. Die maximale Suchtiefe erreicht ist
      11. DANN:
      12. - ZugBewerten (In unserem Fall, ob gewonnen, verloren oder unentschieden gespielt wurde [oder ob die maximale Suchtiefe erreicht wurde])
      13. LOOP durch das Spielbrett (ds_list) von 0 bis 8
      14. - WENN: Stein Nummer i noch frei ist
      15. - DANN:
      16. -- Stein dem Spieler geben
      17. -- ergebnisse = alphabeta(spielbrett, Gegner vom Spieler, Suchtiefe-1, vorherigerAlphaWert, vorherigerBetaWert)
      18. -- Stein wieder freigeben (Niemand besitzt ihn mehr)
      19. -- WENN: Spieler = Aktiver Spieler
      20. -- DANN:
      21. --- WENN: ergebnisse > alpha - DANN: alpha = ergebnisse
      22. --- WENN: alpha >= beta - DANN: return beta
      23. -- SONST:
      24. --- WENN: ergebnisse < beta - DANN: beta = ergebnisse
      25. --- WENN: beta <= alpha - DANN: return alpha
      26. LOOP ENDE
      27. WENN: Spieler = Aktiver Spieler - DANN: return alpha SONST: return beta



      3.5 Fertige GML Scripte

      Wahrscheinlich seid ihr durch die Pseudo-Codes 0% schlauer geworden. Deshalb hier nochmal die fertige GML Version mit ein paar Kommentaren:

      computerMove

      GML-Quellcode

      1. /*
      2. Script by: Jan Ruprecht
      3. Script date: 03.03.2013
      4. Script description:
      5. Lässt den Computer einen Zug machen, welcher mit der Alpha Beta-Suche berechnet wird.
      6. Arguments:
      7. - argument0 = Spielbrett (ds_list)
      8. - argument1 = Aktueller Spieler
      9. Returns:
      10. None
      11. */
      12. var i, results, bestMove, choices, tempBoard, player;
      13. tempBoard = argument0 //Speichert das aktuelle Spielbrett
      14. player = argument1 //Speichert den Spieler, welcher am Zug ist
      15. bestMove = -2 //Der beste Zug ist momentan noch unbekannt. Er wird später einen der folgenden Werte annehmen:
      16. //-2 = Unbekannt [Da maximale Suchtiefe erreicht], -1 = Verloren, 0 = Unentschieden, 1 = Gewonnen
      17. //Wir wissen, dass der Stein in der Mitte die beste Möglichkeit ist, um das Spiel zu gewinnen (Stein mit tokenIndex 4).
      18. //Sollte das Brett noch leer sein, können wir uns die Suche sparen und den Computer direkt ziehen lassen.
      19. //Das heißt es wird keine Rechenzeit verschwendet, da wir so schon wissen, welcher der beste Zug ist.
      20. //Danach wird der Rest des Scriptes abgebrochen.
      21. if movesLeft(tempBoard) = 9
      22. {
      23. tokenClicked(4)
      24. exit
      25. }
      26. //Erstellt eine Liste mit den besten Zugmöglichkeiten.
      27. //Wenn es zum Beispiel 2 Züge gibt mit denen man gewinnen kann, wird ein zufälliger von den beiden ausgewählt
      28. choices = ds_list_create()
      29. //Ein Loop durch das gesamte Spielfeld (Feld 0-8) = 9 Wiederholungen
      30. for (i=0; i<ds_list_size(tempBoard); i+=1)
      31. {
      32. //Sollte das Feld noch nicht besetzt sein...
      33. if getOwner(tempBoard,i) = 0
      34. {
      35. //Das Feld dem aktuellen Spieler geben
      36. setOwner(tempBoard,i,player)
      37. //Das Ergebnis der AlphaBeta - Suche in der Variable 'results' speichern.
      38. //Die AlphaBeta - Funktion ist wie folgt aufgebaut:
      39. //argument0 = Spielbrett (ds_list)
      40. //argument1 = Gegner des aktuellen Spielers
      41. //argument2 = Maximale Suchtiefe des Spielbaumes [-1 heißt, dass es keine Begrenzung gibt und jeder Baum ganz abgesucht wird / jeder mögliche Zug berechnet wird]
      42. //argument3 = Start Alpha-Wert (-2)
      43. //argument4 = Start Beta-Wert (2)
      44. results = alphabeta(tempBoard,getEnemy(player),-1,-2,2)
      45. //Das benutzte Feld wieder frei machen (Niemand besitzt es mehr)
      46. setOwner(tempBoard,i,0)
      47. //Wenn das aktuelle Ergebnis besser ist als das letzte...
      48. if results > bestMove
      49. {
      50. //DANN:
      51. //Wird der beste Zug an das Ergebnis angepasst
      52. //Die Liste der Zugmöglichkeiten wird geleert
      53. //Der beste Zug wird in die Liste aufgenommen
      54. bestMove = results
      55. ds_list_clear(choices)
      56. ds_list_add(choices,i)
      57. }
      58. //SONST:
      59. //Wenn das aktuelle Ergebnis genausogut ist wie das vorhandene
      60. //DANN:
      61. //Wird es in die Liste der möglichen Züge aufgenommen
      62. else if results = bestMove then ds_list_add(choices,i)
      63. }
      64. }
      65. //Die Liste mit den Zugmöglichkeiten wird gemischt
      66. //Ein zufälliger Zug aus den besten Zugmöglichkeiten wird ausgewählt
      67. //Die Liste wird gelöscht, um den Speicher zu leeren
      68. //Der Zug wird mit der Funktion 'tokenClicked' für den Computer ausgeführt
      69. ds_list_shuffle(choices)
      70. bestMove = ds_list_find_value(choices,0)
      71. ds_list_destroy(choices)
      72. tokenClicked(bestMove)


      alphabeta

      GML-Quellcode

      1. /*
      2. Script by: Jan Ruprecht
      3. Script date: 03.03.2013
      4. Script description:
      5. Führt den Minimax-Algorithmus mit AlphaBeta - Suche aus, um den besten Spielzug zu bestimmen.
      6. Arguments:
      7. - argument0 = Spielbrett (ds_list)
      8. - argument1 = Spieler (Gegner vom ziehenden Spieler bei der 1. Suche, sonst wechselnder Spieler)
      9. - argument2 = Maximale Suchtiefe des Spielbaumes [-1 heißt, dass es keine Begrenzung gibt und jeder Baum ganz abgesucht wird / jeder mögliche Zug berechnet wird]
      10. - argument3 = Alpha-Wert (-2 bei der 1. Suche)
      11. - argument4 = Beta-Wert (2 bei der 1. Suche)
      12. Returns:
      13. Je nach Spieler wird entweder der Alpha-Wert oder der Beta-Wert wiedergegeben.
      14. */
      15. var i, results, tempBoard, player, treeDepth, alpha, beta, tempWinner;
      16. tempBoard = argument0 //Speichert das aktuelle Spielbrett
      17. player = argument1 //Speichert abwechselnd den Min bzw. Max Spieler
      18. treeDepth = argument2 //Speichert die maximale Suchtiefe
      19. alpha = argument3 //Speichert den Alpha-Wert
      20. beta = argument4 //Speichert den Beta-Wert
      21. tempWinner = checkWin(tempBoard) //Überprüft, ob es einen möglichen Gewinner gibt
      22. //Überprüft ob:
      23. //- Keine Züge mehr möglich sind ODER
      24. //- Es bereits einen Gewinner gibt ODER
      25. //- Die maximale Suchtiefe erreicht ist
      26. if !movesLeft(tempBoard) || tempWinner || treeDepth = 0
      27. {
      28. //WENN JA:
      29. //Wird der aktuelle Gewinner überprüft.
      30. //Je nach dem wer gewonnen hat wird ein anderer Wert weitergegeben.
      31. //Ist der Gewinner unbekannt, so wird -2 übermittelt.
      32. //Nach der Übermittlung wird der Skript an dieser Stelle abgebrochen.
      33. if tempWinner = getEnemy(global.activePlayer) then return -1 //Gegner hat gewonnen - Ergebnis: -1
      34. if tempWinner = 0 then return 0 //Niemand hat gewonnen - Ergebnis: 0
      35. if tempWinner = global.activePlayer then return 1 //Computer hat gewonnen - Ergebnis: +1
      36. return -2 //Maximale Suchtiefe erreicht - Ergebnis: -2 [Unbekanntes Ergebnis]
      37. }
      38. //Ein Loop durch das gesamte Spielfeld für jeden möglichen Zug
      39. for (i=0; i<ds_list_size(tempBoard); i+=1)
      40. {
      41. //Sollte das Feld noch nicht besetzt sein...
      42. if getOwner(tempBoard,i) = 0
      43. {
      44. //Das Feld dem aktuellen Spieler geben
      45. setOwner(tempBoard,i,player)
      46. //Das Ergebnis der AlphaBeta - Suche in der Variable 'results' speichern.
      47. //Die AlphaBeta - Funktion ist wie folgt aufgebaut:
      48. //argument0 = Spielbrett (ds_list)
      49. //argument1 = Gegner des aktuellen Spielers (Dieser wechselt jetzt immer zwischen Spieler 1 und 2, damit abwechselnde Züge simuliert werden)
      50. //argument2 = Maximale Suchtiefe des Spielbaumes [Dieser wird jetzt bei jeder Suche um 1 verringert, bis 0 erreicht sind]
      51. //argument3 = Aktueller Alpha-Wert, welcher aus der vorherigen Suche übernommen wird
      52. //argument4 = Aktueller Beta-Wert, welcher aus der vorherigen Suche übernommen wird
      53. results = alphabeta(tempBoard,getEnemy(player),treeDepth-1,alpha,beta)
      54. //Das benutzte Feld wieder frei machen (Niemand besitzt es mehr)
      55. setOwner(tempBoard,i,0)
      56. //Die Züge der Spieler werden abwechselnd simuliert
      57. //Deshalb muss überprüft werden, für welchen Spieler gerade der Spielzug simuliert wird
      58. //Entweder der aktive Spieler oder der Gegner des aktiven Spielers
      59. //WENN:
      60. //Der Spieler mit dem aktiven Spieler übereinstimmt
      61. if player = global.activePlayer
      62. {
      63. //DANN:
      64. //Sind die Ergebnisse besser als der aktuelle Alpha-Wert - DANN: Wird der Alpha-Wert an das Ergebnis angepasst
      65. //Wenn der Alpha-Wert größer oder gleich Beta-Wert ist - DANN: Wird der Skript abgebrochen und der Beta-Wert übermittelt
      66. if results > alpha then alpha = results
      67. if alpha >= beta return beta
      68. }
      69. else
      70. {
      71. //SONST:
      72. //Sind die Ergebnisse schlechter als der aktuelle Beta-Wert - DANN: Wird der Beta-Wert an das Ergebnis angepasst
      73. //Wenn der Beta-Wert kleiner oder gleich Alpha-Wert ist - DANN: Wird der Skript abgebrochen und der Alpha-Wert übermittelt
      74. if results < beta then beta = results
      75. if beta <= alpha return alpha
      76. }
      77. }
      78. }
      79. //WENN:
      80. //Der Spieler mit dem aktiven Spieler übereinstimmt
      81. //DANN: Wird der Alpha-Wert übermittelt
      82. //SONST: Wird der Beta-Wert übermittelt
      83. if player = global.activePlayer then return alpha else return beta


      4.0 Zugbeispiel für Tic Tac Toe

      Wir werden jetzt mal die Zugentscheidung bei Tic Tac Toe anschauen.
      Sagen wir einfach mal wir haben folgendes Brett:



      Der Computer hatte den ersten Zug und ist jetzt wieder an der Reihe (Kreis).
      Wir sind dagegen blau (Kreuz).
      MAX bedeutet der Computer ist am Zug. MIN bedeutet wir sind am Zug.
      Der Computer wird mit dem Algorithmus nun folgenden Suchbaum aufstellen:



      Ihr könnt die beiden Bilder gerne in einem neuen Tab öffnen und dann vergleichen.
      Der grüne Kreis oder das grüne Kreuz sind die gewählten Züge.
      Überall wo "Spielende" steht, ist keine Zugmöglichkeit mehr vorhanden, da die aktuelle Runde vorbei ist.
      Spielende (ROT) = Spieler Rot (Kreis/Computer) hat gewonnen
      Spielende (Blau) = Spieler Blau (Kreuz/Mensch) hat gewonnen
      Spielende (Orange) = Das Spiel geht unentschieden aus

      Das heißt also es gibt 5 Möglichkeiten das Spiel zu beenden.
      - 2x Wird der Computer gewinnen
      - 2x Wird unentschieden gespielt
      - 1x Wird der Mensch gewinnen

      Wir erinnern uns an die Bewertung der Züge:
      - Wenn der Computer gewinnt +1
      - Wenn unentschieden gespielt wird 0
      - Wenn der Gegner gewinnt -1

      Die Suche wird gestartet und der Computer überprüft den 1 (linken) Baum:
      - Er setzt seinen Kreis oben links
      - Nun sind wir an der Reihe und es sind noch 2 Felder offen
      - Wir können entweder den Computer gewinnen lassen oder aber unentschieden spielen
      - Da der Computer aber IMMER davon ausgeht, dass wir perfekt spielen, macht er sich keine Hoffnungen auf einen Sieg, da wir ihn nie gewinnen lassen würden
      - Er bewertet den Zug somit als 0 (Es könnte maximal unentschieden gespielt werden)

      Der Computer überprüft nun den 2 (mittleren) Baum:
      - Er setzt seinen Kreis unten in die Mitte
      - Nun sind wir an der Reihe und es sind noch 2 Felder offen
      - Wir können entweder selber gewinnen oder aber unentschieden spielen
      - Wir würden natürlich gewinnen und nicht unentschieden spielen
      - Er bewertet den Zug somit als -1 (Der Computer würde gegen uns verlieren)

      Der Computer überprüft nun den 3 (rechten) Baum:
      - Er setzt seinen Kreis unten in die rechte Ecke
      - Der Computer hätte gewonnen, da er 3 in einer Reihe hat
      - Er bewertet den Zug somit als +1 (Wir können den Computer nicht mehr vom Sieg abhalten)

      Somit kommen für die 3 möglichen Züge folgende Werte zustande: 0 -1 +1
      Davon möchte er das maximale (beste) Ergebnis. Das würde bedeuten der Computer spielt die 3. Möglichkeit, um zu gewinnen.

      Die farbigen Geraden zeigen übrigens den besten Zug für beide Spieler.
      Rot ist der beste Zug, damit der Computer gewinnt.
      Blau ist der beste Zug, damit wir gewinnen.

      5.0 Downloads

      Tic Tac Toe Engine: Download

      Einfach GM Studio öffnen und die gmz-Datei importieren.

      6.0 Nachwort

      So, das war es eigentlich auch schon.
      Ich kann mir jetzt vorstellen, dass es eine menge Fragen gibt und kaum jemand etwas verstanden hat, aber ich hoffe ein paar haben wenigstens das Prinzip des Algorithmus verstanden.
      Wenn nicht, könnt ihr natürlich Fragen stellen. Ich versuche so gut es geht zu helfen.
      Ich bin leider auf den Code nicht wirklich eingegangen. Am besten ist es eigenltich, wenn ihr euch die Datei herunterladet und euch durch die Kommentare lest.

      Dieser Beitrag wurde bereits 9 mal editiert, zuletzt von „Lucy“ ()

      Das ist echt super genial, ich habe zwar nicht alles ganz verstanden, aber Computer gegen Computer ist was neu modisches :D.
      Würdest du auch noch ein Schach machen?
      Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
      Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

      Willst du mit mir auf Discord Chatten/Quatschen?
      Meine Husi's Tutorial Reihe
      Ich habe nochmal eine Beispielrunde Tic Tac Toe und die Zugberechnung dazu aufgeschrieben.
      Das ganze findet ihr unter dem Punkt 4.0 Zugbeispiel für Tic Tac Toe

      husi012 schrieb:

      Das ist echt super genial, ich habe zwar nicht alles ganz verstanden (...)

      Wenn du etwas noch nicht verstanden hast, dann kannst du gerne präzise fragen.
      Ich werde dann versuchen dir so gut es geht zu helfen.
      Das ganze Tutorial musste ich leider etwas schlampig schreiben, aber das ganze Thema und vor allem der Code dahinter ist nicht gerade leicht zu erklären.
      Ich werde aber nach und nach versuchen das Tutorial noch auszubessern und zu erweitern.

      husi012 schrieb:

      Würdest du auch noch ein Schach machen?

      In nächster Zeit wohl eher nicht.
      Aber ich könnte versuchen ein Beispiel für 4 Gewinnt zu machen.
      ah das 4.0 gefällt mir, ist noch besser anschaulich und jetzt weis ich auch,
      das ich nicht von unten nach oben schauen muss nämlich von oben nach unten :D

      also 4 Gewinnt wäre auch dann noch klasse
      Ein Bug ist mehr als nur ein Bug, es ist ein... Käfer!
      Egal, wie gut du eine Mauer baust, sie fällt um.... der klügere gibt nach :D

      Willst du mit mir auf Discord Chatten/Quatschen?
      Meine Husi's Tutorial Reihe
      Vielen, vielen Dank für diese Erklärung!!! War super verständlich :)
      Ich studiere informatik und programmiere gerade an einer KI rum und dieses Tutorial hat mir super geholfen :thumbsup:

      Hab mir extra ein Konto eingerichtet, nur um diesen Kommentar zu verfassen ;)
      Ich bin auf der Suche nach weiteren ähnlichen Erklärungen auf dieses Video vom MIT gestoßen:
      Für alle, dies das Ganze nochmal auf Englisch hören wollen :D

      Nochmal vielen lieben Dank :thumbup:
      Sorry, meine Dateien wurden bei einem früheren Umzug des Servers leider mal gelöscht. An das Projekt und die Seite hier hatte ich gar nicht mehr gedacht.
      Hab die Datei nochmal hochgeladen, allerdings habe ich weder mit GameMaker, noch mit der Seite hier was zu tun.
      Ich werde also wahrscheinlich keine Fragen beantworten oder hier überhaupt reinschauen.

      Neuer Download: Link