ENTUAL Chessbot Part 3
Schach, das königliche Spiel, ist eines der ältesten Brettspiele der Welt. Seit Jahrhunderten messen sich Begeisterte des Schachsports in ihrem strategischen Denken und bewegen hochkonzentriert die 32 Figuren vor sich hin, die Entual Kollegen sind da natürlich auch keine Ausnahme.
Wir haben uns im Sommer ausführlich mit Fragestellungen zu Schach in Verbindung mit Ab Initio beschäftigt. Von FEN-Notationen und grundlegenden Funktionalitäten eines Schachcomputers in unserem ersten Blogpost, über Zugermittlungen und Bewertungsfunktionen in unserem zweiten Blogpost hatten wir bereits geschrieben.
Im dritten Teil unserer Blogserie zum Entual Chessbot werden wir auf die technischen Aspekte bei der Umsetzung mit Ab Initio eingehen. Im Fokus steht dabei die Implementierung eines Webservice Graphen mit Ab Initio, erweitert um schachspezifische Funktionalitäten.
https://www.pexels.com/photo/man-holding-chess-piece-277124/
Grundlegende Funktionalität eines Ab Initio Webservice Graphen
Der Entual Chessbot ist in Ab Initio als Continuous Graph implementiert und beinhaltet die grundlegenden Funktionalitäten eines Webservers:
Zunächst existiert eine Komponente, die eingehende HTTP Requests verarbeitet. Die Requests werden dann, je nach Inhalt, an Komponenten mit dedizierten Funktionalitäten weitergeleitet. Diese Komponenten können Informationen zur Darstellung des User Interfaces via HTML-Files oder die Ergebnisse der Ermittlung des besten Zuges liefern. Zuletzt gibt es eine Komponente, die die ermittelten HTTP Responses zurück an den Browser schickt.
Die folgende Abbildung 1 gibt einen groben schematischen Überblick über die einzelnen Bestandteile des Graphen:
Sämtliche zur Darstellung der User Interfaces benötigten Informationen, wie HTML-, oder CSS-Files befinden sich in der Graph-Sandbox und werden von Ab Initio an den Browser ausgeliefert.
Beim Aufruf der Website “chess.entual.de” sendet der Browser einen GET Request für ein initiales HTML-File an den Continuous Graphen. Dieser Request wird über Strang 1, wie in Abbildung 1 dargestellt, verarbeitet. Dadurch sucht der Continuous Graph in der Sandbox nach dem „main.html“-File. Der Browser erhält das angeforderte File und erstellt für alle darin befindlichen Links zu Ressourcen wie CSS-Stylesheets oder anderen HTML-Files weitere GET-Requests an den Continuous Graphen. Dieser Prozess wird fortgesetzt, bis der gesamte Seiteninhalt fertig geladen werden kann.
In der folgenden Abbildung 2 ist dies schematisch dargestellt:
Rudimentäre Login-Funktionalität
Durch Eingabe eines Nicknames und Drücken des Submit-Buttons sendet HTMX einen POST-Request an den Continuous Graphen. Dieser Request wird dann über Strang 3 in Abbildung 1 verarbeitet. Dabei wird ein Session-Objekt erzeugt, das Informationen wie den Namen, den Zeitpunkt des Logins, sowie eine daraus berechnete ID enthält.
Das Session-Objekt wird in einer Shared Variable Collection abgespeichert. Dabei handelt es sich um eine Art In-Memory-Datenbank in Ab Initio, auf die alle Komponenten innerhalb des gleichen Laufzeitprozesses zugreifen können.
Des Weiteren wird ein Set-Cookie-Header mit der eben ermittelten ID via Response-Header zurück an den Browser geschickt. Bei nachfolgenden Requests des Browsers an den Continuous Graphen führt das Mitliefern dieser ID dann zur Anzeige von Spielstatistiken des Users.
Durch Betätigung des Logout Buttons gelangt man wieder zur initialen Seite zurück und der Cookie wird als gelöscht markiert.
Der eben beschriebene Workflow ist in der folgenden Abbildung 3 schematisch dargestellt:
Das Herzstück des Chessbots bildet das Ermitteln, Ausführen und Darstellen des besten Zuges. Darauf werden wir im Folgenden eingehen.
Ermittlung des nächsten Zuges
Nachdem ein Spieler eine Figur am Brett gezogen und abgesetzt hat, passieren eine Reihe von Aktionen, die im Hintergrund ausgeführt werden:
Eine JavaScript-Funktion testet die Validität des eben durchgeführten Zuges und erstellt, im Falle eines den Spielregeln entsprechenden Zuges, den FEN-String der neuen Brettposition.
Dieser FEN-String wird über einen GET-Request an den Webserver Graphen geschickt, wo er über den Strang 2 in Abbildung 1 verarbeitet wird.
Dabei wird nun der Minimax-Algorithmus, der im zweiten Blogartikel aufgezeigt wurde, zur Bestimmung des nächsten Zuges aufgerufen. Der so vom Schachcomputer ermittelte Zug wird in algebraischer Schachnotation zurück an den Browser gesendet, wo der Zug daraufhin ausgeführt wird.
Im Anschluss daran werden Spielinformationen, wie der aktuelle FEN oder der bisherige Spielverlauf, in HTML aktualisiert.
Im Falle einer Mattstellung werden der Spielername und der Ausgang des Spiels in einer Shared Variable Collection gespeichert, um diese Informationen auf der Spieloberfläche darstellen zu können.
In Pseudocode sieht das dann so aus:
def find_abinitio_chessbot_move(source, target):
is_valid = check_valid_move(source_target)
if (is_valid):
new_fen = create_new_fen(current_fen, source, target)
answer_move = call_http_chessbot_minimax(new_fen)
execute_chessbot_move(answer_move)
update_ui(answer_move)
else:
undo_move(source, target)
Der beschriebene Workflow zur Zugermittlung ist hier noch einmal in Abbildung 4 schematisch dargestellt:
Rückblick und Ausblick
Der Entual Chessbot ist eine rudimentäre Minimalversion eines Schachcomputers. Obwohl er den Großteil von Schachanfängern wohl bezwingen kann, hat er gegen Amateurspieler mit Eröffnungswissen und taktischen Fähigkeiten wenig Chancen. Was unterscheidet ihn nun also von mächtigeren Schachcomputern wie Stockfish und an welchen Punkten könnte man ansetzen, um ihn zu verbessern?
Das Hauptaugenmerk sollte unserer Meinung nach auf der Performanceoptimierung von Teilen des Algorithmus zur Ermittlung des besten Zuges liegen. Im rekursiven Minimax-Algorithmus wird eine Vielzahl an Aufrufen einer Funktion zur Ermittlung aller möglichen Züge einer bestimmten Stellung durchgeführt. Wir benutzen hierfür eine Matrix, in der die Positionen aller Figuren eingetragen sind. Bei jedem Aufruf der Funktion werden sämtliche erlaubten Bewegungen aller Figuren innerhalb der Matrix ermittelt. Will man dann noch mehrere Züge voraus berechnen, muss man diese Funktion schnell mehrere Millionen mal aufrufen, was einen immensen Rechenaufwand mit sich bringt.
Als Alternative dazu könnte man die Zugermittlung mit einem Bitboard durchführen. Dabei handelt es sich um einen 64-bit integer, wobei jedes Bit ein Feld auf dem Brett repräsentiert.
Jede Figur sowie jede Farbe erhalten dabei ihr eigenes Board. Mögliche Züge ergeben sich dann durch Bitverschiebungen sowie Bitboard-Überlappungen. Durch eine Optimierung der Zugermittlung könnte man im Minimax-Algorithmus tiefer hinabsteigen, was zu einer Erhöhung der Spielstärke des Computers führt.
Eine weitere Möglichkeit besteht in einer verbesserten Optimierungsfunktion, die nicht nur das vorhandene Material berücksichtigt, sondern auch den qualitativen Wert davon basierend auf der Position der Figuren auf dem Brett. Ein zentraler Springer oder ein weit vorangeschrittener Freibauer würde demnach besser bewertet werden, als ein Randspringer oder ein Bauer am Startfeld. Der Computer würde dann Züge, die zu qualitativ höherwertigen Stellungen führen, eher ausführen.
Das, und noch viel mehr, sind Ausblicke unseres Backlog für eine zukünftige Iteration des Entual Chessbot powered by Ab Initio. Wir hoffen, ihr hattet beim Lesen ebenso viel Freude wie wir beim Schreiben und Entwickeln.
Gerne könnt ihr auch weiterhin eine Runde Schach spielen, fordert ihn heraus: Entual Chessbot powered by Ab Initio .
Wer noch einmal in die anderen Blogartikel lesen möchte:
Im zweiten Blogartikel befassten wir uns damit, wie ein Schachcomputer alle möglichen Züge einer bestimmten Brettstellung ermitteln kann und wie eine Bewertungsfunktion der jeweiligen Züge umgesetzt wird.
Im ersten Blogartikel befassten wir uns mit allem Grundsätzlichen über die Programmierung eines Schachcomputers, den wir mit Ab Initio umgesetzt haben.