ENTUAL Chessbot Part 1
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.
Während in der prä-digitalisierten Ära Spieler wie Bobby Fischer und Boris Spassky das Geschehen am Brett dominierten, sind es heute KI-gesteuerte Schachprogramme, die nicht zu bezwingen sind. Selbst aktuelle Großmeister wie Magnus Carlsen oder Hikaru Nakamura müssen sich dem Einsatz moderner Technik schon lange geschlagen geben.
Das prominenteste und derzeit stärkste Schachprogramm ist Stockfish, das sich unter anderem neuronaler Netze bedient, um die stärksten Züge in jeder Position zu finden.
Doch wie funktioniert eigentlich ein solcher Schachcomputer? Welche Algorithmen kommen zum Einsatz, um sogar die stärksten menschlichen Spieler in die Knie zu zwingen? Kann man einen Schachcomputer so ohne weiteres selber programmieren?
Entual hat sich im Sommer mit diesen Fragen beschäftigt. Herausgekommen ist dabei ein Prototyp eines Schachcomputers, powered by Ab Initio, mit dem auch einigermaßen fortgeschrittene Spieler ihre Probleme haben werden.
https://www.pexels.com/photo/man-holding-chess-piece-277124/
Was euch erwartet
In der kommenden Blogserie wollen wir euch die Ergebnisse unserer sommerlichen Schachexperimente präsentieren. Zunächst soll Grundsätzliches über die Funktionalität eines Schachcomputers erklärt werden. Es wird dabei davon ausgegangen, dass der Leser bereits mit den Regeln des Schachspiels vertraut ist, weshalb vor allem jene Aspekte beleuchtet werden, die für einen Schachcomputer relevant sind.
In diesem Blogpost werden wir dafür zunächst die sogenannte FEN Notation analysieren, die vom Computer zur effizienten Speicherung sämtlicher relevanter Information einer Brettstellung benutzt wird.
In kommenden Posts beschäftigen wir uns mit der Ermittlung aller möglichen Züge sowie der quantitativen Bewertung einer Brettstellung durch die Bewertungsfunktion.
Danach analysieren wir den Minimax-Algorithmus, einen spieltheoretischen Algorithmus, mit dem man die besten Züge in einem Zwei-Personen-Spiel berechnen kann.
Im finalen Teil gehen wir so gut wie möglich auf Implementierungsdetails des Schachcomputers in Ab Initio ein.
https://stockfishchess.org/
Fen-Notation
Die zentrale Aufgabe eines Schachcomputers besteht darin, für jede vorliegende Brettstellung den bestmöglichen Zug zu ermitteln.
Damit ein Computer eine solche Brettstellung systematisch analysieren kann, benötigt man zunächst eine kompakte Darstellung, die von einem Programm effizient eingelesen werden kann. Diese Darstellung muss sowohl die Positionen sämtlicher Figuren auf dem Brett, als auch Metainformationen des Spiels wie Zuganzahl, Rochaderechte oder en-passant Züge enthalten.
Ein FEN String (Forsyth-Edwards Notation) liefert genau so eine Darstellung. In einem FEN String sind folgende Informationen, durch ein Leerzeichen getrennt, enthalten: Figurenpositionen, Zugrecht, Rochaderechte, En-Passant Schlag, gespielte Halbzüge seit dem letzten Bauernzug oder Schlagen einer Figur (50 Züge Regel), Zugnummer.
Der folgende FEN ergibt sich beispielsweise für die italienische Partie:
“r1bqkbnr/pppp1ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R b KQkq – 3 3”
Im FEN String werden zunächst die Figurenpositionen für alle Ränge des Schachbretts, begonnen bei Rang 8, angegeben, wobei die Informationen für einzelne Ränge durch ein „/“ getrennt sind. Unter einem Rang auf einem Schachbrett versteht man jene Felder, die auf einer gleichen horizontalen Linie liegen.
Die Figuren werden dabei aus der Sicht von Weiß von links nach rechts, also von der a-Linie beginnend bis zur h-Linie, notiert. Unter einer Linie versteht man jene Felder, die auf einer gleichen vertikalen Linie liegen.
Ein Kleinbuchstabe steht für eine schwarze Figur, ein Großbuchstabe für eine weiße Figur. Jeder Buchstabe steht dabei für eine Figur: K-König, Q-Dame, N-Springer, B-Läufer, R-Turm, P-Bauer. Befinden sich auf einem oder mehreren nebeneinanderliegenden Feldern eines Ranges keine Figuren, so wird das durch die Anzahl der leeren Felder dargestellt.
Der erste Teilstring der Figurpositionen “r1bqkbnr” beschreibt daher den 8. Rang und wird folgendermaßen interpretiert:
Schwarzer Turm, freies Feld, schwarzer Läufer, schwarze Dame, schwarzer König, schwarzer Läufer, schwarzer Springer, schwarzer Turm.
Das Zugrecht wird entweder mit „w“ für Weiß oder „b“ für Schwarz angegeben.
Ein kurzes Rochaderecht von Weiß wird mit „K“, ein langes Rochaderecht von Weiß mit „Q“ abgekürzt, für Schwarz entsprechend mit „k“ und „q“. Wird eine Rochade bloß temporär verhindert, eventuell durch ein aktuelles gegnerisches Schachgebot, so wird das Rochaderecht in der FEN Notation dadurch nicht beeinflusst. Hat keine Seite ein Rochaderecht, wird das durch „-“ dargestellt.
Ein Feld, über das sich ein Bauer gerade bewegt hat, falls er initial zwei Felder nach vorn gerückt ist, wird hier angegeben. Die Information wird unabhängig davon geliefert, ob sich ein gegnerischer Bauer an der notwendigen Position befindet, um einen en-passant Schlag ausführen zu können. Das Feld beinhaltet „-„, falls im vorigen Zug kein initialer 2-Felder Zug eines Bauern passiert ist.
Die Anzahl der gespielten Halbzüge seit dem letzten Bauernzug oder dem letzten Schlagen einer Figur. Diese Information wird vor allem in Endspielen zur Vollstreckung der 50-Züge Regel benötigt.
Die Zugzahl wird im FEN String an letzter Stelle angegeben.
Komplexeres FEN Beispiel:
Im folgenden betrachten wir einen potentiellen Spielverlauf, der nach dem obigen Start folgen könnte und analysieren dafür ein paar Aspekte des resultierenden FEN Strings:
“1r4r1/bp1q1p1k/p2p1B1p/1Pp5/P3P3/5Q2/5PPP/3R1RK1 w – c6 0 22”
Wir analysieren exemplarisch den sechsten Rang: “p2p1B1p”
Ein schwarzer Bauer, zwei freie Felder, ein schwarzer Bauer, freies Feld, weißer Läufer, freies Feld, schwarzer Bauer.
In dieser Brettstellung existiert für keine der beiden Seiten ein Rochaderecht, da sowohl Weiß als auch Schwarz bereits davon Gebrauch gemacht haben. Das wird durch den String “-” ausgedrückt.
Ein möglicher En-passant Schlagzug wird durch den String “c6” ausgedrückt, da Schwarz eben den Bauernzug c7-c5 ausführte und ein weißer Bauer auf dem Feld b5 platziert ist.
Ausblick
Im nächsten Blogartikel befassen wir uns damit, wie ein Schachcomputer alle möglichen Züge einer bestimmten Brettstellung ermitteln kann.
Des Weiteren beschäftigen wir uns mit der Bewertungsfunktion, die eine Brettstellung quantifiziert und angibt, welcher der beiden Spieler sich gerade im Vorteil befindet. Sie ist die Grundlage für den Minimax-Algorithmus zur Ermittlung des optimalen nächsten Zuges.