Schachprogramm

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Zweidimensionales Schachbrett, wie es viele Schach-Frontends auf dem Bildschirm ausgeben

EinSchachprogrammist einComputerprogramm,das in der Lage ist,Schachzu spielen. Nach den kommerziellen Anfängen in den 1970er-Jahren, in denen erste zum Schachspielen speziell angefertigteSchachcomputerim Handel angeboten wurden, läuft es inzwischen zumeist auf handelsüblichenComputern(PCs) oder auf diversenMobilgerätenwie beispielsweise den allgegenwärtigenHandys.Die Entwicklung von Schachprogrammen ist eine Disziplin desComputerschachs.

Während bei früheren Schachprogrammen die gesamte Funktionalität in einem Programm vereint war, besteht moderne Schachsoftware in der Regel aus zwei Teilen: der sogenanntenEngine,der „Maschine “, das die vom Computer gespieltenZügeberechnet, und demSchach-Frontend,der „Oberfläche “, das deren Darstellung und die Benutzerinteraktion übernimmt. Für die interne Kommunikation zwischen Engine und Frontend gibt es zwei weit verbreitete offene Schach-Kommunikationsprotokolle:dasXBoard-Protokoll und das neuereUniversal Chess Interface(UCI). Die Stellungen und Partien werden inproprietärenFormaten oder im offenenPortable-Game-Notation-Format(PGN) gespeichert.

Aktuelle Programme

Graphische Schachfrontends

Schachprogramme stehen auf vielen Geräten und Betriebssystemen zur Verfügung.

Zur komfortablen Bedienung wird eine als Schach-Frontend bezeichnete Benutzeroberfläche benötigt. Hierzu kann beispielsweise das ProgrammXBoardgenutzt werden. Es läuft unter den BetriebssystemenMicrosoft Windows(unter dem NamenWinBoard),Unix/LinuxundAmigaund wird zusammen mitGNU Chessausgeliefert. Ein graphischesJava-basierendes Schach-Frontend mit Datenbankfunktionen ist das ebenfalls unter derGPLveröffentlichteJosé.Eine weitere beliebte Benutzeroberfläche unter Windows für mehr als 250 Schachprogramme istArena,die als Freeware verfügbar ist. Es gibt auch weitere Freeware, die sich für den Einsteiger eignet, so beispielsweiseArasan.Das Schach-Frontend vonKDEist Knights.

José-Schachdatenbankund Schach-Frontend

Inzwischen kann man hochklassiges Schach auch aufMobiltelefonen,PDAsund sonstigenHandheldsspielen. AufPalm-OS-basiertenGeräten steht beispielsweise mitOpenChessein freies Schachprogramm zur Verfügung, das die Auswahl zwischen mehreren Schachengines bietet.

Ambitionierte Spieler greifen oft zu kommerziellen Programmen, die neben dem reinen Schachspiel auch viele Zusatzmöglichkeiten bieten, wie beispielsweise Partieanalyse und Schachtraining. Sehr bekannt dürften die ProgrammeShredderundFritzsein. Diese Programme werden unter anderem von der Hamburger FirmaChessBasevertrieben, die den (europäischen) Markt für professionelle Schachsoftware zunehmend beherrscht.

Engines

Seit Mitte der 2000er Jahre sind Schachengines stärker als menschliche Spieler. Sie werden seitdem häufiger zum Training genutzt oder mit speziellen Einstellungen, die die Spielstärke beschränken, genutzt. BeispielsweiseUfimbietet die Möglichkeit einer solchen Beschränkung.

Das Open-Source-ProgrammStockfishist für verschiedeneBetriebssystememit32-Bit-oder64-Bit-Architekturverfügbar und zählt zu den spielstärksten Schachprogrammen überhaupt. Wegen seiner offenen Entwicklung steht Stockfish nicht in Verdacht, ein Plagiat zu sein. Es ist kostenlos erhältlich.

Die Spielstärke von Schachengines wird in eigenen Turnieren ermittelt und verglichen. In der Top Chess Engine Chess Championship dominieren seit Saison 9, also 2016 Stockfish und LCZero und lösten die Dominanz von Komodo und Houdini ab.

Anfänge und frühe Kontroversen

Eines der bekanntesten kostenlos erhältlichen Schachprogramme istCrafty,einOpen-Source-ProjektvonRobert Hyatt.Ein weiteres spielstarkes Schachprogramm istFruit,das bei der Weltmeisterschaft im Computerschach 2005 den zweiten Platz belegte. Bis zur Version 2.1 ist Fruit ebenfalls unter einer Open-Source-Lizenz erhältlich, genauso wie das ungefähr gleich starke Glaurung 2.1. Stockfish führt die Entwicklung von Glaurung Open Source fort.

Das kommerzielle ProgrammHoudinigehört seit Jahren zu den spielstärksten,ist allerdings umstritten. Der Programmierer des SchachprogrammsRybkabehauptet, ihm seiQuelltextgestohlen worden und auf dieser Basis seien diverse, sehr spielstarke Schachprogramme (IPPOLIT-Familie) entstanden, darunter auch Houdini. Ein Beleg für diese Behauptung wurde – zumindest öffentlich – nicht erbracht. Dem Programmierer des Schachprogramms Rybka wiederum wird nachgesagt, sein Programm Rybka basiere auf Fruit.Aufgrund dieser Kontroversen wurde Houdini – ebenso wie einige andere Programme der Ippolit-Familie – von diversen Ranglistenbetreibern zeitweilig nicht gelistet. Im weiteren Verlauf wurde das Programm Rybka als Plagiat vonFruiteingestuft, wodurch Rybka alle Titel und Erfolge aberkannt wurden. Der Programmierer von Rybka wurde auf Lebenszeit für alle Computerschachturniere gesperrt. Houdini hingegen, das wiederum auf Rybka basieren soll, war dann anerkannt die stärkste Schach-Engine und wurde zusammen mit dem FrontendAquariumbei den Schachweltmeisterschaften zurAnalysegenutzt.

Seit 2005 sorgte das ProgrammRybkafür Schlagzeilen in Fachzeitschriften und Computerforen. Rybka hat ausgeprägte Fertigkeiten auf positionellem,schachstrategischemTerrain und ist damit der menschlichen Spielweise näher gekommen als die meisten anderen Schachprogramme. Rybka führte die wichtigsten Computerschach-Ranglisten mit 50–150 Punkten Vorsprung an. Schachgroßmeister wieAnand,TopalowoderMorosewitschnutzten Rybka zur Analyse, inzwischen wird häufiger Stockfish, Critter oder Houdini eingesetzt.

Seit 2014 werden dieRankinglisten,die mittels Partien zwischen den Programmen ermittelt werden, vom kommerziellen ProgrammKomodound der oben beschriebenen Open-Source-Entwicklung Stockfish Kopf an Kopf angeführt.

Aufbau

Die Hauptbestandteile eines Schachprogramms sind derZuggenerator,dieBewertungsfunktionund ein Programmteil zurSteuerung der Sucheund der Auswahl des nächsten Zuges. Von der aktuellen Stellung (Spielsituation) ausgehend, führt das Programm eineiterative Tiefensuchedurch. In jeder Iteration führt es verschiedene Zugfolgen der Reihe nach aus, bewertet die erreichten Stellungen (Blätter desSuchbaums) mit der Bewertungsfunktion, und von diesen Blattwerten ausgehend bewertet es nach demMinimax-Prinzipdie inneren Knoten des Suchbaums und damit auch die Züge, die jeweils zu einem Knoten führen. Nach der letzten Iteration spielt es den höchstbewerteten Zug im Wurzelknoten (der die aktuelle Stellung repräsentiert).

Ein wichtiges Merkmal eines Schachprogramms ist die Art derinternen Brettdarstellung,derer sich alle anderen Bestandteile des Programms bedienen.

Zuggenerator und interne Brettdarstellung

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Das in allen folgenden Darstellungen verwendete Beispiel
Spielstellung nach: 1. e4 e5 2. Sc3

Der Zuggenerator erzeugt eine Liste aller in einer bestimmten Stellung legalen (regelkonformen) Züge (mögliche Bewegungen der Spielfiguren). In der Anfangsstellung sind 20 Züge möglich (16 Bauernzüge, 4 Springerzüge), im weiteren Spielverlauf kann man im Mittel mit etwa 40 legalen Zügen in jeder Stellung rechnen, imEndspielweniger. Der Zuggenerator muss auch komplizierte Züge wieRochaden,Bauernumwandlungen undEn-passant-Schlägeberücksichtigen.

In der Regel lässt man den Zuggenerator alle pseudolegalen Züge berechnen, d. h., die Königsregel wird nicht beachtet; z. B. könnte ein solcher Zug den König auf ein bedrohtes Feld ziehen. Der Zuggenerator wird dadurch erheblich einfacher und schneller. Die illegalen Züge werden später durch den Programmteil zur Steuerung der Suche aussortiert: Ein Zug war illegal, wenn die darauf folgende Zugliste einen Zug enthält, der den König schlägt.

ZurKodierungder Figuren werden hier in den Beispielen folgende Ganzzahlen verwendet:

Figur	Kodierung
	Weiß	Schwarz
Leeres Feld	0	0
Bauer	1	2
Turm	11	21
Springer	12	22
Läufer	13	23
Dame	14	24
König	10	20
Ungültiges Feld	−1	−1

Die Implementierung des Zuggenerators hängt eng mit der internen Brettdarstellung zusammen. Hier gibt es vier wichtige Vertreter:

12×10-Darstellung

Spielstellung nach: 1. e4 e5 2. Sc3

−1 (0)	−1 (1)	−1 (2)	−1 (3)	−1 (4)	−1 (5)	−1 (6)	−1 (7)	−1 (8)	−1 (…)
−1 (10)	−1	−1	−1	−1	−1 (15)	−1	−1	−1	−1 (19)
−1 (20)	21	22	23	24	20	23	22 (27)	21	−1
−1	2	2	2	2	0 (35)	2	2	2	−1 (39)
−1	0	0	0	0	0	0 (46)	0	0 (48)	−1
−1	0	0	0	0	2	0	0	0	−1
−1	0	0	0	0	1	0	0	0	−1
−1	0	0	12	0	0	0	0	0	−1
−1	1	1	1	1	0	1	1	1	−1
−1	11	0	13	14	10	13	12	11	−1
−1	−1	−1	−1	−1	−1	−1	−1	−1	−1
−1	−1	−1	−1	−1 (…)	−1 (115)	−1 (116)	−1 (117)	−1 (118)	−1 (119)

Das Spielbrett wird auf ein eindimensionales und 120 Elemente großesArrayabgebildet. Der Index (Zahlen in Klammern) läuft in der Regel zeilenweise, hier von 0 (links oben) bis 119 (rechts unten). Zusätzlich zu den 64 gültigen Feldern enthält das Array Felder, die eine Figur beim Verlassen des Brettes erreichen würde und die quasi einen Rand um das reguläre Brett bilden. Auf diesen Randfeldern wird ein bestimmter Wert (hier −1) gespeichert, und wenn eine Figur auf ein Feld mit diesem Eintrag ziehen würde, heißt das, dass sie damit das Brett verlassen würde. Dies kann leicht abgefragt werden, da man ohnehin nachsehen muss, ob das Zielfeld von einer eigenen Figur besetzt ist, wodurch der Zug illegal wäre. Diese Technik macht den Zuggenerator einfach und schnell. Der linke und rechte Rand an jeder Seite muss nur ein Feld groß sein, denn ein Springer, der seitlich vom Brett zieht, landet immer entweder auf der linken oder der rechten Randreihe.

Durch Addition der folgenden Konstanten zu einem Feldindex lassen sich die möglichen Zielfelder für eine Figur auf diesem Feld bestimmen.

Bewegung	Konstanten
Horizontale und vertikale Bewegung (Turm, Dame, König)	−10, −1, +1, +10
Diagonale Bewegung (Läufer, Dame, König)	−11, −9, +9, +11
Bewegung wie ein Springer	−21, −19, −12, −8, +8, +12, +19, +21

Betrachten wir den schwarzen Springer auf Feld 27 (Sg8). Die Addition dieser Konstanten zu 27 ergibt die potentiellen Zielfelder: 6, 8, 15, 19, 35, 39, 46 und 48. Ist der Wert im Zielfeld −1, dann ist der Zug nicht möglich, da der Springer über den Rand ziehen würde. Ist der Wert 1 oder 10 bis 14, ist eine weiße Figur auf dem Feld, die geschlagen werden kann, und ist er gleich Null, ist ein Zug auf das leere Feld möglich. Der Springer kann hier also drei verschiedene Züge auf die Zielfelder 35, 46 und 48 ausführen, die der Zugliste hinzugefügt werden. Falls der Zuggenerator nur legale Züge – und nicht alle pseudolegalen – erzeugen soll, muss man noch beachten, ob der Springer gefesselt ist oder ein Schachgebot besteht, das man abwehren muss.

Ähnlich geht es mit den anderen Figurenarten. Die langschrittigen (Dame, Läufer, Turm) können ein besetztes Feld nicht überspringen. Nachdem ein solches erreicht wurde, ist in dieser Richtung kein weiterer Zug möglich und man geht zur nächsten Zugrichtung.

Während der Zuggenerator recht einfach aufgebaut und schnell ist, sind die statischen Bewertungsfunktionen langsamer.

8×8-Darstellung

Spielstellung nach: 1. e4 e5 2. Sc3

21	22	23	24	20	23	22	21
2	2	2	2	0	2	2	2
0	0	0	0	0	0	0	0
0	0	0	0	2	0	0	0
0	0	0	0	1	0	0	0
0	0	12	0	0	0	0	0
1	1	1	1	0	1	1	1
11	0	13	14	10	13	12	11

Die 8×8-Darstellung ist der menschlichen Sicht am nächsten. Das ProgrammGNU Chessverwendete sie bis Version 4. Das Brett wird, wie auch bei 12×10, als eindimensionales Array modelliert, hier mit Indexbereich 0 bis 63 (alternativ 1 bis 64). Ein zweidimensionales Array scheint näherliegend, ist aber langsamer, denn ein Feld muss hier mit zwei Zahlen (Reihe und Linie) bezeichnet werden, zu beiden muss bei der Zugerzeugung eine Konstante addiert werden, und beim Zugriff auf ein Feld ist die Adressberechnung mit zwei Indizes komplizierter.

Der Zuggenerator ist normalerweise komplexer und langsamer als bei der 12×10-Darstellung, da die Spezialfälle am Rand gesondert behandelt werden müssen. Die statische Bewertungsfunktion arbeitet allerdings effizienter, da Reihe und Linie, auf denen ein Feld liegt, mit schnellenBitoperationenbestimmt werden können: UND-Verknüpfen des Index mit 7 ergibt die Linie und Rechtsschieben um 3 Bit die Reihe (bei zeilenweiser Felderanordnung und Indexbereich 0 bis 63). Beim 12×10-Brett muss man hingegen durch 10 dividieren. Die Bewertungsfunktion benötigt diese Information oft, z. B. zur Doppelbauern- oderIsolani-Erkennung.

Auch mit dem 8×8-Brett ist eine schnelle und einfache Zugerzeugung mittels Tabellenzugriff möglich, was aber den Speicherverbrauch erheblich erhöht. GNU Chess verwendet für jede Figurenart ein zweidimensionales Arraynextposmit 64 mal 64 Elementen, dessen Einträge vorab berechnet werden. Indiziert man es mit dem Ausgangsfeldfeiner Figur und einem ihrer Zielfelder, liest man das nächste Zielfeld für die Figur daraus ab.nextpos(f,f)liefert das erste Zielfeld. Für die langschrittigen Figuren gibt es zusätzlich das Arraynextdir,aus dem bei besetztem Zielfeld das nächste Zielfeld gelesen wird (erstes Feld in einer neuen Zugrichtung). Gibt es kein Zielfeld mehr, liefern beide wieder den Wertf.

Eine andere Möglichkeit ist ein dreidimensionales Array, das für alle Felder und Figurentypen alle Zielfelder enthält, die diese Figur von diesem Feld aus erreichen kann. Der dritte Index läuft über diese Zielfelder. Der Speicherverbrauch ist hier niedriger, besonders wenn man ein zweidimensionales Array von Zeigern verwendet, die jeweils auf einHalden-Arraypassender Größe zeigen, entsprechend der unterschiedlichen Anzahl der Zielfelder. Die Einträge sind zweiteilig: Der erste Teil ist der Zielfeldindex und der zweite ist die Anzahl der im Array darauf folgenden Felder, die bei besetztem Zielfeld zu übergehen sind (oder direkt der nächste Index in das Array).

0x88-Darstellung

Diese ist eine Weiterentwicklung der 8×8-Darstellung. Bei zeilenweiser Darstellung mit 16 Feldern je Zeile bildet der linke Bereich von 8 mal 8 Feldern das Schachbrett, der rechte Bereich von 8 mal 8 Feldern wird nicht verwendet. Wenn eine Figur über den Rand ziehen würde, erkennt man das durchbitweise UND-Verknüpfungdes Zielfeldindex mit derHexadezimalzahl0x88 (= 136). Wenn das Ergebnis Null ist, bezeichnet der Feldindex ein gültiges Feld, anderenfalls würde die Figur das Brett verlassen. Reihe und Linie eines Feldes kann man ähnlich wie beim 8×8-Brett durch Rechtsschieben um 4 Bit bzw. UND-Verknüpfen mit 7 berechnen.

Bei dieser Darstellung kann man außerdem anhand der Indexdifferenz zweier Felder ermitteln, ob und mit welcher Figur ein Zug von einem zum anderen Feld möglich ist. Zum Beispiel ist ein Turmzug genau dann möglich, wenn die Differenz im Bereich -7 bis 7 oder ein Vielfaches von 16 ist. Mit der 8×8- oder 10×12-Darstellung geht das nicht, denn das Kriterium wird auch von Feldpaaren erfüllt, die keinen entsprechenden Zug zulassen. Die Felder h4 und a5 zum Beispiel haben dort eine Indexdifferenz kleiner 8, obwohl kein Turmzug möglich ist.

Bitboards

→Hauptartikel:Bitboard

Manche modernen Schachprogramme, etwaRybka,Craftyoder GNU Chess 5, verwendenBitboards.Diese sind besonders effizient auf64-Bit-Rechnerarchitekturenimplementierbar, wo die Anzahl derBitseinesRegisters/Wortsmit der Anzahl der Felder übereinstimmt. Jede Bitposition in einem Wort ist einem Feld des Bretts zugeordnet, und durch das Bit an dieser Position wird eine Angabe über das entsprechende Feld gemacht.

Im folgenden Beispiel wird die Stellung nach den Zügen 1. e4 e5 2. Sc3 mit acht Registern von 64 Bit dargestellt. Das RegisterBenthält überall ein 1-Bit, wo ein Bauer (gleich welcher Farbe) auf dem entsprechenden Feld steht. Auch für die übrigen Figurenarten gibt es je ein Register.WEIundSCHgeben an, wo sich eine weiße bzw. eine schwarze Figur befindet. Zur besseren Übersichtlichkeit sind Bits mit dem Wert 0 durch-wiedergegeben.

Reihe 8 7 6 5 4 3 2 1
Linie abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh
Bitposition 63 56 48 40 32 24 16 8 0
Registername | | | | | | | | |
| | | | | | | | | |
Bauern B -------- 1111-111 -------- ----1--- ----1--- -------- 1111-111 --------
Türme T 1------1 -------- -------- -------- -------- -------- -------- 1------1
Springer S -1----1- -------- -------- -------- -------- --1----- -------- ------1-
Läufer L --1--1-- -------- -------- -------- -------- -------- -------- --1--1--
Damen D ---1---- -------- -------- -------- -------- -------- -------- ---1----
Könige K ----1--- -------- -------- -------- -------- -------- -------- ----1---
Weiss WEI -------- -------- -------- -------- ----1--- --1----- 1111-111 1-111111
Schwarz SCH 11111111 1111-111 -------- ----1--- -------- -------- -------- --------

Mit schnellenbitweisen Operationenkann man nun für alle Felder parallel Informationen über die Stellung berechnen. Zum Beispiel lassen sich durch die UND-VerknüpfungT & WEIalle Positionen der weißen Türme bestimmen, und((B & SCH) >> 8) & ~(WEI | SCH)liefert ein Bitmuster mit den Feldern, auf die ein schwarzer Bauer mit einem Einzelschritt ziehen kann. Dabei bezeichnet>>dieBitverschiebungnach rechts (zum niederwertigen Ende),~die Negation und|die ODER-Verknüpfung.

Bewertungsfunktionen

DieBewertungsfunktionliefert dieheuristischeBewertung einer Stellung, ohne die Nachfolgezüge zu bestimmen. Sie setzt sich aus einermateriellenund einerpositionellenKomponente zusammen. Die positionelle Komponente ergänzt die materielle, da die Stärke der Spielfiguren auch von ihren Positionen untereinander abhängen. Vereinfachte Bewertungsfunktionen können auch von menschlichen Spielern ausgeführt werden, was allerdings nur eine historische Bedeutung hat. Computerprogramme zeigen sehr oft die Bewertung einer Spielsituation numerisch (in sogenanntenBauerneinheiten) an, wobei positive Werte Vorteile und negative Werte Nachteile für einen bestimmten Spieler bedeuten.

Material

Für diematerielleWertung werden für die auf dem Brett befindlichen Spielfiguren Werte addiert. Der ungefähre Wert der Figurenarten in¹⁄₁₀₀Bauerneinheitenist in der folgenden Tabelle angegeben.

Bauer	Springer	Läufer	Turm	Dame
100	310	320	460	900

Dabei werden die weißen Figuren (bzw. die der am Zug befindlichen Partei) positiv gezählt und die schwarzen (bzw. die der nachziehenden Partei) negativ. Der König braucht nicht mitgezählt zu werden, da beide Parteien während des gesamten Spiels jeweils einen König haben.

Position

DiepositionelleWertung zu bestimmen, ist eine Aufgabe von größerer Komplexität, in der sich die verschiedenen Schachprogramme deutlich voneinander unterscheiden. Bei kommerziellen Programmen bleibt sie ein wohlgehütetes Geheimnis. Bei der positionellen Wertung wird versucht, Stellungen aufgrund von schachrelevanten Parametern zu bewerten. Schachrelevante Parameter lassen sich grob klassifizieren in Königssicherheit, Bauernstruktur, beherrschte und bedrohte Felder sowie Figurenentwicklung. So wird zum Beispiel eine Stellung, bei der die Türme noch eingeengt zwischen Springern und Bauern stehen, schlechter bewertet als eine, bei der die Türme schon auf offenen Linien stehen.

Innerhalb dieser Kategorien gibt es quasi beliebig viele Parameter (fürBauernstrukturenzum BeispielFreibauer,Doppelbauer,Hebel,Widder,Isolani,Bauernketten;für Königssicherheit zum Beispiel: Kann der König leicht links oder rechts rochieren? Kann er im Zentrum bleiben? Sind Bauern vor dem König?). Es bietet sich an, diese Parameter zunächst wertneutral aus der gegebenen Stellung zu extrahieren. Schachprogrammierer stehen vor der Entscheidung, wie viel Rechenzeit sie für die positionelle Komponente einer ausgefeilten Bewertungsfunktion aufwenden sollen, und welche Parameter überhaupt einfließen sollen: Je tiefer die Schachprogramme den Suchbaum analysieren können, desto eher wird nämlich die Umwandlung positioneller Vorteile in materielle Vorteile sichtbar.

Statische Bewertungsfunktion

Kann ein Schachprogramm die Werte dieser Parameter pro Stellung effizient bestimmen, müssen diese untereinander gewichtet werden. Die Gewichtung der positionellen Komponente kann teilweise automatisch über das Analysieren vonSchachdatenbankenoder durch Spiele gegen andere Schachprogramme erfolgen. Geschieht dies im Vorfeld der Programmentwicklung, spricht man von einer statischen Bewertungsfunktion. Einfach aufgebaute Bewertungsfunktionen verwenden für die positionelle Komponente Positionsgewichte für die sechs Spielfigurentypen, die aber für Eröffnung, Mittel- und Endspiel jeweils unterschiedlich ausfallen.

Die Bewertungsfunktion kann außer in Grenzfällen wie Endspielen oder Matt- oder Pattsituationen keine objektiv richtigen Ergebnisse liefern. Indem die Bewertungsfunktion die materielle und positionelle Komponente zu einer einzigen Bewertungszahl zusammenfasst, ermöglicht sie aber die Sortierung und Auswahl des „besten “beziehungsweise „schlechtesten “Zuges.

Klassischerweise wird der Algorithmus, der eine Stellung nach den einzelnen Kriterien bewertet, vom Programmierer explizit codiert. Heutige Programme bewerten hingegen die Stellungen oft mit einemneuronalen Netz,das mit einer großen Zahl von Teststellungen trainiert wird. Während der Zugberechnung bekommt es dann die jeweils zu bewertende Stellung (z. B. Blatt des Suchbaums) eingegeben und gibt die Bewertungszahl aus. Damit ein solches Programm schnell läuft, wird in der RegelGrafikhardwarezur Auswertung des Netzes genutzt, die zur parallelen Berechnung der Zustände der Netzknoten (Neurone) gut geeignet ist. Manche Programme, beispielsweiseStockfish,nutzen einNNUE(effizient aktualisierbares Netz). Bei geringen Änderungen an einer Stellung (etwa zurücknehmen eines Zugs und ausführen eines anderen) müssen hier nicht alle Knoten des Netzwerks neu ausgewertet werden, sondern nur einige, die von der Änderung betroffen sind. Dadurch kann es auch von einerCPUschnell ausgeführt werden.

Dynamische Bewertungsfunktion

In der Regel wird die Bewertungsfunktion vom Programmierer implementiert und während des Spieles nicht mehr verändert. Eine erweiterte Möglichkeit besteht darin, während des Spieles vergleichbare Stellungen aus einer Schachdatenbank zu ermitteln und so die Gewichtung der positionellen Parameter zu optimieren. Dies entspricht eher dem menschlichen Ansatz. Ein erfahrener Spieler berücksichtigt Kriterien wie Königssicherheit oder Freibauern auch unter Einbeziehung ihm bekannter Partien und deren Ergebnissen.

Steuerung der Suche und Zugauswahl

Grundsätzlich basiert die Steuerung der Suche auf demSpielbaum.Er enthält, beginnend bei der aktuellen Stellung (Wurzelknoten), alle Züge des Anziehenden, darauf wieder alle möglichen Antwortzüge des Nachziehenden und so weiter, jeweils bis zum Erreichen einer Endstellung (Matt, Patt, technisches Remis oder Stellungswiederholung). Der Spielbaum ist meist viel zu groß, um ihn vollständig durchzurechnen, deshalb beschränkt sich das Programm auf einen Teil davon (Suchbaum).

Im einfachsten Fall arbeitet das Programm nach derA-Strategie,d. h., es berechnet alle möglichen Zugfolgen bis zu einer bestimmten Tiefe (Zahl der aufeinanderfolgenden Züge), die durch die Rechenleistung und die verfügbare Zeit begrenzt wird. Jede dabei entstehende Stellung wird bewertet. Ist es keine Endstellung wie etwa ein Matt, wird die heuristische Bewertungsfunktion eingesetzt. Mit demMinimax-Algorithmuswerden die Züge in der Wurzelstellung bewertet und der höchstbewertete gespielt.

Da die Anzahl der zu untersuchenden Stellungen exponentiell mit der Tiefe wächst, andererseits eine höhere Tiefe eine entsprechende Spielstärkeverbesserung bringt, hat man in den rund 50 Jahren der Programmentwicklung ein ganzes Arsenal an Beschleunigungsmaßnahmen erfunden, die man in zwei Gruppen einteilen kann. Die einen versuchen, den Suchbaum durch allgemeineAlgorithmender Informatik zu verkleinern, so zum Beispiel:

• Alpha-Beta-Suche(Negamax-Verfahren)
• Hashtabellezur Erkennung von Zugumstellungen
• Null-Zug-Suche

Die Alpha-Beta-Suche schneidet Teile des Suchbaums ab, die für die Ermittlung des höchstbewerteten Zuges im Wurzelknoten nicht betrachtet werden müssen. Diese Technik spart sehr viel: Bei guter Implementierung wird die erreichbare Tiefe annähernd verdoppelt.

Die begrenzte Rechentiefe lässt das Programm oft eine taktische Kombination übersehen. Um das zu mildern, vertieft man einzelne interessante Zugfolgen, zum Beispiel nach Schachgeboten oder Zügen, die die gegnerische Königsstellung schwächen, um Mattkombinationen leichter zu entdecken. Die sogenannteRecapture-Heuristikvertieft Zugfolgen, die einen Abtausch enthalten, um die Folgen des Tausches besser abschätzen zu können. Die Methode dersingular extensions(deutsch„vereinzelte Erweiterungen “) vertieft die Suche für erzwungene (forcierte) Zugfolgen, also in Fällen, bei denen es für eine oder beide Seiten jeweils nur eine einzige „vernünftige “Antwort gibt.

Weitere Techniken zur Beschleunigung sind die Verwendung vereinfachter Bewertungsfunktionen nach Zugfolgen, die als wenig sinnvoll eingeschätzt werden, sowie die inkrementelle Bewertung, die den Wert einer Stellung nicht immer neu berechnet, sondern bei Ausführung eines Zuges aktualisiert. Manche Programme erledigen einen Großteil der Bewertungsarbeit durch Analysieren der Wurzelstellung und speichern die Ergebnisse in Datenstrukturen, die dann die Blattbewertung erheblich vereinfachen und beschleunigen (z. B. Figuren-Felder-Tabellen).

Manche Programme berechnen nicht (oder nicht immer) alle Züge, die in einer Stellung möglich sind (B-Strategie). Die Werte der Züge werden heuristisch abgeschätzt, wonach nur die hoch bewerteten in den Suchbaum aufgenommen werden. Dadurch ahmt man das Verhalten eines menschlichen Spielers nach. Der Suchbaum wird erheblich kleiner, aber man riskiert, dass die Heuristik zuweilen einen guten Zug übersieht. Diese Verfahren sind sehr viel schwieriger zu implementieren als die A-Strategie. Auch lassen sie sich nicht ohne weiteres auf andere Spiele wieGoübertragen, denn die Kriterien der Zugauswahl sind dann völlig andere.

Man darf die Berechnung nicht abbrechen und die Blattbewertung durchführen, wenn die Partie gerade mitten in einem Abtausch ist, dies würde eine verzerrte Materialbilanz liefern. Hat eine Partei gerade eine gedeckte Figur geschlagen und wird hier bewertet, erhält man ein unechtes Materialübergewicht für diese Partei. Eine oft angewandte Abhilfe ist die sogenannte Ruhesuche (quiesence-search): In einer Blattstellung berechnet man noch alle Schlagzüge, und darauf wieder nur die schlagenden Antwortzüge usw., wobei meist noch die weniger aussichtsreichen Schlagzüge abgeschnitten werden, und außerdem wird die maximale Länge der Schlagzugfolgen begrenzt, damit das ganze nicht zu viel Zeit braucht. In jeder so erreichten Stellung erfolgt die Blattbewertung durch die heuristische Bewertungsfunktion, und der Wert der Stellung ist das Maximum aus dem Blattwert und den Werten der Schlagzüge. Der Blattwert steht für die Werte der nicht schlagenden Züge, denn es kann sein, das jeder Schlagzug ein Fehler wäre und es am besten ist, nicht zu schlagen.

Bibliotheken und Datenbanken

Eröffnungsbibliothek

→Hauptartikel:Eröffnungstabelle

Schach wird im Wettkampf auf Zeit gespielt, das heißt, für eine Anzahl von Zügen steht nur eine definierte Zeit zur Verfügung. Viele Schachprogramme sind daher mit einer Eröffnungsbibliothek ausgestattet, in der sehr viele „gute “Zugreihenfolgen in der Eröffnungsphase von Schachspielen abgespeichert sind. In der Anfangsphase des Schachspiels sieht das Programm in dieser Bibliothek nach, welcher Zug in einer bestimmten Brettstellung der geeignetste ist. Dieses „Nachsehen “geht schneller, als den Zug auszurechnen. Die so gesparte Rechenzeit steht dem Programm dann in späteren Phasen des Spiels zur Verfügung. Das Verfahren, Brettstellungen einschließlich der „guten “Züge abzuspeichern, ist nur für Eröffnung und Endspiel sinnvoll, da hier die Anzahl der Brettstellungen noch überschaubar ist. Eröffnungsbibliotheken kommerziell erhältlicher Programme weisen einen immer größer werdenden Umfang auf. Sie werden meist aus Meisterpartien generiert. Dies birgt die Gefahr, dass auch unbemerkte Fehler übernommen werden, die das Programm aus eigener Berechnung nicht spielen würde.

Einen großen Anteil an der Spielstärke hat die Abstimmung der Eröffnungsbibliothek auf die später in der Partie genutzte Bewertungsfunktion.

Endspieldatenbank

→Hauptartikel:Endspieldatenbank

ImEndspiel,wenn nur noch wenige Figuren auf dem Brett sind, kann man den optimalen Zug im Vorhinein durch vollständige Analyse (Brute-Force-Methode) berechnen. Es gibt nicht wenige Endspielstellungen, in denen das menschliche Denken, aber auch die Computeranalyse in Echtzeit völlig überfordert wären. Viele Schachprogramme verwenden deshalb Endspieldatenbanken, die alle möglichen Stellungen mit 3, 4, 5, 6 oder sogar 7 Steinen sowie deren Ausgang (bei optimalem Spiel) enthalten. Das Erstellen von Endspiel-Datenbanken geht aufKen Thompsonzurück. Die ersten Sechssteiner wurden 1991 von Lewis Stiller vollständig berechnet, seit 2012 sind alle Siebensteiner erfasst.

Schachdatenbank

→Hauptartikel:Schachdatenbank

Schachdatenbanken enthalten gespielte Partien. Sie helfen zum Beispiel beim Studium vonEröffnungenund bei der Vorbereitung auf die nächsten Gegner.

Für Schachprogramme lassen sich aus dem Datenbestand Eröffnungsbibliotheken generieren. Auch ist es möglich, während der Partie vergleichbare Stellungen aus einer Schachdatenbank zu ermitteln und unter Berücksichtigung des dort verzeichneten Partieverlaufs positionelle Bewertungsparameter (siehe oben) zu optimieren (dynamische Bewertungsfunktion).

Geschichte

Die Geschichte des Schachprogramms hängt sehr eng mit der Geschichte des Schachcomputers zusammen und lässt sich zumeist nicht getrennt behandeln. Hier werden lediglich Entwicklungen der grundlegenden Algorithmen beschrieben. Zu den in den letzten Jahren medienwirksam ausgetragenen Wettbewerben mit Weltklassespielern sieheSchachcomputer im Spiel gegen Menschen.

Konrad Zuse

→Hauptartikel:Konrad Zuse

In den Jahren 1942 bis 1945 schrieb Konrad Zuse das weltweit erste Schachprogramm in seiner neu entwickelten Programmiersprache, demPlankalkül.Erstmals implementiert wurde die Sprache aber erst in den 1970ern.

Alan Turing

→Hauptartikel:Alan Turing

Der britischeMathematikerundCodeknackerAlan Turing entwickelte ein Verfahren, das jedem möglichen Zug einen Wert zuweist. So sollte immer der jeweils beste Zug errechnet werden. Turings Schachprogramm basierte auf folgenden Grundsätzen:

• JedeFigurerhielt einen bestimmten Wert: Bauer = 1; Springer = 3; Läufer = 3,5; Turm = 5; Dame = 10 und König = 1000 (damit dieser niemals geopfert werden konnte).
• Alle weißen Züge und alle schwarzen Gegenzüge wurden untersucht. Wenn Weiß einen Schlagzug ausführen konnte, dann wurden alle Schlagzüge des Gegners, alle darauffolgenden weißen Schlagzüge usw. untersucht, bis die Stellung „tot “war, das heißt, bis es keine weiteren Schlagzüge und kein Matt gab. In den entstehenden Stellungen wurde eine Figurenzählung durchgeführt und der Zug gewählt, der das meiste Material gewann bzw. am wenigsten verlor. Da jedoch, besonders in der Eröffnungsphase, die meisten zur Auswahl stehenden Züge das gleiche Ergebnis (nahe Null) lieferten, führte Turing auch einige positionelle Bewertungskriterien ein, wie Mobilität (Zugmöglichkeiten), Schlagmöglichkeit, Rochade oder Mattdrohung.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Stellung nach dem 29. Zug

Da es zu der Zeit noch keine geeigneten programmierbaren Rechenmaschinen gab, musste Turing jeden Zug von Hand auf Papier selbst ausrechnen, was einen hohen Zeitaufwand bedeutete. Pro Zug musste er ca. 30 Minuten aufwenden.Immerhin wurde das Funktionsprinzip augenfällig, nach dem im Grunde auch alle heutigen Schachprogramme noch arbeiten. Die erste Partie seiner „Papiermaschine “fand im Jahr 1952 statt und soll hier beispielhaft aufgeführt werden:

Turings Papiermaschine – Alick Glennie, Manchester, 1952

1. e4 e5 2. Sc3 Sf6 3. d4 Lb4 4. Sf3 d6 5. Ld2 Sc6 6. d5 Sd4 7. h4 Lg4 8. a4 Sxf3+ 9. gxf3 Lh5 10. Lb5+ c6 11. dxc6 0–0 12. cxb7 Tb8 13. La6 Da5 14. De2 Sd7 15. Tg1 Sc5 16. Tg5 Lg6 17. Lb5 Sxb7 18. 0–0–0 Sc5 19. Lc6 Tfc8 20. Ld5 Lxc3 21. Lxc3 Dxa4 22. Kd2 (22. h5 hätte den Läufer erobert.) 22.… Se6 23. Tg4 Sd4 (23.… Txb2 24. Lxb2 Txc2+) 24. Dd3 Sb5 25. Lb3 Da6 26. Lc4 Lh5 27. Tg3 Da4 28. Lxb5 Dxb5 29. Dxd6 Td8 0:1

Zur „Papiermaschine “gibt es auch Implementierungen für heutige Computer.

Claude Shannon

→Hauptartikel:Claude Shannon

In denBell Laboratorieshielt Claude Shannon am 9. März 1949 einen für die Entwicklung von Schachprogrammen entscheidenden Vortrag. Er beschrieb dort die interne Brettdarstellung, dieBaumsuche,die Bewertungsfunktion sowie die Zugsuche mit Hilfe desMinimax-Algorithmus.Er gab auch schon zwei verschiedene Strategien zur Bestimmung des besten Zuges an:A-StrategieundB-Strategie.

Dietrich Prinz

→Hauptartikel:Dietrich Prinz

Dietrich Günther Prinz von derUniversität Manchesterhat im November 1951 für denFerranti-Mark-I-Computer(GB) ein Programm erstellt, das eine zweizügige Mattaufgabe in 15 Minuten löste. Das Programm gilt als erstes Löseprogramm der Schachgeschichte.

John von Neumann

→Hauptartikel:John von Neumann

a b c d e f 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f

Grundstellung

John von Neumann klassifizierte das Schachspiel in seinerSpieltheorieals Zwei-Personen-Nullsummenspielmit vollständiger Information. Diese Klasse von Problemen (dazu gehört auchTic-Tac-Toe) kann mit demMinimax-Algorithmusgelöst werden. Schach ist jedoch zu komplex, um den Suchbaum vollständig abarbeiten zu können. Schachprogramme sind deshalb auf Näherungsverfahren angewiesen.

Das Schachprogramm von John von Neumann wurde Mitte der 1950er Jahre fertiggestellt und lief auf dem 1950 aufgestellten RöhrenrechnerMANIAC I.Zur Vereinfachung wurde nur auf einem 6×6-Brett gespielt. Das Programm spielte insgesamt drei Partien: die erste gegen sich selbst, eine weitere verlor es gegen einen starken Schachspieler, obwohl dieser ihm eine Dame vorgab, und die dritte gewann es gegen eine junge Frau, die erst seit einer Woche Schach spielte und extra für dieses Spiel trainiert hatte.

a b c d e f 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f

Stellung nach dem 21. Zug

MANIAC I – Mensch, Los Alamos, 1956:

(6×6-Brett ohne Läufer, kein Doppelschritt oder Rochade)

1. d3 b4 2. Sf3 d4 3. b3 e4 4. Se1 a4 5. bxa4 (5. Sd2 nebst 6. Sc4+ Sxc4 7. bxc4 mit gutem Spiel) 5.… Sxa4 6. Kd2 Sc3 7. Sxc3 bxc3+ 8. Kd1 f4 9. a3 Tb6 10. a4 Ta6 11. a5 Kd5 12. Da3 Db5 13. Da2+ Ke5 14. Tb1 Txa5 15. Txb5 Txa2 16. Tb1 (Um 16.… Ta1 matt zu verhindern) 16.… Ta5 17. f3 Ta4 18. fxe4 c4 19. Sf3+ Kd6 20. e5+ Kd5 21. exf6D 21.… Sc5 (22. Dxd4+ Kc6 23. Se5 matt.) 1:0

Zum ersten Mal hat ein Mensch gegen ein Schachprogramm verloren. Diese vereinfachteSchachvariantewird auchLos Alamos Chessgenannt.

1957 implementierte der IBM-Angestellte Alex Bernstein auf einerIBM 704ein Schachprogramm, das nach den Standardregeln spielte. Es selektierte in jeder Stellung die sieben plausibelsten Züge und führte eine Suche von 4 Halbzügen durch, was ungefähr 8 Minuten Rechenzeit erforderte. Bernstein erhielt bei der Entwicklung Unterstützung durch den amerikanischen GroßmeisterArthur Bisguier.Das Programm verlor chancenlos gegen den SchachmeisterEdward Lasker,der dem Computer jedoch ein passables Amateurniveau bescheinigte.

1958 wurde dieAlpha-Beta-SuchevonAllen Newell,John Clifford ShawundHerbert A. Simonentdeckt und brachte einen gewaltigen Leistungsschub.

Richard Greenblatt

→Hauptartikel:Richard Greenblatt

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Mattstellung nach dem 37. Zug

Das erste Programm, das an menschlichen Turnieren teilnahm, warMac Hack,das von 1965 bis 1967 von Richard Greenblatt amMITentwickelt wurde.

Hubert Dreyfus– MacHack, MIT, 1967

1. e4 e5 2. Sf3 Sc6 3. Lc4 Sf6 4. Sc3 Lc5 5. d3 0–0 6. Sg5 Sa5 7. Ld5 c6 8. Lb3 Sxb3 9. cxb3 h6 10. Sh3 d5 11. exd5 Lg4 12. f3 Lxh3 13. gxh3 Sxd5 14. Sxd5 Dxd5 15. Ld2 Dxd3 16. b4 Le7 17. Tg1 e4 18. fxe4 Lh4+ 19. Tg3 Lxg3+ 20. hxg3 Dxg3+ 21. Ke2 Dxh3 22. Dg1 h5 23. Lc3 g6 24. Df2 h4 25. Df6 Dg4+ 26. Kd2 Tad8+ 27. Kc2 Dxe4+ 28. Kb3 De6+ 29. Dxe6 fxe6 30. Th1 Tf4 31. Le1 Tf3+ 32. Ka4 h3 33. b5 Td4+ 34. b4 cxb5+ 35. Kxb5 Ta3 36. Kc5 Td5+ 37. Kc4 b5# 0:1

Von 1967 bis 1970 kam es zu einem Boom in der Schachprogrammierung, der in dieerste Computerschach-Meisterschaft der Geschichtemündete, die von derAssociation for Computing Machinery(ACM)ausgetragen wurde. Sieger warChess 3.0.

Peter Jennings

Peter Jennings entwickelte 1976 Microchess für denKIM-1-Heimcomputer. Das Programm wurde bis 1979 über 50.000-mal verkauft und war damit das erste kommerziell erfolgreiche Mikrocomputerprogramm. Aufgrund des nur 1152 Bytes großen RAM-Speichers warenRochade,En passantundBauernumwandlungnicht implementiert.

Ken Thompson

→Hauptartikel:Ken Thompson

Ken Thompson entwickelte 1979 die berühmte SchachmaschineBelle,die mit einer Eröffnungsbibliothek undHashtablesarbeitete.

Feng-hsiung Hsu

→Hauptartikel:Feng-hsiung Hsu

Das erste Computerprogramm, das einenamtierenden Schachweltmeisterin einer regulären Turnierpartie schlug, warDeep Blue.Entwickelt vonIBMaufgrund einer Anregung und unter der Leitung des jungen Informatikers Feng-hsiung Hsu, besiegte dieses Programm am 10. Februar 1996 auf einer angepassten und auf Schach optimierten Computerhardware, die ebenfalls von IBM stammte, den damaligen WeltmeisterGarri Kasparowin einer dadurch berühmt gewordenenPartie.Den Wettkampf konnte Garri Kasparow noch mit 4:2 für sich entscheiden. Eine verbesserte Version von Deep Blue nahm allerdings am 11. Mai 1997 auch diese Hürde und errang in einem zweiten Wettkampf mit der sechsten Turnierpartie den Gesamtsieg über Kasparow mit 3,5:2,5. Deep Blue wurde nach dem spektakulären Sieg demontiert und eingemottet. Die Entstehung des Programms wurde später vom Erfinder in einem Buch beschrieben.

Chrilly Donninger und Ulf Lorenz

→Hauptartikel:Christian Donninger

Der Erste, der sich nach Deep Blue wieder auf den Bau spezialisierter Schachhardwarekomponenten als Basis für ein Schachprogramm verlegte, war der österreichische Schachprogrammierer „Chrilly “Donninger, der zuvor jahrelang mit seinem PC-Programm an Computerschachturnieren teilgenommen hatte. Er entwarf ab 2002 einen Schachcomputer mit von ihm selbst modifizierter Hardware, den er zunächst Brutus nannte. Geldgeber ChessBase zog seine Unterstützung dafür aber nach dem schlechten Abschneiden bei einem Turnier 2003 in Graz zurück; Christian Donninger und Ulf Lorenz verfolgten das Projekt zunächst auf eigene Faust unter dem neuen NamenHydraweiter. 2004 fanden Donninger und Lorenz einen neuen Sponsor aus den arabischen Emiraten,PAL Computer Systems.Noch im selben Jahr schlug Hydra den damaligen ComputerweltmeisterShredder.Im Juni 2005 fand gegen den britischen GroßmeisterMichael Adams,damals Siebter der Weltrangliste, ein Wettkampf unter Turnierbedingungen statt, den Hydra überlegen mit 5,5:0,5 gewann.Dies entspricht einer Turnierperformance von über 3100 Elo-Punkten, so viel, wie bisher kein Mensch erreicht hat. In dieser Version mit 64 Prozessoren galt Hydra seinerzeit als stärkstes schachspielendes DV-System der Welt.

Aktuelle Entwicklungen

Die Schachprogrammierung hat in den letzten Jahren durch den Einsatz moderner Technologien und Algorithmen enorme Fortschritte gemacht. Die Verteilung des Rechenaufwandes auf viele einzelne Teilprozesse, die parallel ablaufen können und soMulti-Prozessor-Systemesinnvoll nutzen, bleibt aufgrund der Komplexität der Baumsuche weiterhin eine Herausforderung. Allerdings nutzen moderne Schachprogramme wieStockfishmittlerweile fortschrittliche Parallelisierungsstrategien und profitieren von der Leistungsfähigkeit moderner Hardware.

Auf dem Sektor herkömmlicher PC-Schachprogramme hat sich die parallele Nutzung mehrerer Prozessorkerne bereits seit Jahren etabliert. „Deep-Versionen “von Engines wieFritzundKomodonutzen mehrere Prozessorkerne effizient und sind weit verbreitet. Diese Entwicklung wurde durch die Verfügbarkeit von Mehrkernprozessoren und64-Bit-Betriebssystemenunterstützt, was zu schnelleren und stärkeren Engines geführt hat.

Ein weiterer bedeutender Trend ist die Nutzung vonKünstlicher Intelligenzundmaschinellem Lernenin Schachprogrammen.Leela Chess Zero (LCZero)ist ein prominentes Beispiel, das aufneuronalen Netzwerkenbasiert und durch selbstständiges Spielen seine Stärke entwickelt hat. Seit einigen Jahren haben auch andere Engines, wie beispielsweiseStockfish,maschinelles Lernen integriert, um ihre Spielstärke weiter zu verbessern. Hier ist die Implementierung speziellerneuronaler Netzwerkebemerkenswert, die – anders als zuvor allgemein üblich –nichtaufGrafikprozessoren(GPU) angewiesen sind, sondern bereits auf den zahlreichen Kernen desZentralprozessors(CPU) einesComputerseffizient laufen (siehe auch:Efficiently Updatable Neural Network NNUE,deutsch„Effizient aktualisierbares neuronales Netz “). Hierdurch wurde ein weiterer bedeutender Sprung in der Spielstärke von Schachprogrammen erreicht, gegen die der Mensch inzwischen völlig chancenlos ist.

Ein weiterer wichtiger Trend besteht in der expliziten Nutzung der vielen GPUs, die moderneGrafikkartenin Hülle und Fülle zur Verfügung stellen (siehe auch:Compute Unified Device Architecture,„Einheitliche Gerätearchitektur für Computer “) anstelle von oder in Ergänzung zur CPU. Dies ermöglicht eine deutlich schnellere Verarbeitung der riesigen Datenmengen, die für das Training neuronaler Netzwerke benötigt werden. Engines wie LCZero profitieren stark von dieser Hardware, was sie noch leistungsfähiger macht.

Zusätzlich haben Online-Plattformen undCloud-Computingdie Art und Weise verändert, wie Schachprogramme eingesetzt werden. Plattformen wieLichessundChessbieten leistungsstarke Engines zur Analyse und für Turnierspiele, die auf ihrenServernlaufen und somit die Rechenleistung der Nutzergeräte schonen.

Zusammengefasst zeigen diese Entwicklungen, dass die Schachprogrammierung durch den Einsatz vonKünstlicher Intelligenz,maschinellem Lernenund leistungsstarker Hardware wieGPUsneue Höhen erreicht hat. Schachprogramme sind heutzutage stärker und effizienter als je zuvor, was die Zukunft dieses spannenden Forschungsgebiets vielversprechend macht.

Wettbewerbe

→Hauptartikel:World Computer Chess Championship,North American Computer Chess ChampionshipundMikrocomputer-Schachweltmeisterschaft

Es gibt verschiedeneWettbewerbe,bei denen sich Schachprogramme in ihrer Spielstärke gegenseitig messen, selten auch gegen menschliche Schachspieler. Einer der wichtigsten ist die seit 1974 ausgetragene (offene) Computerschachweltmeisterschaft, dieWorld Computer Chess Championship (WCCC),die für alle Arten vonHard-undSoftwareoffensteht. Die älteste Veranstaltung war die von 1970 bis 1994 ausgetrageneNorth American Computer Chess Championship (NACCC).Darüber hinaus gab es von 1980 bis 2001 eine spezielle Schachweltmeisterschaft nur fürMikrocomputer,dieWorld Microcomputer Chess Championship (WMCCC).

Elo-Zahlen

→Hauptartikel:Elo-Zahl

Elo-Zahlen der stärksten Schachprogramme
(Stand Anfang 2021)

Rang	Name	Punkte
1	Stockfish12 NNUE x64	3573
2	KomodoDragon x64	3564
3	Booot6.4 x64	3370
4	Deep Shredder13 x64	3356
5	Vajolet22.8 x64	3297
6	Arasan21.2 x64	3282
7	Wasp4 x64	3257
8	Deep Hiarcs14	3220
9	Deep Rybka4 x64	3199
10	Chiron3.01 x64	3177

Auch Schachprogrammen kann man eine Elo-Zahl geben, die ihre Spielstärke beschreibt. Zum Vergleich: Ein Schachweltmeister von heute bewegt sich im Bereich um Elo 2850. Die Elo-Zahlen in Computer-Ranglisten sind aber nicht ohne weiteres mit denen menschlicher Schachspieler zu vergleichen, da sie praktisch ausschließlich durch Partien zwischen Computern ermittelt wurden. Hinsichtlich der absoluten Größe der Wertungszahlenfehlt eine Kalibrierungzwischen Leistungsskalen menschlicher Meisterspieler und jenen von Schachprogrammen; diese würde sehr zahlreiche ernste Wettkampfpartien zwischen beiden Spielergruppen erfordern. D. h., das Zahlenniveau in reinen Computerwertungslisten muss notgedrungen von einer plausiblen oder praxisgeeigneten Annahme ausgehen, und die konkreten Resultate der Programme gegeneinander bestimmen lediglich dieRangfolge und die Abständezwischen ihren Wertungszahlen.

Wegen der grundsätzlich unterschiedlichen Methoden von Menschen und Computerprogrammen beim Schachspiel ist eine hohe Spielstärke gegen ein anderes Schachprogramm nicht zwingend gleichbedeutend mit entsprechend besserer Leistung gegenüber einem menschlichen Gegner. Wettbewerbe von Schachprogrammen untereinander sagen daher nur bedingt etwas über die Spielstärke gegen Menschen aus. Jedoch hat die Praxis gezeigt, dass eine hohe Spielstärke gegen Programme in der Regel auch eine hohe Spielstärke gegen Menschen bedeutet. Das ProgrammRybkahat gegen verschiedene Großmeister – teilweise miteinem Bauern Vorgabe– gewinnen können. Andere Programme sind inzwischen noch spielstärker.

Eine Bewertung der Spielstärke von Schachprogrammen und Schachcomputern ist darüber hinaus auch mit Hilfe einer festgelegten Reihe von Schachproblemen möglich. Zum Beispiel besteht ein alsBT2450bezeichneter Test aus 30 Stellungen, zu denen der jeweilige Lösungszug zu finden ist. Aus den dafür benötigten Zeiten für alle Stellungen wird ein BT2450-Testwert berechnet, der mit der Elo-Zahl von menschlichen Spielern begrenzt vergleichbar ist. Es gibt inzwischen weitere, zum Teil umfangreichere und/oder schwierigere Tests, die innerhalb der Computerschach-Community erstellt und angewandt werden.

Siehe auch

• Computer Chess Rating Lists(CCRL)
• Forsyth-Edwards-Notation(FEN)

Literatur

• Rainer Bartel, Hans-Joachim Kraas, Günther Schrüfer:Das große Computerschachbuch.Data Becker, Düsseldorf 1985,ISBN 3-89011-117-3(gute Einführung in die Programmierung von Computerschach mit Beispielen inBASIC).
• Computerschach und Spiele(CSS).1/1986 bis 6/2004 (danach nur noch online); Zeitschrift überwiegend zum Thema Computerschach.
• Claude Shannon:Programming a Computer for Playing Chess.In:Philosophical Magazine.1950/41, S. 256–257.
• Claude Shannon:Programming a Computer to Play Chess.In:Scientific American.2/1950, S. 48–51.
• Botvinnik:Meine neuen Ideen zur Schachprogrammierung.Springer 1982,ISBN 3540110941.
• Botvinnik:Über den Schach-Algorithmus und dessen Anwendung in der Langzeitplanung.,dt. Dortmund 1992
• Dieter Steinwender,Frederic A. Friedel:Schach am PC.Markt und Technik, Haar bei München 1995,ISBN 3-87791-522-1(Geschichte des Computerschachs, didaktisches Schachprogramm mit Quellen in BASIC undC,inkl. CD).

Weblinks

• Seite von Ed Schröder.(Mementovom 30. Januar 2010 imInternet Archive). Autor von Rebel und ProDeo, sehr viele Informationen zum Thema Computerschach und detaillierte Beschreibungen zumInnenleben von Rebel.(Mementovom 31. Mai 2010 imInternet Archive). (Englisch).
• Schachprogramm Micro-Max.Schachprogramm in C mit weniger als 2000 Byte Quellcode (englisch).
• Das erste Schachprogramm der Welt als modernes Java-Applet.
• B. Monien, U. Lorenz, D. Warner:Der Alphabeta-Algorithmus. Wie bringe ich meinen Computer zum Schachspielen?(Mementovom 15. Dezember 2015 imInternet Archive). 2006.
• 9. Computerschach-Weltmeisterschaft vom 14. bis 20. Juni 1999 in Paderborn.Bericht aufTeleSchach.
• Online-Fortsetzung der ehem. Zeitschrift Computerschach und Spiele.
• SSDF Computer-Rangliste.
• CEGT-Rangliste.
• Microchess – das erste Mikrocomputer Schachprogramm.
• Wiki zur Schachprogrammierung (englisch).(Mementovom 20. Januar 2010 imInternet Archive).