4.4. Tic-Tac-Toe
Obwohl Tic-Tac-Toe zu einem der ersten Computerspiele gehört, habe ich mich mit ihm noch nie beschäftigt. Es schien mir zu simpel zu sein. Das ist allerdings ein Irrtum. Googelt man nach Spiel Tic Tac Toe, werden einem knapp eine halbe Million Treffer angeboten. Natürlich auch ein Wikipedia-Artikel: https://de.wikipedia.org/wiki/Tic-Tac-Toe Sucht man nach Spiel Tic Tac Toe Strategie sind es merkwürdigerweise mehr als eineinhalb Millionen Treffer.
Unter den Treffern finden sich sehr unterschiedliche Beiträge und darunter auch für fast jede Programmiersprache die Programmquellen.
Die sehr ergiebige Seite Rosetta-Code Tic Tac Toe (https://rosettacode.org/wiki/Tic-tac-toe) liefert die Lösung in 62 verschiedenen Programmiersprachen. Scratch und meine mBlock-Lösung sind hierbei nicht enthalten.
Für mBlock habe ich allerdings nichts gefunden. Und für den Arduino fast ausschließlich Anleitungen, wie man unter Einsatz von Microschaltern und LEDs ein Spielbrett bauen kann.
Meistens wird außerdem der Code für ein Spiel angeboten, in dem zwei menschliche Spieler gegeneinander spielen. Das Programm achtet nur darauf, dass die Regeln eingehalten werden.
Bevor ich die Programmierung in mBlock für den mBot beginne, wollte ich mich etwas tiefer in die Materie einarbeiten. Ich habe daher nach Programmquellen in PHP und/oder Javascript gesucht. Das Ergebnis war nicht sehr ergiebig. Teilweise waren die Lösungen sehr umfangreich und unübersichtlich.
Am besten gefallen hat mir die Lösung von Dietmar Henke in Javascript: https://www.henked.de/spiele/tictactoe/tictactoe.htm
Ich habe daraufhin Herrn Henke per Email kontaktiert und angefragt, ob ich sein Programm hier einbauen dürfe. Da er zugestimmt hat, folgt sein Programm im nächsten Abschnitt.
Die mBot-Lösung werde ich in Kürze angehen.
Die Sprache MBlock ist ja eine Erweiterung von Scratch. Bei einer Google-Suche nach Scratch tic tac toe erhält man über eine Million Treffer. Wählt man z.B. https://scratch.mit.edu/projects/1425/remixes/ dann bekommt man eine Übersicht mit mehr als 150 Treffern. Der überwiegende Teil davon hat allerdings die gleiche Klick-Grafik; Stichproben haben ergeben, dass sie alle auf einer einzigen Quelle basieren.
Für das Spiel gegen den Computer existiert ein Ansatz, bei dem der Computer nie verliert, egal, wer anfängt. Dies ist die Minimax-Strategie. Umgesestzt wird sie mit einer rekursiven Programmierung. Einfach gesagt bedeutet dies, dass eine Funktion (in Scratch: ein Block) sich selbst aufruft. Hierfür ist es erforderlich, dass in dieser Funktion auch lokale Variable verfügbar sind. Dies ist in Scratch nicht der Fall. Außerdem benötigt ein rekursives Programm oft viel Speicherplatz. Dieser ist beim Arduino Uno sehr begrenzt. Ich habe aus diesen Gründen bisher darauf verzichtet, den Minimax-Algorithmus für den mBot zu programmieren.
Ein weiterer Grund spricht für mich auch dagegen: Es gibt zwar den Satz "Wer nicht kämpft, hat schon verloren." Aber gegen ein Programm, von dem ich weiß, dass ich nicht gewinnen kann, will ich es gar nicht erst versuchen.
In meiner Lösung kann man die Spielstärke einstellen: 0 = minimal, 1 = mittel.
Bei Spielstärke 0 arbeitet das Programm eigentlich planlos. Wenn es an der Reihe ist, werden Zufallszahlen zwischen 0 und 8 erzeugt. Die neun Felder sind entsprechend nummeriert. Wenn das entsprechende Feld leer ist, wird es belegt, wenn nicht, wird die nächste Zufallszahl erzeugt. Der Computer ist also quasi blind und erkennt weder offensichtliche Gewinnstellungen noch offensichtliche Verluststellen.
Das ist natürlich sehr unbefriedigend. In Stufe 1 ist die Strategie folgende: Es werden zuerst alle freien Felder daraufhin geprüft, ob ihre Belegung zu einer vollständigen Reihe für den Computer führt. Ist dies der Fall, wird das Feld besetzt (Angriff). Der Computer hat also gewonnen.
Findet das Programm kein solches Feld, wird im zweiten Schritt für alle leeren Felder geprüft, ob ihre Besetzung durch den Gegner dazu führt, dass er gewonnen hat. Dieses Feld wird dann vom Computer besetzt (Verteidigung). Wenn dies das einzige Verlustfeld ist, hat der Computer erst einmal nicht verloren. Insbesondere in der Anfangsphase des Spiels gibt es weder eine klare Gewinnposition noch eine klare Verlustposition. Es wird dann (wie bei Stufe 0) über einen Zufallsgenerator blind irgendein freies Feld besetzt.
Eine weitere Stufe könnte statt dieses Zufallszuges eine Strategie einsetzen, um vielversprechende Felder zu besetzen.
Vorerst ist dies eine offene Erweiterungsmöglichkeit.
Das Skript kann hier heruntergeladen werden: tictactoe.sb2
Das YouTube-Video kann hier angesehen werden: https://youtu.be/0Z-i2QR6tm8
