(Computer and Human controlled Environment for Chess)

Alessio Mossudu, Ovidiu Victor Tatar

Berlin 2017/2018

CHE4C, MATE! spielt eine geringfügig vereinfachte Version von Schach, gegen Menschen und gegen sich selber. Der Mensch kann Figuren auf einem physischen Schachbrett bewegen, der Roboter kann Schachzüge erkennen/überprüfen und Schachzüge erwidern.

Anders als viele bereits existierende Schachprogramme kann CHE4C, MATE! insbesondere mit physischen Figuren auf einem physischen Brett interagieren, das Schachspiel ist nicht auf eine Benutzeroberfläche beschränkt (wobei ein Schachspiel auch über eine Benutzeroberfläche gespielt werden kann), Bewegungen sind direkt beobachtbar; dies ist als Grundsatz in den Entwicklungszielen verkörpert. CHE4C, MATE! spielt in Echtzeit, ist in der Lage verschiedene Schachvarianten zu spielen und ist erweiterbar, insbesondere was die Software angeht.
Damit hebt sich CHE4C, MATE! von vielen dedizierten Schachsystemen ab: Viele sind nicht in der Lage Figuren zu bewegen, fast alle verhalten sich wie eine „Blackbox“. Sie sind nicht erweiterbar, ihr innerer Aufbau bleibt verborgen.
Auch sind dedizierte Schachsysteme zu einer Seltenheit geworden, schließlich kann auf einem normalen PC Schach gegen den Computer oder andere Spieler gespielt werden. CHE4C, MATE! ist jedoch simpel und flexibel aufgebaut, bietet dennoch die Vorteile eines realen Schachspiels: Begonnene Partien können unterbrochen werden und später fortgesetzt werden, das Feeling eines realen Schachspiels bleibt erhalten.

Es wird empfohlen besondere Aufmerksamkeit den Dateien im unteren Bereich zu schenken. Auch haben wir einen Setup-Guide geschrieben, welcher bei der schnelleren Einrichtung und Benutzung von CHE4C-MATE! behilflich sein soll.

Ähnliche Projekte:

• Übersicht verschiedener Schachcomputer
• Stockfish: eines der mächtigsten Schachprogramme (OpenSource)
• Übersicht und Informationen der Uni Bayreuth
• Abstrakte Implementation einer Schach-KI über den MiniMax-Algorithmus der TU München
• zu CHE4C, MATE! ähnliches Hobbyprojekt

CHE4C, MATE! besteht grob aus 3 verschiedenen Untersystemen und deren Schnittstellen:

• Einer physischen Konstruktion, welche das Schachbrett und die Schachfiguren enthält und die Bewegung der Figuren ermöglicht (siehe Abb. 2);
• Ein System aus verschiedenen Sensoren (Schaltern), Aktuatoren (Stepper) und Steuereinheiten (insbesondere einem Arduino), welches die Interaktion mit dem Spieler und den Figuren kontrolliert (siehe die Abbildungen 9, 10, 11, 12);
• Einem separaten PC, der eine Schach-KI mit integrierter Schachbretterkennung und Benutzeroberfläche ausführt, welche Züge auswählen und analysieren kann. Sie sendet Befehle an die Steuerung durch den Arduino. Für die Kabelverbindungen siehe Abb. 8.

Im Folgenden ist grob der Ablauf eines Spielzuges und des Gegenzuges dargestellt:
Zunächst muss die Ausgangsposition der Figuren (wie beim normalen Schach) hergestellt werden. Davon ausgehend kann der Spieler seinen Zug auf dem Schachbrett tätigen (das Schachbrett ist in Abb. 2 gut zu sehen).
Wenn der Spieler einen Zug getätigt hat, muss er auf einen Bestätigungsknopf drücken (siehe Abb. 6), sodass das Ende des Spielzuges wahrgenommen wird. Über eine Kamera erkennt dann der Roboter das Schachfeld und die Position der Figuren auf dem Brett (siehe Abb. 7). Dafür werden die Schachfiguren mit verschiedenen Farben markiert, damit die Figuren durch Farberkennung möglichst präzise wahrgenommen werden können. Diese Informationen gelangen zunächst an den PC, werden für die Schach-KI kompatibel gemacht und an die KI weitergeleitet.
Alternativ kann der Spieler seinen Zug auf der Benutzeroberfläche ausführen. Die nachfolgenden Schritte bleiben gleich. Es macht keinen Unterschied, ob der Zug auf der Benutzeroberfläche oder auf dem physischen Brett getätigt wurde, es kann auch abwechselnd mit beiden Methoden gezogen werden.
Die KI prüft dann die Gültigkeit des Zuges und berechnet über eine abgewandte Form des MiniMax-Algorithmus den nächsten Zug. Diese Informationen werden verarbeitet und an den Arduino gesendet. Falls ein nicht korrekter Zug erkannt wurde, wird der Spieler durch das Aufleuchten einer RGB-LED (siehe Abb. 9) am Rand des Bretts informiert und muss einen gültigen Zug ausführen. Ist der Zug allerdings korrekt, dann bekommt der Arduino den Befehl einen kalkulierten Gegenzug durchzuführen.
Die Bewegung funktioniert folgendermaßen: Ein Gestell mit einem oben befestigten Elektromagneten (siehe Abb. 5) kann von zwei zueinander orthogonal stehenden Ebenen bewegt werden (siehe Abb. 3). Die beiden auf Rollen liegenden Konstruktionen werden über zwei Stepper-Motoren bewegt (siehe Abb. 4).
Sobald der Elektromagnet unter der zu bewegenden Schachfigur ankommt, wird er eingeschaltet. Schachfiguren sind am Boden mit ferromagnetischen Material versehen, sodass sie angezogen und bewegt werden können. Die Figur wird entlang der Linien des Schachfeldes bewegt, um nicht mit anderen Figuren zu kollidieren und gleichzeitig genug Abstand herzustellen, um die Anziehung von sich in der Nähe befindenden Figuren zu verhindern. Nach Beendigung des Zuges wird der Magnet wieder abgeschaltet und CHE4C, MATE! wartet auf den nächsten Spielzug.

Hier ist eine Demonstration der Funktionsweise:

Hier sind einige Abbildungen zum Gesamtsystem:

Abbildung 2: Gesamtkonstruktion

Abbildung 3: Bewegungsvorrichtung; Die Bewegung des Elektromagneten ist auf zwei Ebenen aufgeteilt.

Abbildung 4: Stepper der y-Ebene; Man sieht, dass durch Drehen des Zahnrades die Zahnstange und die daran befestigte Ebene über die Blockrollen bewegt werden kann.

Abbildung 5: Halterung des Elektromagnetens; Die hier gezeigte Version unterscheidet sich geringfügig (jedoch kaum visuell) von der aktuellen Version, da noch einige Muttern und Federn hinzugefügt wurden.

Abbildung 6: Bestätigungsknopf an der Seite des Balkens, am dem die Webcam befestigt ist

Abbildung 7: ideales Sichtfeld der Webcam auf das Schachbrett; Die kleinen Holzblöcke (teilweise mit falschen Markierungen) sind die Figuren.

Abbildung 8: USB-Kabelverbindungen an der Seite des Roboters; Das Kabel des Arduinos sitzt an der einen Stütze des Schachbrettes, das Kabel der Webcam am Balken, an dem auch die Webcam befestigt ist.

Hier sind einige Abbildungen zur Elektronik von CHE4C, MATE!; für die Bedeutung der Markierungen siehe die Legende weiter unten.

Abbildung 9: reale Verschaltung des Steckbretts am Roboter

Abbildung 10: Stecker/Anschlüsse zu den Netzteilen

Abbildung 11: Schaltplan mit Markierungen; Für eine Version ohne Markierungen siehe Abb. 25.

Abbildung 12: Grafik des Steckbretts mit Markierungen; Für eine Version ohne Markierungen siehe Abb. 26.

♦ : Elektromagnet-Steuerung
♦ : Bestätigungsknopf- & Mikroschalter-Verbindung
♦ : RGB-LED
♦ : y-Stepper-Steuerung
♦ : x-Stepper-Steuerung
♦ : Netzteil-Verbindung für die Motoren
♦ : Netzteil-Verbindung für den Elektromagneten

Im Folgenden werden die einzelnen Teilbereiche detailliert beschrieben.

Unser Roboter ist auf einer großen Grundplatte befestigt. An der unteren Seite der Grundplatte sind einige Holzbalken per Klebeband befestigt, damit die Konstruktion stabil stehen kann; Auf der Unterseite sind nähmlich auch viele Schrauben befestigt, auf denen die Konstruktion nicht stehen soll.
Auf der Grundplatte sind vier Balken mit Winkeln befestigt, auf denen das Schachbrett und die y-Bewegungsebene liegen. Die Balken sind so plaziert, dass der Elektromagnet etwa 44cm oder mehr Platz hat bewegt zu werden. Auf einem weiteren Balken ist die Webcam befestigt.
In der einen Ecke sind zwei Mikroschalter, jeweils einer für jede Bewegungsebene, befestigt; Diese dienen dazu die Ausgangsposition des Elektromagneten festzulegen, wie im Abschnitt Steuerung beschrieben wird.

Jede der Bewegungsebenen besteht aus 3 Holzstangen und einem Aluminiumrohr, welche ein Quadrat bilden. An der einen Seite jeder Ebene sind zwei 25cm Zahnstangen zusammenhängend befestigt (siehe Abb. 13). Leider sind die Bewegungsebenen beide etwas schief, sodass wir ziemlich viele Rollen brauchen, auf denen sich die Ebenen bewegen können.
An den Seiten der Bewegungsebenen sind jeweils einige Barrieren in Form von Holzbalken oder -platten, damit die Bewegungsebenen seitlich nicht ausbrechen können.
Die Stepper sind durch jeweils fünf Winkel und Kabelbindern festgehalten (siehe Abb. 14). Die Stepper haben ein Zahnrad, welches genau auf die Zahnstangen der Bewegungsebenen passt. Durch Drehung des Zahnrades können wir also eine Ebene bewegen (siehe Abb. 4). Wie wir durch Messungen ermittelt haben führt jeder Schritt eines Steppers zu einer Bewegung der Bewegungsebene um 0.0234375mm.

Abbildung 13: Eine der Bewegungsebenen, beide sind nahezu identisch;

Abbildung 14: Halterung der Stepper, hier am x-Stepper; Die Halterung des y-Steppers ist analog aufgebaut.

Die Halterung des Elektromagneten ist wohl der komplexeste und problematischste Teil der ganzen Konstruktion. Zum Zeitpunkt der Abgabe des Projektes funktioniert die Halterung z.B. nicht, obwohl sie ein paar Tage vorher funktionierte. Wir umreißen kurz den Werdegang der jetzigen Lösung, da sich dies vielleicht für andere Gruppen als nützlich erweist.
Das jetzige Design ist die fünfte Iteration der Halterung (siehe Abb. 5). Das Grundprinzip ist bei allen gleich und schon in der Projektplanungsphase entstanden (siehe Abb. 15):
Jeweils zwei Holzplättchen sind in einem Abstand platziert, sodass je einer der Aluminiumstangen der Bewegungsebenen durchpasst. Die Halterung kann auf den beiden Stangen gleiten. Auf der oberen Seite sitzt der Elektromagnet auf einem weiteren Holzplättchen, getragen von Federn um Höhenunterschiede der Konstruktion ausgleichen zu können.
Die ersten beiden Versionen waren vollständig aus Holz. Dadurch ergaben sich zwei Probleme:

1. Die Konstruktion ist unflexibel. Als wir feststellten, dass wir die Ebenen doch lieber etwas näher zusammenbringen war plötzlich die erste Version zu groß.
2. Die Konstruktion hält keine Druck- und Zugspannung aus. Wir hatten versucht die einzelnen Holzkomponenten mit Nägeln und Klebeband zusammenzuhalten, da diese ziemlich filigran waren. Es hat sich aber herausgestellt, dass diese sofort auseinanderbrechen, wenn wir versuchen den Elektromagneten zu bewegen.

In der nächsten Version haben wir es geschafft diese beiden Probleme zu lösen:
Wie auch in der aktuellen Version sind die vier Holzplättchen durch Schrauben und Muttern festgehalten. Durch verschieben der Muttern ist die Konstruktion auch zu einem gewissen Grade Höhenverstellbar. Außerdem halten die Schrauben die Belastungen bei der Bewegung aus.
Nun war aber das Problem, dass die Halterung nicht mehr gleiten konnte, da zu viel Reibung entstand. In den nächsten Versionen verwendendeten wir daher 8 kleine Rädchen, jeweils vier für jede Ebene, welche auf den Schrauben befestigt sind. Diese gleiten wunderbar auf den Aluminiumstangen und können sich zusätzlich drehen. In den nächsten Iterationen hatten wir noch mit den Muttern zu kämpfen; Diese müssen richtig eingestellt sein, damit die Halterung gut gleiten kann.

Abbildung 15: Sizze der Elektromagnethalterung aus der Projektplanungsphase

Das Schachbrett musste möglichst dünn sein, damit die Anziehungskraft des Elektromagneten bei voller Leistung ausreicht um die Figuren zu bewegen. Dies haben wir mit der 2mm dicken Plexiglasscheibe wohl gut erreicht. Auf dieser Scheibe haben wir selbst ein Schachbrett aufgezeichnet.
Dieses besteht aus 8 x 8 quadratischen Feldern mit jeweils 4cm Kantenlänge. Optimalerweise könnte der Elektromagnet auch noch die 4cm Rand auf beiden Seiten erreichen, wobei er zum Zeitpunkt der Abgabe lediglich 2cm vom Rand erreichen kann. Dies reicht in der Regel auch aus; der Rand wird benötigt um Figuren zu entfernen, wie im Abschnitt Steuerung beschrieben ist.
Die Figuren haben einen Radius von maximal 1cm um bei der Bewegung nicht zu kollidieren. Wie im Abschnitt Schachfigurenerkennung erklärt, sind die Figuren oben farbig markiert. Für ein Bild der Figuren und des Schachbrettes siehe Abb. 7.

CHE4C, MATE! soll primär ein Gegenspieler für Schach sein. Dafür sind Interaktionen mit dem Spieler äußerst wichtig. Der Spieler sollte z.B. wissen, in welchem Stadium sich der Gegenspieler befindet. Davon abgesehen interagiert der Spieler natürlich mit den Figuren, diese Interaktion soll sich aber nicht wesentlich vom normalen Schach unterscheiden. Für die Auswertung dieser Interaktion siehe Abschnitt Schachfigurenerkennung. Auch kann der Spieler über eine Benutzeroberfläche mit CHE4C, MATE! interagieren, dies wird genauer im Abschnitt Benutzeroberfläche erklärt.

Eine RGB-LED wird benutzt um den Spieler über den Status von CHE4C, MATE! zu informieren. Je nach Status zeigt die LED ein anderes Verhalten (siehe Tabelle 1). Über den Bestätigungsknopf (siehe Abb. 6) kann der Spieler seinen Zug auf dem physischen Brett bestätigen.

Zur Kommunikation zwischen dem PC und dem Arduino im Bezug zur Benutzer-Interaktion steht das SUIfM-Protokoll (Simple-User-Interface-for-Machinery) zur Verfügung. Die genauere Funktionsweise unserer selbstentwickelten Protokolle wird im Abschnitt Kommunikation mit der Steuerung erklärt.
Das SUIfM-Protokoll beschreibt ein sehr allgemeines Protokoll, welches eine Bestätigungsnachricht und eine Statusübermittelung (in Form des Control-Bytes; siehe Tabelle 1) definiert. Die Interpretation und Auslösung der Bestätigung, sowie die Interpretation und Bedeutung des Status werden nicht definiert. Es wird lediglich die Bitte ausgesprochen, dass diese Informationen auf eine interaktive Weise benutzt werden.
Unsere Implementation, festgelegt durch ControlStatus und suifm-device.ino, definiert somit konkret die Bedeutung und die Interpretation dieser Werte (siehe Tabelle 1). Die Bestätigungsnachricht (diese ist /confirm\r\n) wird bei Betätigung des erwähnten Bestätigungsknopf an den PC gesendet. Damit das Protokoll auf die Eingaben des Benutzers reagieren kann und zeitabhängig die LED steuern kann, muss die interact()-Methode durch das Hauptprogramm auf dem Arduino (che4c-arduino.ino) kontinuierlich aufgerufen werden.

Bei Programmstart auf dem PC wird eine Benutzeroberfläche gestartet (siehe Abb. 16). Durch Drücken der Shift-Taste wird einem das Sichtfeld der Webcam angezeigt.
Auf der GUI können auch Schachfiguren gesteuert werden und der Spielverlauf wird angezeigt. Zum Bewegen einer Figur sollte Start- und Zielfeld ausgewählt werden und anschließend Enter gedrückt werden. Falls eine andere Auswahl gewünscht ist, kann die Entf- bzw. die Del-Taste gedrückt werden um die Auswahl zurückzusetzen. Durch das Mausrad kann die Umwandlung in eine andere Figurenart eingestellt werden (dies wird bei der Umwandlung von Bauern benutzt). Um eine Rochade zu tätigen sollte vom eigenen König auf den gewünschten Turm gezogen werden.
Die Benutzeroberfläche hat noch einige andere Funktionen, welche allerdings noch nicht über die GUI gesteuert werden können. Diese können allerdings eingestellt werden, wenn man einige globalen Variablen in der Hauptdatei CHE4C.pde ändert. Siehe dazu Tabelle 2.

Die Bilddateien der Figuren haben wir vom Wikipedia-Benutzer Cburnett¹⁾. Um die Figuren und das Schachbrett darzustellen, zeichnen wir einfach ein Quadrat in der jeweiligen Farbe für jedes Schachfeld, und für jede Figur das entsprechende Bild.

Abbildung 16: GUI auf dem PC; blau markiert das Startfeld, rot markiert das Zielfeld (Änderungen vorbehalten)

Die Schachfiguren sind alle mit einem farbigen Punkt auf dem Kopf markiert.
Die Schachfigurenerkennung ist in der Klasse FigureDetector implementiert.
Beim Aufruf von calibrate(PImage) scannt FigureDetector das ganze Bild nach der oberen linken und unteren rechten Ecke des Schachfeldes ab. Es ist hierbei egal, ob die Schachfiguren sich auf dem Feld befinden oder nicht, weil erstens das Programm abbricht, sobald es die Ecke gefunden hat und zweitens keine der Schachfiguren schwarz markiert ist.
Außerdem werden anhand einer weißen Stelle (ein Blatt Papier neben dem Feld, siehe Abb. 7) variierende Lichtverhältnisse kompensiert. Normalerweise sollte reines Weiß die RGB-Werte (255, 255, 255) haben, aufgrund der Lichtverhältnisse können sich diese Werte jedoch verändern, sodass im Array whiteDifArray der Wert für die Differenz vom Weiß eingespeichert wird. Wenn z.B. etwas rötliches Licht auf die weiße Stelle strahlt, dann ist der detektierte RGB-Wert zum Beispiel (255, 230, 230). Die Differenz zum eigentlichen „Weiß“, in diesem Beispiel also (0, 25, 25) wird festgehalten und ab nun bei allen folgenden Messungen dazuaddiert und damit korrigiert. Die Werte bei schwächerem Licht werden durch die Verwendung dieser Werte künstlich angehoben und dadurch nutzbar gemacht.
Diese Methode sollte beim Programmstart aufgerufen werden und wird zusätzlich in zufälligen Intervallen durch analyse(PImage) aufgerufen um zu rekalibrieren.

Diese zwei Punkte werden durch die Methode analyse(PImage) benutzt, welche dann den von den zwei Pixeln eingegrenzten Bereich in ein 8 x 8 Feld aufteilt und jedes Feld nach bestimmten Farben absucht. Ob die Suche erfolgreich war oder nicht wird im Array figureArray festgehalten. Dabei steht jede Zahl von 1 bis 12 für eine Schachfigur und die 0 für keine Schachfigur (siehe Tabelle 3).
Beim Aufruf der Methode getFigures() wird figureArray in eine ArrayList<ChessFigure> umgewandelt. Diese kann vom Hauptprogramm direkt benutzt werden um daraus eine Instanz von Checkerboard mit den neuen Figuren zu erstellen. Die neuen Positionen der Figuren werden natürlich überprüft, um potentielle Betrüge zu verhindern (siehe dazu den Abschnitt programminterne Darstellung eines Schachspiels).

Das Schachzüge und das Schachbrett bzw. die Figuren müssen im Programm auf dem PC verfügbar sein. Wir haben uns für eine objektorientierte Implementierung entschieden, da diese verständlicher umzusetzen ist und flexibel erweiterbar ist. Es sei angemerkt, dass eine Implementierung auf Arrays wesentlich leistungsstärker sein kann (, aber auch weniger selbsterklärend ist und nur schwer zu erweitern ist). Im Folgenden wird die Funktionsweise unserer Implementierung erklärt (dazu begleitend Abb. 17):

• Instanzen des Enums²⁾ ChessFigureColor stellen eine Spielerfarbe (Schwarz, Weiß) dar. Diese wird insbesondere von Figuren benutzt um zu bestimmen, zu welchem Spieler sie gehören. Aber hierdurch wird auch eine Referenz zum aktuell Ziehenden gehalten und ChessFigureColor wird benutzt um ausschließlich die nächsten Züge für einen Spieler zu berechnen, etc. (deshalb haben eine Vielzahl von wichtigen Methoden ChessFigureColor als Argument, wie Abb. 17 zeigt).
• Instanzen des Enums ChessFigureType stellen einen Figurentyp (König, Dame, Bauer, etc.) dar. Diese wird insbesondere von Figuren benutzt um zu bestimmen, zu welchem Spieler sie gehören. Aber hierdurch wird auch eine Referenz zum aktuell Ziehenden gehalten und ChessFigureColor wird benutzt um ausschließlich die nächsten Züge für einen Spieler zu berechnen, etc. (deshalb haben eine Vielzahl von wichtigen Methoden ChessFigureColor als Argument, wie Abb. 17 zeigt).
• Instanzen der Klasse ChessFigure stellen Schachfiguren dar. Sie haben eine Position (durch eine x- und y-Koordinate geprägt), eine Spielerfarbe und einen Figurentyp. Figuren können sich auf verschiedene Weise bewegen und haben verschiedene relative Werte (sogennante Bauerneinheiten), siehe dazu auch Tabelle 4.
• Instanzen der Klasse Checkerboard stellen Schachbretter (für klassisches Schach) dar, insbesondere den Zustand eines Schachbrettes. Eine solche Instanz kann also als bestimmte Konfiguration von Figuren auf dem Brett angesehen werden. Sie besitzen eine Liste von ChessFigure und zwei Wahrheitswerte um festzuhalten, ob die jeweilige Spielerfarbe eine Rochade getätigt hat. Die Klasse Checkerboard und von ihr ableitende Klassen (z.B. AntichessCheckerboard, siehe Abb. 17) legen die Zugregeln von den einzelnen Figuren fest (getSuccessionalBoards(ChessFigure)), bestimmen somit alle gültigen Folgezüge (getSuccessionalBoards()) und legen Gewinner und Verlierer (hasWon(ChessFigureColor) & hasLost(ChessFigureColor)) fest. Dies ermöglicht das einfache Hinzufügen neuer Spielmodi durch Erstellen einer Unterklasse von Checkerboard; neue Zug- und Gewinnregeln können dann hinzugefügt werden.
• Instanzen der Klasse ChessMovement stellen Schachzüge dar. Sie können den Zustand von Checkerboard-Instanzen gemäß des Schachzuges, den sie darstellen, ändern. Diese Schachzüge können direkt in Befehle für die Steuerung umgewandelt werden (toSChFiMCommandSequence()).

Eine Instanz von Checkerboard stellt immer den aktuellen Spielzustand dar. Diese besitzt auch gleichzeitig die Fähigkeit alle möglichen, gültigen Folgezüge zu berechnen. (Diese Berechnung dauert wenige Millisekunden.) Damit ist sie auch in der Lage die Gültigkeit eines Zuges zu überprüfen. Die Methode isSuccessionalBoard(Checkerboard) überprüft, ob das übergebene Schachbrett-Objekt Resultat eines Folgezuges sein kann. Die Schach-KI kann somit nur Züge ausführen, welche durch getSuccessionalBoards() generiert werden. Die Spielzüge des Spielers selbst werden aber durch dieses System auf Gültigkeit überprüft. Um die Anfangskonstellation des Schachspiels zu erhalten, existiert ein eigener Konstruktor (new Checkerboard(true)).
Ein Schachzug wird als Zustandswechsel von einem Checkerboard zum nächsten Checkerboard angesehen. Ein Wechsel bei der nur eine Figur auf ein gültiges Feld gezogen wird wäre damit z.B. ein möglicher, gültiger Zug. Um einen Zug auszuführen muss also nur die Referenz von der aktuellen Checkerboard-Instanz auf die nächste Instanz gewechselt werden.
Die ChessMovement-Klasse scheint daher überflüssig, da es nun zwei unterschiedliche Vorgehen zur Darstellung eines Schachzuges gibt. Zu einem gewissen Grad ist sie dies auch. Jedoch wird sie benötigt, um Schachzüge in Befehle für die Steuerung umzuwandeln. Jedoch weißt dieses System Redundanz auf und könnte daher auch durch eine Funktion ersetzt werden, welche die Unterschiede zwischen zwei Checkerboard-Instanzen in Befehle umwandelt. Außerdem führt ChessMovement zu einer Intransparenz der Rochade und einer eingeschränkten Erweiterbarkeit von Schachzügen. Eine solche Funktion wäre aber vermutlich sehr komplex, weswegen wir uns zunächst für das System mit der zusätzlichen ChessMovement-Klasse entschieden haben.

Die Zugregeln für das klassische Schach sind bereits in Checkerboard implementiert. Die Implementation ist möglichst kompakt gehalten, was aber auch zu einer komplexen Implementation führt. Die einzelnen Züge folgen aber einfachen Zugregeln. Es folgt eine Erklärung der Zugregeln, wie sie abstrakt umgesetzt wurden:

• Alle Figuren können sich nur innerhalb des Schachbretts bewegen. Figuren können nicht auf Figuren der gleichen Spielerfarbe ziehen.
• Die Königin kann für die Berechnung der möglichen Züge als Läufer und Turm gleichzeitig betrachtet werden.
• Türme und Läufer können sich auf 4 Geraden bewegen (4 Diagonalen für Läufer, 4 Himmelsrichtungen für Turm), bis sie auf eine andere Figur treffen. Ist die andere Figur eine gegnerische Figur, können sie diese Schlagen. Türme und Läufer können weiter nicht ziehen, die Betrachtung möglicher Züge in die aktuelle Richtung wird also angehalten.
• Springer können sich grundsätzlich auf 8 Feldern bewegen, welche allerdings ein Oktagon bilden. Aus Symmetriegründen können sich alle acht Züge als Drehung eines einzigen, l-förmigen Zuges berechnen lassen.
• Bauern können sich ein Feld nach vorn bewegen, falls das Feld frei ist, oder diagonal nach vorn bewegen, falls dort eine gegnerische Figur vorhanden ist. Falls ein Bauer noch nicht bewegt wurde, kann er einen Doppelsprung ausführen, sofern beide vorderen Felder frei sind. Erreicht ein Bauer die gegnerische Feldbegrenzung muss er in eine beliebige andere Figur umgewandelt werden.
• Der König kann sich auf alle acht Nachbarfelder bewegen. Züge, die den König ins Schach bringen sind ebenfalls gültig. Falls beide beteiligten Figuren nicht bewegt wurden und der Raum zwischen den Figuren frei ist, kann ein König mit einem Turm der selben Farbe eine Rochade durchführen. Eine Rochade bewegt den König zwei Felder in Richtung des Turmes. Der Turm wird dabei ein benachbartes Feld von der Ausgangsposition des Königs gestellt, und zwar in Richtung seiner vorherigen Position.

Diese Zugregeln haben allerdings drei wesentliche Einschränkungen, die sich daraus ergeben, dass vorherige und nachfolgende Schachzüge nicht analysiert werden:

1. Bauern können nicht en passant schlagen.
2. Es existiert kein Remis durch wiederholt auftretende Figurenkonstellationen o.ä..
3. Es existiert kein Patt. Wenn keine andere Möglichkeit existiert, muss der König ins Schach gezogen werden.

Dies bedeutet also somit auch, dass weder Schach-KI, noch Spieler von diesen drei Phänomenen profitieren können und dass ein Unentschieden/Remis unmöglich ist. Die Unfähigkeit einen Schachzug zu tätigen führt damit auch nicht zu einem Remis, sondern zu einer verlorenen Partie für den zugunfähigen Spieler. Außerdem wird das Spiel immer „bis zum Ende“ gespielt, d.h. der gegnerische König muss geschlagen werden um zu gewinnen.

Abbildung 17: UML-Klassendiagramm für die relevanten Klassen der Spieldarstellung mit den wichtigsten Attributen und Methoden; Ausschnitt des ganzen Programms

Die KI benutzt die Klassen und Funktionen, welche im Abschnitt programminterne Darstellung eines Schachspiels und Abbildung 17 beschrieben wurden, um Folgezüge zu berechnen. Da die KI eine der beiden Spielerfarben oder sogar beide gleichzeitig beliebig spielen kann, ist unsere Implementierung der unten beschriebenen Algorithmen immer Spielerfarben-bezogen.

Um Züge auswählen zu können, muss der Zustand des Schachspiels im Bezug zur Gewinnchance bewertet werden können. Die getScore(ChessFigureColor)-Methode von Checkerboard ist in unserem Fall diese „Bewertungsfunktion“. So eine Bewertung qualitativ durchzuführen ist etwas problematisch; oft lässt sich gar kein Unterschied zwischen Zügen im Bezug zur Bewertung einbauen. Ist es zum Beispiel besser den ersten Zug mit einem Pferd oder einem Bauern zu tätigen? Aber andererseits lässt sich sagen, dass ein Figurenvorteil durchaus bewertbar ist.
Wenn die Bewertungsfunktion positive Werte zurückgibt, heißt das, dass das Spiel für den betrachteten Spieler besser läuft, als für den Gegner. Negative Werte bedeuten folglich, dass das Spiel für den Gegner besser läuft. Je größer der Betrag des zurückgegebenen Wertes ist, desto besser sind die Gewinn- bzw. Verlustchancen.
Es sei angemerkt, dass Bewertungsfunktionen für Schach, z.B. bei Stockfish, sehr komplex werden können und damit einzelne Zustände akkurater bewerten können, da sie Faktoren, wie z.B. Konfiguration der Bauern, Bedrohte Figuren, Mobilität, Sicherheit des Königs mit einberechnen. Unsere Implementation ist im Vergleich damit relativ primitiv.

Die Grundlage jeder Bewertungsfunktion sollte der Figurenvorteil sein. Da wir aus Sicht einer Spielerfarbe bewerten, summieren wir die Punkte der Figuren der Spielerfarbe und bilden die Differenz mit der Summe der Punkte der gegnerischen Figuren. Um die Punktanzahl einer Figur zu bestimmen haben wir die Methode getFigureScore(ChessFigure) in Checkerboard implementiert, welche getRelativeValue() von ChessFigureType aufruft und diese Werte (siehe Tabelle 4) geringfügig verändert zurückgibt. Diese Bewertung sieht dann beispielsweise wie bei Abb. 18.

In einigen Fällen, wird jedoch, wie schon erwähnt, dieser Wert verändert³⁾:

• Bauern sind mehr Punkte wert, wenn sie auf dem Brett avancieren und weniger Figuren auf dem Brett sind, da sie umgewandelt werden können.
• Läufer werden wertvoller, wenn weniger Figuren auf dem Brett sind. (40% wertvoller bei 0 Figuren)
• Springer verlieren am Wert, wenn weniger Figuren auf dem Brett sind. (10% wertvoller bei 32 Figuren, 10% weniger wertvoll bei 0 Figuren)

Außerdem wird in getScore(ChessFigureColor) die Gesamtpunktzahl maximal bzw. minimal, wenn gewonnen bzw. verloren wurde. Dies resultiert letztendlich in einer Bewertung, welche beispielsweise in Abb. 19 dargestellt wurde.

Abbildung 18: Bewertung einer Spielbrettkonfiguration (Checkerboard) aus Sicht des weißen Spielers; Die hier dargestellte Bewertung berücksichtigt nur den Figurenvorteil.

Abbildung 19: Bewertung einer Spielbrettkonfiguration (Checkerboard) aus Sicht des weißen Spielers; Die hier dargestellte Bewertung ist gemäß unserer kompletten Implementierung. Wie man sieht, ist der Unterschied im Ergebnis nicht enorm.

Weiterführende Links zur Bewertungsfunktion in Schachprogrammen:

• Artikel über die Grundlagen von Bewertungsfunktionen für Schach
• Diskussion über Bewertungsfunktionen für Schach

Da Schachbrett-Zustände bewertet werden können, können wir nun einen bekannten Algorithmus aus der Spieltheorie anwenden: den MiniMax-Algorithmus.
Dieser eignet sich insbesondere für Schach, aber auch für andere Spiele, wie z.B. Tic-Tac-Toe kann er angewendet werden. Der MiniMax-Algorithmus wird ebenfalls von den besten Schachprogrammen verwendet⁴⁾.

Das Grundprinzip des Algorithmus ist die eigenen Punkte zu maximieren und die des Gegners zu minimieren. Wir sollten aber davon ausgehen, dass der Gegner ebenfalls nach diesem Prinzip spielt bzw. dass der Gegner ebenfalls den besten Zug finden kann.
Nehmen wir an, wir wollten den besten Zug bestimmen, wenn wir nur unseren eigenen Zug und den Folgezug des Gegners bedenken. Wir erhalten die Farbe Weiß, der Gegner die Farbe Schwarz. Können wir z.B. mit unserer Dame die Dame des Gegners schlagen, scheint dies sehr vorteilhaft, allerdings nicht mehr, wenn der Gegner in seinem Zug unsere Dame schlagen kann. Möglicherweise gibt es einen anderen, besseren Zug. Wir sollten also am besten alle möglichen Zugkombinationen durchgehen. Wie im Abschnitt programminterne Darstellung des Schachspiels erklärt wurde, können wir die Methode getSuccessionalBoards(ChessFigureColor) benutzen um alle möglichen Folgezüge einer Checkerboard-Instanz zu bestimmen. Wir gehen folgendermaßen vor:
Wir durchlaufen alle unseren möglichen Züge, also rufen wir getSuccessionalBoards(ChessFigureColor.WHITE) mit unserer eigenen Spielerfarbe auf. Nun müssen wir aber für jeden unserer eigenen Züge die darauffolgenden Züge des Gegners bedenken. Also rufen wir für jeden unserer eigenen Züge auch getSuccessionalBoards(ChessFigureColor.BLACK) auf und durchlaufen somit für jeden Zug auch alle möglichen Folgezüge. Nun bewerten wir die Züge des Gegners und wählen den Folgezug aus, welcher für den Gegner am besten ist (wir gehen schließlich davon aus, dass der Gegner bestmöglich ziehen wird). Da wir davon ausgehen können, das der jeweils beste Folgezug des Gegners das letztendliche Ergebnis unseres eigenen Zuges ist, heißt das, dass die Punktzahl unseres eigenen Zuges sich immer nach der Punktzahl des besten Gegnerzuges richtet. Nun damit wir unseren besten Zug auswählen, müssen wir die Punktzahl maximieren, also den Zug auswählen, der nach der Betrachtung der gegnerischen Züge, immer noch die höchste Punktzahl erreicht.
Unser hier dargestelltes Szenario wäre eine Suche mit einer Suchtiefe von 2. Jedoch können wir desto besser Spielen, desto mehr Züge wir „vorausdenken“, sodass höhere Suchtiefen vorteilhaft sind. Da die Betrachtung aber somit immer komplizierter wird, wollen wir versuchen uns den Algorithmus bildlich darzustellen:
Die Abfolge von Zügen wird typischerweise als Spielbaum dargestellt. Jede Ebene stellt eine Runde dar, die oberste Ebene ist der momentane Zustand und enthält somit nur den momentanen Spielzustand. Die Anzahl der Ebenen entspricht somit der Anzahl der Runden bzw. der Suchtiefe. Aus jedem Spielzustand einer Ebene gehen Verbindungen zu den resultierenden Folgezuständen in der nächsten Ebene. Wir betrachten zunächst die unterste Ebene, wählen dort die besten Züge aus, bedenken diese in der nächsthöheren Ebene, usw. bis wir in der obersten Ebene angekommen sind und den bestmöglichen Zug für die jeweilige Suchtiefe erhalten haben. Die Abbildung 20 zeigt einen vereinfachten Spielbaum und die Auswertung über den MiniMax-Algorithmus.

Anmerkung: In der Implementation wird nicht ebenenweise vorgegangen, sondern zunächst wird der linke Teilbaum bis in die unterste Ebene durchlaufen. D.h. die Suchrichtung ist von links nach rechts, von unten nach oben. Für eine detailliertere Erklärung hierzu siehe (beschränkte) Tiefensuche.

Bei mehreren Zügen, welche gleichgut sind, sollte einer der Züge zufällig ausgewählt werden, damit das Spiel interessant bleibt. Wir benutzen HashMaps um alle möglichen Züge anzugeben (getSuccessionalBoards()). Diese bieten keine Garantie ihre ursprüngliche Ordnung beizubehalten. Bei der Menge an Objekten, die wir der HashMap hinzufügen, ist das Verhalten der HashMap in Bezug zur Reihenfolge nahezu zufällig⁵⁾. Somit können wir uns darauf beschränken lediglich den ersten gefundenen besten Zug auszuwählen.

Abbildung 20: ein vereinfachter Spielbaum der Tiefe 4, weitere Züge sind möglich, werden jedoch nicht betrachtet; Beginnend bei der untersten Ebene werden die besten Züge einer Ebene ausgewählt und das Ergebnis in die nächsthöhere Ebene übertragen. Für die detailliertere Funktionsweise siehe Abb. 21.

Für höhere und/oder variable Suchtiefen⁶⁾ wird das Prinzip der Rekursion genutzt, da der Progammcode damit wesentlich kompakter, einfacher und flexibler ist.
Da wir davon ausgehen, dass der Gegner ebenfalls seine Punkte maximiert, werden wir auf jeder Ebene maximieren. Wir müssen aber die Punkte beim Übertrag in die nächsthöhere Ebene negieren: Wenn der Gegner eine positive Bewertung erhalten hatte, heißt das, dass er am gewinnen ist. Für uns resultiert das in einer negativen Bewertung und umgekehrt. Dies entspricht der sogenannten NegaMax-Variante des MiniMax-Algorithmus. Die Funktionsweise ist konkret mit beispielhafter Bewertungsfunktion in Abb. 21 dargestellt.

Abbildung 21: ein vereinfachter Spielbaum der Tiefe 4, weitere Züge sind möglich, werden jedoch nicht betrachtet; Der NegaMax-Algorithmus mit einer beispielhaften Bewertungsfunktion sind dargestellt. Die Hintergrundfarbe zeigt an, wer den vorherige Zug getätigt hat. Es können alle Spielbrettzustände bewertet werden, jedoch ist die Bewertung nur auf Blättern (Zustände ohne Folgezuständen) wichtig. In der untersten Ebene werden alle Zustände ausgewertet und in die nächsthöhere Ebene übertragen. Beim Übertragen in die nächsthöhere Ebene wird das Ergebnis negiert, da jetzt aus der Sicht des anderen Spielers bewertet wird. Der Prozess wiederholt sich nun fortlaufend.

Um die Laufzeit der Suche zu senken, also den besten Zug schneller zu finden, benutzen wir die Alpha-Beta-Suche. Diese Optimierung benutzt das Prinzip, dass einige Züge wichtiger sind als andere; Menschen benutzen diesen Trick intuitiv. Wenn z.B. die König bedroht wird, dann sollte man nicht Züge betrachten, die dies nicht beheben, da das Zeitverschwendung wäre. Ob wir z.B. einen Bauern in eine Dame umwandeln können, spielt überhaupt keine Rolle, wenn wir im Folgezug verlieren.
Durch die Alpha-Beta-Suche wird also der Spielbaum auf die wichtigeren Züge verkleinert.

Letztendlich kann das ganze dann wie in Abb. 22 aussehen.

Abbildung 22: ein beispielhaftes Spiel, wie die KI gegen sich selbst spielt; Im letzten Zug hat die KI den König ins Schach bewegt, da es keine Möglichkeit mehr gab dem Verlieren zu entkommen. Jede Bewegung hätte innerhalb von vier Zügen zum Verlust geführt.

In diesem Abschnitt beschäftigen wir uns mit der Elektronik, der Steuerung durch den Arduino und wie wir durch Zusammenspiel von Elektromagneten und Steppermotoren Figuren bewegen können. Grundsätzlich beziehen wir uns auf die Datei schfim-device.ino, wenn wir von der Software reden.

Im Gegensatz zum restlich hier beschriebenen Programm befindet sich die LED-Ansteuerung in der Datei suifm-device.ino.
Grundsätzlich bestehen RGB-LEDs aus 3 kleineren farbigen LEDs, welche in einem Gehäuse sitzen. Durch Lichtdiffusion können die einzelnen Farbbereiche gemischt werden und ein Großteil des sichtbaren Lichtspektrums abgedeckt werden; bei unserer LED ist dies aber momentan nicht der Fall, sie kann die drei Grundfarben nicht mischen. Unsere RGB-LED besitzt 4 Pins: jeweils einen Pin für jeden „Farbkanal“ (rot, grün, blau) und einen Pin als gemeinsamen Minuspol (siehe Tabelle 7.
Um die RGB-LED anzusteuern haben wir eine eigene Library geschrieben, welche in den Programmdateien zu finden ist. Diese muss zur Verwendung des Programms ebenfalls installiert werden.
Die einfachste Methode die LED über die Library zu steuern ist auf das RGBLed-Objekt die Methode writeColor(int, int, int) aufzurufen: Die einzelnen Werte für die Farbkanäle werden ggf. negiert, die Spannungen werden durch analogWrite(…) für die RGBLed gesetzt. Mit der Methode writeColor(unsigned int) können Farben z.B. als RGB-Hexcode übermittelt werden, dabei wird der Farbcode per Bitshifting in die einzelnen Kanäle unterteilt; z.B. writeColor(0xFF66AA).

Um die Steppermotoren zu steuern benutzen wir je einen Stepper-Driver. Wenn man den Erklärungen auf dieser Seite und der Seite der jeweiligen Stepper-Drivern folgt, sollte man in der Lage sein die Stepper-Driver richtig zu einzustellen, verkabeln und die Steuersignale richtig zu verwenden (siehe Tabelle 7, Abb. 12). Für die Stromversorgung der Stepper benutzen wir eine separate 5V Stromquelle (siehe Abb. 10), da der Arduino zu wenig Leistung liefert um die Stepper antreiben zu können. Wir benutzen die weißen, low-voltage Stepper-Driver, welche auch mit niedrigen Spannungen, wie 5V auskommen, sie könnten aber variabel verschiedene Spannungen von benutzen.
Für die Ansteuerung der Stepper-Driver benutzen wir die eingebaute Stepper-Library und können dann per step(int) einfach die Anzahl der Schritte angeben, welche die Stepper ausführen sollen; negative Werte führen zu einer entgegengesetzten Bewegungsrichtung.
Mit Mikroschaltern können wir den Ausgangspunkt des Elektromagneten festlegen. Dabei lassen wir sich die Stepper einfach jeweils um einen Schritt bewegen, bis der Mikroschalter aktiviert worden ist (siehe Tabelle 7 und Abb. 12). Damit ergibt sich unsere resetMotors()-Methode:

void resetMotors() {
  [...]
  while(digitalRead(X_RESET_SWITCH_PIN) == LOW)
    xStepper.step(-1);
  while(digitalRead(Y_RESET_SWITCH_PIN) == LOW)
    yStepper.step(-1);
  [...]
}

Für die Stromversorgung des Magneten verwenden wir eine 12V Stromquelle (siehe Abb. 10), da hier der Elektromagnet seine maximal zulässige Leistung erreicht. Ähnlich wie bei den Steppern, ist die Stromversorgung durch den Arduino hierfür viel zu schwach. Da es sich bei 12V um eine relativ hohe Spannung handelt, was den Rest der Elektronik angeht (sonst benutzen wir 5V), sollte die Stromversorgung des Elektromagneten mit besonderer Vorsicht gehandhabt werden, damit Komponenten nicht beschädigt werden.
Um den Elektromagneten ein- und auszuschalten benutzen wir ein n-Kanal-MOSFET, also einen Transistor. Grundsätzlich kann man sich Transistoren als „elektrische Schalter“ vorstellen. Durch Einschalten der Spannung am Gate schalten wir den Magneten ein; liegt am Gate eine Spannung von 0V an, so ist der Magnet auch aus (siehe Tabelle 7). Ein einfaches digitalWrite(MAGNET_PIN, …); reicht also aus um den Elektromagneten vom Arduino aus zu steuern. Unsere Schaltung ist am Beitrag über Schaltung von induktiven Lasten orientiert, nur dass unsere induktive Last kein Motor, sondern ein Elektromagnet ist (siehe Abb. 12).

Um die Bewegung von Figuren auszuführen haben wir die Bewegung in mehrere einfache Abläufe zerbrochen.
Zunächst definieren wir „Eckkoordinaten“: Auf unserem 8 x 8 Feld gibt es 21 x 21 Eckkoordinaten. Jedes Feld wird in vier kleinere Felder unterteilt und besitzt dann an seinen Ecken jeweils eine solche Koordinate; die Randfelder, welche auf dem Brett nicht mehr eingezeichnet sind, werden ebenfalls so eingeteilt. Insgesamt ergibt sich eine Aufteilung wie in Abb. 23.
Außerdem bewegen wir Figuren ausschließlich auf den Kanten der Schachfelder um Kollisionen zwischen den Figuren zu vermeiden. Wir haben zwei, low-level Methoden um den Elektromagneten zu bewegen:

• goTo(byte, byte): Bewegt den Elektromagneten zu den angegebenen Eckkoordinaten.
• moveTo(byte, byte): Bewegt den Elektromagneten zu den angegebenen Eckkoordinaten unter Berücksichtigung der Feldkanten.

Alle Bewegungsmethoden greifen auf goTo(…), so auch moveTo(…); hier eine kurze Beschreibung von moveTo(byte, byte):
Wir nehmen an, dass der Elektromagnet in der Mitte eines Schachfeldes ist und, dass die angegebene Zielposition ebenfalls in der Mitte eines Schachfeldes ist. Diese Annahme können wir treffen, da dies die einzigen Umstände sind, in denen moveTo(…) aufgerufen werden sollte.

1. Bewege den Elektromagneten eine Ecke weiter nach links. Damit ist der Elektromagnet auf einer Kante.
2. Bewege den Elektromagneten zur angegebenen y-Eckkoordinate, plus eine Ecke weiter nach unten. Der Elektromagnet bleibt an der gleichen x-Eckkoordinate und verlässt damit nicht die Kante. Damit ist der Elektromagnet auf einer Kreuzung zwischen Kanten.
3. Bewege den Elektromagneten zur angegebenen x-Eckkoordinate. Der Elektromagnet bleibt an der gleichen y-Eckkoordinate und verlässt damit nicht die Kante.
4. Bewege den Elektromagneten eine Ecke weiter nach oben. Der Elektromagnet ist nun an seiner Zielposition, die einzelnen Verschiebungen auf den Kanten wurden wieder rückgängig gemacht.

Die higher-lever Methoden zur Bewegung der Figuren (moveFigure(byte, byte, byte, byte), removeFigure(byte, byte), swapWithStorage(byte, byte, byte)) benutzen alle die low-level Methoden. Generell benutzen wir folgendes Prinzip:

1. Schalte den Elektromagneten aus.
2. Bewege den Elektromagneten mit goTo(x1, y1) zur Position einer Figur.
3. Schalte den Elektromagneten ein.
4. Bewege den Elektromagneten mit moveTo(x2, y2) zur neuen Position der Figur.
5. Schalte den Elektromagneten aus.

Wir wissen also, wie wir die Stepper auf den Eckkoordinaten bewegen müssen. Nun wandeln wir die Eckkoordinaten in Stepper-Schritte um, damit wir die Stepper bewegen können:
Wie schon weiter oben erwähnt haben wir durch Messungen bestimmt, dass ein Schritt unserer Stepper zu einer Bewegung von 0.0234375mm der Bewegungsebenen führt; dieser Wert ist in der globalen Variable STEPSIZE gespeichert. Wir wissen, dass alle unsere Felder 4cm groß sind, die Distanz von einer Eckkoordinate zur nächsten beträgt also 2cm; gespeichert in der globalen Variable fieldSize. Mit den Methoden getXDistanceMillimeters(int) und getYDistanceMillimeters(int) konvertieren wir Abstände von Eckkoordinaten in Millimeter. Anschließend können wir mit der Methode convertToSteps(int) die Anzahl der Schritte pro Steppermotor ermitteln.
Insgesamt ergibt sich folgende Formel: convertToSteps(getXDistanceMillimeters(distanceX))) = (distanceX * fieldsize) / STEPSIZE

Abbildung 23: Grafik zur Verdeutlichung der Position von Eckkoordinaten

Um die Kommunikation zwischen Arduino und PC (bzw. den einzelnen Programmteilen) festzulegen und zu standardisieren haben wir eigene Protokolle entworfen. Die genaue Spezifikation der Protokolle (inklusive aller Befehle, und Funktionen) lassen sich im Abschnitt Code und Rohdaten im Unterpunkt Protokoll-Dokumentation finden.

Für CHE4C, MATE! haben wir drei Protokolle entworfen. Alle drei sind verbindungslose Protokolle, sodass z.B. nicht garantiert wird, dass Nachrichten in der ursprünglichen Reihenfolge, vollständig oder überhaupt ankommen. Auch enthalten unsere Protokolle keine Adressierung; Nachrichten sind somit an alle Endpunkte im Netzwerk gerichtet⁷⁾. Da die Übertragung auf kurzer Distanz mit nur zwei Endpunkte besteht, ergeben sich für uns hieraus keine Probleme.
Alle drei Protokolle benutzen bei uns konkret die serielle Schnittstelle über USB um zu kommunizieren, allerdings können die Protokolle ohne viel Aufwand auch andere Kommunikationsmöglichkeiten nutzen, eine Schnittstelle existiert um Strings bzw. char-Arrays zu übertragen. Für die serielle Kommunikation über USB nutzen wir die Standard-Übertragungsrate von 9600Baud.
Die drei Protokolle sind folgende:

• ChFiM-Protokoll (Chess-Figure-Movement-Protokoll): Das ChFiM-Protokoll ist ein abstraktes Protokoll zur Bewegung von Schachfiguren. Diese abstrakte Version wird in unserem Programm nicht benutzt, jedoch das SChFiM-Protokoll als konkrete Erweiterung. Jedoch ist das ChFiM-Protokoll um einiges flexibler, was die Umsetzung angeht und wäre somit auch für andere figurenbasierte Spiele oder exotische Schachbrettformen einsetzbar.
• SChFiM-Protokoll (Steppermotor-Chess-Figure-Movement-Protokoll): Das SChFiM-Protokoll ist eine konkrete Spezialisierung des ChFiM-Protokolls, welche eine Umsetzung mit Steppermotoren und einem Magneten vorsieht. Außerdem wird ein quadratisches Spielbrett aus 8×8 quadratischen Feldern und einem Rand vorgeschrieben. Unsere Implementierung bewegt Figuren, wie im Abschnitt Steuerung beschrieben.
• SUIfM-Protokoll (Simple-User-Interface-for-Machinery-Protokoll): Wie im Unterabschnitt Kommunikation der Interaktion beschrieben, handelt es sich bei SUIfM-Protokoll um ein abstraktes, sehr allgemeines Protokoll, welches seinen Daten keine besondere Bedeutung oder Interpretation vorgibt. Es wird erwartet, dass das Protokoll auf interaktive Weise benutzt wird.

Befehle in allen drei Protokollen sind gleich aufgebaut.
Zunächst kündigt ein backslash (\) den Befehl an, dann folgt die Befehls-ID. Befehlsargumente werden durch Leerzeichen voneinander abgetrennt übergeben. Hier sind die wichtigsten Befehle aufgelistet:

Da Arduino und PC zwei verschiedene Rollen haben, ist die Implementation der Protokolle auch unterschiedlich. Der Arduino wartet auf Befehle ab und führt sie dann aus; ist damit die Einheit, welche über das Protokoll übermittelte Befehle ausführt. Der PC sendet die benötigten Befehle und erwartet ggf. Antworten; damit ist der PC die Einheit, welche das Verhalten der Steuerung kontrolliert.

Auf Seite der Ausführeinheit enthalten die konkreten Implementierungen der Protokolle (schfim-device.ino & suifm-device.ino) die Methoden, welche auch durch die Protokolldokumentation vorgeschrieben wird. Sie enthalten die Funktionalität um erhaltene Befehle auszuführen; diese wird jeweils im Abschnitt Steuerung bzw. Kommunikation der Interaktion genauer beschrieben. Das Hauptprogramm auf dem Arduino (che4c-arduino.ino) empfängt Daten über den serialEvent und leitet alle Befehle an beide Protokolle weiter. Das heißt, dass in unserer Implementierung momentan die Befehle der Protokolle disjunkt seinen sollten, da wir keine Adressierung an die verschiedenen Protokolle eingebaut haben.

Auf der Seite der Kontrolleinheit sind lediglich Klassen implementiert, welche das Senden der Befehle und das Abfragen der Antworten vereinfachen; das Hauptprogramm könnte auch direkt die Befehle in die serielle Schnittstelle schreiben. Stattdessen haben wir zwei Klassen für die beiden konkreten Protokolle, welche von der abstrakten Klasse SerialTransceiver ableiten, siehe dazu auch Abb. 24.

SerialTransceiver enthält einige wirkungsvolle Methoden, welche generell auch für andere Formen der seriellen Kommunikation geeignet sind. So sind z.B. Methoden zur Verbindungsherstellung und -auflösung enthalten (connect(Serial), disconnect()). Außerdem bietet SerialTransceiver die statische poll()-Methode an, welche allen seinen ableitenden Instanzen die Datenverarbeitung erleichtert. Die konkreten Implementierungen benutzen Queues, um mehrere angeforderte Daten zwischenzuspreichern. Falls über die serielle Schnittstelle Daten verfügbar sind, werden sie an alle Instanzen verteilt, sodass nicht eine einzelne Instanz alle Daten für sich behält und die anderen ausschließt. Außerdem wird über transmit(String) eine Methode bereitgestellt, um Daten als String über die serielle Schnittstelle zu übertragen. Da die Serial.write(…)-Methoden in Processing den aktuellen Prozess blockieren⁸⁾, wir aber natürlich das Programm weiterlaufen haben wollen, haben wir uns für eine Lösung mit Threads entschieden, sodass die Datenübertragung über die serielle Schnittstelle nie den Programmlauf stört.
Für jede Datenübertragung wird ein eigener, simpler Thread ausgeführt, welcher ausschließlich die Daten über Serial.write(String) senden soll. Hierfür steht die innere Klasse SerialTransmissionRunnable zur Verfügung, welche mit Threads kompatibel ist und die Datenübertragung ausführt. Das heißt, dass zu jedem Zeitpunkt jede Instanz, welche von SerialTransceiver ableitet keine bis mehrere Threads offen hat (siehe Abb. 24). Falls diese nach einer gewissen Zeitspanne (wir haben uns auf 2s entschieden) nicht terminieren⁹⁾, heißt das, dass die serielle Verbindung geschlossen werden kann; es wird angenommen, dass die Verbindung nicht hergestellt wurden konnte. Falls das Senden erfolgreich war (das Senden ist „erfolgreich“, wenn die Verbindung nicht abgebrochen ist), wird beim Aufruf von transmit(String) true zurückgegeben, sonst false.

SChFiMTransceiver und SUIfMTransceiver als erbende Klassen bieten beide Methoden an, die den Datenaustausch ermöglichen, ohne über die Funktionsweise der Protokolle Bescheid zu wissen (z.B. setBaseSpeed(long), requestControlStatus()). Diese führen dann die transmit(String)- und poll(Serial)-Methoden mit den entsprechend richtigen Argumenten aus.
Außerdem überschreiben sie die abstrakte Methode interpretLines(String), welche von poll(Serial) aufgerufen wird und den Protokollen ermöglicht, Daten einzulesen.

Abbildung 24: UML-Klassendiagramm für die relevanten Klassen der Protokolle auf dem PC mit den wichtigsten Attributen und Methoden; Ausschnitt des ganzen Programms

Hier sind Schaltplan und Steckbrett nochmals ohne Markierungen dargestellt, wodurch sie übersichtlicher sind. Die Grafiken wurden mithilfe von Fritzing erstellt, das Fritzing-Projekt lässt sich im Abschnitt Code und Rohdaten finden.

Abbildung 25: Schaltplan

Abbildung 26: Grafik des Steckbretts

Es folgt eine Tabelle mit der Belegung der einzelnen Pins, die Datei, in welcher sich die Zuordnung befindet, das Format der Signale und einer kurzen Beschreibung ihrer Funktion.

CHE4C, MATE! erfüllt viele der von uns geforderten Aufgaben. CHE4C, MATE! kann:

• Schachfiguren auf dem Spielbrett bewegen
• Figuren auf dem Brett erkennen
• erkennen, ob das Spielbrett valide ist
• erkennen, ob der Gegner einen validen Spielzug getätigt hat
• Schachfiguren vom Spielbrett entfernen
• eine Partie Schach spielen und dabei in der Lage sein den Spieler zu schlagen
• mit dem Spieler über eine Status-LED zu kommunizieren (invalider Spielzug, Berechnungsstatus, etc.)
• über eine Benutzeroberfläche in Processing gesteuert werden
• verschiedene Spielmodi/Schachvarianten (Schach, Antischach/Räuberschach)
• Computer vs. Computer (→ Schachbrett spielt eigenständig)

Aber natürlich arbeitet CHE4C, MATE! nicht perfekt.
Zum einen sind wie oben beschrieben, einige last-minute Probleme bei der Elektromagnethalterung aufgetreten, welche beseitigt werden müssen, bevor der Roboter einsatzbereit ist.
CHE4C, MATE! ist ein relativ komplizierter Aufbau, welcher an verschiedenen Stellen Probleme aufweist.
Zum Beispiel können Schrauben sich lockern, die Stepper halten gut, aber ihre Halterung ist mit jeweils 5 Winkeln etwas kompliziert. Das Holz der Bewegungsvorrichtung ist leicht verbogen, sodass wir relativ viele Räder anbringen mussten, damit die Bewegung nicht blockiert wird. Auch existiert ein nicht vernachlässigbarer Höhenunterschied durch das gebogene Holz. Die Barrieren an den Seiten der Bewegungsvorrichtungen lassen noch etwas Spiel übrig. Die Kabel, die von außen in das Steckbrett führen (z.B. Stromversorgung) können sich lösen. Mit 4 Kabel, welche nach außen verbunden werden müssen ist das Projekt wenig mobil. Durch einen Umstieg z.B. auf einen Raspberry PI könnte die Figurenbewegung, Schach-KI und Bilderkennung an einem Ort zusammengefasst werden. Die Stromversorgung könnte man auch weiter vereinfachen, sodass auch hier weniger Kabel nötig wären.
Außerdem ist es dem Roboter momentan unmöglich Bauern umzutauschen, sodass dies der Spieler manuell für CHE4C, MATE! die Figur austauschen muss. Theoretisch können Figuren auf dem Spielbrett mit Figuren auf dem Schachbrettrand ausgetauscht werden, es existieren dafür Bewegungsbefehle¹⁰⁾. Aber dieses System ist ebenfalls eingeschränkt, die Schachbrettanalyse betrachtet momentan nicht solche Randfälle.

Außerdem kann man noch an CHE4C, MATE! weiterarbeiten. Mögliche Ideen für die Weiterarbeit an dem Projekt sind:

• Verbesserung des Aufbaus
• mehr Spielmodi
• Statistik über die Benutzeroberfläche
• Möglichkeit einer Zeitbegrenzung pro Schachzug
• Verbesserung/Erweiterung der Benutzeroberfläche
  • weitere Konfigurationsmöglichkeiten
  • Möglichkeit zurückzuspringen
• Laufzeitsenkung der Schach-KI (z.B. durch Zugsortierung, Multi-Threading, Neuimplementierung auf Arrays / in C)
• Möglichkeit der KI ein Remis vorzuschlagen und eine Evaluation der KI dieses Angebotes
• bessere Bewertungsfunktion bzw. Verbesserung der Spielweise der Schach-KI
• Ansteuerung von CHE4C, MATE! über das Internet
  • Fernspiel über Website
  • 2 Menschen spielen über Website gegeneinander und sehen über die Webcam das Schachfeld am Roboter
• Zeichnen mit CHE4C, MATE!

• Aktuelle Version auf GitHub (Änderungen der Funktionsweise vorbehalten): https://github.com/Impelon/CHE4C-MATE-
• Version auf GitHub mit nur geringfügigen Änderungen der Funktionsweise: https://github.com/Impelon/CHE4C-MATE-/tree/legacy
• Funktionale Version: che4c.zip

• Arduino-Stepper-Library (bereits im Arduino-Standard-Packet enthalten)
• Processing-Video-Library (über die Processing-IDE installierbar)

• Fritzing Projekt: che4c-fritzing.zip
• Protokoll-Dokumentation (englisch):
  • bearbeitbare .docx-Dateien: protokoldateien.zip
  • ChFiM-Protokoll: chfim-protocol.pdf
  • SChFiM-Protokoll: schfim-protocol.pdf
  • SUIfM-Protokoll: suifm-protocol.pdf
• Abschlusspräsentation: praesentation.zip

(Computer and Human controlled Environment for Chess)

Dieser Guide soll als Teil der Projektdokumentation behilflich sein um das CHE4C, MATE!-System einzurichten und zu benutzen.
Benötigt werden:

• der CHE4C, MATE!-Roboter
• ein PC mit Processing/Java, den Programdateien und zwei freien USB-Ports
• USB-Standard-A - nach - USB-Mini-B - Kabel (Verbindungskabel zum Arduino)
• 5V Netzteil
• 12V Netzteil

Alessio Mossudu, Ovidiu Victor Tatar

Berlin 2017/2018

Ein mechanisches Gerüst hält nicht ewig, Transport, etc. können den Zustand verändern. Deshalb sollte zuerst der Zustand überprüft werden um schwerwiegende Schäden zu vermeiden.

Die beiden quadratischen Vorrichtungen auf denen der Elektromagnet gleitet sollten leicht bewegbar sein, ohne dass die Bewegung blockiert ist. Außerdem braucht die Vorrichtung genug Platz nach hinten um bewegt werden zu können, die Vorrichtung kann und wird also über die Grundplatte hinausschauen. Dies wird insbesondere auf der y-Achse (siehe Abb. 3) der Fall sein. Es sollte nicht möglich sein, dass sich die Vorrichtung z.B. an den Seiten festhängt oder seitlich ausbricht.
Die beiden Stepper sollten mit den Zahnrädern auf den Zahnstangen liegen und nicht durchdrehen.

Abbildung 27: Bewegungsvorrichtung

Die Kabel sind relativ gut befestigt und abgesichert. Es kann jedoch sein, dass Kabel sich an Verbindungsstellen (insbesondere am Steckbrett) lösen. Falls etwas nicht/falsch verbunden ist, sollte die Verbindung gemäß Abb. 26 hergestellt werden.
Besonders anfällig könnten folgende Verbindungen sein (alle folgenden Verbindungen sind am Steckbrett, markiert auf Abb. 28):
a) beide Verbindungsstecker der Stepper,
b) die beiden Kabel des Elektromagnets,
c) die Kabel der Stecker für die beiden Netzteile,
d) die Kabel der beiden Mikroschalter,
e) das Kabel des Bestätigungsknopf
Die schwarzen Punkte an den Verbindungsstecker der Stepper sollten zu den Drivern zeigen.
Die (hellgraue) Markierung an der Freilaufdiode zeigt in Richtung Pluspol.

ACHTUNG: Kabel sollten nicht falsch verpolt werden! Pluspole sind rote Kabel, Minuspole schwarze (siehe Abb. 26).

Auf die Mikroschalter kann z.B. durch Fehler und Gewicht hohe Belastungen zukommen, sodass die Metallplättchen abknicken können. Sie wieder zu befestigen sollte durch einfaches anheben/einrasten möglich sein. Auch ist es möglich, dass ihre Halterungen lose werden, dies sollte natürlich auch überprüft und ggf. repariert werden.

Die 8 Kugellager sollten sich leicht drehen können und wenig Spiel haben. Falls dies nicht der Fall ist, können die Muttern nachgezogen werden, sodass diese an den Kugellagern liegen und sich nicht drehen, wenn die Kugellager sich drehen. Die Kugellager sollten auf einer Höhe befestigt werden, sodass keine Spannung auf die Bewegungsvorrichtung ausgeübt wird. Die unteren Kugellager sollten auf dem Aluminiumrohr aufliegen. Die Federn unter dem Elektromagneten sollten auf beiden Holzscheiben befestigt sein, sodass sich der Elektromagnet nicht zu sehr biegt, wenn er unter das Schachbrett fährt. Das Schachbrett sollte leicht auf dem Elektromagnet liegen und nicht viel Druck ausüben, sodass der Elektromagnet unter dem Brett gleiten kann.

Abbildung 28: reales Bild des Steckbretts, die jeweiligen oben genannten Kabel sind markiert

Abbildung 29: Grafik des Steckbretts; Anordnung und Färbung auf dem Steckbrett ist nahezu identisch mit der realen Verkabelung, daher sollte diese Grafik als übersichtlichere Referenz gewählt werden

Falls nun die Kabelverbindungen überprüft wurden, können die externen Verbindungen zur Stromversorgung und Datenübertragung hergestellt werden.

Der Arduino muss mit Strom versorgt werden und muss Daten mit dem PC austauschen können. Daher muss der Arduino per USB-Kabel (siehe Abb. 8) mit einem der freien USB-Ports am PC angeschlossen werden. Der Port muss mit dem Port der seriellen Schnittstelle im Programm übereinstimmen.

Das USB-Kabel der Webcam muss ebenfalls mit einem der freien USB-Ports am PC angeschlossen werden. Falls die Länge des Kabels (siehe Abb. 8) nicht ausreicht, könnte man einen USB-Hub oder ein Verlängerungskabel benutzen.

Abbildung 30: USB-Kabelverbindungen

Die Steppermotoren brauchen eine Stromverbindung. Wir haben uns für ein 5V Netzteil entschieden, aber die Stepperdriver könnten auch 2.5V bis 10.8V Gleichstrom akzeptieren. Falls der Arduino und die Stepper gleichzeitig mit dem Strom verbunden sind, startet der Arduino bereits das Programm und kann die Stepper bewegen. Da der Programmteil auf dem Arduino zuerst die Stepper zu ihrer Ausgangsposition (an den Mikroschaltern) bringt, sollte zunächst sichergegangen werden, dass sich die Bewegungsvorrichtung (Abb. 27) einwandfrei funktioniert.

Abbildung 31: Stromkabel des Steppermotoren

Der Elektromagnet braucht möglichst viel Energie um die Figuren anziehen zu können. Seine maximale, zulässige Leistung erreicht er bei 12V Gleichstrom, sodass das von uns gewählte Netzteil 12V liefert. Das braune Kabel am Stecker bleibt unverwendet und unverbunden. Da es sich um etwas höhere Spannungen handelt, als es für den Arduino zulässig ist, sollte die Stromversorgung des Elektromagnets zuletzt geschlossen werden, wenn alles andere bereits einsatzbereit ist.

Abbildung 32: Stromkabel des Elektromagnets

ACHTUNG: Das Kabel (Abb. 32) darf nicht falsch verpolt werden! Pluspol am Stecker ist das rote Kabel, Minuspol das schwarze. Der Stecker wurde auch nochmals zusätzlich markiert.

Die Webcam muss komplette Übersicht über das Schachbrett haben können. Dazu sollte die Kamera ein Sichtfeld ähnlich der Abbildung 7 haben.

Damit das Sichtfeld der Webcam überprüft werden kann muss die Webcam zum PC verbunden sein. Anschließend kann das Sichtfeld über ein weiteres Programm überprüft werden. Dies geht z.B. über https://turncameraon.com/ (Wir garantieren nicht die Seriosität oder den Datenschutz der Website). Auch mit Processing kann die Webcam getestet werden. Dafür kann einfach eins der Beispielskripte benutzt werden, welches unter Datei > Beispiele … > Libraries > Video > Capture > GettingStartedCapture zu finden ist.

Die Webcam kann einfach bewegt werden, sodass das Sichtfeld einstellbar ist.

Abbildung 33: ideales Sichtfeld der Webcam

Um den Programmteil von CHE4C, MATE! zu benutzen, muss die Verbindung zum Arduino und zur Webcam sichergestellt sein. Theoretisch (und praktisch) funktioniert die Benutzeroberfläche auf dem PC auch ohne Verbindung zum Roboter, aber der Roboter macht dann natürlich auch nichts. Auf dem PC muss Processing oder Java installiert sein, und falls auf dem Arduino nicht die aktuellste Version des Programmteils installiert ist, wird auch die Arduino-IDE benötigt um das Programm hochzuladen.

Falls das Programm erst auf den Arduino geladen werden muss, sollte die Arduino-IDE gestartet werden. Nun sollte überprüft werden, dass die IDE auf das richtige Arduino-Modell eingestellt ist (Board: Arduino Nano, Processor: ATmega328T, und der richtige Port). Anschließend sollte das Programm des Arduinos (der Ordner che4c-arduino) hochgeladen werden.
Damit das Programm hochgeladen werden kann, sollte dafür zuerst unsere RGBLed-Library installiert werden. Diese muss hierfür einfach in den Library-Ordner der Arduino-IDE kopiert werden (normalerweise unter C:\Users\<Benutzer>\Documents\Arduino\libraries; nähere Infos unter http://www.arduino.cc/en/Guide/Libraries).
Zum Testen der Programmfunktionalität kann über die serielle Schnittstelle ein Befehl gesendet werden (z.B. über den seriellen Monitor).
Durch Übermittlung des SChFiM-Befehls /m 0 0 1 1 \n sollte z.B. die Figur in der Ecke neben den Mikroschaltern (Anfangsposition) um ein Feld in der Diagonalen bewegt werden.

Das Programm auf dem PC sollte über eine selbsterklärende GUI verfügen. Aber gewisse Einstellungen können auch direkt in der Hauptdatei über Processing bearbeitet werden.
Die Verbindung zum Arduino muss auf dem richtigen Port geschehen und die Webcam muss im richtigen Modus laufen.
Auf der GUI können auch Schachfiguren gesteuert werden und der Spielverlauf wird angezeigt. Zum Bewegen einer Figur sollte Start- und Zielfeld ausgewählt werden und anschließend Enter gedrückt werden. Falls eine andere Auswahl gewünscht ist, kann die Entf- bzw. die Del-Taste gedrückt werden um die Auswahl zurückzusetzen. Durch das Mausrad kann die Umwandlung in eine andere Figurenart eingestellt werden (dies wird bei der Umwandlung von Bauern benutzt). Um eine Rochade zu tätigen sollte vom eigenen König auf den gewünschten Turm gezogen werden.

Abbildung 34: GUI auf dem PC; blau markiert das Startfeld, rot markiert das Zielfeld (Änderungen vorbehalten)