Wir haben uns vorgenommen einen intelligenten Roboter zu programmieren, der TicTacToe spielen kann, sowie Markierungen in das Feld einzeichnen. Dazu haben wir selbst den Roboter gebaut, sowie die Ansteuerung des Roboters programmiert, und eine künstliche Intelligenz programmiert, die das Spiel TicTacToe spielen kann.

Gesetzes Ziel Der Roboter soll das Spiel verstehen, in der Lage sein vom Spieler gemachte Züge zu erkennen und selber zu spielen, dass heißt auf ein Feld zu fahren und seine Markierung zu setzen. Ob dabei auf einem echten Spielfeld gespielt wird oder einem PC soll im Laufe des Arbeitsprozesses entschieden werden.

Sollte Der Roboter kann so interagieren, dass er mit dem Spieler festlegen kann, wer das Spiel beginnt. Ist der Roboter zuerst am Zug, dann gewinnt er immer das Spiel, da er nicht nur reagieren kann, sondern das Spiel so versteht, dass er nicht mehr verliert. Das Spielfeld zeichnet er dabei selber und die Markierung ist ein Symbol wie ein Kreis oder 'X' und nicht nur irgendetwas.

Nice to have
-Der Roboter erkennt, wenn ein ungültiger Spielzug gemacht wird (z.B. Feld eines anderen Übermalen).
-Der Roboter reagiert auf einen Gewinn bzw. eine Niederlage.

Bewusst weggelassen Das Spielfeld wird sich auf eine Oberfläche beschränken, die eben ist und vorher durch ausprobieren genormt. Der Roboter kann nicht durch Sensoren Tischkanten erkennen oder Wände, er fährt quasi blind zu Koordinaten, da unser Spielfeld immer gleich ist. Dies wurde zur Vereinfachung der Programmierung und des Bauprozesses so gewählt.

Aufgabenreihenfolge zur Realisierung des Projekts

-Intelligenz programmieren: den Arduino befähigen zu spielen (zunächst wahrscheinlich am Computer)
-eigenen Roboter bauen, der auf dem Boden fahren kann, sich drehen und zeichnen
-Konstruktion für den Stift zur Markierungssetzung bauen
-den Roboter programmieren das Feld zu zeichnen und Makierungen zu setzen
-die Kamera befähigen das Spielfeld zu erkennen und mit dem Roboter zu kommunizieren

Da mitunter eine große Rechenleistung gefragt ist, haben wir die Überlegung dem Arduino zusätzliche Rechenleistung über die Einbindung eines PC's in die Berechnungen zu geben.

-Materialliste überlegen -Grundgerüst bauen -alles verkabeln -fahren lassen -Stiftkonstruktion bauen

-Kamera auf das Feld richten
-eigene Position bestimmen
-an richtige Position fahren
-Spielfeld malen und Position der Linien merken

-immer selber anfangen

-Feld erkennen
-erkennen, was neu dem Feld hinzugefügt wurde
-eigenen Zug einleiten

-Feld wieder erkennen
-erkennen, was schon auf dem Feld geschehen ist
-durchrechnen, welcher Zug sinnvoll wäre
-Zug machen

-Kommunikation mit Rechner, um Rechnung auszulagern -Verarbeitung des Ergebnisses und Umsetzung der Reaktion

-Feld erkennen
-erkennen, wenn 3 Zeichen eine Linie bilden
-wissen, dass dies das Ende des Spiels bedeutet

-Feld erkennen
-sehen wer den Gewinnerzug gemacht hat
-Gewinner mitteilen (z.B. Bildschirmausgabe)

-weiß wo die Felder sind
-alle Felder durchgehen
-neuste Veränderung merken

Materialien

Wichtigster Bestandteil unseres Roboters ist seine Intelligenz, welche aus der Programmierung bestehen wird. Außerdem muss die Kommunikation zwischen unserem Programm und dem Roboter, der sich aus der Arbeit der anderen Gruppe heraus bewegt, funktionieren. Daraus erschließt sich, dass wir für den Materialaufwand zunächst nicht viel berücksichtigen müssen und sich unsere Planung auf das finden von Alternativen des Spielfeldes und/oder nur der Programmierung beziehen wird.

Wissen

Hier stellen wir uns die Frage, was muss noch recherchiert werden?

- Funktionsweise des Algorithmus, der die Spielzüge berechnet
- wie viel können wir mit der Kamera erkennen?
- wie kommuniziert unser Programm mit dem Roboter der Tafelwischgruppe?
- ist es sinnvoll einen PC zur Berechnung der Züge zu benutzen
- Malfunktion

Risiken

- Feld wird nicht erkannt
→ Zeichnet der Roboter das Feld selber, sollte er sich dieses Feld selber merken und kein Problem mit dem Erkennen haben, da er es abspeichern kann
- Kommunikation mit der anderen Gruppe funktioniert nicht und/oder die Programme untereinander
→ Da nicht die ganze Zeit über zusammengearbeitet wird, könnte es schon Probleme bei der Kommunikation geben. Als Alternative wäre das Spiel nur auf dem Rechner zu simulieren oder den Roboter alleine zu bauen.
- Bau des Roboters und Intelligenz programmieren ist zu viel

Roboter-Gesamtbild:

Hier sieht man den Roboter in der Vogelperspektive. Wir haben auf Grund der verschiedenen Projektteile (Roboterbau und -programmierung und KI-Programmierung) weniger auf Schönheit, als auf Funktionalität geachtet.

Stiftkonstruktion:

Der Servo kann sich in einem Bogen von 180 Grad bewegen. Dieses Radius nutzen wir aus, um den Stift entweder abzusenken oder hochzufahren. Die Feder sorgt dabei dafür, dass Unebenheiten im Boden beim Zeichnen ausgeglichen werden. Der Stift an sich, wird von einem kleinen Rohr geführt, um nicht unnötig Bewegungsspielraum zu haben.

Verkabelung:

Die Stepper-Treiber werden benötigt, um pro Treiber einen Steppermotor anzusteuern. Der Akku betreibt den Arduino und die Motoren, sobald sie vom Computer getrennt sind. Der Akku ist außerdem von Nöten, da die Spannung des Arduino nicht ausreicht, um die Motoren zu betreiben. Mit dem Wlan-Modul wird dem Arduino vom PC den über Processing weitergegebenen nächsten Spielzug mitgeteilt und Processing erfährt, wann der Arduino seine Aufgabe, das Ziehen des Zuges mit dem Roboter beendet hat.

Unterseite:

Hier sieht man die Räder und Steppermotoren. In der Mitte der Motoren ist die Öffnung der Stiftkonstruktion. Der Schleifer am oberen Ende des Bildes wird benutzt, um stabil Kurven fahren zu können. Ein weiteres kleines Rad würde nur mehr Ungenauigkeiten hervorrufen, da es bei der Kurvenfahrt mal stockt oder stehen bleibt. Da Korrigieren der Fahrbahn nicht mit einprogrammiert wurde, haben wir probiert mit der Kugel als Schleifer dieses Problem zu umgehen.

Roboterprogrammierung:

roboterprogrammierungtictacmint.zip

Der Roboter ist in 4 Stufen programmiert.

Stufe 1 beinhaltet die Basisfunktion wie fahren, drehen und das Bewegen des Stifts.

Stufe 2 ermöglicht es dem Roboter sich eigenständig auf dem Spielfeld zu orientieren. Da wir am Ende keine Kamera verwendet haben kann der Roboter nur mit internen Daten arbeiten. Der Roboter besitzt eine ganze Reihe von Variablen (Tab KoordinatenBewegen ganz oben) mit denen der Roboter seine Position und die Ergebnisse seiner Berechnungen speichert.

Wenn der Roboter den Befehl bekommt an eine Stelle zu fahren vergleicht er zuerst die gespeichert Daten zu seiner Position auf dem (theoretischen) Koordinatensystem und seinem Winkel zu X-Achse (berechnet mit Atan2) mit der Zielposition. Das Programm berechnet dabei die zurückzulegende Strecke mit dem Satz des Pytagoras. Der zu drehenden Winkel wird berechnet indem mit Atan2 der Winkel des Vekors zum Ziel (relativ zur X-Achse) berechnet wird. Von diesem Winkel wird dann der aktuelle Winkel des Roboters abgezogen. Das Ergebniss gibt an wie weit sich der Roboter drehen muss. Strecke und Winkel werden eingespeichert und von den Basisfunktionen in Bewegung umgewandelt.

Der Roboter verwendet eine Sammelfunktion(zuKoordinateBewegen(float x, float y)) die alle notwendigen Funktionen aufruft und am Ende die Positionsdaten aktualisiert.

Stufe 3 empfängt einen auszuführenden Zug als char kodiert und verwendet eine SwitchCase Funktion um das anvisierte Feld und den Spieler zu bestimmen. Das Feld wird als die X- und Y-Koordinate des Feldmittelpunkts gespeichert. Der Spieler wird umgesetzt indem eine der beiden Zeichenfunktionen( zeichneKreuz() und zeichneLinie()) aktiviert wird. Die Zeichenfunktionen verwenden die eingespeicherten Mittelpunktskoordinaten und fahren zu Positionen die relativ dazu berechnet werden. Die Zeichnung entsteht indem der Stift je nach Stelle im Programm entweder angehoben oder abgesenkt wird und so einige der gefahrenen Strecken eine Linie hinterlassen.

Stufe 4 findet im Mainloop statt. Das Programm liest zu Beginn des Loops ein char mit SoftwareSerial ein und überprüft ob dieser Zug mit dem letzten ausgeführten Zug übereinstimmt. Wenn ja, tut dass Programm nichts und beginnt den Loop neu. Wenn nicht wird die Funktion zum ausführen des Zugs aus Stufe 3 aufgerufen und der Zug als der letzte ausgeführte Zug gespeichert. Dann beginnt alles von vorne.

Tatsächlich kann ich im Moment nicht sagen, wie gut die Kommunikation mit der KI funktioniert, da ich keine Gelegenheit mehr hatte das zu testen.

tictactoe.zip

Die KI funktioniert mit Hilfe des Minimax Algorithmus, dieser findet nicht nur bei Tic-Tac-Toe, sondern auch in Spiele-KI’s für z.B. Schach oder GO Anwendung. Der Algorithmus läuft dabei in zwei Schritten ab:

1. Der Algorithmus führt jeden möglichen Zug auf dem Spielfeld probeweise aus und prüft ob eine der beiden Parteien gewonnen hat oder das Spiel unentschieden ist. Im obigen Beispiel gibt es noch 3 mögliche Züge
   1. Ist das Spiel schon gewonnen oder vorbei wird das momentane Spielfeld eine Punktzahl berechnet, dabei bekommen Siege einen positiven Punktestand und Niederlagen einen negativen. Beim bewerten des Spielfelds spielt es auch eine wichtige Rolle wann eine Partei das Spiel gewonnen hat. So bringen schnelle Siege mehr Pluspunkte bzw. schnelle Niederlagen mehr Minuspunkte. Dies ist wichtig weil der Computer schnelle Siege bevorzugen, und schnelle Niederlagen verhindern soll, würde dies nicht beachtet werden, wären die beiden Siege in der Abbildung unten z.B. gleichwertig und der Computer würde sich evtl. nicht für den sicheren Sieg entscheiden
   2. Ist das Spiel noch nicht entschieden, dann ruft sich der Algorithmus selbst auf, diesmal wird aber nicht das Ursprungs-Spielbrett, sondern das Belegte Spielbrett übergeben. Außerdem ändert sich der aktuelle Spieler da bei Tic-Tac-Toe ja immer abwechselnd gespielt wird. Dieser Prozess wird solange wiederholt bis das Spiel zu Ende ist und ein Punktestand berechnet werden kann.
2. Inzwischen hat der Algorithmus für jedes mögliche Spielergebnis einen Punktestand berechnet, jetzt müssen die Punktestände der Felder aber noch miteinander verglichen werden um eine fundierte Entscheidung über den besten Spielzug treffen zu können. Dabei vergleicht der Algorithmus die Punktestände aller Züge des aktuellen Spielbretts (diese wurden ja zuvor ermittelt). Dieser Vergleich geschieht je nachdem welcher Spieler am Zug ist Unterschiedlich:
   1. Der Computer ist am Zug: Der Computer vergleicht er die unterschiedlichen Punktestände und wählt den MAXIMALEN Score für die Rückgabe aus. Dies tut er weil das der bestmögliche Zug für den Computer ist und seine Gewinnchancen Maximiert
   2. Der Spieler ist am Zug: Wieder werden alle Punkte verglichen doch diesmal sucht der Computer den MINIMALEN Punktestand. Warum? Naja, der Spieler versucht ja selber möglichst schnell zu gewinnen, was bedeutet das er stets das Feld wählen wird, welches die wenigsten Punkte für den Computer bringt. Der Computer weiß also NICHT welchen Zug der Spieler machen wird, deshalb muss er davon ausgehen das der Spieler stets den bestmöglichen Zug wählen wird.

Da sich die beiden Spieler stets abwechseln, wechselt auch das Vergleichsverfahren immer hin und her. Das abwechselnde maximieren und minimieren des Punktestands ist damit auch der Namensgeber für den Algorithmus Minimax. Das Ergebnis ist in der folgenden Abbildung veranschaulicht:

Das Feld oben rechts hat die höchste Punktzahl erreicht und ist damit der best mögliche Zug (was hier aber auch recht offensichtlich ist )