Not logged inCSS-Forum
Forum CSS-Online Help Search Login
CSS-Shop Impressum Datenschutz
Up Topic Hauptforen / Schachprogrammierung / Einführung in die Schachprogrammierung
- - By Lothar Jung Date 2021-10-09 12:03 Edited 2021-10-09 12:18 Upvotes 1
Im Rahmen dieser Einführung werden die wesentlichen Elemente der Schachprogrammierung dargelegt.

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.

Weiterführend ist folgender Wikipedia Artikel:
https://de.wikipedia.org/wiki/Bitboard?wprov=sfti1

2. Die Schachregeln

Sind natürlich die gleichen.
Im Computerschach werden die legalen Züge durch einen Zuggenerator festgelegt, der auf das Bitboardfeld zugreift.

Hier eine ausführliche Erklärung: https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/

3. Die Bewertung

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) verwandt.

b) der Stellung wird nach der Schacherfahrung (Heuristik) bewertet, indem der Figurenwert erhöht oder vermindert wird. Diese hängt im wesentlichen vom Standort 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 oder sich selbst trainierendes (Reinforcement Learning) Netz vorgenommen (NN, NNUE).

Siehe Wikipedia Artikel: https://de.wikipedia.org/wiki/AlphaZero?wprov=sfti1

4. Die Suche

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 ein ausführliche Wikipedia Beschreibungen:
https://de.wikipedia.org/wiki/Alpha-Beta-Suche?wprov=sfti1
https://www.chessprogramming.org/Monte-Carlo_Tree_Search

5. 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 verschiedene Datenbanken (Eröffnungsbücher, Endspieltabellen) und Berechnungstabellen (Hash- bzw. Transformationstabellen) zur Verfügung.
Siehe: https://en.wikipedia.org/wiki/Transposition_table?wprov=sfti1
https://www.chessprogramming.org/Endgame_Tablebases

6. 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.html
Parent - By Lothar Jung Date 2021-10-10 11:35 Edited 2021-10-10 12:00
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=sfti1

2. 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=28583

b) 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=sfti1

4. 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=sfti1
https://www.chessprogramming.org/Monte-Carlo_Tree_Search

5. 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=sfti1
https://www.chessprogramming.org/Endgame_Tablebases

6. 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.html

7. 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
- By Lothar Jung Date 2021-11-10 09:44 Upvotes 1
Eine Architekturübersicht von DokChess:

https://www.dokchess.de/00_ueberblick/
- By Lothar Jung Date 2022-05-12 13:22 Upvotes 1
Hier eine mathematische Untersuchung zu der Frage, wieviel Züge maximal eine Schachpartie erreichen kann:

https://math.stackexchange.com/questions/194008/how-many-turns-can-a-chess-game-take-at-maximum
- By Lothar Jung Date 2022-09-17 13:48 Edited 2022-09-17 13:50 Upvotes 1
Eine lesenswerte Abhandlung - gerade für den Einstieg - über

„Software Engineering in Theorie und Praxis: Die Entwicklung und Implementierung einer Schach-Software“

https://www.grin.com/document/124079
- By Lothar Jung Date 2022-09-17 16:16 Upvotes 1
Hier eine Webseite der „Rustic Chessengine“:

https://rustic-chess.org/front_matter/title.html
- By Lothar Jung Date 2022-09-18 15:55 Upvotes 1
Hier eine Wiki zur Schachprogrammierung:

https://de.wikipedia.org/wiki/Schachprogramm?wprov=sfti1
- - By Lothar Jung Date 2022-11-05 08:47 Upvotes 1
Hier eine anschauliche Eiführung von chess24.com:

https://chess24.com/de/lesen/news/wie-denkt-ein-schachprogramm
Parent - By Lothar Jung Date 2022-11-05 15:32 Upvotes 1
- By Lothar Jung Date 2023-02-06 19:34
Webseite von Thomas Petzke zu Engine Programming:

http://www.fam-petzke.de/chess_home_en.shtml
- By Lothar Jung Date 2023-07-08 12:53 Upvotes 1
Ein Schachcomputerprogramm nutzt verschiedene Funktionen, um effektiv zu arbeiten.

Hier ist eine Zusammenfassung der wichtigsten Funktionen und wie sie zusammenwirken:

1. Ein- und Ausgabe der Brettstellung über UCI (Universal Chess Interface):
   UCI ist ein Protokoll, das die Kommunikation zwischen dem Schachcomputerprogramm und einer Benutzeroberfläche ermöglicht. Über UCI kann die Benutzeroberfläche dem Programm die aktuelle Stellung des Schachbretts mitteilen, und das Programm kann seine Züge an die Benutzeroberfläche zurückgeben.

2. Bitboards:
   Bitboards sind eine effiziente Darstellung der Schachbrettstellung mithilfe von Bitmasken. Jedes Bitboard repräsentiert eine bestimmte Schachfigur oder eine bestimmte Eigenschaft des Schachbretts. Bitboards ermöglichen schnelle und parallele Berechnungen, indem sie Bitoperationen nutzen, um beispielsweise mögliche Züge zu generieren oder Angriffsrichtungen zu bestimmen.

3. Alpha-Beta-Suche:
   Die Alpha-Beta-Suche ist ein Algorithmus zur Bestimmung des besten Zuges in einem Spielbaum. Es handelt sich um eine Variante des Minimax-Algorithmus, der den Suchraum durch den Einsatz von Alpha- und Beta-Grenzen einschränkt. Das Schachcomputerprogramm nutzt die Alpha-Beta-Suche, um in den Spielbäumen nach den besten Zügen zu suchen und eine Bewertungsfunktion einzusetzen, um die Qualität der Züge zu bewerten.

4. Hashtables:
   Hashtables dienen als Zwischenspeicher für Positionen und Bewertungen. Sie ermöglichen eine effiziente Wiederherstellung von bereits analysierten Positionen, indem sie eine Position als Schlüssel verwenden und die dazugehörige Bewertung speichern. Hashtables werden verwendet, um die Suche zu beschleunigen, indem bereits bewertete Positionen wiederverwendet werden können.

5. Transpositionstabellen:
   Transpositionstabellen sind eine spezielle Art von Hashtables, die verwendet werden, um Positionen zu speichern, die durch unterschiedliche Zugfolgen erreicht wurden, aber zur gleichen Stellung führen. Durch die Nutzung von Transpositionstabellen kann das Programm unnötige Duplikate in der Suche vermeiden und die Effizienz verbessern.

6. Forwardpruning:
   Forwardpruning ist eine Technik, bei der bestimmte Teile des Spielbaums vorzeitig ausgeschlossen werden, um die Suchtiefe zu reduzieren. Das Schachcomputerprogramm verwendet Forwardpruning, um vielversprechende Zugfolgen zu priorisieren und weniger aussichtsreiche Varianten zu verwerfen.

7. Bewertungsfunktion:
   Die Bewertungsfunktion ist ein zentrales Element eines Schachcomputerprogramms. Sie bewertet eine gegebene Schachstellung und weist ihr einen numerischen Wert zu, der angibt, wie gut die Stellung für den Spieler ist. Die Bewertungsfunktion berücksichtigt verschiedene Faktoren wie Materialunterschiede, Königssicherheit, Figurenaktivität und Bauernstruktur. Sie hilft dem Schachcomputerprogramm, die Qualität einer gegebenen Position zu bestimmen.

8. Eröffnungsbibliothek:
   Eine Eröffnungsbibliothek enthält vorberechnete Züge und Varianten für die Anfangsphase des Schachspiels. Das Schachcomputerprogramm nutzt die Eröffnungsbibliothek, um schnell zu den besten Eröffnungszügen zu gelangen, ohne sie vollständig durchsuchen zu müssen. Dies spart Zeit und ermöglicht eine effiziente Nutzung der Rechenressourcen.

9. Endspieldatenbank:
   Eine Endspieldatenbank enthält vorberechnete Informationen über die bestmöglichen Züge in Endspielen mit einer geringen Anzahl von Figuren auf dem Brett. Das Schachcomputerprogramm nutzt die Endspieldatenbank, um Endspiele präzise zu analysieren und optimale Entscheidungen zu treffen.

Diese Funktionen wirken zusammen, um ein Schachcomputerprogramm zu unterstützen. Das Programm verwendet UCI für die Kommunikation mit einer Benutzeroberfläche, Bitboards zur effizienten Darstellung des Schachbretts, Alpha-Beta-Suche mit Bewertungsfunktion und Forwardpruning zur Findung des besten Zuges, Hashtables und Transpositionstabellen zur Speicherung und Wiederverwendung von Positionen, eine Eröffnungsbibliothek für schnelle Zugauswahl in der Eröffnungsphase und eine Endspieldatenbank für präzise Endspielsimulationen. Zusammen ermöglichen diese Funktionen die Entwicklung eines starken und effizienten Schachcomputerprogramms.

Hier ist ein genereller Programmablauf, der die verschiedenen Funktionen eines Schachcomputerprogramms berücksichtigt:

1. Initialisierung:
   - Laden der Eröffnungsbibliothek und Endspieldatenbank in den Speicher.
   - Aufbau der Hashtables und Transpositionstabellen.

2. Benutzereingabe:
   - Über das UCI-Protokoll die aktuelle Brettstellung von der Benutzeroberfläche erhalten.

3. Zuggenerierung:
   - Verwenden der Bitboards, um mögliche Züge für den aktuellen Zustand des Schachbretts zu generieren.
   - Überprüfen von Zugregeln, um ungültige Züge zu eliminieren.

4. Alpha-Beta-Suche:
   - Starten der Alpha-Beta-Suche mit einer festgelegten Suchtiefe oder Zeitbegrenzung.
   - Iterative Tiefensuche, um den Suchraum schrittweise zu erweitern.
   - Anwenden von Forwardpruning, um nicht vielversprechende Zugfolgen auszuschließen.
   - Bewertung der Positionen mit Hilfe der Bewertungsfunktion.
   - Aktualisieren der besten Zugsequenz und des Bewertungswerts während der Suche.

5. Transpositionstabellen und Hashtables:
   - Überprüfen der Transpositionstabellen und Hashtables, ob die aktuelle Position bereits bewertet wurde.
   - Bei Treffern (Position bereits analysiert) direktes Abrufen der Bewertung.

6. Endspielsimulation:
   - Falls das Spiel in ein Endspiel übergeht und die Endspieldatenbank relevante Informationen enthält, Nutzung der Endspieldatenbank zur präzisen Analyse des Endspiels.

7. Zugauswahl und Ausgabe:
   - Auswahl des besten Zuges aus der gefundenen Zugsequenz.
   - Rückgabe des besten Zuges an die Benutzeroberfläche über das UCI-Protokoll.

8. Wiederholung:
   - Wiederholung der Schritte 2 bis 7, bis das Spiel beendet ist oder die maximale Suchtiefe bzw. Zeitbegrenzung erreicht wurde.

Dies ist nur ein grundlegender Ablauf, und die tatsächliche Implementierung kann je nach Schachcomputerprogramm variieren. Es gibt auch viele Optimierungsmöglichkeiten und weitere Funktionen, die in einem Schachcomputerprogramm integriert werden können, aber dieser Ablauf gibt einen Überblick über die wichtigsten Schritte und Funktionen.
- By Lothar Jung Date 2023-11-28 09:02
Hier ein Schachprojekt in Rust mit Quellcode und Erläuterungen:

https://rustic-chess.org/front_matter/title.html
Up Topic Hauptforen / Schachprogrammierung / Einführung in die Schachprogrammierung

Powered by mwForum 2.29.3 © 1999-2014 Markus Wichitill