Ziel dieses Projekts war es, einen Schach spielenden Roboter zu bauen. Ein Greifarm kann Figuren greifen und diese gezielt wieder absetzen. Dieser besteht aus einer Drehbasis, einem Kranarm und einer Art Fahrgestell mit einem Greifer. Hierbei werden Greifer und Fahrgestell mit Seilwinden bewegt, der Kranarm dreht sich durch einen Schrittmotor in der Drehbasis. Eine Kamera kann über farbige Punkte Rückmeldung über die Position des Greifarms geben. Durch das Subtrahieren zweier Fotos kann der Zug des Menschen ebenfalls festgestellt werden. Ein Schachalgorithmus gibt Befehle an den Roboter, um möglichst starke Züge auszuführen.

Der Roboter besteht aus drei Teilen. Es gibt den eigentlichen kranförmigen Roboter, welcher mithilfe vierer Motoren Figuren greifen und setzen kann. Eine Kamera, welche zum einen einem Computer die Position des Roboters über das Tracken von farbigen Punkten weitergibt und zum anderen Züge des menschlichen Spielers erkennt. Zu Letzt gibt es noch einen Schach-Algorithmus, welcher dem Roboter die Züge vorgibt. Bei allen Bestandteile mussten Probleme gelöst werden. So waren die Motoren des Greifarms zu schwach und zu ungenau, es war schwierig die menschlichen Züge zu erkennen und der Schachalgorithmus war zu langsam. Ursprünglich wollten wir eine Schachuhr implementieren, bei dem finalen Tempo unseres Roboters würde die Uhr aber keinen Sinn mehr haben, da dann der Mensch immer auf Zeit gewinnen würde.

Bild 1: Der Schachroboter im Überblick

Aufzuteilen ist die Hardware in den Kamerastand und den Roboter selbst, der sich noch einmal in die Basis, den Greifarm und den Dreharm unterteilen lässt.

Auf der Basis sitzt der Dreharm. Sie bietet Platz für den Motor, der für die Drehbewegung zuständig ist. Zudem bietet sie Platz für das Breadboard.

Bild 2: Die Drehbasis

Die Anfertigung und Installation der Basis lief fast problemlos ab, mit Ausnahme davon, dass sie den Motor, der sich in ihr verbirgt nicht ausreichend festhielt, sodass sich dieser, statt den Dreharm zu drehen, um die eigene Achse drehte. Dies konnte allerdings mit ein paar Winkeln schnell behoben werden.

Der Dreharm besteht aus zwei Planken, die parallel voneinander verlaufen. Dies ermöglicht es dem Wagen, auf dem sich der Greifarm befindet auf dem Dreharm vor und zurück zu fahren. Des Weiteren kann sich der Dreharm natürlich drehen, was dazu führt, dass der Greifarm und somit die Schach Figur jedes Feld erreichen kann.

Bild 3: Der Dreharm

Es fing damit an die beiden Planken parallel voneinander zu halten, um dem Wagen überhaupt zu ermöglichen frei auf dem Dreharm fahren zu können. Mit der Montage von jeweils einer Stange vorne und hinten an den beiden Planken war dieses Problem jedoch schnell behoben. Komplizierter wurde es dann bei der Frage, wie wir den Wagen bewegen wollten. Die Wahl fiel schnell auf Fäden, die mithilfe von Motoren zum Einen den Wagen nach vorne und hinten- und zum Anderen den Greifarm nach oben und unten bewegen sollten. Diese Entscheidung brachte allerdings weitere Probleme mit sich, da sich die Fäden immer wieder verknoteten und so einen reibungslosen Betrieb schier unmöglich machten. Um dieses Problem zu lösen bauten wir verschiedene Kniffe ein, um die Fäden kontrollierter auf- und abwickeln zu können. So leiteten wir z.B. ankommende Fäden ganz nach rechts und bemühten uns den Faden beim abwickeln ganz links von der Rolle zu lassen.

Bild 4: Die Step Motoren für die Bewegung des Greifers durch Seile

Anschließend ergab sich ein neues Problem. Der Motor, der den Greifarm bewegen sollte hatte nicht genügend Zugkraft. Nach langem Überlegen fiel die Wahl auf die Verwendung von mehreren Flaschenzügen, die das Problem sofort behoben.

Bild 5: Flaschenzüge am Greifer

Der Greifarm sitzt auf einem Wagen, der auf dem Dreharm hin und her bewegt werden kann. Er ist dafür da, den eigentlichen Greifer nach oben und unten zu bewegen und die Schachfigur zu greifen und wieder loszulassen.

Bild 6: Der Greifer hält eine weiße Dame

Mit dem Greifer an sich hatten wir keine Probleme. Mit der Vertikalbewegung des Greifarms dafür allerdings einige. Zum Einen ließ er sich anfangs nicht waagerecht nach oben bewegen, sondern kippte immer wieder nach vorne, weil der Zug nur von einer Seite, nämlich von der Basis ausgehend, auf den Greifarm wirkte. Zum Anderen stockte der Apparat häufig beim Ziehen nach oben. Um dies zu beheben installierten wir zwei Schienen, an denen wir den Greifarm kontrolliert bewegen konnten.

Bild 7: Schienen zur Stabilisierung des Greifers

Dies behob die ersten beiden Probleme, führte jedoch dazu, dass sich der Greifer nicht mehr von Allein nach unten bewegte, da der Wiederstand der Schienen zu groß war. Durch ein Gewicht, welches wir auf dem Greifarm platzierten lösten wir aber auch dieses Problem.

Dieser hält die Kamera konstant an einem Platz und sorgt dafür, dass die Kamera das gesamte Schachbrett aufnehmen kann.

Bild 8: Die Kamera

Das einzige Problem mit dem Kamerastand war es, die richtige Höhe zu ermitteln um das komplette Schachfeld erfassen zu können.

Ein weiterer großer Teil des Projektes war die Erkennung der Züge des Menschen. Ein grober exemplarischer Ablauf ist im folgenden dargestellt.

1 do()
2 while True:
3     print("white to move")
4     time.sleep(2)
5     do(mat=S)
6     
7     print("black to move")
8     time.sleep(2)
9     roboterarm(bestMove)
10    do()

Die Definition do() beinhaltet hierbei die Bilderkennung. Wenn do() ohne weitere Parameterübergabe ausgeführt wird, wird zunächst nur ein Foto mit der Webcam aufgenommen (Zeile 1). Nun wird folgender Vorgang beliebig oft wiederholt: Weiß beginnt und zieht eine Figur. Danach wird do(mat=S) (Zeile 5) ausgeführt. Hierbei werden die derzeitigen Figurenpositionen in Form einer Matrix übergeben. Am Anfang entspricht dies der Startaufstellung. Nun wird ein neues Bild aufgenommen und mit dem alten verglichen, um den Zug, den Weiß gemacht hat zu bestimmen. Dazu später mehr. Jetzt ist Schwarz an der Reihe, in diesem Falle ist das unser Roboter. Mithilfe des Schachalgorythmus ermittelt der Roboter den besten Zug und kann die Änderung der Figurenpositionen direkt in die Matrix speichern, ohne das eine Bilderkennung notwendig wäre. Der Roboterarm führt dann den Zug aus (Zeile 9). Jetzt wird erneut ein Foto mit do() (Zeile 10) gemacht, was dann für den nächsten Zug von Weiß als Vergleichsbild dient. Nun wiederholt sich der ganze Vorgang bis zum Ende des Spiels.

Ausgangspunkt von der Zugerkennung sind nun zwei Bilder, einmal vor und einmal nach dem Zug. Ein solches Bild sieht beispielsweise so aus:

Bild 9: Das Schachbrett aus der Sicht der Kamera

Der erste Schritt besteht darin, die Grenzen des Schachbretts zu erkennen und die Bilder auf dessen Maße zuzuschneiden. Die Eckpunte des Bretts geben wir zurzeit per Hand ein. Dieser Kalibrierungsprozess bürgt in jedem Falle Optimierungspotential, da dieser sehr lange daurert und man das Spiel vorher nicht beginnen kann.

Video 1: Animation zur Veranschaulichung der Bretterkennung

Nun werden die zwei Bilder voneinander subtrahiert. Nun sind die Unterschiede im Bild weiß gefärbt, alles Gleichgebliebene Schwarz.

Video 1: Animation zur Veranschaulichung der Bretterkennung

Hier kommt ein Algorithmus ins Spiel, der die durchschnittliche Farbe eines jeden Feldes misst. Bei einem großen Unterschied im Bild gibt es einen hohen Weiß-Anteil, deshalb ist die durchschnittliche Farbe heller. Der Algorithmus sucht zunächst die hellsten zwei Felder. Interpretation: Auf diesen zwei Feldern ändert sich der Figurenwert.

Video 2: Bilddifferenz

Das obenstehende Video ist hierbei nur eine Simulation. Ein Beispiel von wirklich Bilder befindet sich hier:

Video 2.1: Bilddifferenz und Bilddifferenz in nur zwei Helligkeiten

Hier sieht man noch einmal deutlich, dass die Bilderkennung durch die Bildeffekte im rechten Bild in ihrer Funktionalität verbessert werden kann, indem die hellen Stellen erhellt werden. Andersherum wird hier der Schatten der links zu sehen ist im rechten Bild nocheinmal verstärkt und erhöht so die Fehleranfälligkeit. Hier wäre ein höherer Schwellwert für die Erhellung heller Flächen die Lösung.

Zum Schluss werden die Figurenwerte auf den beiden Feldern getauscht und falls eine gegnerische Figur auf einem Feld stand, wird diese durch ein leeres Feld ersetzt.

Video 3: Animation zur Veranschaulichung der Zugerkennung

Besonders kompliziert wurde es durch die Extraregeln Rochade und en passant im Schach. Hierbei sind bei einem Zug gleich mehr als zwei Felder beteiligt.

Die Rochade ist der einzige Doppelzug der nach den Schachregeln erlaubt ist. Jeder Spieler darf einmal pro Spiel entweder die lange Rochade (grün) oder die kurze Rochade (rot) durchführen. Außerdem ist dieser Zug an eine Reihe von Bedingungen geknüpft.

Grafik 1: Rochade im Schach

Um unnötiges Rechnen zu ersparen übergibt der Schachalgorithmus jedes Mal bevor die Bilderkennung durchgeführt wird Information darüber, ob die Bedingungen für eine Rochade überhaupt erfüllt, und so eine Rochade möglich ist. Falls dem nicht so ist wird der oben beschriebene Algorithmus verwendet. Ansonsten wird davor überprüft, ob es in dem subtrahierten Bild vier Felder mit ähnlich hohem Helligkeitswert gibt. Dann wird zwischen der langen und kurzen Rochade unterschieden und die dementsprechenden neuen Figurenpositionen gespeichert.

Beim en passant schlägt ein Bauer einen gegnerischen Bauern „im Vorbeigehen“ (franz.: en passant). Der Bauer geht also auf ein freies Feld und auf dem benachbarten Feld wird der gegnerische Bauer weggenommen.

Grafik 2: En Passant im Schach

Auch hier wird zunächst vom Schachalgorithmus überprüft, ob das en passant überhaupt möglich ist. Wenn ja werden dann dieses Mal drei Felder auf ihre Helligkeit untersucht.

Durch Schatten der Figuren auf dem Brett, oder zu geringen Kontrasten (z. B. vom weißen Läufer auf weißem Feld) kann es schnell zur falschen Erkennung der am Zug beteiligten Felder kommen. Dieses Problem ist am besten mit gleichmäßiger Beleuchtung zu beheben. In einer eleganteren Lösung könnte man den Kontrast von den dunklen oder hellen Schachfeldern zu den Figurenfarben messen und daran die Figurenfarben bestimmen. Ansonsten funktioniert der Schachalgorithmus einwandfrei und zuverlässig.

Der Algorithmus kann noch in der Genauigkeit optimiert werden. Beispielsweise kann man verschiedene Methoden zur Regulierung des Schwellwerts, ab dem eine Figur auf einem Feld erkannt wird verwenden. Durch weitere Bildbearbeitung kann man außerdem die Bildunterschiede verstärken. Außerdem kann man eine Konturerkennung verwenden, anstatt lediglich die Helligkeitswerte zu vergleichen. Es wäre ebenfalls schön, wenn die Eckpunkte des Schachbretts in Zukunft automatisch erkannt werden. Auch dies ist mit höherer Bilderkennung und Konturerkennung möglich. Im besten Falle erkennt der Roboter zu Beginn des Spiels ebenfalls welche Farbe seine und die des Gegners ist. Dies wurde eigentlich bereits umgesetzt, aber für unsere Lösung wird eine sehr gleichmäßige Beleuchtung vorrausgesetzt.

Der einfachste Weg einen Schachalgorithmus zu schreiben war, die Programmiersprache Python zu verwenden es gibt sogar eine Bibliothekchess, welche das Implementieren der Schachregeln komplett übernimmt. Über den Minimax Algorithmus in Verbindung mit dem sogenannten Alpha-Beta-Pruning hatten wir hier auch bereits frühe Erfolge erzielt. Leider war das Program sehr langsam, weshalb wir uns entschlossen, die Programmiersprache auf C++ zu ändern.

Auf den acht mal acht Feldern des Spielbretts können Figuren legale und illegale Züge machen, „1. Sf3“ also Springer nach F3 wäre zum Beispiel ein legaler erster Zug, aber „1. Dxe8“ also Dame nimmt E8, also den schwarzen König, wäre ein illegaler Zug. Im Allgemeinen haben alle Figuren Muster nach denen sie sich bewegen, ausgeführt werden darf aber so ein im Muster liegender Zug nur, wenn dadurch der eigene König nicht angegriffen wird. Im Programmcode wird entsprechend zwischen den Methoden „half_legal“ also halb legal und „legal“ entschieden. (Offiziell wird anstatt halb legal eigentlich pseudo legal gesagt, für den Code ist das aber egal.) Ein Zug ist genau dann legal, wenn nach der Ausführung des Zuges der eigene König nicht angegriffen ist. Also werden die Methode „move“ um einen Zug durchzuführen und „back“ um eien Zug zurückzunehmenebenfalls verwendet. In der Version des Codes die hier gefunden werden kann, spielt weiß (Computer) gegen schwarz (Mensch) in einer Konsolenanwendung. In main() (Zeile 858) wird zunächst eine while Schleife aufgerufen. In jedem getätigtem Zug wird diese Schleife einmal durchgangen. In jeder Iteration wird überprüft ob das Spiel endet, indem die Endstand() Methode der Klasse chess aufgerufen wird. Innerhalb dieser wird zunächst geprüft, ob es legale Züge gibt. Falls das nicht der Fall ist, so ist das Spiel entweder ein Unentschieden (Patt) oder ein Schachmatt, wenn der König im Schach steht. Es ist ebenfalls ein Unentschieden, falls sich eine Stellung dreimal wiederholt oder falls 50 Züge lang keine Figur geschlagen und kein Bauer bewegt wurde. Die Methode gibt 0 für eine noch nicht beendete Partie-, 1 für einen Sieg von Weiß-, 2 für einen Sieg von Schwarz -und 3 für ein Remi aus. Falls der Computer am Zug ist, würde über Minimax (Zeile 785) der beste Zug über Rekursion ermittelt. Dafür wird der Parameter depth verwendet, um eine Suchtiefe festzulegen. Falls depth = 0,so gibt minimax() einfach nur die durch Bewertung() erfahrene Zahl aus. Bewertung() rechnet momentan nur das Material von Schwarz und von Weiß gegeneinander auf. Durch das folgende if - else Konstrukt wird Rekursiv abwechselnd der beste Zug von Schwarz und der beste Zug von Weiß gespielt. Mithilfe von Alpha Beta Pruning kann der ganze Prozess beschleunigt werden. Auf diese Weise findet der Computer den besten Zug heraus, falls der Mensch am Zug ist werden über die Methoden simplenotation() und legal() alle legalen Züge aufgelistet, der Mensch wählt sich lediglich einen dieser aus.

Grafik 3: Minimax Algorithmus

Es gibt noch eine Menge Fehler, und nichtgewünschtes Verhalten des Programms. Wenn zum Beispiel ein Bauer des a oder h Rangs von Weiß ein en passant durchführt, so muss im nächsten Zug Schwarz entsprechend auf den a oder h Rang setzen. Auch das Umwandeln der Bauern funktioniert noch nicht, wie gewünscht. Die Konstante zugzeichen mag rätselhaft wirken, ist aber zunächst der einfachste Weg um Züge fehlerfrei im Programm zu beschreiben. Alle anderen Varianten waren entweder langsam, oder sehr fehleranfällig. Ein Zug besteht aus zwei Zeichen. Der Index beider Zeichen in zugzeichen wird bestimmt, also „AB“ wird beispielsweise zu 0,1. Das erste Feld bestimmt welche Figur sich bewegen soll, 0 ist zum Beispiel immer der König. Das zweite Feld bestimmt das Zielfeld, also 0 wäre a8 und 63 wäre h1. Falls sich ein Bauer Umwandelt kann über die floordivision und dem Modulo der ersten Zahl neben dem zu bewegenden Bauern zusätzlich die gewünschte Figur bestimmt werden.

Eine Fehlerlose Version ist definitiv absehbar, auch gibt es eine Menge Ideen alles zu beschleunigen. So reicht es häufig zum Beispiel aus sich nur die Veränderungen des Zuges anzusehen und daran die Veränderung der legalen Züge abzulesen. Eine Implementierung einer solchen Regelung würde alles mindestens doppelt so schnell machen. auch muss die Bewertungsfunktion verbessert werden. So gibt es zum Beispiel für jede Figur Karten, auf welche diese am liebsten zu plazieren ist. Auch sollte in minimax nicht nur in eine feste Tiefe geschaut werden, sondern ein Zuglimit festgelegt werden. So werden erzwungene Züge deutlich tiefer berechnet und auch zum Beispiel ein Matt 5 besser gefunden.

Für die Kommunikation verwenden wir .txt Dateien. Hier ist ein Beispiel, wie das funktionieren könnte. Beide Programme sind sehr ähnlich aufgebaut. Ein while Loop wartet bis in der Datei testcp.txt entweder „Python“ oder „C++“ steht, ist das der Fall, so wird der Benutzer gefragt in der jeweiligen Konsole gefragt, ob das Programm fortfahren soll. Falls dem so ist, ändert das Programm die Datei in „C++“ oder „Python“ um, nun beginnt das gleiche in der anderen Konsole. Diese Methode ist sicher nicht die eleganteste, aber eine sehr zuverlässige.

Mit Hilfe der Figurenerkennung, sowie des Algorithmuses weiß der Roboter, was er tun soll. Aber wie setzt dieser einen Zug um? Das Ansteuern bestimmter Felder unterteilt sich in drei Teilaufgaben: Das Zielfeld in Koordinaten speichern, die aktuelle Position des Greifers bestimmen und den Kranarm dann gezielt bewegen.

Hierzu nutzen wir die Eckpunkte des Schachbretts, die bereits in Koordinatenform ermittelt wurden. Anhand dieser vier Punkte wird ein perspektivisch verzerrtes Gitternetz mit 64 Feldern erzeugt. Dazu werden sechs Punkte mit gleichem Abstand voneinander auf den eckpunktverbindenden Linien errechnet, die jeweils mit dem gegenüberliegenden Punkt verbunden wird. Nun kann man an den Punkten das gewünschte Feld abzählen. In der Grafik sieht man, dass dann der Mittelpunkt des Feldes ermittelt wird. Dieser liegt dann in Koordinaten vor.

Grafik 4: Konvertierung von Feldern zu Koordinaten

Um die aktuelle Position des Greifers zu bestimmen, wird erneut eine Bilderkennung verwendet. Dieses Mal werden zwei farbige Punkte, die an dem Wagen befestigt sind getrackt.

Bild 10: Sicht der Kamera bei Greiferpositionsbestimmung

Anhand derer Position kann man nur mit einberechnung eines Offsets die vorläufige Position des Greifers bestimmen. Da sich die Farbpunkte jedoch nicht auf der selben Höhe wie der Greifer, wenn er die Figuren greift, befindet, ist eine perpektivische Korrektur notwendig. Da wir die Kamerahöhe und die Höhe der Farbpunkte kennen, lässt sich diese perspektive Verzerrung leicht errechnen.

Es gibt an dem Roboter vier Farbpunkte, da nicht immer bei jeder Position des Arms alle Punkte zu sehen sind. Das macht die Berechnung komplizierter: Wenn der rote oder blaue Punkt nicht zu sehen ist, wird die Position des Greifers mithilfe eines grünen Punkts berechnet.

Um den Kranarm zu bewegen, muss zunächst eine Schnittstelle zwischen dem Python Code und den Arduino Bauteilen hergestellt werden. Dies geschieht unter Verwendung von dem Programm Standard Firmata, was auf dem Arduino läuft und von Python aus angesteuert werden kann. Durch die Seilwinden ist es notwendig, dass sich zwei Motoren gleichzeitig drehen, um den Wagen zu bewegen, und gleichzeitig den Greifer nicht runterzulassen / hochzuziehen. Auch dies musste in dem Programm mit berücksichtigt werden. Wenn jetzt Koordinaten von aktueller Position und Ziel bekannt sind, werden nun diese beiden Informationen verglichen: Wenn die x-Koordinate des Roboters kleiner ist als die jene des Ziels bewegt sich der Wagen in Richtung Drehbasis. Wenn die y-Koordinate des Roboters größer ist als die jene des Ziels bewegt sich der Roboterarm gegen den Uhrzeigersinn. Diese Schritte werden wiederholt, bis die Greiferposition mit der des Ziels übereinstimmt. Durch hoch -und runter fahren des Greifers können nun Figuren gesetzt werden. Um feindliche Figuren zu bewegen, werden diese schlicht zuerst an den Rand des Spielfeldes gesetzt.

Momentan kann der Roboter Felder mehr oder weniger präzise ansteuern. Die Zugerkennung des Menschen funktioniert ziemlich gut. Der Schachalgorithmus gibt ebenfalls halbwegs vernünftige Züge aus. Auch die Kommunikation zwischen C++ und Python über eine „.txt“ Datei funktioniert. In allen diesen Bereichen kann sich der Roboter aber auch noch weiterentwickeln. So ist immernoch die Mechanik des Roboters nicht immer verlässlich und Fehleranfällig, das Ansteuern der Felder funktioniert nur sehr langsam und ungenau durch lange Bildverarbeitungszeiten und es gibt noch viele Bugs im Schachalgorithmus. Wir haben uns ein sehr umfangreiches Projekt ausgesucht, welches zudem eine Menge Probleme durch die Größe des Roboters birgt. So gab es viele Probleme mit zu schwachen Step Motoren. Auch die Kamera wurde immer höher gestellt, um alles zu erfassen, jedoch war diese sehr störanfällig, da nach jeder Veränderung der Position die Kamera neu kalibriert werden muss. In Zukunft könnte man Optimierungen im Bereich des Ansteuern der Felder vornehmen. Zum einen ein schnellerer Algorithmus zum Ansteuern der Felder, zum Anderen weniger Reibung bei dem Bewegen des Greifers würden hier helfen. Trotz des fehlenden Zusammenhangs und den vielen Optimierungen, welche wir noch an unserem Roboter vornehmen könnten, funktioniert er wenn man alles separat ansteuert. Daher hier ein abschließendes Video unseres Roboters in Aktion:

Video 4: Der Roboter in Aktion