Im Rahmen dieser Einführung werden die wesentlichen Elemente der Schachprogrammierung dargelegt.
Die Elemente können durch die jeweiligen Links oder durch die Themen im Unterforum „Schachprogrammierung“ deutlich vertieft werden.
1. Das Schachbrett
Das wird im Schach als quadratisches 8x8 Brett mit 32 Figuren oder optisch auf einem Bildschirm angezeigt.
Im Computerschach ist es durch ein quadratisches Variablenfeld von 8x8 oder 12x12 (Bitboard) mit den Grundfigurenwerten intern festgelegt. Es wird durch Schlüsselwerte adressiert. Die Bitboardwerte sind 64 Bit Variablen.
Ein zentrales Problem bei der Umsetzung eines Schachprogramms stellt die Berechnung der möglichen Folgezüge aus einer gegebenen Position heraus dar. Bei Benutzung von Bitboard-Strukturen erfolgt dies durch logische Operationen auf der Spielplan-Belegung. Hierbei müssen zwei Arten von Figuren unterschieden werden: bei den „springenden“ Figuren wie Bauern, Springern und König ist allein die Belegung des Zielfelds entscheidend. Bei den „gleitenden“ Figuren wie Türmen, Läufer und Dame ist die Zugmöglichkeit komplexer, da Figuren bestimmte Zielfelder blockieren können, ohne diese selbst zu belegen.
Weiterführend ist folgender Wikipedia Artikel:
https://de.wikipedia.org/wiki/Bitboard?wprov=sfti12. Die Schachregeln (Zuggenerator)
Sind natürlich die gleichen. Sie können im Computerschach auch abweichend festgelegt werden (z.B. Shogi).
Im Computerschach werden die legalen Züge durch einen Zuggenerator festgelegt, der auf das Bitboardfeld zugreift (siehe oben).
Hier eine ausführliche Erklärung:
https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/3. Die Bewertung (Evaluation)
a) die Figurenwerte von 1 (Bauer), 3 (Läufer, Springer), 5 (Turm) 9 (Dame) wird auf dem internen Variablenfeld den jeweilen Positionen zugewiesen. Zumeist werden jedoch größere Werte (100, 300, 500, 900) oder modifizierte Werte verwandt (z.B. Läufer 310).
Hier ein Beitrag zur Bewertung der Figuren in Abhängigkeit von der Position auf dem Brett:
https://www.stmintz.com/ccc/index.php?id=28583b) der jeweilige Stellung wird nach der Schachtheorie (Heuristik) bewertet, indem der Figurenwert erhöht oder vermindert wird. Diese hängt im wesentlichen vom Standort/Wechselwirkung der eigenen und der gegnerischen Figuren ab. Die Bauernstruktur erfährt eine besondere Behandlung.
So wird z.B. die Figurenbewertung des Turms auf einer halboffenen Linie von 5 auf 5,5 bei einer offnen Linie von 5 auf 6 erhöht. Die Königssicherheit spielt dabei eine besondere Rolle.
Hier eine allgemeine Beschreibung:
https://chessfox.com/example-of-the-complete-evaluation-process-of-chess-a-chess-position/c) in der KI wird die Bewertung durch ein neuronal trainiertes (Managed Learning) oder sich selbst trainierendes (Reinforcement Learning) Netz vorgenommen (NN, NNUE).
Siehe Wikipedia Artikel:
https://de.wikipedia.org/wiki/AlphaZero?wprov=sfti14. Die Suche (Search)
ist beim Menschen das vorwärtsgewandte Berechnen und Beurteilung der Stellung unter Berücksichtigung der gegnerischen Züge.
Berechnung und Bewertung werden durch Training und Literatur gelernt.
Beim Computerschach wird aus der aktuellen Stellung heraus ein Suchbaum generiert. Im einfachsten Fall wird jedem Knoten im Suchbaum ein Wert zugewiesen. Der Knoten mit dem höchsten Wert wird ausgewählt. Die Anzahl der Knoten steigen jedoch mit der Rechentiefe exponentiell. Deshalb muß die Suche nach bestimmten Verfahren eingeschränkt werden (Alpha/Beta-Verfahren, Zügeordnung, Ruhesuche) ohne jedoch im wesentlichen die Treffsicherheit der Suchbewertung einzuschränken.
Bewertung und Suche bilden im Programm einen wechselseitigen Kreislauf.
Bei KI-Schachprogrammen wird oft der Monte Carlo Tree Search angewandt.
Hier ausführliche Wikipedia Beschreibungen:
https://de.wikipedia.org/wiki/Alpha-Beta-Suche?wprov=sfti1https://www.chessprogramming.org/Monte-Carlo_Tree_Search5. Hilfstabellen und Datenbanken
a) stehen dem Menschen vor (Vorbereitung, Training) und nach der Partie (Analyse), jedoch nicht während der Partie zur Verfügung.
b) der Computerberechnung (Algorithmen) stehen während der Partie Zugriff auf verschiedene Datenbanken (Eröffnungsbücher, Endspieltabellen) und Berechnungstabellen (Hash- bzw. Transformationstabellen) zur Verfügung.
Siehe:
https://en.wikipedia.org/wiki/Transposition_table?wprov=sfti1https://www.chessprogramming.org/Endgame_Tablebases6. Ein- und Ausgabe
Für die Ein- und Ausgabe zur GUI oder zu einem elektronischen Schachbrett werden Schnittstellenprogramme (GUI) oder Übertragungsprotokolle (Schachbrett) verwandt.
Diese sind USB, WLAN, LAN, Bluetooth i.V.m. UCI, WinBoard oder propäritäre Schnittstellen.
Für UCI siehe:
http://wbec-ridderkerk.nl/html/UCIProtocol.html7. Umsetzung in der Programmierung
Programme, somit auch Computerprogramme, bestehen aus Algorithmen (Rechen- und Entscheidungsanweisungen) und Datenstrukturen.
Schachprogramme verwenden eine Reihe von Datenstrukturen:
1. Arrays bei der Brettdarstellung
2. Zeichenketten (Strings) sowie streams für die Ein- und Ausgabe (UCI)
3. Bäume (trees) für die Mini-Max und Alpha-Beta-Suche (mit Schlüsselwerten)
4. Tabellen für das hashing auf Transformation Tabellen, (indexierte) Endspiel- und Eröffnungstabellen
5. Netze (nets) für NNUE und Lc0 (Tensornets)
Hier ein ausführlicher Artikel dazu:
https://www.gamedev.net/tutorials/programming/artificial-intelligence/chess-programming-part-ii-data-structures-r1046/Diese Datenstrukturen werden in den höheren Programmiersprachen durch Klassen definiert.
Bei der Bewertung (Eval) werden Algorithmen d.h. Schleifen, Entscheidungsanweisungen, Funktionen mit Variablen und logische Operationen verwendet.
Dabei wird auf die o.a. Datenstrukturen zugegriffen und die Daten werden verändert.
Als Programmiersprachen werden vorrangig C, C++ auch in Verbindung von oder in Python (KI) eingesetzt.
Hier ein guter Beitrag mit vielen Diagrammen zur Umsetzung eines Schachprogramms:
https://www.theseus.fi/bitstream/handle/10024/502571/Developing%20Chess%20Engine.pdf?sequence=2
Forum
CSS-Shop